Posts Tagged ‘planning’

8 Jan

Towards Runtime Behavior Adaptation for Embodied Characters

Posted by cognitivecomputing in Agents, Game AI, Learning. Tagged: , , , , , .

Typically, autonomous believable agents are implemented using static, hand-authored reactive behaviors or scripts. This hand-authoring allows designers to craft expressive behavior for characters, but can lead to excessive authorial burden, as well as result in characters that are brittle to changing world dynamics.

In this paper we present an approach for the runtime adaptation of reactive behaviors for autonomous believable characters. Extending transformational planning, our system allows autonomous characters to monitor and reason about their behavior execution, and to use this reasoning to dynamically rewrite their behaviors. In our evaluation, we transplant two characters in a sample tag game from the original world they were written for into a different one, resulting in behavior that violates the author intended personality. The reasoning layer successfully adapts the character’s behaviors so as to bring its long-term behavior back into agreement with its personality.

Towards Runtime Behavior Adaptation for Embodied Characters

by Peng Zang, Manish Mehta, Michael Mateas, Ashwin Ram

International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, India, January 2007
www.cc.gatech.edu/faculty/ashwin/papers/er-07-02.pdf

15 May

Context-Sensitive Asynchronous Memory

Posted by cognitivecomputing in Agents, Learning. Tagged: , , , , , .

Retrieving useful answers from large knowledge bases given under-specified questions is an important problem in the construction of general intelligent agents. The core of this problem is how to get the information an agent needs when it doesn’t know how to ask the right question and doesn’t have the time to exhaustively search all available information.

Context-sensitive asynchronous memory is a model of memory retrieval that solves this problem. The context-sensitive asynchronous memory approach exploits feedback from the task and environment to guide and constrain memory search by interleaving memory retrieval and problem solving. To achieve this behavior, a context-sensitive asynchronous memory uses an asynchronous retrieval system to manage a context- sensitive search process operating over a content-addressable knowledge base. Solutions based on this approach provide useful answers to vague questions efficiently, based on information naturally available during the performance of a task.

The core claims of this approach are:
•  Claim 1: An efficient, domain-independent solution to the problem of retrieving useful answers from large knowledge bases given under-specified queries is to interleave memory retrieval with task performance and use feedback from the task or environment to guide the search of memory.
•  Claim 2: Interleaving memory retrieval with and exploiting feedback from task performance can be achieved in a domain-independent way using a context- sensitive, asynchronous memory retrieval process.
•  Claim 3: A rich, reified, grounded semantic network representation enables context-sensitive memory retrieval processes to retrieve useful information in a domain-independent way for a wide variety of tasks.
•  Claim 4: To effectively use a context-sensitive asynchronous memory to retrieve useful answers, a task must be able to work in parallel with a memory process, communicate with it, provide feedback to it, and must possess integration mechanisms to incorporate asynchronous retrievals provided by the memory.

The context-sensitive asynchronous memory approach is applicable to tasks and domains which exhibit the following criteria: problems are difficult to solve, questions are difficult to formulate, a large knowledge base is available yet contains only a small selection of relevant information, and, most importantly, the environment is regular, in that solutions in the knowledge base occur in patterns and relationships similar to those found in situations in which the solutions are likely to be applicable in the future. This approach is domain independent: it is applicable to a wide variety of tasks and problems from simple search applications to complex cognitive agents.

To exploit context-sensitive asynchronous memory, reasoners need certain properties. Experience-based agency is an agent architecture which provides an outline of how to construct complete intelligent agents which use a context-sensitive asynchronous memory to support a reasoning system performing a real task. The experience-based agent architecture combines a context-sensitive asynchronous memory retrieval process with a global store of experience used by all agent processes, a global working memory to provide a uniform way to collect feedback, and a global task controller which orchestrates reasoning and memory. The experience-based agent architecture also provides principles for constructing integration mechanisms that enable reasoning tasks to work with the context-sensitive asynchronous memory.

Furthermore, to help determine when these approaches should be used, this research also contributes theoretical analyses that predict the classes of tasks and situations in which the context-sensitive asynchronous memory and experience-based agent approaches will provide the greatest benefit.

