![\includegraphics[width=.8\linewidth]{life-ed}](img1.png) |
University of Bath
Department of Computer Science
Artificial models of natural Intelligence (AmonI)
This paper also addresses the issue of Individuated Agent-Based Modelling (IABM), where individual agents display different behavior. It gives examples of existing IABM systems and describes how these can be moved into more mainstream ABM simulators via two relatively simple mechanisms: either exploiting individual local variables or by specifying different priorities within the action selection mechanism. This allows individual agents to vary in their behavior while sharing the vast majority of their code.
This paper discusses action selection in the framework of agent based modelling. Action selection is the means by which an autonomous agent solves the ongoing problem of choosing what to do next. Action selection is the executive part of agent intelligence.
The remainder of agent intelligence -- which is at least as important and difficult to construct -- are the actions which are chosen between and the perceptions which inform the decisions and shape the acts. There is of course a tradeoff here in the granularity of control: the more an `action' is capable of, the less complexity the executive must handle, but the less control it has. For example, the action `walk-to attended-location' is at a much larger granularity than `extend left-knee'. If you are developing an entire agent intelligence from scratch, then the best way to optimise this trade off is to follow an iterative development process that provides heuristics to allow refactoring when either actions or action selection become too complicated (see further Beck, 2000; Bryson and Stein, 2001b; Bryson, 2003). For most people doing agent-based modelling (ABM), however, the actions and perceptions are already provided, either by the simulation platform or in terms of existing libraries of behaviours from other developed simulations, so these issues will not be further discussed here.
Because agent-based modellers often lack experience with artificial intelligence, they frequently don't use formal action-selection mechanisms. This can make programming the agents unnecessarily complicated, and simulations more difficult to understand, maintain and extend. This paper sets out a description of a number of established idioms for action selection, each of which is useful in at least some domains. As such, it is intended to help modellers increase the clarity of their work. Another emphasis of this chapter is on relatively complex action-selection required for supporting individuated agent based modelling -- ABM where each agent may be programmed with different behaviour. Section 2 begins with a short discussion of the utility of IABM. Section 3, which makes up the bulk of the paper, is a description of four different action-selection idioms, which may be useful for either conventional ABM or IABM. The paper then concludes with a description of engineering issues in bringing the more complex forms of action selection into familiar agent-based modelling environments, such as Swarm, RePast and NetLogo.
Much of the research which exploits ABM examines the patterns that emerge from the behaviour of very simple agents. This research has shown that such simple agents can do a good job of replicating the behaviour of complex real-world actors, even humans, at a high level of abstraction. This level of abstraction seems to be most useful for large numbers of agents, where individual variation or details of decision making can be treated as random noise. In recent years, a number of software tools have been developed which support this sort of research, including Swarm, RePast and NetLogo.
There is another sort of agent-based social simulation though, where the individual agents are given relatively complex intelligent controls. This is typically done to simulate the behaviour of relatively small numbers of individual actors. One of the most spectacular examples of this kind of work is that of Tu (1999), which replicates aquatic animal behaviour from swimming through fluid dynamics up to mating and predation. Another example is the work by Hemelrijk (2000,2002), which has made significant contributions to evolutionary theories of the differences in macaque social behaviour. Hemelrijk's work involves modelling colonies of primates with individual differences in initial rank. She has shown that differences in social organisation can emerge as a simple consequence of a single variable, the level of violence in the average antagonistic interaction (Hemelrijk, 2000).
Tyrrell (1993) built a complex simulated environment (which he creatively called the SE) to test a variety of action-selection mechanisms. The test agent in the SE is a small omnivorous animal which needs to survive and breed. This involves six types of subproblems:
The work of these three researchers has two things in common:
Many researchers would like to be able to produce models exploring their own theories or hypotheses working at this level of complexity, but are either unwilling or unable to accept the cost of constructing such simulations. I personally am aware of several theoretical biologists wanting to construct models of social insects (e.g. particular species of wasps and ants) with small numbers of members per colony, at least two groups of primatologists interested in exploring and demonstrating their own hypotheses which are at odds with Hemelrijk's, and a cross-disciplinary group working on understanding social predator communication. It would be nice if we could find a way to enable such research within existing ABM toolkits. If we cannot, it may be that a new toolkit is called for.
As indicated in the introduction, one way to get more complex behaviour from existing simulators is just to simplify code by using (and commenting) a good model of action selection. In the next section, I will go through several such models in increasing order of complexity. Following that, we will return to examining the question of whether current toolkits can support IABM.
There is no established name for what is really the simplest way to do action selection, so I have called it `Environmental Determinism'. This model assumes that:
|
In the event that a reader is unfamiliar with the Game of Life, I strongly recommend typing ``game life'' into Google™, to view the incredible variety of `emergent' (higher-level) growth and action that results from this simple program. There are claims that this system is a fairly realistic model of bacterial life in a petri dish, but I leave it to the reader determine their veracity.
Coding Environmental Determinism only requires a set of if-then
statements. The environmental conditions should be made clear by
using functions and function names to keep them clean, and of course
comments. For example:
if (cell is dead) AND (number-of-neighbors is 3)
then {set cell alive}; /* new cell is born */
if (cell is alive) AND (number-of-neighbors is 2 OR 3)
then {no action}; /* Leave the cell alive */
if (cell is alife AND (number-of-neighbors is NOT 2 OR 3)
then {set cell dead}; /*lonely or over-crowded cells die*/
if (cell is dead) AND (number-of-neighbors is NOT 3)
then {no action}; /* leave cell dead */
In general, programmers prefer to think about agents rather than environments. Generally speaking, agents tend to be much simpler than there environment -- they tend to have less possible behaviours than there are possible external situations. So programmers find it simpler to organise coding around actions, not events. The standard way of controlling many machines, notably AI game agents, is by using the abstraction of a Finite State Machine (FSM). Programming a finite state machine requires two thing:
For the purpose of ALife action selection, we can think of each state as being a situation in which an agent should perform a particular action. To go back to the Game of Life, we now have to think of the cell/agent as expressing one of two behaviours: looking alive, or looking dead (Figure 2).
 |
Documentation for an FSM should ideally include a diagram. The coding should be the possible transitions clustered by state:
/* Transitions from state DEAD */
if (self dead) AND (number-of-neighbors is 3)
then (self be-born);
/* Transitions from state ALIVE */
if (self alive) AND ((number-of-neighbors NOT in {2,3})
then (self die);
To be formal, a finite state machine should also enumerate all possible environmental or internal events, and specify the situations in which no change takes place, like this:
The advantage of this is that one can check the code to make certain their are no possible transitions the programmer overlooked or forgot to code. The disadvantage is that it might make the code less readable, and that in most situations such a check may take intractably long. In general, programmers should try to put in as much code and comments as is required. For example, if a condition existed that either the programmer had to take a long time to think about or that another person needed explained to them, then those conditions deserve comments and possibly code to make the comments more explicit. For ALife modellers who run large and long simulations, it is almost never a good idea to code the cases where there is no change explicitly because they will take CPU time, though they can be coded for clarity and then commented out.
It's important to realise that in either environmental determinism or finite state machines, the programmer winds up needing to create discrete categories of both environmental events and behavioural acts. The only differences are that in the FSM, the programmer also needs to enumerate states for the agent, and that actions are tied to these states rather than to the environmental categories. Often the states turn out to be a useful abstraction, but that doesn't have to be the case. For many simulations, it may be that the environment really is the more salient actor, and the agents really are simple enough that there is no reason to add theoretical entities such as internal states for the agents.
Most agents, of course, have more than two possible actions. If there
are a limited way of transitioning from each action to the next, then
FSMs are a good way to describe that behaviour. However, if behaviour
is largely driven by environmental prompting, and the
environment is very dynamic and unpredictable (as when it contains
many other types of complex actors), then there may be transitions
from every state to every other state. This means that for every new
action or capability added to an agent, as many transitions will need
to be added to both it and to the other states as there are other
capabilities. The number of transitions (and therefore the size of
the code) grows quadratically, since all 
nodes must have 
transitions in them. It would be better to have a way to code action
selection that didn't grow much faster than the number of possible
actions.
Consider an example where the agents approach a more humanoid sort of intelligence than Conway's cells. Let's start with some arbitrary character chosen from a Jane Austen novel. The typical Austen character might be thought of as having four states: flirting, engaged, in church and married. A first cut at an FSM for this agent might look something like Figure 3.
 |
The problem comes when we start trying to label the transitions. When you think about it, a good Georgian English agent wouldn't only go to church in order to get married, but might attend regularly at any stage of his or her life. On reading Austen further, one realises that marriage is not in fact a terminal state: some characters continue to flirt and may even become re-engaged. In fact, the only terminal state is death, which can occur at any time (Figure 4).
 |
The problem with the FSM is that it is required to represent all possible transitions for an agent. But if we are trying to create a working agent, we really only need to specify the transitions that the agent makes itself. In fact, in the AI for abstract simulations, we generally only need to model the transitions that an agent might rationally choose to take in pursuit of its own goals.
The Basic Reactive Plan (BRP) is a name I've given to an idiom or pattern found in several (though not most) influential reactive planning architectures (Bryson and McGonigle, 1998; Nilsson, 1994; Bryson and Stein, 2001a; Fikes et al., 1972). Building a BRP requires a few assumptions. For example, it requires that one assumes that the agent has a goal, and that it has a set of actions it is capable of doing that can lead to solving that goal. The BRP is a prioritised list of these actions. The most important action is the one that consummates the goal, the second most important action is one that enables the most important act, and so on.
If the agent can already do the most important action it doesn't need to execute the other ones. A reactive plan recognises this situation, which means it can behave opportunistically. This means that each action is paired not only with a priority but also with a perceptual condition which allows it to know when it can execute that action. This is important not only for opportunism (skipping unnecessary steps in a conventional plan) but also for robustness (possibly repeating steps if they fail or if they simply need repeating such as digging a hole until you hit water).
Instead of having to explicitly code how to recognise every possible transition between action states, a BRP programmer needs only code how to recognise the situation in which each action can fire, a task made simpler by the invariant that no better (higher priority) action can fire, or the current one wouldn't be considered. This means that for each action, the programmer only has to hand-code one situation: the minimal requirements where that action might be usable. There is no reason to describe when the action should be skipped anyway, because that is encoded by its priority within the BRP.
Let's return to the Jane Austen agent. We'll assume we are programming one of the `pure' characters with no devious intentions. The agent's highest goal is to become married. In order to become married, the agent must be in a church, but there is no point in going to the church without one's fiancé, and one can't have a fiancé without having gotten engaged. If one isn't engaged, one must flirt. Flirting of course also has preconditions, but for the sake of simplicity we'll stop here.
Here is a possible BRP:
| 1. |
(fiancé present and in church) |
→ marry |
| 2. |
(fiancé present) |
→ goto church |
| 3. |
(engaged) |
→ goto fiancé |
| 4. |
(receiving attention) |
→ become engaged |
| 5. |
() |
→ flirt |
The numbers on the left list priority, with 1 being the highest. Thus if one is in a church but does not have a fiancé present, one does not get married, rather one either goes to be with the fiancé (if one exists) or else one flirts. Unless of course one is receiving attention already, in which case flirting can be skipped; one can become engaged and on the next iteration become married, assuming nothing has happened to remove the new fiancé from the church between program cycles. On the other hand, a character that never receives attention can flirt indefinitely, or, if suddenly receiving notice that it has become engaged (perhaps by arrangement of its parents), skip directly to going to the fiancé.
Obviously, encoding this BRP in an FSM would take at least 25 lines of code, assuming that the goal takes one line to describe and each possible transition between states could be specified in one line. Similarly, a large amount of possible environmental states have been neatly ignored as not relevant to this particular agent's pursuit of its goal.
For all its elegance, a BRP is simple to code in most programming languages. It is best coded as a switch (in Java or C) or cond (in Lisp), though it can also be coded as cascading if-then-else statements in pseudo-languages that lack this idiom. Details of building successful BRPs can be found in Bryson (2003), but essentially they are a simple derivation from a conventional, sequential plan:
| flirt → become engaged → go to church → get married |
The life-like agents such as I have described as Individuated above generally have more than one goal. Further many `actions' may themselves require some multiple sub-actions to complete, and these in turn may require a BRP to organise.
If you examine the history of the action-selection literature (see for a review Bryson (2000a)), you find that there are three sorts of problems that any successful approach must address:
It might seem simpler to represent everything as a sense/action pair -- one enormous BRP1. However, it is untenable (that is, computationally intractable) to have every possible skill that requires this level of attention be equally accessible all the time. The reflexive response to the loud noise I mentioned is one of a relatively limited number of such stimuli (some learned, some innate) which seem to be stored in a separate (and fairly small) part of the brain, the amygdalic system. This is not only a consequence of combinatorics and computational limits, but also of perception and context. In another context, that shade of blue might trigger you to follow a friend wearing a particular shirt through a large crowd or to pass a ball to a teammate rather than having anything to do with puzzle pieces.
I have developed an action selection mechanism that supports all three of these sorts of situations with three types of representations and a development methodology to determine when to apply which (Bryson and Stein, 2001b; Bryson, 2001). The development methodology is called Behaviour Oriented Design (BOD), and is an iterative process for determining not only which type of action-selection representation should be used, but also the granularity of the primitive actions. Primitives are encoded in object-like behavior modules, thus the name. Bryson (2003) gives a good summary of the heuristics and practicalities of using BOD.
The representational framework for BOD action selection is called Parallel-rooted, Ordered, Slip-stack Hierarchical (POSH) reactive plans. POSH reactive plans contain five types of elements. First there are the primitives actions and senses. There are only two differences between these:
The other three types of components in POSH plans are action patterns -- simple sequences to handle the second case above (things that almost always follow), competences -- essentially BRPs which handle the third case above (things checked in certain contexts), and drive collections.
The drive collection is a special extension of the BRP. It serves as the root of the POSH plan hierarchy. It has several important special characteristics:
The POSH action-selection mechanism is itself a sequential process, and it grants only course-grained parallelism and scheduling, because it is dependent on the return-time of the primitives. However, since the primitives are supported by independent modules (which may themselves be threaded) POSH agents can exhibit smooth, continuous parallel behavior.
For an example (drawn from Bryson and McGonigle (1998)), consider a robot which is moving through a cluttered space. The robot in a dynamic environment might need to resample its sensors 7 times a second, but there is no reason for it to stop moving while it does this. The primitive that creates movement can send the wheel drivers the current direction and speed for motion, with the understanding that the drivers will continue in that velocity until the next message is received2.
Reflecting on the four types of action selection I've offered, let's return to the question of individuating agent based modelling. Can platforms such as Swarm, NetLogo and RePast support individuated action selection? Absolutely. The main requirement is only that each individual agent be able to have its own variable state. From here there are two possible solutions:
I can demonstrate that both of these methods are plausible in existing ABM platforms. Of the three modelling platforms I've listed, Swarm and RePast have access to `real' programming languages for describing agent intelligence (objective C and java), while NetLogo only allows modellers access to a toy / teaching language (Logo). Recently, two Bath M.Sc. students have replicated some of the most basic Hemelrijk (2000) results in NetLogo using method one above (Wang, 2003; Muhd Fathil, 2003). Thus even in the simplest of the three platforms, method one is possible.
We have not yet demonstrated method two in a major ABM platform, but Bryson (2000b) implements POSH action selection on a minor ABM platform, the SE developed by Tyrrell (1993). This works because of the sequential nature (described above) of the actual action-selection mechanism that exploits POSH plans. It was easy because I had a version of POSH in the native language of the SE available at the time. All that was required was that the POSH code was linked to the SE code, and then central iterator for POSH was replaced by an individual call to a single POSH program cycle from inside the modelled agent. Code for this implementation is available from the Web page for that project, currently:
http://www.cs.bath.ac.uk/~jjb/web/edmund.html#code
The main obstacle in the way of using POSH on a major ABM platform then is a version of POSH in the appropriate language. This would in practice be impractical done by modellers for NetLogo, because the overhead of the extra action selection mechanism would be too high -- the system is already significantly slower than the other two platforms mentioned. On the other hand, there's no in principle reason that POSH couldn't be translated into java -- it currently exists in C++ (Bryson and McGonigle, 1998), Lisp (CLOS) (Bryson, 2001) and Python (Kwong, 2003).
IABM by no means requires the complexity of POSH action selection -- Method 1 above does not require it, nor did the Hemelrijk replications. It might also be possible to make a simpler systems for Method 2, though I have tried to keep POSH plan structures as parsimonious as possible. As I emphasised in the previous section, any sort of ABM can be improved and extended by simply making clear, intentional decisions about how the action selection will be handled, and by clearly coding and commenting the action-selection part of the agent's intelligence. In modelling as well as the rest of computer science, it's important to do the simplest, clearest thing possible for the problem at hand.
This paper has presented two related topics: how to make action selection better for agent based modelling, and how to individuate agent based modelling. The important steps of improving action selection are:
The easiest way to individuate agent behaviors is to have all the agents share the bulk of their behavior code, the `how' part, then to individuate their action selection, either by having their (shared) action selection program reference individual agent state in its decision making, or by providing different action-selection for different agents.
There is a danger that simplifying action selection coding may lead researchers to make more complicated models than necessary. Already our most difficult task as modellers is to analyse and explain the group behavior that emerges from the interactions of agents -- the more difficult their behavior, the harder this explanation. I believe that having clearer code is worth this risk. The history of science is full of examples where the first successful model was not the simplest, but given that it was the first it must have also been the most immediately intuitive. Once a good model has been built, simplifying it is part of the scientific process of analysing how it works. What good coding technique can do is to make it easier to build both the first and the simplified models.
I must acknowledge that I grossly oversimplified many Jane Austen characters. Thanks also to David Sallach and Tom Howe for encouraging me to write on this topic.
This document was generated using the LaTeX2HTML translator Version 2002 (1.62)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 as4iabm
The translation was initiated by Joanna Bryson on 2004-04-26