In artificial intelligence, reactive planning denotes a group of techniques for action selection of autonomous agents. They differ from classical planning techniques in two aspects. First, they operate in a timely fashion and hence can cope with higly dynamic and unpredictable artificial environments. Second, they compute just one next action in every instant based on the current context and reactive plans, which are stored structures desribing agent's behaviour. Hondas intelligent humanoid robot AI redirects here. ... Action selection is a way of characterizing the most basic problem of intelligent systems: what to do next. ... Simple reflex agent Learning agent In computer science, an intelligent agent (IA) is a software agent that exhibits some form of artificial intelligence. ... This atricle is related to software agents and intelligent agents. ...

Reactive plan representation

There are several ways of how to represent a reactive plan. Always, we have a basic representational unit and a method of how to compose these units to plans.

Crisp condition action rules

A condition action rule, or if-then rule, is a rule in the form: if condition then action. These rules comes from the domain of expert systems. The meaning of the rule is as follows: if the condition holds, perform the action. The action can be either external (i.e., to perform an action in the environment), or internal (e.g., write a fact into the internal memory, or evaluate a new set of rules). The conditions are boolean and the action either can be performed, or not. The rules are organised in flat-structures, as in the case of simplified subsumption architecture described by Wooldridge, or hierarchical structures (trees and others), as is the case of most other architectures. Flat structures allows only for description of a simple behaviour. An expert system is a class of computer programs developed by researchers in artificial intelligence during the 1970s and applied commercially throughout the 1980s. ... Subsumption architecture is an AI concept originating from behavior based robotics. ... In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...

The important part of action selection algorithms is a conflict resolution mechanism. It is a mechanism of solving a conflict among more rules that hold in a given instant. The conflict can be solved for example by assigning fixed priorities to the rules in advance (e.g. in POSH architecture), by assigning preferences (e.g. in Soar architecture) or by exploiting a form of planning. SOAR (also spelled Soar) is a symbolic cognitive architecture, created by John Laird, Allen Newell, and Paul Rosenbloom at Carnegie Mellon University. ... This article focusses on approaches in artificial intelligence on the problem of automated planning and scheduling. ...

Crisp Finite State Machines

Finite state machine (FSM) is model of behaviour of a system. FSMs are used widely in computer science and modelling behaviour of agents is only one of their possible applications. A typical FSM, when used for describing behaviour of an agent, consists of a set of states and transitions between these states. The transitions are actually condition action rules. In every instant, just one state of the FSM is active, and its transitions are evaluated. If a transition holds, it activates another state. That means, that transitions are the rules in the following form: if condition then activate-new-state. Fig. ... Look up Agent in Wiktionary, the free dictionary An agent is an autonomous entity with an ontological commitment and agenda of its own. ...

There are two ways of how to produce behaviour by a FSM. They depend on what is associated with the states by a designer --- they can be either 'acts', or scripts. An 'act' is an atomic action that should be performed by the agent if its FSM is the given state. This action is performed in every time step then. However, more often is the latter case. Here, every state is associated with a script, which describes a sequence of actions that the agent has to perform if its FSM is in a given state. If a transition activates a new state, the former script is simply interrupted, and the new one is started.

If a script is more complicated, it can be broken down to several scripts and a hierarchical FSM can be exploited. In such an automaton, every state can contain substates. Only the states at the atomic level are associated with a script (which is not complicated) or an atomic action.

Computationally, hierarchical FSMs are equivalent to FSMs. That means that each hierarchical FSMs can be converted to a classical FSMs. However, hierarchical approach facilitate a design a lot. See the paper of Damian Isla (2005) for an example of ASM of computer game bots, which uses hierarchical FSMs. A bot, most prominently in the first person shooter PC game types (FPS), is a roBOTic computer controlled entity that simulates an online or LAN multiplayer human deathmatch, team deathmatch opponent or a cooperative human player. ...

Fuzzy approach

Both if-then rules and FSMs can be combined with fuzzy logic. The conditions, states and actions are no more boolean or "yes/no" respectively, rather, they become approximate and smooth. Consequently, resulted behaviour can be more smooth, especially in the case of transitions between two tasks. However, evalutation of the fuzzy conditions is much slower then evaluation of their crisp counterparts. Fuzzy logic is derived from fuzzy set theory dealing with reasoning that is approximate rather than precisely deduced from classical predicate logic. ...

See the architecture of Alex Champandard.