To evaluate the approach, the experience-based agent architecture has been implemented in the Nicole system. Nicole is a large Common Lisp program providing global long-term and working memory stores represented as a rich, reified, grounded semantic network, a context-sensitive asynchronous memory process based on a novel model of context-directed spreading activation, a control system for orchestrating reasoning and memory, and a task language to implement reasoning tasks. Nicole enables the context-sensitive asynchronous memory approach to be applied to real problems, including information retrieval in Nicole-IRIA, a information management application that uses context to recommend useful information (Francis et al. 2000), planning in Nicole-MPA, a case-based least-commitment planner that adapts multiple plans (Ram & Francis 1995) and language understanding in ISAAC (Moorman 1997), a story understanding system which uses Nicole’s retrieval system as part of its creative understanding process. Nicole and her children thus provide a testbed to evaluate the context-sensitive asynchronous memory approach.

Experiments with Nicole support the claims of the approach. Experiments with Nicole-IRIA demonstrate that a context-sensitive asynchronous memory can use feedback from browsing to improve the quality of memory retrieval, while experiments with Nicole-MPA demonstrate how information derived from reasoning can improve the quantity of retrieval. The use of Nicole’s memory in the ISAAC system demonstrates the generality of the context-sensitive asynchronous memory approach. Other experiments with Nicole-MPA demonstrate the importance of representation as a source of power for context-sensitive asynchronous memory, and further demonstrate that the core features of the experience-based agent architecture are crucial sources of power necessary to enable a reasoning task to work with and exploit a context-sensitive asynchronous memory.

In sum, these evaluations demonstrate that the context-sensitive asynchronous memory approach is a general approach to memory retrieval which can provide concrete benefits to real problems.

Read the thesis:

Context-Sensitive Asynchronous Memory

by Anthony Francis

PhD Thesis, College of Computing, Georgia Institute of Technology, Atlanta, GA, 2000
www.cc.gatech.edu/faculty/ashwin/papers/git-cc-00-01.pdf

1 Aug

Introspective Multistrategy Learning: On the Construction of Learning Strategies

Posted by cognitivecomputing in Language, Learning. Tagged: , , , , .

A central problem in multistrategy learning systems is the selection and sequencing of machine learning algorithms for particular situations. This is typically done by the system designer who analyzes the learning task and implements the appropriate algorithm or sequence of algorithms for that task. We propose a solution to this problem which enables an AI system with a library of machine learning algorithms to select and sequence appropriate algorithms autonomously. Furthermore, instead of relying on the system designer or user to provide a learning goal or target concept to the learning system, our method enables the system to determine its learning goals based on analysis of its successes and failures at the performance task.

The method involves three steps: Given a performance failure, the learner examines a trace of its reasoning prior to the failure to diagnose what went wrong (blame assignment); given the resultant explanation of the reasoning failure, the learner posts explicitly represented learning goals to change its background knowledge (deciding what to learn); and given a set of learning goals, the learner uses nonlinear planning techniques to assemble a sequence of machine learning algorithms, represented as planning operators, to achieve the learning goals (learning-strategy construction). In support of these operations, we define the types of reasoning failures, a taxonomy of failure causes, a second-order formalism to represent reasoning traces, a taxonomy of learning goals that specify desired change to the background knowledge of a system, and a declarative task-formalism representation of learning algorithms.

We present the Meta-AQUA system, an implemented multistrategy learner that operates in the domain of story understanding. Extensive empirical evaluations of Meta-AQUA show that it performs significantly better in a deliberative, planful mode than in a reflexive mode in which learning goals are ablated and, furthermore, that the arbitrary ordering of learning algorithms can lead to worse performance than no learning at all. We conclude that explicit representation and sequencing of learning goals is necessary for avoiding negative interactions between learning algorithms that can lead to less effective learning.

Read the paper:

Introspective Multistrategy Learning: On the Construction of Learning Strategies

by Mike Cox, Ashwin Ram

Artificial Intelligence, 112:1-55, 1999
www.cc.gatech.edu/faculty/ashwin/papers/er-99-01.pdf

26 Jul

Needles in a Haystack: Plan Recognition in Large Spatial Domains Involving Multiple Agents

