Action selection
5033373
222800604
2008-07-01T04:43:18Z
203.26.123.147
/* References */ typo
{{portal|Artificial intelligence}}
'''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 [[animat]]s—artificial systems that exhibit complex behaviour in an [[agent environment]]. The term is also sometimes used in [[ethology]] or [[animal behavior]].
One problem for understanding action selection is determining the level of abstraction used for specifying an "act". At the most basic level of abstraction, an [[atomic]] act could be anything from ''contracting a muscle cell'' to ''provoking a war''. Typically for any one action-selection mechanism, the set of possible actions is predefined and fixed.
Most researchers working in this field place high demands on their agents:
* The acting [[Intelligent agent|agent]] typically must select its action in [[agent environment|dynamic]] and [[agent environment|unpredictable]] environments.
* The agents typically act in [[Real-time computing|real time]]; therefore they must make decisions in a timely fashion.
* The agents are normally created to perform several different tasks. These tasks may conflict for resource allocation (e.g. can the agent put out a fire and deliver a cup of coffee at the same time?)
* The environment the agents operate in may include [[humans]], who may make things more difficult for the agent (either intentionally or by attempting to assist.)
* The agents themselves are often intended to [[computer model|model]] animals and/or humans, and animal/human [[behavior|behaviour]] is quite complicated.
For these reasons action selection is not trivial and attracts a good deal of research.
== Characteristics of the action selection problem ==
The main problem for action selection is [[complexity]]. Since all [[computation]] takes both [[time]] and [[space]] (in memory), agents cannot possibly consider every option available to them at every instant in time. Consequently, they must be [[biased]], and [[constrain]] their [[search]] in some way. For AI, the question of action selection is ''what is the best way to constrain this search''? For biology and ethology, the question is ''how do various types of animals constrain their search? Do all animals use the same approaches? Why do they use the ones they do?''
One fundamental question about action selection is whether it is really a problem at all for an agent, or whether it is just a description of an [[emergent]] property of an intelligent agent's behaviour. However, if we consider how we are going to build an intelligent agent, then it becomes apparent there must be ''some'' mechanism for action selection. This mechanism may be highly distributed (as in the case of distributed organisms such as [[social insect]] colonies or [[slime mold]]) or it may be a special-purpose module.
The action selection mechanism (ASM) determines not only the agent’s actions in terms of impact on the world, but also directs its perceptual [[attention]], and updates its [[memory]]. These [[egocentric]] sorts of actions may in turn result in modifying the agents basic behavioural capacities, particularly in that updating memory implies some form of [[machine learning|learning]] is possible. Ideally, action selection itself should also be able to learn and adapt, but there are many problems of [[combinatorics|combinatorial complexity]] and computational [[tractability]] that may require restricting the search space for learning.
In AI, an ASM is also sometimes either referred to as an [[agent architecture]] or thought of as a substantial part of one.
== AI Mechanisms of action selection ==
Generally, artificial action selection mechanisms can be divided into several categories: [[automated planning and scheduling|symbol-based systems]] sometimes known as classical planning, [[distributed systems|distributed solutions]], and reactive or [[reactive planning|dynamic planning]]. Some approaches do not fall neatly into any one of these categories. Others are really more about providing [[scientific model]]s than practical AI control, these last are described further in the next section.
=== Symbolic approaches ===
{{main|Automated planning and scheduling}}
Early in the [[history of artificial intelligence]], it was assumed that the best way for an agent to choose what to do next would be to compute a [[Logical argument|provably optimal]] plan, and then execute that plan. This led to the [[physical symbol system]] hypothesis, that a physical agent that can manipulate symbols is [[sufficient|necessary and sufficient]] for intelligence. Many [[software agents]] still use this approach for action selection. It normally requires describing all sensor readings, the world, all of ones actions and all of one's goals in some form of [[predicate logic]]. Critics of this approach complain that it is too slow real-time planning and that, despite the proofs, it is still unlikely to produce optimal plans because reducing descriptions of reality to logic is a process prone to errors.
[[Satisficing]] is a decision-making strategy which attempts to meet criteria for adequacy, rather than identify an optimal solution. A satisficing strategy may often, in fact, be (near) optimal if the costs of the decision-making process itself, such as the cost of obtaining complete information, are considered in the outcome calculus.
* '''Goal driven architectures''' In these [[symbolism|symbolic]] architectures, agent's behaviour is typically described by a set of goals. Each goal can be achieved by a process or an activity, which is described by a prescripted plan. The agent must just decide which process to carry on to accomplish a given goal. The plan can expand to subgoals, which makes the process slightly recursive. Technically, more or less, the plans exploits condition-rules. These architectures are [[reactive planning|reactive]] or hybrid. Classical examples of goal driven architectures are implementable refinements of [[BDI software agent|Belief-Desire-Intention]] architecture like [http://www.marcush.net/IRS/irs_downloads.html JAM] or [http://urtax.ms.mff.cuni.cz/ive/public/about.php IVE].
* '''[http://www.ai-center.com/projects/excalibur/index.html Excalibur]''' is a research project led by Alexander Nareyek featuring any-time planning agents for computer games. The architecture is based on structural [[constraint satisfaction]], which is an advanced [[artificial intelligence]] technique. Recently, the project is discontinued.
=== Distributed approaches ===
In contrast to the symbolic approach, distributed systems of action selection actually have no one "box" in the agent which decides the next action. At least in their idealized form, distributed systems have many [[Module (programming)|modules]] running in parallel and determining the best action based on local expertise. In these idealized systems, overall coherence is expected to [[emerge]] somehow, possibly through careful design of the interacting components. This approach is often inspired by [[neural networks]] research. In practice, there is almost always ''some'' centralised system determining which module is "the most active" or has the most salience. There is evidence real brains also have such [[Executive system|executive decision systems]] which evaluate which of competing systems deserves the most [[attention]], or more properly, has its desired actions [[disinhibited]].
* '''Spreading activation''' including [[Maes Nets (ANA)]]
* '''Extended Rosenblatt & Payton''' is a spreading activation architecture developed by Toby Tyrrell in 1993. The agent's behaviour is stored in the form of a hierarchical [[connectionist|connectionism]] network, which Tyrrell named free-flow hierarchy. Recently exploited for example by [http://vrlab.epfl.ch/Publications/pdf/Sevin_Thalmann_CGI_05.pdf de Sevin & Thalmann] (2005) or [http://cyber.felk.cvut.cz/gerstner/eth/download/dpdk2.pdf Kadleček] (2001).
* '''[[Behavior based AI]]''' including [[subsumption architecture]]; [[Blumberg]]
* '''[[Creatures (artificial life program)|Creatures]]''' are virtual pets from a computer game driven by three-layered [[artificial neural network|neural network]], which is adaptive. Their mechanism is reactive since the network in every time step determines the task that has to be performed by the pet. The network is described well in the paper of [http://www.cp.eng.chula.ac.th/~vishnu/gameResearch/AI/creatures.pdf Grand et al.] (1997) and in [http://www.double.co.nz/creatures/ The Creatures Developer Resources]. See also [http://creatures.wikia.com/wiki/Creatures_Wiki_Homepage Creatures wiki].
=== Dynamic planning approaches ===
Because purely distributed systems are difficult to construct, many researchers have turned to using explicit hard-coded plans to determine the priorities of their system.
Dynamic or [[reactive planning]] methods compute just one next action in every instant based on the current context and pre-scripted plans. In contrast to classical planning methods, reactive or dynamic approaches do not suffer [[combinatorial explosion]]. On the other hand, they are sometimes seen as too rigid to be considered [[strong AI]], since the plans are coded in advance. At the same time, natural intelligence can be rigid in some contexts although it is fluid and able to adapt in others.
Example dynamic planning mechanisms include:
* '''[[Finite state machine|Finite-state machines]]''' These are [[reactive planning|reactive]] architectures used mostly for computer game agents, in particular for first-person shooters [[Computer game bot|bots]], or for virtual movie actors. Typically, the state-machines are hierarchical. For concrete game examples, see [http://www.gamasutra.com/gdc2005/features/20050311/isla_pfv.htm Halo 2 bots paper] by Damian Isla (2005) or [http://www.kbs.twi.tudelft.nl/Publications/MSc/2001-VanWaveren-MSc.html Quake III bots disertation] of Jean Paul van Waveren (2001). For movie example, see [[Softimage]].
* Other '''structured reactive plans''' tend to look a little more like conventional plans, often with ways to represent [[hierarchical]] and [[sequential]] structure. Some, such as [http://www.ai.sri.com/~prs/ PRS]'s 'acts', have support for [[partial plan]]s. Many agent architectures from the mid 1990s included such plans as a "middle layer" that provided organization for low-level [[behavior based AI|behavior modules]] while being directed by a higher level real-time planner. Despite this supposed [[interoperability]] with automated planners, most structured reactive plans are hand coded (Bryson 2001, ch. 3).
Examples of structured reactive plans include [[James Firby]]'s [http://people.cs.uchicago.edu/~firby/raps/ RAP] System and the [[Nils Nilsson]]'s [http://ai.stanford.edu/users/nilsson/trweb/tr.html Teleo-reactive plans]. PRS, RAPs & TRP are no longer developed or supported. One still-active (as of 2006) descendent of this approach is the Parallel-rooted Ordered Slip-stack Hierarchical (or [http://www.bath.ac.uk/comp-sci/ai/AmonI-sw.html#BOD POSH]) action selection system, which is a part of Joanna Bryson's Behaviour Oriented Design.
Sometimes to attempt to address the perceived inflexibility of dynamic planning, hybrid techniques are used. In these, a more conventional AI planning system searches for new plans when the agent has spare time, and updates the dynamic plan library when it finds good solutions. The important aspect of any such system is that when the agent needs to select an action, some solution exists that can be used immediately (see further [[anytime algorithm]]).
=== Others ===
* [[Soar (cognitive architecture)|Soar]] is a [[symbolism|symbolic]] [[cognitive architecture]]. It is based on condition-action rules known as [[AI production|productions]]. Programmers can use the Soar development toolkit for building both reactive and planning agents, or any compromise between these two extremes.
* [[ACT-R]] is similar to Soar. It is less powerful as a programming language, but simpler to get working. It includes a [[Bayesian]] learning system to help prioritize the productions.
* ABL/Hap
* '''[[Fuzzy control system|Fuzzy architectures]]''' The [[fuzzy logic|Fuzzy approach]] in action selection produces more smooth behaviour than can be produced by architectures exploiting boolean condition-action rules (like Soar or POSH). These architectures are mostly [[reactive planning|reactive]] and [[symbolism|symbolic]]. See the work of [http://aigamedev.com/ Alex Champandard].
== Theories of action selection in nature ==
Many dynamic models of artificial action selection were originally inspired by research in [[ethology]]. In particular, [[Konrad Lorenz]] and [[Nikolaas Tinbergen]] provided the idea of an [[innate releasing mechanism]] to explain instinctive behaviors ([[fixed action pattern]]s). Influenced by the ideas of [[William McDougall (psychologist)|William McDougall]], Lorenz developed this into a "[[psychohydraulic]]" model of the [[motivation]] of behavior. In ethology, these ideas were influential in the 1960s, but they are now regarded as outdated because of their use of an [[energy flow]] metaphor; the [[nervous system]] and the control of behavior are now normally treated as involving information transmission rather than energy flow. Dynamic plans and neural networks are more similar to information transmission, while spreading activation is more similar to the diffuse control of emotional / hormonal systems.
[[Stan Franklin]] has proposed that '''action selection''' is the right perspective to take in understanding the role and evolution of [[mind]]. See his page on [http://www.msci.memphis.edu/~franklin/paradigm.html the action selection paradigm].
=== AI models of neural action selection ===
Some researchers create elaborate models of neural action selection. See for example:
* The [http://ccnlab.colorado.edu/mambo/ Computational Cognitive Neuroscience Lab] (CU Boulder).
* The [http://www.abrg.group.shef.ac.uk/ Adaptive Behaviour Research Group] (Sheffield).
== See also ==
*[[Artificial intelligence]]
*[[Expert system]]
*[[Game artificial intelligence]]
*[[Inference engine]]
*[[Intelligent agent]]
*[[OPS5]]
*[[Production system]]
*[[Rete algorithm]]
*[[Robot intelligence]]
=== External links ===
*The University of Memphis: [http://www.msci.memphis.edu/~classweb/comp7990/fall2002/action.htm Agents by action selection]
*Michael Wooldridge: [http://www.csc.liv.ac.uk/~mjw/pubs/mas99.pdf Introduction to agents and their action selection mechanisms]
*Cyril Brom: [http://ksvi.mff.cuni.cz/~brom/teaching.html#umelebytosti Slides on a course on action selection of artificial beings]
* [http://sitemaker.umich.edu/soar Soar project]. University of Michigan.
* [http://publishing.royalsoc.ac.uk/natural-action Modelling natural action selection], a special issue published by [[The Royal Society]] - [[Philosophical Transactions of the Royal Society]] B: Biological Sciences:
<blockquote>
This theme issue focusses on a particular strategy for finding scientific explanations - computer modelling. The contributions employ state-of-the-art modelling techniques ranging from large networks of simulated brain cells, through to models of individuals (people or animals) viewed as agents operating in simulated worlds.
</blockquote>
== References ==
* Bratman, M.: Intention, plans, and practical reason. Cambridge, Mass: Harvard University Press (1987)
* Brom, C., Lukavský, J., Šerý, O., Poch, T., Šafrata, P.: [http://urtax.ms.mff.cuni.cz/ive Affordances and level-of-detail AI for virtual humans]. In: Proceedings of Game Set and Match 2, Delft (2006)
* 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
* Huber, M. J.: [http://www.marcush.net/IRS/irs_downloads.html 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.: [http://www.gamasutra.com/gdc2005/features/20050311/isla_pfv.htm Handling complexity in Halo 2]. In: Gamastura online, 03/11 (2005)
* Maes, P.: The agent network architecture (ANA). In: SIGART Bulletin, 2 (4), pages 115–120 (1991)
* Nareyek, A. [http://www.ai-center.com/projects/excalibur/index.html Excalibur project]
* 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)
* 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)
[[Category:Artificial intelligence]]
[[Category:Cognitive science]]