This section develops a theory of agent-based programming, that is, a model of programming strongly based on animate metaphors. Agent-based programming begins with the traditional anthropomorphic mapping underlying the idea of computation and changes it in two ways. First, it changes the nature of the mapping so that instead of presenting the computer as a single anthropomorphic entity, it is instead seen as a society of interacting autonomous agents. Second, it extends the mapping between the anthropomorphic representation and the underlying computational reality to include new characteristics, such as goals and emotions based on the state of goals.
Using multiple applications of the anthropomorphic metaphor in the description of a program is not a particularly new idea. It is present, in varying degrees of explicitness, in the little-person model, in object-oriented programming, in the Actor model of computation, and in the Society of Mind. However, in these systems, the metaphor has for the most part remained in the background, used only for teaching purposes or to illustrate a set of concepts that quickly become detached from their metaphorical roots. The animate parts in such systems are for the most part seen as rote instruction followers.
In agent-based programming, the animate metaphor is taken more seriously. Anthropomorphic characteristics are deliberately brought forward into the language and interface, and the user is encouraged to think of agent activity and interaction in those terms. More importantly, agent-based programming seeks to provide a richer form of anthropomorphism than earlier models. In contrast to the rote-instruction-follower version of animacy found in most of the standard models of computation, the animacy of agent-based systems attempts to emphasize the characteristics of animacy we have found to be the most important: autonomy, purposefulness, and reactivity.
We will see that the single most important technique for realizing this concept of agents is to give them explicit goals--that is, concrete and accessible representations of what it is they are supposed to accomplish. Goals can help crystallize the anthropomorphic metaphor: an agent is not just any sort of person, it's a person with a job to do. Goals can support reactivity (agents react to events that affect their goal) and support detection of conflicts when one agent interferes with another's goal.
In the loosest sense of the term, an agent-based system is simply one whose functionality is distributed among active functional modules. If a module can be seen to be taking an action to achieve a purpose, it partakes of agenthood. By this criterion, even the most ordinary programs written in standard procedural languages may be seen as agent-based: agents are procedures, while the communications between them are procedure calls. So this definition does not capture anything very distinctive, although it does allow us to see that the roots of the agent metaphor are to be found in standard programming practice.
How can we design agents that are more likely to be seen in animate terms? We have identified three characteristics in particular that contribute to the feeling of animacy: purposefulness, autonomy, and reactivity. These characteristics do not have simple technical definitions, and are deeply intertwined with one another. The following sections explore how these characteristics can be realized in concrete computational terms. Other criteria must be taken into consideration when designing an agent language. We would like our agent system to be at least as powerful and usable as more traditional languages. This means that we also need to consider traditional language design issues such as understandability, expressiveness, modularity, and composability.
Agent-based programming, by its nature, emphasizes action-taking rather than computation in the narrow sense. Because of this, it is crucial that agents be embedded in some kind of environment in which they can act on other active or passive objects. The environment, then, will be just as important as the language in determining the nature of agent-based programming, since it determines the kinds of action and interaction that can take place. Chapter 4 treats these issues in detail; for now, we should just keep in mind that agents are involved in interactions with a complex world.
When we talk about a "goal", we mix a thousand meanings in one word.
Marvin Minsky, Society of Mind
In a complex software system, every component is there to achieve some goal of the designer. This goal may be evident to an expert familiar with the global workings of the system and the relationships of the parts, but may not be at all evident to a novice attempting to understand the system from scratch. In fact, even experts often have trouble understanding the purpose of other's code, and occasionally even their own.
Agent-based programming can make these underlying purposes explicit, by including a computational representation of the state of affairs the agent is supposed to bring about. Agents allow procedural programs to be associated with declarative information about what they do. In the same way that objects in a dynamic language like Lisp can carry around their type with them, agents can carry around their goals. Explicit goals serve a number of different purposes in an agent system:
Control: The most basic use of goals is simply to control and structure activity by triggering procedures at appropriate times. A goal tells an agent when to run--that is, when its goal is unsatisfied.
Verification: Goals allow agents to monitor the success or failure of their actions--successful actions make the goal become satisfied. This can make debugging easier, since parts of programs that fail to achieve their stated purpose are explicitly revealed. The fact that agents can have an idea of success and failure also provides a way to deal with unreliable problem-solving techniques. Agents may create several subagents to help achieve its goal, each subagent having the same goal as its superior, but using different methods of achieving it. Because the agents can tell whether or not they have succeeded, the superior agent can use this knowledge to dispatch among its subagents.
Conflict detection: If an agent achieves its goal, it can continue to monitor that goal and detect if some other agent causes the goal to no longer hold. This is one way to detect inter-agent conflict. Conflict situations are quite common in complex systems, and are a common source of bugs. The presence of explicit goals permits an agent to detect situations in which another agent interferes with its goal, and makes it easier to convey to the user the nature of the problem.
Organization: Agent-based programming can be viewed as a particular way of organizing program fragments, by analogy with object-oriented programming. Just as OOP organizes procedures around the objects that it manipulates, in agent-based systems procedures can be viewed as organized around the goals they are meant to achieve. Each of these forms of modularity provides a degree of encapsulation or black-boxing, that is, a separation between the external interfaces of objects and their internal implementations. In OOP, this means that an object can send another object a message without having to know about the internal structure of the receiving object or the methods that process the message. The analogous property for agent-based systems is that an agent can assert a goal to be satisfied without having to worry about the details of the other agents that will be recruited to satisfy that goal
Visualization: Explicit goals can also make programs more comprehensible to an observer who is reading the program or watching it execute. The goals serve as annotations or comments that explain in a declarative style what a procedure is trying to do. But unlike textual comments, goals are in a machine-usable form and can thus be used for a variety of interface tasks.
Goals thus form the conceptual and computational basis for giving agents explicit representations of their purpose, which also contributes to the realization of the other two major qualities of animacy we seek: autonomy and reactivity.
In the standard procedural model of programming, programs run only when they are explicitly invoked by an outside entity, such as a user or another program. Agents, by contrast, should be able to invoke themselves, without the need for external invocation. That is, they should be autonomous in the sense we have been using the word in this chapter--capable of initiating action, or being seen as such. Of course, since an agent is also a constructed mechanism, one which the programmer builds and understands using a more mechanical, causal point of view, this apparent autonomy may only be skin-deep. No action really happens all by itself. So agents will always have to be capable of being seen in at least two ways: as autonomous action takers and as mechanical responders to outside conditions.
The simplest way to realize agent autonomy is to make each agent into a separate process, and let it run in a loop concurrently with all other agents (and other activity, such as user actions). Concurrency in some form is a minimal requirement for agent autonomy. But concurrency by itself is a bare-bones approach to constructing agents. It provides a necessary platform to support autonomy, but no structure for handling conflicts or explicitly dealing with goals.
A somewhat different approach is to allow agents to be triggered by specific events or states. That is, agents specify somehow what states or events they are interested in, and are activated whenever these occur, without having to continuously check for them. This has the same effect as the concurrent approach, but it can be more efficient and the metaphor is different. In some sense triggering is causal or non-autonomous, because the agent is being activated by an outside force, but if we use the monitoring metaphor the agent may still be seen as the source of action.
Reactivity means that agents should be responsive to the world. But what does this mean? For one thing, it implies that the agent is operating in a changing world--an assumption at odds with the standard model of procedural programming, where the environment is generally static. It also implies that the agent has some readily available means of sensing the state of the world. More importantly, it means that the image of the agent is different from the sequential executor that the rote-instruction-follower model suggests. While agent-based systems should certainly be capable of executing sequences of operations, it should also be easy for them to respond to changes in the world at any time.
Reactivity is related to the properties of autonomy and purposefulness. An autonomous entity initiates action--but to seem purposeful must have some reason for taking action. For simple systems, the reason is usually going to be a change in the state of the world, that is, the entity is reacting to something in its environment.
This section examines some of the ways in which the term "agent" has been used to refer to elements of larger computational systems, and analyzes their strengths and deficiencies compared to the criteria outlined above.
The simplest realization of computational agents is as concurrent processes that can execute simple loops. This approach is used by MultiLogo (Resnick 1988). In MultiLogo, agents are processes that can execute any procedure. Agents are thus general purpose entities rather than being specialized for particular functions. Each agent has a graphic turtle of its own, so turtles are controlled by a single agent, but the agents can communicate freely with the sensors and effectors of LEGO creatures, permitting experiments in which multiple agents can be controlling a single creature. Agents communicate by sending messages to one another. Each agent has an input queue for messages and has some control over how messages are inserted into the queue of recipients.
MultiLogo agents, being separate processes, are certainly autonomous. The language provides no special constructs for supporting goals or reactivity, although it is a fairly simple matter to set up procedures with conditionals that provide these kinds of features. There are no built-in facilities for handling conflict: if two agents try and control the same LEGO motor, contention will arise. Agents, however, are protected from conflicting commands by handling them through a queue, which effectively serializes them.
One major difference between MultiLogo's approach and the agent-based systems of LiveWorld is the sharp distinction in the former between agents and procedures. This follows standard computing practice, but led to some confusion among students learning to use MultiLogo, who had to learn to perform two separate types of problem decomposition. In effect, agents (processes) are a separate facility for concurrent operation that is augmenting a standard procedural language (Logo). Perhaps the confusion arises because both concepts partake of animacy in different ways, and get conflated in the students' minds.
Another model for agent is a rule or demon. In this model, agents have a condition and an action to be taken when the condition is met. A collection of such agents, together with a procedure for resolving conflicts, forms a forward-chaining rule system, that is, a system that is driven solely by the current state of the world rather than by goals. While agents may have a purpose, they do not have explicit goals. Teleo-reactive programming (Nilsson 1994) is an example of a formalism that uses sets of rules to implement agents; for more discussion see Section 5.1.3.
Although the agent-as-process model is more general (since a process can presumably implement a rule using conditionals), the more restrictive format of the agent-as-rule model can simplify conflict resolution and makes possible certain control strategies (such as recency or specificity) and efficient implementations (such as storing rules in a data structure that permits fast triggering (Forgy 1982)).
Rules, considered as a programming metaphor, are quintessentially reactive but are not goal-oriented and are not usually thought of in particularly anthropomorphic or autonomous terms. One way in which rules are anthropomorphized is to think of them as demons that are triggered by specific events or conditions.
Shoham's Agent Oriented Programming (AOP) formalism (Shoham 1993) is a computational framework explicitly designed as an extension or specialization of object-oriented programming. Objects become agents by redefining both their internal state and their communication protocols in intentional terms. Whereas normal objects contain arbitrary values in their slots and communicate with messages that are similarly unstructured, AOP agents contain beliefs, commitments, choices, and the like; and communicate with each other via a constrained set of speech acts such as inform, request, promise, and decline. The state of an agent is explicitly defined as a mental state.
The AOP concept of agent is coarser-grained than that found in LiveWorld's agent systems. Each agent has its own mentality or belief system as opposed to components of a single mind. There is no real opportunity for conflict in AOP, because each agent is responsible for maintaining consistency among its commitments. If given contradictory information a choice must be made, but there is no built-in mechanism for doing this.
Oddly enough, the AOP formalism appears to have no explicit representation of desire or goals. Nor do the languages that implement AOP provide processes or other constructs that support autonomous activity. Agents, despite their mental qualities, are essentially passive like ordinary objects, but communicating at a higher level of abstraction. The agency in AOP is entirely representational, rather than active. The roots of agency are seen as having explicit beliefs and knowledge, rather than in being goal-directed or autonomous.
This makes Shoham's concept of agency almost entirely orthogonal to LiveWorld's. They are not necessarily incompatible though--there is the interesting possibility that it might be possible to combine Shoham's representational agency with the purposive, autonomous idea agency developed here. This is an area for future research.
Playground (Fenton and Beck 1989) had a rather idiosyncratic view of agents as a combination of a slot and a value-producing form for that slot. An agent in this system is something like a spreadsheet cell that is also part of an object. See Section 2.2.3.2 for further discussion of Playground.
Playground's model of agent seems rather un-agent-like in the context of our discussion, in that it cannot take any action to effect the world outside of itself. Functional agents like these can be anthropomorphized to some extent by describing their computation as a "pulling" of values from other cells in the system to use in its computation of its own value. This is opposed to the usual "pushing" activity of more imperatively-structured languages. This terminology at least puts the agent in an active role, but does not really allow it to act on the world.
A Playground agent is autonomous, in the sense that it continuously updates its value without outside intervention, and reactive for the same reason. It has no explicit representation of goal or purpose. Since there is exactly one agent per slot, there is no real opportunity for conflict to arise.
A wide variety of systems for controlling the behavior of an intelligent creature employ distributed networks of simple modules. Some of these refer to the modules "agents", but it is more common in this realm for the creatures themselves to be called agents. To avoid confusion we will continue to use agent to refer to the internal active parts.
These systems arise from a movement within the AI and artificial life fields that focuses on intelligent action rather than the more traditional symbolic problem solving. In part this focus stems from frustrations with the state of work in traditional paradigms, in part from an interest in modeling animal behavior for its own sake, in part from philosophical standpoints about the nature of human intelligence and activity (see section 2.1.4), and in part by a search for alternatives to the dominant planning and reasoning paradigm, which can be computationally intractable and has a limited ability to deal with a dynamic world (Chapman and Agre 1986).
While situated action does not rule out representation and reasoning, it de-emphasizes them. Intelligent action is generated first by responsiveness to current conditions in the world. Systems that work in this way tend to be organized around a functional modularity. Rather than the centralized architecture of traditional AI, these systems are divided up into more-or-less independent, modules each of which is in charge of a particular behavior. These modules are connected in networks so that some control can be exerted, but each module is in charge of managing its own connection to the world through sensors and effectors.
A variety of computational constructs are used to implement the internal agents of these situated creatures. I will survey a few of these systems; for a fuller treatment see (Agre 1995).
The subsumption architecture (Brooks 1986) (Connell 1989) is a design methodology for robot control systems. A subsumption program consists of a number of modules connected in a network, usually arranged in a layered fashion, with each layer capable of controlling action independently. Higher-level layers are capable of preempting lower-level ones using a scheme based on fixed priority gates that make up the network. Each module is an autonomous augmented finite-state machine, which can communicate with the outside world through sensors, to other modules through the network, and to itself through a small set of registers. Modules typically implement fairly simple behavioral control rules, sometimes augmented with state. Goals are implicit rather than explicit, and conflict between modules is handled by hardwired priorities in the connections between the modules and the network.
The Agar system is a software kit for modeling animal behavior (Travers 1988), and its conception of control is based loosely on Tinbergen's ethological models (Tinbergen 1951) (also see section 5.2). In Agar, an animal's behavioral control system consists of a network of agents. An agent is something of a cross between a process and a rule, and has an activation level and a threshold that determines when it can run. Agents in general connect a sensory stimulus to an action, which may be an external action or the activation of another agent. Agents affect one another by passing activation in this manner, and the usual practice is to arrange them into a control hierarchy so that higher-level agents can activate ones at lower levels. There are no explicit goals. Conflict is avoided by hard-wired inhibitory links between agents that conflict.
Maes' Action Selection Algorithm (Maes 1989) (Maes 1990) is somewhat different from the above systems. It too posits a division of a control system into functional modules, with variable activation levels. However, the relations between them are modeled after the relations of classical STRIPS-like planning operators, so that modules are connected to other modules that represent their preconditions and expected results. Unlike the other models, this allows the activation of the system to respond to changing goals as well as to conditions in the world. The action selection algorithm is explicitly non-hierarchical so that there are no managers, however, there is a "bottleneck" in that only one module can actually act at any one time.
The agents of these systems are highly limited, yet can perform complex tasks. As agents in the sense of this chapter, they are somewhat deficient. All three systems offer a high degree of reactivity. Agar's agents and Brooks' behavior modules are semi-autonomous: they run concurrently, and take action on their own. Maes' competence modules are less so, since only one can act at a time. All the architectures implement purposefulness, but only Maes' uses an explicit representation of goals.
Narrative deals with the vicissitudes of intention.
Jerome Bruner (Bruner 1986)
The agent metaphor allows computational elements to be envisioned using more natural and powerful conceptual tools than those provided by more formalistic approaches. But thinking about program parts in animate terms is only the first step. Once that mapping is created, what other uses can be made of it? One possibility is to explore the traditional methods for expressing the interactions and histories of human agents; that is, of narrative forms. There would seem to be great potential in using the form of stories both to create software agents (through programming-by-example or case-based techniques) and to present the activity of such agents to the user.
This second technique was explored in prototype form in the Nose Goblins system (Travers and Davis 1993). This project included an agent architecture that was one of the predecessors of LiveWorld's, and allowed users to construct constraint-like agents that performed tasks in a graphic design domain. In this architecture, agents related goals and methods, and could detect inter-agent conflict.
When an agent conflict was detected, Nose Goblins created a story about the conflict and expressed the story to the user using a format that combined a comic-strip/storyboard format with clips of animated cartoon characters (see Figure 3.1). The storyboard served to present the temporal qualities of the story, while the animated characters presented the emotional states of the actors, based on the satisfaction state of their goals (happy, unhappy, or angry if in a conflict situation). When a conflict was detected, a partial storyboard was generated with the final panel showing the characters in an angry state; it was then up to the user to resolve the situation. The resolution was stored in a case library and used to deal with future conflicts.
Figure 3.1: Four panels from a Nose Goblins storyboard. The first two frames illustrate the goals of the two agents involved, while the last two illustrate how one agent clobbers another's goal and the resultant conflict.
Narrative is a natural form for describing action, particularly action that involves the interaction of multiple actors. If computational objects are going to be understood anthropomorphically, their actions are going to be best understood through narrative forms.