Posted by cognitivecomputing in Agents, Learning. Tagged: , .

While plan recognition research has been applied to a wide variety of problems, it has largely made identical assumptions about the number of agents participating in the plan, the observability of the plan execution process, and the scale of the domain. We describe a method for plan recognition in a real-world domain involving large numbers of agents performing spatial maneuvers in concert under conditions of limited observability. These assumptions differ radically from those traditionally made in plan recognition and produce a problem which combines aspects of the fields of plan recognition, pattern recognition, and object tracking. We describe our initial solution which borrows and builds upon research from each of these areas, employing a pattern-directed approach to recognize individual movements and generalizing these to produce inferences of large-scale behavior.

Read the paper:

Needles in a Haystack: Plan Recognition in Large Spatial Domains Involving Multiple Agents

by Mark Devaney, Ashwin Ram

15th National Conference on Artificial Intelligence (AAAI-98), Madison, Wisconsin, July 1998
www.cc.gatech.edu/faculty/ashwin/papers/er-98-03.pdf

28 Jul

A New Heuristic Approach for Dual Control

Posted by cognitivecomputing in Learning, Robotics. Tagged: , , , .

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
www.cc.gatech.edu/faculty/ashwin/papers/er-97-02.pdf

25 Jul

Case-Based Planning to Learn

Posted by cognitivecomputing in Game AI, Learning. Tagged: , , , .

Learning can be viewed as a problem of planning a series of modifications to memory. We adopt this view of learning and propose the applicability of the case-based planning methodology to the task of planning to learn. We argue that relatively simple, fine-grained primitive inferential operators are needed to support flexible planning. We show that it is possible to obtain the benefits of case-based reasoning within a planning to learn framework.

Read the paper:

Case-Based Planning to Learn

by Bill Murdock, Gordon Shippey, Ashwin Ram

2nd International Conference on Case-Based Reasoning (ICCBR-97), Providence, RI, July 1997
www.cc.gatech.edu/faculty/ashwin/papers/er-97-04.pdf

13 Aug

Multi-Plan Retrieval and Adaptation in an Experience-Based Agent

Posted by cognitivecomputing in Agents, Learning. Tagged: , , , , .

The real world has many properties that present challenges for the design of intelligent agents: it is dynamic, unpredictable, and independent, poses poorly structured problems, and places bounds on the resources available to agents. Agents that opearate in real worlds need a wide range of capabilities to deal with them: memory, situation analysis, situativity, resource-bounded cognition, and opportunism.

We propose a theory of experience-based agency which specifies how an agent with the ability to richly represent and store its experiences could remember those experiences with a context-sensitive, asynchronous memory, incorporate those experiences into its reasoning on demand with integration mechanisms, and usefully direct memory and reasoning through the use of a utility-based metacontroller. We have implemented this theory in an architecture called NICOLE and have used it to address the problem of merging multiple plans during the course of case-based adaptation in least-committment planning.

Read the paper:

Multi-Plan Retrieval and Adaptation in an Experience-Based Agent

by Ashwin Ram, Anthony Francis

In Case-Based Reasoning: Experiences, Lessons, and Future Directions, D.B. Leake, editor, AAAI Press, 1996
www.cc.gatech.edu/faculty/ashwin/papers/er-96-06.pdf

15 May

Introspective Multistrategy Learning: Constructing a Learning Strategy under Reasoning Failure

Posted by cognitivecomputing in Language, Learning. Tagged: , , , , , .

The thesis put forth by this dissertation is that introspective analyses facilitate the construction of learning strategies. Furthermore, learning is much like nonlinear planning and problem solving. Like problem solving, it can be specified by a set of explicit learning goals (i.e., desired changes to the reasoner’s knowledge); these goals can be achieved by constructing a plan from a set of operators (the learning algorithms) that execute in a knowledge space. However, in order to specify learning goals and to avoid negative interactions between operators, a reasoner requires a model of its reasoning processes and knowledge.

With such a model, the reasoner can declaratively represent the events and causal relations of its mental world in the same manner that it represents events and relations in the physical world. This representation enables introspective self-examination, which contributes to learning by providing a basis for identifying what needs to be learned when reasoning fails. A multistrategy system possessing several learning algorithms can decide what to learn, and which algorithm(s) to apply, by analyzing the model of its reasoning. This introspective analysis therefore allows the learner to understand its reasoning failures, to determine the causes of the failures, to identify needed knowledge repairs to avoid such failures in the future, and to build a learning strategy (plan).