Connectionists approach

Reactive plans can be expressed also by connectionist networks like artificial neural networks or free-flow hierarchies. The basic representational unit is a unit with several input links that feed the unit with "an abstract activity" and output links that propagate the activity to following units. Each unit itself works as the activity transducer. Typically, the units are connected in a layered structure. Connectionism is an approach in the fields of artificial intelligence, cognitive science, neuroscience, psychology and philosophy of mind. ... A neural network is an interconnected group of neurons. ...

Positives of connectionist networks is, first, that the resulted behaviour is more smooth than behaviour produced by crisp if-then rules and FSMs, second, the networks are often adaptive, and third, mechanism of inhibition can be used and hence, behaviour can be also described proscriptively (by means of rules one can describe behaviour only prescriptively). However, the methods have also several flaws. First, for a designer, it is much more complicated to describe behaviour by a network comparing with if-then rules. Second, only relatively simple behaviour can be described, especially if adaptive feature is to be exploited.

Reactive planning algorithms

Typical reactive planning algorithm just evaluates if-then rules or computes the state of a connectionist network. However, some algorithms have special features.

• Rete evaluation: with a proper logic representation (which is suitable only for crisp rules), the rules need not to be re-evaluated at every time step. Instead, a form of a cache storing the evaluation from the previous step can be used.
• Scripting languages: Sometimes, the rules or FSMs are directly the primitives of an architecture (e.g. in Soar). But more often, reactive plans are programmed in a scripting language, where the rules are only one of the primitives (like in JAM or ABL).

The Rete algorithm is an efficient pattern matching algorithm for implementing rule-based (expert) systems. ... SOAR (also spelled Soar) is a symbolic cognitive architecture, created by John Laird, Allen Newell, and Paul Rosenbloom at Carnegie Mellon University. ... Scripting languages (commonly called scripting programming languages or script languages) are computer programming languages initially used only for simple, repeated actions. ...

Steering

Steering is a special reactive technique used in navigation of agents. It is based on superposition of attractive or repulsive forces that effect on the agent. Steering is based on the original work on boids of Craig Reynolds. By means of steering, one can achieve a simple form of: Boids, developed by Craig Reynolds in 1986, is an artificial life program, simulating the flocking behaviour of birds. ...

• towards a goal navigation
• obstacles avoidance behaviour
• a wall following behaviour
• enemy approaching
• predator avoidance
• crowd behaviour

The advantage of steering is that it is computationally very efficient. In computer games, hundreds of soldiers can be driven by this technique. In cases of more complicated terrain (e.g. a building), however, steering must be combined with path-finding, which is a form of planning. This article is about computer and video games. ... In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ...

Refereces

• Bryson, J.: Intelligence by Design: Principles of Modularity and Coordination for Engineering Complex Adaptive Agents. PhD thesis, Massachusetts Institute of Technology (2001)
• Champandard, A. J.: AI Game Development: Synthetic Creatures with learning and Reactive Behaviors. New Riders, USA (2003)
• Grand, S., Cliff, D., Malhotra, A.: Creatures: Artificial life autonomous software-agents for home entertainment. In: Johnson, W. L. (eds.): Proceedings of the First International Conference on Autonomous Agents. ACM press (1997) 22-29
• Creatures development resource
• Huber, M. J.: JAM: A BDI-theoretic mobile agent architecture. In: Proceedings of the Third International Conference on Autonomous Agents (Agents'99). Seatle (1999) 236-243
• Isla, D.: Handling complexity in Halo 2. In: Gamastura online, 03/11 (2005)
• Reynolds, C. W. Flocks, Herds, and Schools: A Distributed Behavioral Model. In: Computer Graphics, 21(4) (SIGGRAPH '87 Conference Proceedings) (1987) 25-34.
• de Sevin, E. Thalmann, D.:A motivational Model of Action Selection for Virtual Humans. In: Computer Graphics International (CGI), IEEE Computer SocietyPress, New York (2005)
• Softimage/Behavior product. Avid Technology Inc.
• Tyrrell, T.: Computational Mechanisms for Action Selection. Ph.D. Dissertation. Centre for Cognitive Science, University of Edinburgh (1993)
• van Waveren, J. M. P.: The Quake III Arena Bot. Master thesis. Faculty ITS, University of Technology Delft (2001)
• Wooldridge, M. An Introduction to MultiAgent Systems. John Wiley & Sons (2002)