Reactive planning

Last updated

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. The term reactive planning goes back to at least 1988, and is synonymous with the more modern term dynamic planning.

Contents

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: ifconditionthenaction. 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: ifconditionthenactivate-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 NPCs 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

Related Research Articles

<span class="mw-page-title-main">Finite-state machine</span> Mathematical model of computation

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.

<span class="mw-page-title-main">State diagram</span> Diagram of behavior of finite state systems

A state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, while at other times this is a reasonable abstraction. Many forms of state diagrams exist, which differ slightly and have different semantics.

<span class="mw-page-title-main">Symbolic artificial intelligence</span> Methods in artificial intelligence research

In artificial intelligence, symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence research that are based on high-level symbolic (human-readable) representations of problems, logic and search. Symbolic AI used tools such as logic programming, production rules, semantic nets and frames, and it developed applications such as knowledge-based systems, symbolic mathematics, automated theorem provers, ontologies, the semantic web, and automated planning and scheduling systems. The Symbolic AI paradigm led to seminal ideas in search, symbolic programming languages, agents, multi-agent systems, the semantic web, and the strengths and limitations of formal knowledge and reasoning systems.

A cognitive model is an approximation of one or more cognitive processes in humans or other animals for the purposes of comprehension and prediction. There are many types of cognitive models, and they can range from box-and-arrow diagrams to a set of equations to software programs that interact with the same tools that humans use to complete tasks. In terms of information processing, cognitive modeling is modeling of human perception, reasoning, memory and action.

<span class="mw-page-title-main">Boids</span> Artificial life program

Boids is an artificial life program, developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds, and related group motion. His paper on this topic was published in 1987 in the proceedings of the ACM SIGGRAPH conference. The name "boid" corresponds to a shortened version of "bird-oid object", which refers to a bird-like object. Reynolds' boid model is one example of a larger general concept, for which many other variations have been developed since. The closely related work of Ichiro Aoki is noteworthy because it was published in 1982 — five years before Reynolds' boids paper.

In computer science, a software agent is a computer program that acts for a user or another program in a relationship of agency.

Soar is a cognitive architecture, originally created by John Laird, Allen Newell, and Paul Rosenbloom at Carnegie Mellon University. It is now maintained and developed by John Laird's research group at the University of Michigan.

<span class="mw-page-title-main">Dynamical systems theory</span> Area of mathematics used to describe the behavior of complex dynamical systems

Dynamical systems theory is an area of mathematics used to describe the behavior of complex dynamical systems, usually by employing differential equations or difference equations. When differential equations are employed, the theory is called continuous dynamical systems. From a physical point of view, continuous dynamical systems is a generalization of classical mechanics, a generalization where the equations of motion are postulated directly and are not constrained to be Euler–Lagrange equations of a least action principle. When difference equations are employed, the theory is called discrete dynamical systems. When the time variable runs over a set that is discrete over some intervals and continuous over other intervals or is any arbitrary time-set such as a Cantor set, one gets dynamic equations on time scales. Some situations may also be modeled by mixed operators, such as differential-difference equations.

Automated planning and scheduling, sometimes denoted as simply AI planning, 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 complex and must be discovered and optimized in multidimensional space. Planning is also related to decision theory.

A cognitive architecture refers to both a theory about the structure of the human mind and to a computational instantiation of such a theory used in the fields of artificial intelligence (AI) and computational cognitive science. The formalized models can be used to further refine a comprehensive theory of cognition and as a useful artificial intelligence program. Successful cognitive architectures include ACT-R and SOAR. The research on cognitive architectures as software instantiation of cognitive theories was initiated by Allen Newell in 1990.

<span class="mw-page-title-main">Decentralised system</span> Systems without a single most important component or cluster

A decentralised system in systems theory is a system in which lower level components operate on local information to accomplish global goals. The global pattern of behaviour is an emergent property of dynamical mechanisms that act upon local components, such as indirect communication, rather than the result of a central ordering influence of a centralised system.

Specification and Description Language (SDL) is a specification language targeted at the unambiguous specification and description of the behaviour of reactive and distributed systems.

<span class="mw-page-title-main">Intelligent agent</span> Software agent which acts autonomously

In artificial intelligence, an intelligent agent (IA) is an agent acting in an intelligent manner; It perceives its environment, takes actions autonomously in order to achieve goals, and may improve its performance with learning or acquiring knowledge. An intelligent agent may be simple or complex: A thermostat or other control system is considered an example of an intelligent agent, as is a human being, as is any system that meets the definition, such as a firm, a state, or a biome.

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 complex behaviour in an agent environment. The term is also sometimes used in ethology or animal behavior.

A hierarchical control system (HCS) is a form of control system in which a set of devices and governing software is arranged in a hierarchical tree. When the links in the tree are implemented by a computer network, then that hierarchical control system is also a form of networked control system.

<span class="mw-page-title-main">TPT (software)</span> Software test automation tool

TPT is a systematic test methodology for the automated software test and verification of embedded control systems, cyber-physical systems, and dataflow programs. TPT is specialised on testing and validation of embedded systems whose inputs and outputs can be represented as signals and is a dedicated method for testing continuous behaviour of systems. Most control systems belong to this system class. The outstanding characteristic of control systems is the fact that they interact closely interlinked with a real world environment. Controllers need to observe their environment and react correspondingly to its behaviour. The system works in an interactional cycle with its environment and is subject to temporal constraints. Testing these systems is to stimulate and to check the timing behaviour. Traditional functional testing methods use scripts – TPT uses model-based testing.

UML state machine, also known as UML statechart, is an extension of the mathematical concept of a finite automaton in computer science applications as expressed in the Unified Modeling Language (UML) notation.

In artificial intelligence research, the situated approach builds agents that are designed to behave effectively successfully in their environment. This requires designing AI "from the bottom-up" by focussing on the basic perceptual and motor skills required to survive. The situated approach gives a much lower priority to abstract reasoning or problem-solving skills.

Winner-take-all is a computer science concept that has been widely applied in behavior-based robotics as a method of action selection for intelligent agents. Winner-take-all systems work by connecting modules in such a way that when one action is performed it stops all other actions from being performed, so only one action is occurring at a time. The name comes from the idea that the "winner" action takes all of the motor system's power.

GOLOG is a high-level logic programming language for the specification and execution of complex actions in dynamical domains. It is based on the situation calculus. It is a first-order logical language for reasoning about action and change. GOLOG was developed at the University of Toronto.

References