Thus, the research goal is to develop both a content theory and a process theory of introspective multistrategy learning and to establish the conditions under which such an approach is fruitful. Empirical experiments provide results that support the claims herein. The theory was implemented in a computational model called Meta-AQUA that attempts to understand simple stories. The system uses case-based reasoning to explain reasoning failures and to generate sets of learning goals, and it uses a standard non-linear planner to achieve these goals.

Evaluating Meta-AQUA with and without learning goals generated results indicating that computational introspection facilitates the learning process. In particular, the results lead to the conclusion that the stage that posts learning goals is a necessary stage if negative interactions between learning methods are to be avoided and if learning is to remain effective.

Read the thesis:

Introspective multistrategy learning: Constructing a learning strategy under reasoning failure

by Michael T. Cox

PhD Thesis, Technical Report GIT-CC-96/06, College of Computing, Georgia Institute of Technology, Atlanta, GA, 1996
www.cc.gatech.edu/faculty/ashwin/papers/git-cc-96-06.pdf

7 Nov

Interacting Learning-Goals: Treating Learning as a Planning Task

Posted by cognitivecomputing in Language, Learning. Tagged: , , , , , .

This research examines the metaphor of goal-driven planning as a tool for performing the integration of multiple learning algorithms. In case-based reasoning systems, several learning techniques may apply to a given situation. In a failure-driven learning environment, the problems of strategy construction are to choose and order the best set of learning algorithms or strategies that recover from a processing failure and to use those strategies to modify the system’s background knowledge so that the failure will not be repeated in similar future situations.

A solution to this problem is to treat learning-strategy construction as a planning problem with its own set of goals. Learning goals, as opposed to ordinary goals, specify desired states in the background knowledge of the learner, rather than desired states in the external environment of the planner. But as with traditional goal-based planners, management and pursuit of these learning goals becomes a central issue in learning. Example interactions of learning-goals are presented from a multistrategy learning system called Meta-AQUA that combines a case-based approach to learning with non linear planning to achieve goals in a knowledge space.

Read the paper:

Interacting Learning-Goals: Treating Learning as a Planning Task

by Mike Cox, Ashwin Ram

In J.-P. Haton, M. Keane, & M. Manago (editors), Advances in Case-Based Reasoning (Lecture Notes in Artificial Intelligence), 60-74, Springer-Verlag, 1995. Earlier version presented at the Second European Workshop on Case-Based Reasoning (EWCBR-94), Chantilly, France, 1994.
www.cc.gatech.edu/faculty/ashwin/papers/er-95-09.ps

23 Feb

Introspective Reasoning using Meta-Explanations for Multistrategy Learning

Posted by cognitivecomputing in Language, Learning. Tagged: , , , , .

In order to learn effectively, a reasoner must not only possess knowledge about the world and be able to improve that knowledge, but it also must introspectively reason about how it performs a given task and what particular pieces of knowledge it needs to improve its performance at the current task. Introspection requires declarative representations of meta-knowledge of the reasoning performed by the system during the performance task, of the system’s knowledge, and of the organization of this knowledge.

This paper presents a taxonomy of possible reasoning failures that can occur during a performance task, declarative representations of these failures, and associations between failures and particular learning strategies. The theory is based on Meta-XPs, which are explanation structures that help the system identify failure types, formulate learning goals, and choose appropriate learning strategies in order to avoid similar mistakes in the future. The theory is implemented in a computer model of an introspective reasoner that performs multistrategy learning during a story understanding task.

Read the paper:

Introspective Reasoning using Meta-Explanations for Multistrategy Learning

by Ashwin Ram, Mike Cox

In Machine Learning: A Multistrategy Approach, Vol. IV, R.S. Michalski and G. Tecuci (eds.), 349-377, Morgan Kaufmann, 1994
www.cc.gatech.edu/faculty/ashwin/papers/git-cc-92-19.pdf
« Older Entries
Newer Entries »