The design of the dynamic agent system and its predecessors attempts to weave together a number of different ideas and influences:
The developmental history of the agent systems began with the idea of loosely anthropomorphic agents. I built several behavioral control systems using them, and then attempted to integrate the agent idea with a more general-purpose language. This involved thinking about agents driven by goals rather than by situations, and led to the realization that agents could be a good basis for constraint solving systems.
DA provides equivalents to most of the basic control and modularity constructs found in procedural languages: sequencing, conditionals, iteration, abstraction, and recursion. These appear in different forms than they do in procedural languages, however. Iteration, for example, is to some extent implicit in the concept of an agent. Therefore rather than having an explicit iteration construct, DA provides a construct, repeat, which does not generate a loop in the way imperative loop constructs do but instead influences the behavior of the iterative agent interpreter.
It is worth clarifying the conceptual relationship between DA agents and procedures. Agents are clearly similar to procedures (or more precisely, procedure invocations): both perform tasks, both are capable of being anthropomorphized; agents can invoke other agents and thus create a hierarchy similar to a tree of procedure invocations. However, there are important differences. Agents can be running concurrently, whereas only one thread of a procedure tree can be active at any one time. Agents are persistent, and are driven iteratively and thus capable of autonomous activity. An agent's supervisor can activate or deactivate it, but while active it is in charge of its own operation. When an agent has a goal, this means that it is in effect constantly monitoring the goal and taking action to achieve it when necessary.
One notable feature of procedural languages that is missing from DA is the notion of the value of an expression. In DA, tasks do not have values, and all computation is strictly by means of side-effects. The choice to omit values was made to emphasize the notion of an agent as something that performs an action, rather than as something that computes a value. In part this was a reaction (perhaps an over-reaction) to the emphasis on value computation found in functional or mostly-functional languages, as well as some attempts to model agents in a functional style (see section 3.4.2.4) which did not, to my mind, capture agency adequately. Another reason for de-emphasizing the return of values was the accessibility of Lisp substrate for doing actual computation when necessary.
Programs that normally work by returning values can be transformed into equivalent programs that work via side-effects, by creating temporary boxes to hold the intermediate values (see the factorial example above). It might be possible to integrate value-returning back into the language. It did not fit into earlier agent systems, in which agents were totally independent, but since DA preserves a calling hierarchy the idea that a called agent could return a value would be more natural.
As a behavioral control system, DA offers capabilities roughly equivalent to those of its predecessor Agar, Brook's subsumption architecture (Brooks 1986), Pengi (Agre and Chapman 1987) or teleo-reactive systems (Nilsson 1994). Agents can implement a set of responses to conditions in the world that implement adaptive behavior. Unlike these systems (except for Agar), DA uses a hierarchy of agents for control. This makes writing agents simpler since sets of behaviors can be treated as a group (for instance, see how get-to is used as a "prepackaged" behavior in several of the examples above), and it increases the salability of the system. Another advantage of DA in comparison to other behavioral control systems is built in structures for implementing sequences.
DA's method of handling inter-agent conflict is somewhat different than these other systems, most of which require hardwired conflict links or other methods of arbitration, if they treat conflict at all. DA detects conflicts at the last possible moment, that is, only if agents actually attempt to simultaneously take incompatible actions (see section 5.2.6). When a conflict is detected, arbitration is performed based on the determination of the agents. The determination of agents is usually fixed, although since it is specified by a regular slot it is possible to alter its value by other agents (say, a hunger-simulating agent that would slowly increase the determination of a food-finding agent).
More sophisticated methods of handling determination are possible within the DA framework. One possibility would be to use a system similar to Maes' Action Selection algorithm (AS), which spreads activation energy (more or less equivalent to determination) between behavior modules based both on current goals and the state of the world (Maes 1990). This algorithm provides a flexible way for modules to string themselves into sequences of action in an emergent fashion. There are some differences in style and goals between this work and DA that make this complicated.
First of all, AS is explicitly non-hierarchical. There are no managers or "bureaucratic modules"; instead all modules exist in an unlayered network, connected by successor, predecessor, and conflict links. To generate these links, AS modules must specify in detail both their preconditions and the expected results of their actions, expressed as lists of conditions. DA is somewhat more flexible, allowing agents to be controlled by either preconditions or goals (expected results). DA does no backwards chaining through the precondition, relying instead on supervisory agents to order goals appropriately. Only one AS module can run at any one time, so all are essentially in competition with one another to run, which contrasts with DA's emphasis on concurrency.
Whereas AS deliberately avoids pre-specified sequences of behavior, preferring them to emerge from the interaction of the available behavior modules, the world, and the goals of the creature, being able to specify sequences explicitly is a design goal of DA. This reflects a deeper difference in the purpose of the two schemes. AS is deliberately done in an emergent or bottom-up style. This is certainly a worthwhile scientific goal. However, emergent systems are notoriously difficult to understand, since their knowledge and activity is concealed as a collection of opaque numerical values. This makes them less suitable as a vehicle for encouraging constructionist novice programming, which is top-down (in some sense) by nature.
Of course DA must make use of numerical values too, as a last-resort mechanism for resolving conflicts. In any distributed control system, such values act as a lingua franca for making comparisons between agents. However, the semantics of such values are difficult to define and their opacity makes systems that use them hard to understand. One alternative is to use symbolic statements of preference: that is, explicitly state that behavior a has priority over behavior b, rather than hiding this fact behind numbers. This technique has been used in the Pengi and Sonja systems (Agre and Chapman 1987) (Chapman 1991). Symbolic Preferences are easier to understand, but must be specified explicitly for every new behavior. Another advantage they have is that they are easily specified by the user using a conflict display like the one described in section 5.1.1.3.
DA has been shown to be capable of performing some of the functions of a constraint system. Tasks can be declarations of relationship, and templates can be written that generate agents that enforce these relationships. Since templates can take arbitrary action, it is difficult to characterize exactly how powerful the constraint system is. The ability to match task patterns and generate new tasks is similar to the equational-rewriting techniques of Bertrand (Leler 1988). This ability can be used to implement the simple constraint-solving technique of local propagation of known states, as seen in the temperature conversion example and elsewhere (see section 5.2.7). It can also be used to implement special-purpose methods for solving constraints that cannot be performed by local propagation. For instance, a constraint of the form (= a (* b b)) cannot be solved for b by local propagation, but DA allows templates to be added that know how to compute square roots in this particular case. Inequalities are another instance where DA's agent-based approach works well. While they cannot be solved in general, special-purpose methods can be created to handle them in ways appropriate to the domain.
The main problem with DA is that its control system is limited and often hard to understand. Here is an example that illustrates some of these limits. The world below contains two rectangle tasks as well as the within task that is visible (see section 5.2.5.2). This latter task specifies that the solid rectangle is to be contained within the hollow rectangle. The effect is to allow the user to drag either object around, and have the other one adjust its position or size accordingly.
Figure 5.27: The within world, in working and anomalous
states.
However, if the user should increase the size of the inner solid rectangle, the system fails to come to a stable state (that is, a state in which all top-level tasks are satisfied). Instead, both objects begin traveling to the left until they are off the stage!
The reason for this behavior is a limitation in the way conflicts are detected and handled. A worker agent's action will be suppressed (that is, fail) only if there is a slot conflict involved--that is, if it attempts to alter a slot that another more determined agent has laid claim to. As it turns out, in the situation above there is a conflict but it is a goal conflict: agents interfere with each other's goals, but alter mutually exclusive sets of slots (see section 5.2.6). Therefore, rather than picking a better way of resolving the conflict, the agents just alternate their actions ad infinitum.
There are several possible solutions to this problem: one is to support undoing an action. If an agent's action could be withdrawn if it was found to cause a goal conflict with a stronger agent, then it could be undone. Another, perhaps more general technique is to employ another type of manager agent that is separate from the main hierarchy of agents and monitors it for looping behavior, and can intervene if necessary (this idea derives from the Society of Mind concept of a B-Brain (Minsky 1987)). In fact, these ideas were explored in various early versions of DA, but rejected as too difficult to fit into the agent model. The current model is a compromise between power and simplicity.
There is a large body of work on constraint-based problem solving, and a smaller one on interactive graphic systems based on constraints, including the classic systems Sketchpad (Sutherland 1963) and ThingLab (Borning 1979) as well as more recent efforts such as Juno-2 (Heydon and Nelson 1994). Garnet (Myers, Giuse et al. 1994), while not providing true constraints (it has so-called "one-way constraints", which are more like spreadsheet cells or LiveWorld's self-computing slots) is of interest because it also explores prototype-based object systems in the context of interaction. ThingLab, in particular, is oriented towards creating dynamic simulations as well as static drawings.
(Ishizaki 1996) applied agents to problems of graphic design. The emphasis of this work was different, however. Rather than solving static constraints, agents were employed to create dynamic designs, or to endow graphic elements with responsive behavior. For instance, in a Dynamic News Display, an agent would be in charge of creating and placing a headline when a news story arrived, based on its contents and the current display. The system (called Model of Dynamic Design) had three levels of control, agents, strategies, and actions, which correspond roughly to top-level agents, manager agents, and worker agents in DA. However, there is no concept of conflict resolution or constraint solving in the model.
DA agents are intended to be understood through animate metaphors. Recall that for our purposes animacy was defined by three key properties:
These qualities are woven into the way DA agents work. An agent is continually clocked (subject to being activated by its superior), which allows it to take action whenever it needs to. It should be emphasized that the clocking process in DA and the other agents systems exists in some sense at a level beneath the animate metaphor, in the sense that in a person, a heartbeat is something that is necessary for action but is not normally considered a factor in the process leading to action. The clocking process (based on animas in the simpler agent systems) does, in fact, serve to give the agents that are clocked the equivalent of both an energy source and a metronomic pulse that can be harnessed to drive action when necessary. This clocking allows an agent to appear autonomous by initiating action at any time. It is equally responsible for allowing agents to be responsive to changing conditions (indeed, autonomy and responsiveness are really two sides of the same coin (see section 3.4.1). Purposefulness is realized by allowing agents to be controlled by goal-like tasks.
The anthropomorphic icons used in agent boxes serve to indicate, in a limited way, the state of the agents vis-a-vis their goals and actions. Two different displays were created that make use of these icons. The agent graph shows all the agents in the system in their hierarchical structure, and updates them as the system runs through its cycles. It can be used to watch the agents states change in real time. The other form of display is the storyboard, which is generated after the fact and selectively presents the dynamics of the agent system in a static narrative form.
One aspect of the way the agent system works seems to violate the anthropomorphic metaphor, or at least strain it. This is the manner in which new agents come into being. When a template specifies that new tasks are to be created, new agents are also created to embody and supervise the tasks. However, this means that agents are constantly coming into being (and are discarded rather unceremoniously as garbage when they have outlived their usefulness). This is a rather callow way to treat anthropomorphic beings! Of course, the ease of creating agents is also one of the chief features of DA, so this problem is fundamental in some sense.
One way to fix this is simply to change the metaphor a bit, so that agents are recruited instead of created. In this variant of the metaphor, tasks are created, but agents are drawn from a pool of pre-existing agents to deal with the tasks as they are needed. When the task is completed, the agent (and any subordinates it might have recruited) are returned to the pool.
While this may make agents appear more like real living entities, it complicates the implementation and its presentation. Now there is a new entity, the pool, and there will be the problem of how many agents it should be staffed with, what happens when it runs out, and so forth.
In both variants of the metaphor, an agent is a general-purpose worker who can perform any task. The knowledge of how to perform these tasks come from templates (which might be metaphorically presented as making up an "employee's manual", were we to extend the corporate metaphor a bit more). Another possible modification to the metaphor would be to conflate agents and templates. In this variant, an agent would be specialized for particular tasks, and emerge from idleness to deal with them as necessary. The problem with this is that there may be a need for multiple agents of the same type, so there is still the problem of agent creation, which now can't even be handled by having a pool of general purpose agents (see the next section for further discussion). Perhaps agents could train other "new hire" agents in their expertise.
All this shows that the details of the mapping between the animate and computational domains is not at all straightforward. In this case the ease with which software entities come into being, which is a principle source of the power of any programming system, is in direct tension with anthropomorphism.
The fact that there are three different but closely related entities in DA--tasks, agents, and templates--seems somewhat unfortunate. Although they all serve necessary and separate functions, it is confusing and can strain the anthropomorphic metaphor.
While developing DA, I resisted the separation of agents and templates for a long time. Most of the earlier prototypes did not have this distinction. In my earlier images of how the system should work, based on Society of Mind, agents are both program specifications and concrete instantiated mechanisms. Rather than having procedural instantiations and bound variables, their "arguments" are supplied again by fixed hardware buses called pronomes (Minsky 1987, p226). This picture may be more biologically realistic (in the sense that functionality is closely linked to a piece of hardware), but a programming language that works this way is severely handicapped by the lack of basic tools such as recursion. It is conceivable to add these capabilities to a Society of Mind-based model with the addition of special stack memory that incorporates K-lines for remembering the state of agents, but this is awkward. Some early implementations of agents did work this way. However, my devotion to realism gave way to a greater need for simplicity. Working without the separation between program and invocation felt like going back in time to older languages like FORTRAN that did not support recursion. To address these problems, I developed the idea of templates as entities separate from agents.
It might be possible to hide this split from the user. For instance, it might be possible to combine the functionality of agents and templates, call the results "agents", and allow them to make copies of themselves, thus preserving the ability to support multiple instantiations. It is also probably possible to de-emphasize tasks as a separate entity, since tasks are mostly matched one-to-one with agents. There still needs to be some way to talk about the specification of an agent's job (the task) as separate from the agent itself, which includes a good deal of other information besides the task.
Each agent is very simple, just embodying an expression from the rather basic task language and executing a simple interpreter to achieve them. This simplicity makes for an understandable system, yet it strains somewhat against the anthropomorphic metaphor. Can such simple things be thought of in animate terms? In particular, some constructs force us to posit more "people" in the agent hierarchy than you might expect (i.e. the repeat construct forms an agent whose only job is to tell its one subordinate to continue doing whatever it is already trying to do[20]). The graphic version of Fahrenheit/centigrade conversion, for instance, can use up to 70 agents to accomplish its task.
One early version of DA attempted to deal with this problem by compressing tasks into an agent that was slightly more complex than the final version. This agent could have both a goal and an action; that is, it could combine what would be two agents in the final version. Because the pattern of task-generation often alternates between goals and actions, this had the effect of generating about half as many agents as in the final version. It also helped strengthen the notion of an agent as something that tied together declarative and procedural information. However, the process of packing tasks two-to-an-agent was complex and confusing, and so I decided to use the simpler form of agent described here.
This problem would only be worse in a system that was uniformly agent-based (see section 6.3.4). If all computation was done with agents, rather than offloading some tasks to Lisp, there would be at least an order of magnitude more agents to deal with. The solution, then, might be not to reduce the total number of agents but to use some form of hierarchical display to normally hide the low-level ones from the view of the user. This is already done to some extent in the current agent display and storyboard system, and is in keeping with the general interface style of LiveWorld.
Part of LiveWorld's general design aesthetic is to not hide anything from the user. Detail must often be suppressed to save screen resources and the user's attentional resources, but it should always be ultimately accessible. Another design goal is simplicity and regularity. These goals may sometimes be in conflict with the goal of using anthropomorphic metaphors. It may help convey the anthropomorphic feel of the system to suppress some of the internals of the system. For instance, the god agent strains the metaphor of the system at several points. It exists primarily for the sake of internal regularity, making it possible to treat the entire group of agents as a single structure. But from the user's point of view, it is at variance with the metaphor of distributed agents. Why are we gathering the diverse set of top-level tasks under a single director? Perhaps it would be better to hide god from the user, preserving the impression of independent agents for top-level tasks.
Another instance in which the anthropomorphic mapping is not simple is in the area of emotional icons. We would like to use the emotional state anger to indicate that two nodes are in conflict. But this can't be done with a straightforward mapping between the agent states and the displayed emotional states, because in the usual case, at any given time one of the nodes involved in a conflict is going to be satisfied (its goal is currently met) and one is not. Satisfaction and being-in-conflict are thus somewhat orthogonal properties of nodes, and if they were translated straightforwardly into a screen representation, there would have to be an angry face and a smiling face displayed (in fact an early version of the system worked in just this way). However, this would strain the anthropomorphic metaphor, which dictates that an agent present a single face to the world. The solution was to just show the angry face, which encoded the more salient of the node properties. Another solution would be to have richer icons that could represent angry-and-satisfied and angry-and-unsatisfied in a single expression, or even better, generate faces parametrically rather than using fixed icons. This opens up the possibility for incorporating all relevant information about an agent (satisfaction, determination, success, conflict status) in a single highly expressive facial representation generated on the fly (Thórisson 1996). Humans can read a lot into a face--whether the computer can write out its state in such a way that it can be so read remains to be seen.