In this section we develop and examine a couple of "toy" agent architectures that illustrate some of the issues involved in using agents in a dynamic environment. In the first system, Simple Agents, goals are implicit and agents are simply repeating procedures. Trivial though it is, the Simple Agents system still illustrates some of the issues involved in agent concurrency and conflict handling. In the second system, Goal Agents, agents are more structured and have explicit goals that can be used for a variety of purposes. Both systems offer an essentially static agent model, that is, agents are not created or deleted during the course of activity. Systems that allow for the dynamic creation of agents will be the subject of the next section.
The simplest form of agent that we will consider is essentially just a procedure that can arrange for itself to be invoked repeatedly, or in other words, a procedure that can be readily converted into a process. These agents have no explicit goals or declarative aspect, nor do they have any convenient way to communicate with other agents. Their agenthood rests solely with their ability to carry out their function independent of outside control. LiveWorld provides a way to turn any method of zero arguments into an agent by dropping in an anima (see section 4.6.1). Thus, the Simple Agents system is really just a straightforward extension of the existing LiveWorld method structure. Animas are hooks for LiveWorld's activity driver, so to understand the action of simple agents in more detail, we will need to look at the anima driver mechanism, and modify it to handle some of the issues raised by agents.
The default anima driver is a simple loop which calls the function run-animas repeatedly. Each call is considered an anima cycle. This driver is shown in Listing 5.1. Note that this driver ensures that anima-driven agents run in lock-step with each other, in the sense that each gets to execute exactly once during each clock cycle. This form of concurrency makes agents synchronized by default, allowing them to be simpler than they would have to be if they needed to achieve synchronization through explicit constructs.
Figure 5.1: a turtle executing a classic turtle circle using two simple agents, one to go forward, and one to turn by a variable amount.
(defun run-animas () (dolist (a *running-animas*) (send a :step)))
Listing 5.1: The very simplest anima driver.
When several animas are active, issues of concurrency and conflict can arise. The default anima driver shown in Listing 5.1 basically ignores these issues. Each agent simply executes in turn, creating problems of unpredictability and order-dependency. The unpredictability comes from the fact that the ordering of agents in this round-robin execution is arbitrary, so that two seemingly identical agent systems might exhibit different behavior if the animas happen to be listed internally in different orders. Additionally, the execution of one agent may affect the subsequent action of another. Ideally, all agents would execute concurrently, so that the results of one could not affect the other and the results of execution would always be predictable.
A form of simulated concurrent execution can be accomplished rather easily in LiveWorld by modifying the anima driver. The basic idea is this: all effects of agents are ultimately expressed as side-effects to the values of boxes. So if all side effects are delayed until the end of an agent cycle, the effects of concurrent execution can be simulated. To do this, the agent driver needs to be changed. Rather than simply stepping each anima in turn, it needs to operate in two phases: one to compute the new values, and another to make those new values current. The ability to annotate boxes makes this simple to implement. All that is necessary is to modify the global :set method so that instead of actually altering the value of a box, it will store the new value in an annotation on the box. Then this action is made conditional on the value of a variable *phase*. The master anima driver now will step all animas with *phase* set to 1, then go back and update the actual values of any changed boxes. The implementation of this is shown in Listing 5.2. This code basically says that when *phase* is 1, the new value is stored on the annotation named :new-value of the given box, and the box is saved in a global list for later processing in phase 2. If *phase* is 2, a normal set is done using set-slot-1, the primitive function for changing a slot's value. The anima driver is changed so that it drives the two phases alternately.
(defvar *phase* 0)
(defvar *phase2-boxes*)
(def-lw-method :set #/global (new-value)
(case *phase*
(1 (progn
;; use lower-level mechanism to save new value in annotation
(set-slot-1 (getb-force self :new-value) new-value)
(pushnew self *phase2-boxes*)
new-value)) ; return the new value
((0 2) (set-slot-1 self new-value))))
(defun run-animas ()
(let ((*phase* 1)
(*phase2-boxes* nil))
(dolist (a *running-animas*)
(send a :step))
(setf *phase* 2)
(dolist (f *phase2-boxes*)
(send f :set (slot f :new-value)))))
Listing 5.2: two-phase slot setting in Simple Agents.
In addition to properly simulating concurrency, this two-phase-clock technique
has an additional advantage and one severe drawback. The advantage is that
it also gives us the hooks to deal with conflict in a systematic way, a
topic dealt with in the next section. The drawback is that it significantly
changes the semantics of the languages. Under the two-phase clock regime,
if a method sets a slot value and then uses that slot value in further computation,
it will no longer obtain the right answer. This serious problem is somewhat
offset by the fact that agents are usually quite simple and rarely need
to examine the value of a slot that has been set in the same cycle.
Delaying the operation of :set to achieve concurrency also gives some leverage for dealing with conflict. A conflict occurs when two or more agents try to specify different values for the same slot. If this happens under the system as described above, we will again suffer order-dependencies among the agents (since the last agent to run during phase 1 will be the one that ends up supplying the new value). To deal with this, we can extend the above scheme to keep track of all the :sets done to a slot during the course of a single agent cycle (during phase 1), and then during phase 2, figure out for each slot which value will prevail.
(def-lw-method :set #/global (new-value)
(case *phase*
(1 (progn (push (list new-value *agent*)
(slot self :proposals))
(pushnew self *phase2-boxes*)))
((0 2) (set-slot-1 self new-value))))
(defun run-animas ()
(let ((*phase* 1)
(*phase2-boxes* nil))
(dolist (a *running-animas*)
(let ((*agent* (box-home a)))
(send a :step)))
(setf *phase* 2)
(dolist (f *phase2-boxes*)
(send f :resolve-set))))
(def-lw-method :resolve-set #/global ()
(let ((proposals (slot-or-nil self :proposals)))
(case (length proposals)
(0 (error "No proposals for ~A" self))
(1 (send self :set (caar proposals)))
(t (send self :resolve-conflict)))
(setf (slot self :proposals) nil)))
(def-lw-method :resolve-conflict #/global ()
(let* ((proposals (slot self :proposals))
(best (maximize proposals
:key
#'(lambda (proposal)
(let ((agent (cadr proposal)))
(or (ask-if agent :urgency)
0))))))
(send self :set (car best))))
Listing 5.3: Conflict handling in Simple Agents.
To make this work, we need some way to arbitrate between conflicting agents.
This is accomplished by equipping them with an :urgency slot. When
an agent sets a slot's value, a pointer to the agent gets saved along with
the proposed new value, so the phase 2 code can compare the urgency values
of conflicting agents (we assume that no agent sets the same slot twice
on the same cycle).
In this version of the system, during phase 1 each slot collects proposals for what its new value should be. Proposals consist of the new value and a pointer to the agent that is responsible for suggesting it. During phase 2, the proposals are evaluated and resolved by the :resolve-set and :resolve-conflict methods. maximize is a utility function that will select an element from a list (in this case the list of proposals) that yields the maximum value of a key function (in this case, the urgency of the agent that generated the proposal).The code above is not as efficient as it could be, since there is no real need to store all the proposals and find the maximum later, but we will see that keeping the proposals around will be useful for generating user displays and for establishing alternative conflict resolution strategies.
Since urgency values are just slots, they can be dynamically updated by additional agents (for instance, the urgency of a find-food agent might increase with time and decrease when food was found).
Figure 5.2: Three simple agents, with urgency.
An example where agents conflict is shown in Figure 5.2. This is the same as the previous example with the addition of a new agent, bounce-agent, a sensor, and a new rectangle actor. Bounce-agent checks to see if the turtle overlaps this rectangle, and if so it makes it back up and turn around. The :urgency slot of bounce-agent is 1, allowing it to supersede the other agents, which have the default urgency value of 0. The result is that the normal circling behavior prevails except when the turtle is in contact with the rectangle, when bounce-agent takes charge.
A few other things to note about this example: it is obviously necessary for bounce-agent to move the turtle as well as changing its heading, since otherwise, the turtle would still overlap the rectangle and the :turn-right action would be repeated on the next cycle. Less obvious is the fact that the two asks in bounce-agent are effectively done in parallel, because of the delay built into slot-setting in this agent system. That is why the turtle must back up rather than simply turning around and then going forward. Essentially, no sequentially-dependent operations can appear inside the action of a single agent when the two-phase-clock method is used. The two asks can appear in either order without changing the effect of the agent.
Note that this method of conflict resolution can result in part of an agent's action being carried out while another part is overridden by another agent with a higher urgency. In other words, conflicts are resolved at the slot level rather than at the agent level. Whether this is desirable or not depends on how one interprets the anthropomorphic metaphor. A partially-successful action might be interpreted as a compromise.
(def-lw-method :resolve-conflict #^/cast/turtle/heading ()
(let* ((proposals (slot self :proposals))
(average (/ (reduce #'+ proposals :key #'car)
(length proposals))))
(send self :set average)))
Listing 5.4: An alternative conflict resolution method.
Also note that other methods of resolving a conflict are possible. For instance,
for a numerical slot like heading, the values of all proposals could
be averaged rather then selecting one of them. These alternate resolution
methods can be implemented on a per-slot basis by specializing the :resolve-conflict
method. Listing 4 shows an example in which proposals to set the heading
of any turtle will be averaged.
The ability of the simple agent system to capture conflict can be exploited to generate displays for the user. This allows the user to specify the resolution to conflicts, and can automatically generate agent urgency values.
Figure 5.3: Presenting the user with an agent conflict situation.
An example of this is shown in Figure 5.3. In between phase 1, when each agent has made its attempt to set slots, and phase 2, when actions must be selected and performed, the system surveys the changed slots for agent conflicts. If conflicts are found that cannot be arbitrated by the urgency mechanism (because the agents involved have equal urgency), the system generates a display illustrating the effects of each agent and presenting the choice of agents to the user. Each agent generates a corresponding box containing copies of the slots it effects, and a thumbnail snapshot of the world as it would be if that agent alone was allowed to execute. Thumbnails are based on a special kind of slot whose value is a picture. In this case, the conflict is a complex one: bounce-agent is in conflict with turn-agent over the heading slot, and in conflict with fd-agent over the xpos and ypos slots.
The user then has to select some combination of agents that avoids conflicts. In the figure, bounce-agent could be selected by itself, or turn-agent and fd-agent could be selected together, since they don't conflict with each other. The system can then adjust the urgencies of the selected agents so that this particular conflict will be arbitrated the same way automatically in the future.
In a more complicated system (for instance, one with multiple active actors) there are likely to be multiple sets of conflicting agents. This situation could be handled with multiple sets of thumbnails to choose among, although this could get confusing rather quickly.
The simpler agent systems lend themselves particularly well to a mode of programming in which behaviors are selected from a library and cloned and dropped into an actor. An example of such a library is shown in Figure 5.4. This library contains both simple agents and goal agents (which are described below). Library agents generally refer to other objects through relative boxpath references (see 4.5.4) so that their clones will work properly in any context. Additionally, library agents may refer to slots of their own, which allows them to be parameterized (see behavior get-to in the figure for an example).
Figure 5.4: A library containing a variety of drop-in behaviors.
Figure 5.5: A library of objects containing agents.
Figure 5.5 illustrates how agents can be embedded into a library of other objects. This library contains a variety of turtles and patches (actor objects that are stationary but do something when another object contacts them). Velocity-turtle, for example, has a simple agent, fd, that gives it a constant forward velocity, and another Goal Agent (see the next section) that implements the wrapping behavior seen in most Logo environments. The sound-patch object plays a sound when another object passes over it (the sound, like the agent that generates the behavior, is an internal annotation to the patch object itself). The other patches, curve-patch and slow-patch, will change the motion of turtles that pass over them.
This section describes a slightly more sophisticated form of agent-based programming called Goal Agents. This system illustrates several additional aspects of agents. Specifically, it shows how agents can be based around goals, and how this further enables the use of simple anthropomorphic metaphors to illustrate agent activity. A goal-agent consists of a box whose value is a goal in the form of a Lisp predicate expression. The agent's task is to keep this goal satisfied. In addition to the goal itself, the box display includes an icon that indicates the state of the agent. A satisfied goal displays a smiley face icon, while an unsatisfied one produces a frown. Goal agents have a few other properties which are stored as internal annotations. Of these, the most significant is the action, which specifies how the agent is to attempt to satisfy its goal.
In Figure 5.6 we see an instance of a satisfied goal agent inside an actor (Opus). The agent's goal is that the overlap-sensor have a value of :no, or in other words that its parent actor should not be in contact with any other actor.
Figure 5.6: A satisfied goal-agent.
In Figure 5.7 the turtle has moved, causing the agent to become unsatisfied, as indicated by the changed icon. The agent has been opened to reveal the action within. This action will execute repeatedly until the agent is once again satisfied. In this case the action moves the actor 20 pixels in a randomly chosen direction, so eventually (assuming the turtle is static) Opus will elude the turtle and the goal will once again be satisfied.
Figure 5.7: The goal-agent, unsatisfied and open.
Goal-agents act somewhat like an iterative construct of a procedural language, such as the repeat...until construct of Pascal, running the action until the test is satisfied. Goal Agents are also somewhat similar to situation/action rules, with the difference that instead of specifying a triggering condition and action, a goal-agent contains the negation of the triggering condition as its goal, and acts only when this goal is unsatisfied, or as the ethologist Hinde put it, "The concept of a goal refers always to a situation which brings a sequence of behaviour to an end." (Hinde 1978, p. 624).
It's worthwhile noting that this agent (and all the other types of agents presented in this chapter) operate concurrently with user interaction. For example, the above agent allows the user to chase Opus around by dragging another object. It is this property, the ability to interact with running agent programs, that gives LiveWorld its feeling of liveliness.
Goal-agents can also have precondition, urgency, and satisfied-action slots. The precondition slot contains another predicate and determines whether or not the agent is allowed to run its action. Satisfied-action is an action to take if the goal is satisfied, as opposed to the normal action which is done if the goal is unsatisfied. The satisfied-action slot is included mainly for the sake of symmetry, although since it is somewhat in conflict with the goal-seeking metaphor its use is discouraged.
(def-lw-method :step #/goal-agent ()
(if (ask self :precondition)
(if (ask-self self) ; are we satisfied?
(progn (ask self :satisfied-action)
(setf (ask self :icon) *smile-icon*))
(progn (ask self :action)
(setf (ask self :icon) *frown-icon*)))))
Listing 5.5: Step method for goal agents.
Goal Agents (as described so far) can be implemented by equipping a LiveWorld
object with the :step method shown in Listing 5.5. Implementing goal-agents
also requires installing defaults for the slots involved, that is, goal
agents must have a default :satisfied-action method that does nothing,
and a default :precondition that is always true. Some other mappings
into emotional icons are possible; for instance, an agent whose goal was
unsatisfied but could not act because of a precondition might appear as
frustrated.
As described so far Goal Agents don't really have much more computational power than Simple Agents, since simple agents can simulate the goal/precondition/action mechanism of goal agents with ordinary Lisp conditionals. However, Goal Agents provide some additional structure, in that the separate parts of the conditional are now separate objects and can thus be accessed separately. This means that the system now has the ability to know more about the state of agents. This property is what enables the anthropomorphic icon display. It also enables some alternative control strategies. Agents can test the satisfaction condition of other agents, and conflict resolution strategies can be used that take into account the knowledge about which agents need to run, based on the state of their goals. This permits agents to be arranged in sequences, albeit awkwardly (see the next section).
A useful variant of goal agents can be made by replacing the goal with a condition. The result is an if-then-agent, which consists of three clauses corresponding to the usual parts of a conditional statement: if, then, and else (see section 5.4.1 for an example). Sometimes this is a more natural way to formulate an agent, but because it is not based on a goal it is less amenable to anthropomorphization.
It is instructive to compare Goal Agents with other goal-based formalisms for controlling action. The teleo-reactive program formalism (Nilsson 1994) was developed to address one of the same issues that motivated LiveWorld: the fact that sequential programming is not always suited to the control of agents that are in a continuous relationship with their environment. Other languages at this level include GAPPS (Kaelbling 1988), Chapman's circuit-based architecture (Chapman 1991), and universal plans (Schoppers 1987).
The teleo-reactive program formalism is particularly simple to understand. A teleo-reactive program consists of an ordered set of rules, rather like production rules. Unlike traditional production systems, however, actions are not discrete events (such as adding a token to a list) but durative actions like move. Durative actions persist as long as the triggering condition remains the first satisfied condition in the program. Nilsson suggests thinking of the program in terms of a circuit, which is constantly sensing the world and turning on a specific action. Equivalently, one can think of the T-R program as being called repeatedly in a loop whose cycle time is short compared with the typical length of time of actions. Rules are tested in order until one of the left-hand sides is true, and when one is found its right-hand side action will be executed. Then the process is repeated. For instance, here is a sample program (from Nilsson) that is intended to get the actor to navigate to a bar and grab it:
is-grabbing -> nil
at-bar-center & facing-bar -> grab-bar
on-bar-midline & facing-bar -> move
on-bar-midline -> rotate
facing-midline-zone -> move
T -> rotate
The equivalent program in Lisp would be something like this, with the understanding that the program is enclosed in a rapidly-repeating loop:
(if is-grabbing
nil
(if (and at-bar-center facing-bar)
grab-bar
(if (and on-bar-midline facing bar)
rotate
(if ...
While this language is rather simple, there are a few nonintuitive peculiarities about it. One thing to note is that actions are not directly associated with their goals. Instead, the action of rule n is intended to achieve the goal of rule n-1. Another is that considered as a plan for action, it reads backwards: the last action to be performed, grab-bar, comes first.
To express the equivalent program with Goal Agents requires creating an agent corresponding to each rule as follows (the notation Gn is short for "agent n's goal is satisfied"):
| n |
goal |
action |
precondition |
| 5.1.3.1 |
is-grabbing |
grab-bar |
G2 |
| 5.1.3.2 |
at-bar-center & facing-bar |
move |
G3 & ~G1 |
| 5.1.3.3 |
on-bar-midline & facing-bar |
rotate |
G4 & ~G1 & ~G2 |
| 5.1.3.4 |
on-bar-midline |
move |
G5 & ~G1 & ~G2 & ~G3 |
| 5.1.3.5 |
facing-midline-zone |
rotate |
T & ~G1 & ~G2 & ~G3 & ~G4 |
One problem with this is that the preconditions get rather complicated for long action chains. Agent n has to check that agent n+1 has been satisfied and check that all agents 1...n-1 have not been satisfied! The reason for this is our refusal to have any sort of central arbitrator or serializer that decides which agent should run. Instead we want each agent to figure out for itself if it is applicable, but that means that each agent has to know about all the other agents involved that come before it in the sequence. This is hardly modular.
Figure 5.8: A teleo-reactive program expressed as Goal Agents.
The long visible sensor of the ant is the facing-midline-zone sensor;
other predicates are implemented with overlap-sensors. The bar is the thick
rectangle, the bar midline is visible as a guideline.
The Goal Agents system thus provides a richer way to allow agents to interact than does Simple Agents, but still does not make it very natural to talk about sequences of action. This issue (and others) are addressed by Dynamic Agents.