Reactive planning

"Dynamic planning" redirects here. For the anime studio, see Dynamic Planning.

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.

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 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 heuristics 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 machine (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 bots, which uses hierarchical FSMs.

Fuzzy approaches

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 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 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.

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.

Steering

Steering is a special reactive technique used in navigation of agents. The simplest form of reactive steering is employed in Braitenberg vehicles, 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 (as e.g. in Milani ), which is a form of planning .

See also

References

    External links

    This article is issued from Wikipedia - version of the Friday, January 29, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.