Reactive planning
Encyclopedia
In artificial intelligence
, reactive planning denotes a group of techniques for action selection
by autonomous agents
. These techniques differ from classical planning
in two aspects. First, they operate in a timely fashion and hence can cope with highly dynamic and unpredictable environments. Second, they compute just one next action in every instant, based on the current context. Reactive planners often (but not always) exploit reactive plans, which are stored structures describing the agent's priorities and behaviour.
Although the term reactive planning goes back to at least 1988, the term reactive
has now become a pejorative
used as an antonym
for proactive
. Since nearly all agents using reactive planning are proactive, some researchers have begun referring to reactive planning as dynamic planning.
Production rules may be organized in relatively flat structures, but more often are organized into a hierarchy
of some kind. For example, subsumption architecture
consists of layers of interconnected behaviors, each actually a finite state machine
which acts in response to an appropriate input. These layers are then organized into a simple stack, with higher layers subsuming the goals of the lower ones. Other systems may use trees
, or may include special mechanisms for changing which goal / rule subset is currently most important. Flat structures are relatively easy to build, but allow only for description of simple behavior, or require immensely complicated conditions to compensate for the lacking structure.
An important part of any distributed action selection
algorithms is a conflict resolution mechanism. This is a mechanism for resolving conflicts between actions proposed when more than one rules' condition holds in a given instant. The conflict can be solved for example by
Expert systems often use other simpler heuristic
s such as recency for selecting rules, but it is difficult to guarantee good behavior in a large system with simple approaches.
Conflict resolution is only necessary for rules that want to take mutually exclusive actions (c.f. Blumberg 1996).
Some limitations of this kind of reactive planning can be found in Brom (2005).
(FSM) is model of behaviour of a system. FSMs are used widely in computer science. Modeling 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 is taken it activates another state. That means, in general transitions are the rules in the following form: if condition then activate-new-state. But transitions can also connect to the 'self' state in some systems, to allow execution of transition actions without actually changing the state.
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 FSM can be converted to a classical FSM. However, hierarchical approaches facilitate designs better.
See the paper of Damian Isla (2005) for an example of ASM of computer game bot
s, which uses hierarchical FSMs.
. The conditions, states and actions are no more boolean or "yes/no" respectively but are approximate and smooth. Consequently, resulted behaviour will transition smoother, especially in the case of transitions between two tasks. However, evaluation of the fuzzy conditions is much slower than evaluation of their crisp counterparts.
See the architecture of Alex Champandard.
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.
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.
, which map sensor inputs directly to effector outputs, and can follow or avoid. More complex systems are based on a superposition of attractive or repulsive forces that effect on the agent. This kind of steering is based on the original work on boids
of Craig Reynolds.
By means of steering, one can achieve a simple form of:
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
.
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, reactive planning denotes a group of techniques for action selection
Action selection
Action selection is a way of characterizing the most basic problem of intelligent systems: what to do next. In artificial intelligence and computational cognitive science, "the action selection problem" is typically associated with intelligent agents and animats—artificial systems that exhibit...
by autonomous agents
Intelligent agent
In artificial intelligence, an intelligent agent is an autonomous entity which observes through sensors and acts upon an environment using actuators and directs its activity towards achieving goals . Intelligent agents may also learn or use knowledge to achieve their goals...
. These techniques differ from classical planning
Automated planning and scheduling
Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...
in two aspects. First, they operate in a timely fashion and hence can cope with highly dynamic and unpredictable environments. Second, they compute just one next action in every instant, based on the current context. Reactive planners often (but not always) exploit reactive plans, which are stored structures describing the agent's priorities and behaviour.
Although the term reactive planning goes back to at least 1988, the term reactive
Reactive
Reactive may refer to:*Generally, capable of having a reaction*Reactance , the imaginary component of AC impedance*Reactive mind*Reactive programming...
has now become a pejorative
Pejorative
Pejoratives , including name slurs, are words or grammatical forms that connote negativity and express contempt or distaste. A term can be regarded as pejorative in some social groups but not in others, e.g., hacker is a term used for computer criminals as well as quick and clever computer experts...
used as an antonym
Antonym
In lexical semantics, opposites are words that lie in an inherently incompatible binary relationship as in the opposite pairs male : female, long : short, up : down, and precede : follow. The notion of incompatibility here refers to the fact that one word in an opposite pair entails that it is not...
for proactive
ProActive
ProActive is Java grid middleware for parallel, distributed, and multi-threaded computing. It is developed by the OW2 Consortium, including INRIA, CNRS, University of Nice Sophia Antipolis, and ActiveEon...
. Since nearly all agents using reactive planning are proactive, some researchers have begun referring to reactive planning as dynamic planning.
Reactive plan representation
There are several ways to represent a reactive plan. All require a basic representational unit and a means to compose these units into plans.Condition-action rules (productions)
A condition action rule, or if-then rule, is a rule in the form: if condition then action. These rules are called productions. The meaning of the rule is as follows: if the condition holds, perform the action. The action can be either external (e.g., pick something up and move it), or internal (e.g., write a fact into the internal memory, or evaluate a new set of rules). Conditions are normally boolean and the action either can be performed, or not.Production rules may be organized in relatively flat structures, but more often are organized into a hierarchy
Hierarchy
A hierarchy is an arrangement of items in which the items are represented as being "above," "below," or "at the same level as" one another...
of some kind. For example, subsumption architecture
Subsumption architecture
Subsumption architecture is a reactive robot architecture heavily associated with behavior-based robotics. The term was introduced by Rodney Brooks and colleagues in 1986...
consists of layers of interconnected behaviors, each actually a finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
which acts in response to an appropriate input. These layers are then organized into a simple stack, with higher layers subsuming the goals of the lower ones. Other systems may use trees
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
, or may include special mechanisms for changing which goal / rule subset is currently most important. Flat structures are relatively easy to build, but allow only for description of simple behavior, or require immensely complicated conditions to compensate for the lacking structure.
An important part of any distributed action selection
Action selection
Action selection is a way of characterizing the most basic problem of intelligent systems: what to do next. In artificial intelligence and computational cognitive science, "the action selection problem" is typically associated with intelligent agents and animats—artificial systems that exhibit...
algorithms is a conflict resolution mechanism. This is a mechanism for resolving conflicts between actions proposed when more than one rules' condition holds in a given instant. The conflict can be solved for example by
- assigning fixed priorities to the rules in advance,
- assigning preferences (e.g. in SoarSoar (cognitive architecture)Soar is a symbolic cognitive architecture, created by John Laird, Allen Newell, and Paul Rosenbloom at Carnegie Mellon University, now maintained by John Laird's research group at the University of Michigan. It is both a view of what cognition is and an implementation of that view through a...
architecture), - learning relative utilities between rules (e.g. in ACT-RACT-RACT-R is a cognitive architecture mainly developed by John Robert Anderson at Carnegie Mellon University. Like any cognitive architecture, ACT-R aims to define the basic and irreducible cognitive and perceptual operations that enable the human mind....
), - exploiting a form of planningAutomated planning and schedulingAutomated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...
.
Expert systems often use other simpler heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
s such as recency for selecting rules, but it is difficult to guarantee good behavior in a large system with simple approaches.
Conflict resolution is only necessary for rules that want to take mutually exclusive actions (c.f. Blumberg 1996).
Some limitations of this kind of reactive planning can be found in Brom (2005).
Finite State Machines
Finite state machineFinite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
(FSM) is model of behaviour of a system. FSMs are used widely in computer science. Modeling behaviour of agents
Intelligent agent
In artificial intelligence, an intelligent agent is an autonomous entity which observes through sensors and acts upon an environment using actuators and directs its activity towards achieving goals . Intelligent agents may also learn or use knowledge to achieve their goals...
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 is taken it activates another state. That means, in general transitions are the rules in the following form: if condition then activate-new-state. But transitions can also connect to the 'self' state in some systems, to allow execution of transition actions without actually changing the state.
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 FSM can be converted to a classical FSM. However, hierarchical approaches facilitate designs better.
See the paper of Damian Isla (2005) for an example of ASM of computer game bot
Computer game bot
A bot, most prominently in the first-person shooter types , is a type of weak AI expert system software which for each instance of the program controls a player in deathmatch, team deathmatch and/or cooperative human player. Computer bots may play against other bots and/or human players in unison,...
s, which uses hierarchical FSMs.
Fuzzy approaches
Both if-then rules and FSMs can be combined with fuzzy logicFuzzy logic
Fuzzy logic is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. In contrast with traditional logic theory, where binary sets have two-valued logic: true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1...
. The conditions, states and actions are no more boolean or "yes/no" respectively but are approximate and smooth. Consequently, resulted behaviour will transition smoother, especially in the case of transitions between two tasks. However, evaluation of the fuzzy conditions is much slower than evaluation of their crisp counterparts.
See the architecture of Alex Champandard.
Connectionists approaches
Reactive plans can be expressed also by connectionist networksConnectionism
Connectionism is a set of approaches in the fields of artificial intelligence, cognitive psychology, cognitive science, neuroscience and philosophy of mind, that models mental or behavioral phenomena as the emergent processes of interconnected networks of simple units...
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.
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 evaluationRete algorithmThe Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper...
: 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 SoarSoar (cognitive architecture)Soar is a symbolic cognitive architecture, created by John Laird, Allen Newell, and Paul Rosenbloom at Carnegie Mellon University, now maintained by John Laird's research group at the University of Michigan. It is both a view of what cognition is and an implementation of that view through a...
). But more often, reactive plans are programmed in a scripting languageScripting languageA scripting language, script language, or extension language is a programming language that allows control of one or more applications. "Scripts" are distinct from the core code of the application, as they are usually written in a different language and are often created or at least modified by the...
, where the rules are only one of the primitives (like in JAM or ABL).
Steering
Steering is a special reactive technique used in navigation of agents. The simplest form of reactive steering is employed in Braitenberg vehiclesBraitenberg Vehicles
A Braitenberg vehicle is a concept conceived in a thought experiment by the Italian-Austrian cyberneticist Valentino Braitenberg to illustrate in an evolutive way the abilities of simple agents. The vehicles represent the simplest form of behavior based artificial intelligence or embodied...
, which map sensor inputs directly to effector outputs, and can follow or avoid. More complex systems are based on a superposition of attractive or repulsive forces that effect on the agent. This kind of steering is based on the original work on boids
Boids
Boids is an artificial life program, developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds. His paper on this topic was published in 1987 in the proceedings of the ACM SIGGRAPH conference...
of Craig Reynolds.
By means of steering, one can achieve a simple form of:
- 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
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
, which is a form of planning
Automated planning and scheduling
Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...
.
External links
- Creatures, an implementation of reactive planning by Grand et. al.