Posts Tagged ‘real-time cbr’

Situation Assessment for Plan Retrieval in Real-Time Strategy Games

Case-Based Planning (CBP) is an effective technique for solving planning problems that has the potential to reduce the computational complexity of the generative planning approaches. However, the success of plan execution using CBP depends highly on the selection of a correct plan; especially when the case-base of plans is extensive.

In this paper we introduce the concept of a situation and explain a situation assessment algorithm which improves plan retrieval for CBP. We have applied situation assessment to our previous CBP system, Darmok, in the domain of real-time strategy games. During Darmok’s execution using situation assessment, the high-level representation of the game state i.e. situation is predicted using a decision tree based Situation-Classification model. Situation predicted is further used for the selection of relevant knowledge intensive features, which are derived from the basic representation of the game state, to compute the similarity of cases with the current problem. The feature selection performed here is knowledge-based and improves the performance of similarity measurements during plan retrieval. The instantiation of the situation assessment algorithm to Darmok gave us promising results for plan retrieval within the real-time constraints.

Read the paper:

Situation Assessment for Plan Retrieval in Real-Time Strategy Games

by Kinshuk Mishra, Santi Ontañón, Ashwin Ram

9th European Conference on Case-Based Reasoning (ECCBR-08), Trier, Germany, September 2008

On-Line Case-Based Plan Adaptation for Real-Time Strategy Games

Traditional artificial intelligence techniques do not perform well in applications such as real-time strategy games because of the extensive search spaces which need to be explored. In addition, this exploration must be carried out on-line during performance time; it cannot be precomputed. We have developed on-line case-based planning techniques that are effective in such domains. In this paper, we extend our earlier work using ideas from traditional planning to inform the real-time adaptation of plans. In our framework, when a plan is retrieved, a plan dependency graph is inferred to capture the relations between actions in the plan. The plan is then adapted in real-time using its plan dependency graph. This allows the system to create and adapt plans in an efficient and effective manner while performing the task. The approach is evaluated using WARGUS, a well-known real-time strategy game.

Read the paper:

On-Line Case-Based Plan Adaptation for Real-Time Strategy Games

by Neha Sugandh, Santi Ontañón, Ashwin Ram

23rd AAAI Conference on Artificial Intelligence (AAAI-08), Chicago, IL, July 2008

Case-Based Planning and Execution for Real-Time Strategy Games

Artificial Intelligence techniques have been successfully applied to several computer games. However in some kinds of computer games, like real-time strategy (RTS) games, traditional artificial intelligence techniques fail to play at a human level because of the vast search spaces that they entail. In this paper we present a real-time case based planning and execution approach designed to deal with RTS games. We propose to extract behavioral knowledge from expert demonstrations in form of individual cases. This knowledge can be reused via a case based behavior generator that proposes behaviors to achieve the specific open goals in the current plan. Specifically, we applied our technique to the WARGUS domain with promising results.

Read the paper:

Case-Based Planning and Execution for Real-Time Strategy Games

by Santi Ontañón, Kinshuk Mishra, Neha Sugandh, Ashwin Ram

Seventh International Conference on Case-Based Reasoning (ICCBR-07), Belfast, Northern Ireland, August 2007

Transfer Learning in Real-Time Strategy Games Using Hybrid CBR/RL

The goal of transfer learning is to use the knowledge acquired in a set of source tasks to improve performance in a related but previously unseen target task. In this paper, we present a multi-layered architecture named CAse-Based Reinforcement Learner (CARL). It uses a novel combination of Case-Based Reasoning (CBR) and Reinforcement Learning (RL) to achieve transfer while playing against the Game AI across a variety of scenarios in MadRTS, a commercial Real-Time Strategy game. Our experiments demonstrate that CARL not only performs well on individual tasks but also exhibits significant performance gains when allowed to transfer knowledge from previous tasks.

Read the paper:

Transfer Learning in Real-Time Strategy Games Using Hybrid CBR/RL

by Manu Sharma, Michael Holmes, Juan Santamaria, Arya Irani, Charles Isbell, Ashwin Ram

International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, India, January 2007

Case-Based Reasoning for Gas Turbine Diagnostics

General Electric used case-based reasoning for gas turbine diagnostics at their monitoring and diagnostics center in Atlanta, GA. This application had requirements that included accuracy, maintainability, modularity, parameterization, robustness, and integration of the system into an existing infrastructure. The CBR system has a modular “plug and play” architecture to facilitate experimentation and optimization. It was integrated into the production environment in 2004. The CBR system is currently in a trial deployment where diagnoses made by the system are created along with the previous process of using human-generated diagnosis.

Case-Based Reasoning for Gas Turbine Diagnostics

by Mark Devaney, Bill Cheetham

18th International FLAIRS Conference (FLAIRS-05), Clearwater, FL, May 2005

A New Heuristic Approach for Dual Control

Autonomous agents engaged in a continuous interaction with an incompletely known environment face the problem of dual control (Feldbaum, 1965). Simply stated, actions are necessary not only for studying the environment, but also for making progress on the task. In other words, actions must bear a “dual” character: They must be investigators to some degree, but also directors to some degree. Because the number of variables involved in the solution of the dual control problem increases with the number of decision stages, the exact solution of the dual control problem is computationally intractable except for a few special cases.

This paper provides an overview of dual control theory and proposes a heuristic approach towards obtaining a near-optimal dual control method that can be implemented. The proposed algorithm selects control actions taking into account the information contained in past observations as well as the possible information that future observations may reveal. In short, the algorithm anticipates the fact that future learning is possible and selects the control actions accordingly. The algorithm uses memory-based methods to associate long-term benefit estimates to belief states and actions, and selects the actions to execute next according to such estimates. The algorithm uses the outcome of every experience to progressively refine the long-term benefit estimates so that it can make better, improved decisions as it progresses. The algorithm is tested on a classical simulation problem.

Read the paper:

A New Heuristic Approach for Dual Control

by Juan Carlos Santamaria, Ashwin Ram

AAAI-97 Workshop on On-Line Search, Providence, RI, July 1997

Continuous Case-Based Reasoning

Case-based reasoning systems have traditionally been used to perform high-level reasoning in problem domains that can be adequately described using discrete, symbolic representations. However, many real-world problem domains, such as autonomous robotic navigation, are better characterized using continuous representations. Such problem domains also require continuous performance, such as on-line sensorimotor interaction with the environment, and continuous adaptation and learning during the performance task.

This article introduces a new method for continuous case-based reasoning, and discusses its application to the dynamic selection, modification, and acquisition of robot behaviors in an autonomous navigation system, SINS (Self-Improving Navigation System). The computer program and the underlying method are systematically evaluated through statistical analysis of results from several empirical studies. The article concludes with a general discussion of case-based reasoning issues addressed by this research.

Read the paper:

Continuous Case-Based Reasoning

by Ashwin Ram, Juan Carlos Santamaria

Artificial Intelligence journal, (90)1-2:25-77, 1997

Case-Based Reactive Navigation: A Case-Based Method for On-Line Selection and Adaptation of Reactive Control Parameters in Autonomous Robotic Systems

This article presents a new line of research investigating on-line learning mechanisms for autonomous intelligent agents. We discuss a case-based method for dynamic selection and modification of behavior assemblages for a navigational system. The case-based reasoning module is designed as an addition to a traditional reactive control system, and provides more flexible performance in novel environments without extensive high-level reasoning that would otherwise slow the system down. The method is implemented in the ACBARR (A Case-BAsed Reactive Robotic) system, and evaluated through empirical simulation of the system on several different environments, including “box canyon” environments known to be problematic for reactive control systems in general.

Read the paper:

Case-Based Reactive Navigation: A Case-Based Method for On-Line Selection and Adaptation of Reactive Control Parameters in Autonomous Robotic Systems

by Ashwin Ram, Ron Arkin, Kenneth Moorman, Russ Clark

IEEE Transactions on Systems, Man, and Cybernetics, 27B(3), 1997. Preliminary version published as Technical Report GIT-CC-92/57, College of Computing, Georgia Institute of Technology, Atlanta, GA, 1992

Learning Adaptive Reactive Controllers

Reactive controllers has been widely used in mobile robots since they are able to achieve successful performance in real-time. However, the configuration of a reactive controller depends highly on the operating conditions of the robot and the environment; thus, a reactive controller configured for one class of environments may not perform adequately in another. This paper presents a formulation of learning adaptive reactive controllers. Adaptive reactive controllers inherit all the advantages of traditional reactive controllers, but in addition they are able to adjust themselves to the current operating conditions of the robot and the environment in order to improve task performance. Furthermore, learning adaptive reactive controllers can learn when and how to adapt the reactive controller so as to achieve effective performance under different conditions.

The paper presents an algorithm for a learning adaptive reactive controller that combines ideas from case-based reasoning and reinforcement learning to construct a mapping between the operating conditions of a controller and the appropriate controller configuration; this mapping is in turn used to adapt the controller configuration dynamically. As a case study, the algorithm is implemented in a robotic navigation system that controls a Denning MRV-III mobile robot. The system is extensively evaluated using statistical methods to verify its learning performance and to understand the relevance of different design parameters on the performance of the system.

Read the paper:

Learning Adaptive Reactive Controllers

by Juan Carlos Santamaria, Ashwin Ram

Technical Report GIT-CC-97/05, College of Computing, Georgia Institute of Technology, Atlanta, GA, January 1997

Learning Adaptive Reactive Agents

An autonomous agent is an intelligent system that has an ongoing interaction with a dynamic external world. It can perceive and act on the world through a set of limited sensors and effectors. Its most important characteristic is that it is forced to make decisions sequentially, one after another, during its entire “life”. The main objective of this dissertation is to study algorithms by which an autonomous agents can learn, using their own experience, to perform sequential decision-making efficiently and autonomously. The dissertation describes a framework for studying autonomous sequential decision-making consisting of three main elements: the agent, the environment, and the task. The agent attempts to control the environment by perceiving the environment and choosing actions in a sequential fashion. The environment is a dynamic system characterized by a state and its dynamics, a function that describes the evolution of the state given the agent’s actions. A task is a declarative description of the desired behavior the agent should exhibit as it interacts with the environment. The ultimate goal of the agent is to learn a policy or strategy for selecting actions that maximizes its expected benefit as defined by the task.

The dissertation focuses on sequential decision-making when the environment is characterized by continuous states and actions, and the agent has imperfect perception, incomplete knowledge, and limited computational resources. The main characteristic of the approach proposed in this dissertation is that the agent uses its previous experiences to improve estimates of the long-term benefit associated with the execution of specific actions. The agent uses these estimates to evaluate how desirable is to execute alternative actions and select the one that best balances the short- and long-term consequences, taking special consideration of the expected benefit associated with actions that accomplish new learning while making progress on the task.

The approach is based on novel methods that are specifically designed to address the problems associated with continuous domains, imperfect perception, incomplete knowledge, and limited computational resources. The approach is implemented using case-based techniques and extensively evaluated in simulated and real systems including autonomous mobile robots, pendulum swinging and balancing controllers, and other non-linear dynamic system controllers.

Read the thesis:

Learning Adaptive Reactive Agents

by Juan Carlos Santamaria

PhD Thesis, College of Computing, Georgia Institute of Technology, Atlanta, GA, 1996