The agent-based programming systems introduced so far are quite limited in their expressive power. While agents can pursue goals, they are limited to a single fixed method for achieving them. Agent systems have fixed sets of agents and cannot readily modify their goals during execution. There is no easy way to specify sequences of action or lists of goals to be achieved sequentially. This essentially means that actors driven by simple agent systems are limited to a single fixed response to a given situation.
Dynamic Agents (DA) was designed to overcome some of these limitations, and is the most powerful agent language implemented within LiveWorld. In contrast to earlier systems in which agents were basically static entities, in Dynamic Agents, new goals can be created on the fly and agents created to realize them. As in Goal Agents, agents are responsible for a single goal or task. But to carry out their task, they can create new tasks which in turn results in the creation of new, subordinate agents. The agents in a DA system thus form a hierarchy, but a hierarchy that can dynamically change over time.
Imagine an agent as a person. It has a job to do, which can involve either keeping a goal satisfied or carrying out an action. It is created and activated by its superior, but otherwise acts autonomously. Its actions can consist of direct changes to the world, or it can recruit subordinate agents to pursue subtasks that contribute to its own success.
In terms of the anthropomorphic metaphor, the hierarchy consists of managers and workers. Managers can have goals, which they monitor but take no direct action to achieve. Instead they create and supervise the activity of other agents. Worker agents actually make changes to the world. Managers have some flexibility in the manner in which they activate their subordinates. For example, an agent to stack blocks might have a subordinate in charge of finding blocks, another in charge of moving the hand to the block, another to grasp the block, another to move the hand so that the block is on top of the stack, and another to release the block from the hand. This agent would want to activate its subagents sequentially and in a fixed order. An agent which maintains a set of graphic constraints would have a subagent for each constraint, but would typically not care about the order in which they were achieved. It would, however, need to make sure that one agent did not interfere with the goals of another agent. The language for specifying agents has to be flexible enough to accommodate these different sorts of managers.
| little-person model |
Tinbergen model |
dynamic agents | |
| basic model |
procedural |
reactive |
task-driven |
| units |
"little people" (procedure invocations) |
drive centers |
agents |
| persistence |
dynamic |
static |
dynamic |
| goals |
no support |
implicit |
explicit |
| action |
executing procedures |
releasing energy |
performing tasks |
| communi-cation |
LPs ask other LPs to perform procedures |
passing energy |
agents post tasks which generate new agents |
| conflict |
no model |
intra-layer inhibition |
slot conflict and goal conflict |
| multiple methods |
one LP per procedure call |
one unit per behavior |
can have multiple agents for a task |
| failure handling |
none |
none (except repetition) |
agents can fail, allowing other methods to be tried |
| state |
running, dormant, waiting |
blocked; activation energy |
dormant,[un]satisfied, failed, succeeded, determination |
| concurrency |
exactly one LP active at a time |
one active unit per layer |
multiple active agents |
| top |
"chief LP" initiates activity |
top-center |
God agent organizes activity |
| bottom |
primitive procedures |
motor units |
worker agents |
Two earlier forms of hierarchical control system have influenced the design
of the agent hierarchy underlying DA. The first of these is the hierarchy
of procedure calls generated by the activity of an interpreter for a procedural
programming language, and the little-person metaphor sometimes used to illustrate
it (see 3.3.2.1). The notion
of a society of experts performing tasks on demand is retained, but extended
in several significant ways. A little person executes a procedure once then
disappears, but a dynamic agent is a persistent entity. This allows agents
to have significantly greater capabilities. Agents operate in parallel,
they can monitor goals as well as carry out procedures, and there can be
more than one agent created to accomplish a given task. Because agents can
have goals, there is a basis in the model for thinking of agents as satisfied
or unsatisfied, successful or failed, and for handling conflict.
The other major model for DA's hierarchy of agents is Tinbergen's model of animal behavior control systems (Tinbergen 1951), and computational attempts to realize it such as (Travers 1988) and (Tyrrell 1993). Like Tinbergen's drive units and releasing mechanisms, agents in a DA hierarchy are constantly checking their state against the world, and so can take control when necessary, possibly overriding other agents. This flexibility is not found in the standard procedural models of programming. In some sense, DA can be understood as an attempt to integrate the reactive hierarchies of Tinbergen with the formal simplicity and power of the procedural model.
Table 5.2 shows a point-by-point comparison of dynamic agents with the little-person model of procedural programming and Tinbergen's model of animal behavior. The basic metaphor behind procedural programming is serialized following of instruction, while in the Tinbergen model it is reacting to environmental stimuli. Dynamic Agents attempts to integrate these by basing its model of an agent on tasks which can specify both sequences to execute and goals to be achieved. From the LP model, DA takes the idea that agents can dynamically create subagents as part of their activity. From the Tinbergen model, DA takes the idea that agents while arranged in a hierarchy have a measure of autonomous control, can run concurrently, can constantly check on the state of the world and can seize control from each other. The possibility of combining the best features of these two rather different models of control was the inspiration behind the design of Dynamic Agents.
This section presents a technical overview of the structures, concepts, and operation of the Dynamic Agents system. The DA system works by building a hierarchy of agents (see Figure 5.8) based on user specified tasks. In a cyclic process, the agents are activated and may take actions which consist of either a direct action which changes the world, or the creation of subtasks and subagents. Agents may come into conflict by attempting to perform incompatible actions or by interfering with another agent's goal. The system attempts to resolve conflicts and schedule agent activity in such a way as to satisfy as many agents as possible.
Each agent is in charge of a single task, which determines its type and behavior. Primitive tasks specify a direct action to take in the world. Other kinds of tasks can specify goals to be achieved, or complex procedures to perform that invoke a number of subtasks. Tasks are specified using a vocabulary of built-in control constructs and user-defined templates. For instance an and task specifies a number of subtasks, all of which must be satisfied simultaneously for the and task to be satisfied. A script task, on the other hand, activates its subtasks sequentially. Agents have a numerical determination value which corresponds roughly to how hard they try to take their action in the face of conflicts.
At the top of the agent hierarchy is an agent with a special task called (god). This agent serves to organize the activity of the next lowest layer of agents, which embody top-level tasks. These tasks can be specified explicitly by the user in task objects, or arise implicitly from user actions. They can also be part of objects in a simulation or library.
Figure 5.9: An agent hierarchy.
Agents can be in a number of different states. Agents whose task is a goal can be satisfied or unsatisfied. Agents that carry out an action can be successful, failed, or waiting for a subordinate. Worker agents succeed when they are able to carry out their action. They can fail for a variety of reasons, including coming into conflict with other agents. Manager agents generally succeed or fail based on the success or failure of their subordinates. For example, the failure of a single subordinate will cause an and agent to fail, while a similar subordinate failure under an or agent will instead cause a different subordinate to be activated.
The agent interpreter begins its process of activating agents from the top agent and works its way downwards. At each level, the task of an agent determines which subagents, if any, will become activated. For instance, a script agent will only activate one subagent, whereas an and agent will activate all of its subagents. An agent that is satisfied needs to take no action and will not activate any subagents.
Eventually this process bottoms out in worker agents who attempt to execute primitive tasks. The actions of these agents are deferred so that concurrency and conflict resolution can work right, in a manner very similar to that used in simple agents (see 5.1.1.2). The conflicts are resolved using the determination values of the agents involved. Agents that prevail (or are not in conflict) are marked as successful, while losers are marked as failed. Success and failure propagate upwards in a manner determined by the tasks involved. The successful actions are realized, that is, their proposed changes for LiveWorld slots become the current values. This may cause other agents to become unsatisfied. Agent determination values can change as other agents fail and succeed, so that conflict resolution is not permanent--the "balance of power" can shift. This cycle is repeated either indefinitely or until all top-level tasks are satisfied.
This section explains the major structures used in dynamic agents: tasks, agents, and templates. To briefly summarize the relationship between these three separate but closely related concepts:
Templates extend the kinds of tasks that can be handled and thus in some sense constitute the program specification of an agent system. To extend this rough analogy with traditional procedural programming, tasks correspond to procedure calls, while agents correspond (roughly) to the stack frames or other internal structures used to keep track of procedure invocations. However, agents are longer-lived, keep more information, and have more complicated associated control mechanisms than stack frames.
A task is an expression in Lisp syntax that represents either a goal to be achieved or an action to be taken. While tasks are in the form of Lisp structures, they are not (in general) interpreted as Lisp expressions. The first element of a task specifies the general type of task, and may be a special symbol such as and or do, or the name of a domain task. Because tasks and agents are closely coupled, we will use the terminology for tasks and agents interchangeably (for instance, we might refer to the type of agent, which is simply the type of its task). There are a number of different general classes of task:
To summarize: tasks can be split along several dimensions into disjoint pairs of classes. Goals and actions are one such pair, as are manager and primitive tasks; and special and domain tasks. For instance, an and task is a special task, a goal, and a manager task.
Some sample tasks are presented here. More detailed examples may be found later (see especially section 5.4).
(= #^/rect/xsiz #^/rect/ysiz)
This task is a goal since it has a predicate value. The task it denotes is to keep the values of two slots equal (it ensures that the #/rect object is a square). An agent for this task would take no action if the task was satisfied. If it was unsatisfied, the agent would create subagents to try to achieve satisfaction.
(go-to #^/ant #^/food-3)
This is a user-defined goal task. The goal is satisfied when the ant is in contact with food-3, and when unsatisfied will create subagents that will cause the ant to move towards its goal. These subagents will manage the ant's direction and movement.
(do (ask #^/turtle :forward 20)
This is a primitive task. An agent with this task will make the turtle go forward when it is activated.
(script (find-free-block @^/marker/)
(go-to @^/hand @^/marker/)
(grasp @^/hand))
This script task from the blocks world instructs the agent to make three subagents and activate them serially. The first instructs a marker object to find a free block, the second instructs the actor representing the hand to go to the marker, while the third instructs the hand to grasp whatever object it finds. All three of these subtasks are high-level domain tasks that generate manager agents.
An agent is a structure created to carry out and monitor a task. Agents are arranged hierarchically as described above. Internally agents are represented by low-level Lisp structures for efficiency, but they also have representations in box form for presentation to the user.
The most important property of an agent is its task. An agent also contains an assortment of additional state variables that are used to control its activity. This includes its precondition, its current subordinate agent (for script tasks and others that activate only one subagent at a time), its determination, and its success or failure state including information about lost conflicts. Agents also contain the necessary pointers to maintain the agent hierarchy. If an agent was generated by a template, it contains a pointer back to that template along with the variable bindings that resulted from the match of the template's task-pattern to the agent's task.
Agents are intended to be understood anthropomorphically as the active and interested components of the system. To that end, a set of icons are used to represent the state of agents in terms suggestive of human emotion. In addition to the icons for goal satisfaction used in goal-agents (see 5.1.2), dynamic agents can express the state of their action (succeeded, failed, or waiting) and the presence of conflict. The icons and their interpretation are:
Roughly, an iconic face is used to indicate the satisfaction state of the task, while an iconic hand is used to show the state of any action taken to achieve that task. These are somewhat independent, since an agent's task can become satisfied without direct action by the agent.
A template specifies a method for constructing an agent to handle a particular class of domain task. The relationship between templates and agents is similar to the relationship between a procedure specification and a procedure invocation in a standard procedural language: that is, the template is a static, generalized structure that serves as a pattern for dynamically creating other structures (agents) to deal with particular instances of tasks. Thus, templates correspond to what is normally thought of as "the program", that is, they contain the specifications of what the computer is to do.
When an agent with a domain (non-special) task is expanded, the system matches its task against all[18] templates. If exactly one template matches, then a single subagent is created using that template's information. If more than one template matches the task, an intervening ONEOF task is created to manage the multiple agents that result.
Templates consist of a number of fields. Some of these have values that are patterns used to match and generate tasks. The most important of these are the task-pattern and the action-pattern, which specifies a new task. The semantics of a template are (roughly) that if there is an active task that matches the task-pattern of the template, then a subagent should be built that incorporates the new task specified by the action-pattern. Templates can also specify preconditions for the agent and other relevant agent properties.
In this document, templates are shown defined by Lisp forms. It is also possible to create templates in the form of box structures within LiveWorld, by the usual method of cloning a specialized object and filling out the appropriate slots.
Patterns are specified using a pattern-matching language based on the one in (Norvig 1992). A pattern consists of a Lisp list in which some of the elements are pattern variables. Pattern variables are symbols beginning with the ? character. For example, the pattern (= ?a ?b) would match the task (= @^/rect/x @^/rect/y), binding the variables ?a and ?b to the appropriate matched values. This information is used to substitute the values for pattern variables in the other patterns in the template, such as the action.
Here is an example of a template from an animal-behavior simulation:
(deftemplate (get-food-forward ?a)
:precondition '(and (yes? (ask ?a :left-food))
(yes? (ask ?a :right-food)))
:action '(repeat (do (ask ?a :forward 10))))
The task-pattern of this template is (get-food-forward ?a), and the effect of the template is to say that if a task of that form is asserted (for some actor that will match the pattern variable ?a), and the two food sensors are both returning :yes values, then go forward. The pattern variable ?a will be bound to the actor when the template is matched against outstanding tasks, and the precondition and action are evaluated in a context that includes the resultant bindings of the pattern variables. In the above example, the pattern matching facility does not add much power over and above the agent systems already seen. However, the next example uses multiple pattern variables to establish templates for tasks that involve relations between slots:
(deftemplate (= (+ ?b ?c) ?a) :name +left :precondition '(settable ?b) :action '(= ?b (- ?a ?c)))
This template specifies one method for satisfying a particular form of arithmetic constraint by reducing it to a simpler constraint. This template is part of the system's general arithmetic capabilities. As this example suggests, there can be more than one template matching a task. When a task matches with multiple templates, the system will generate multiple agents under a oneof agent (see 5.2.4.4).
The fields of a template specification are:
Users can define their own goals by using the :satisfied parameter of templates. This essentially defines both the declarative and procedural parts of a high-level goal simultaneously. For instance,
(deftemplate (square ?a) :satisfied (= (ask ?a :xsiz) (ask ?a :ysiz)))
This template definition both defines a one-argument Lisp predicate square with the obvious definition, and creates a template that if given a square task will attempt to achieve it by posting the appropriate equality task. This process involves converting the task-pattern into a Lisp function specifier and argument list, and for this reason a template that includes a :satisfied field must have a task-pattern that is of the form (<symbol> <pattern-var>*).
The pattern-matcher is actually more powerful than described so far. Most of its capabilities (for instance, matching a variable to a segment of arbitrary length) have not been used. One extension that has proved useful is syntax that allows patterns to specify that a pattern variable must match a box of a particular type. For instance, the pattern
(yes? (?spinoff ?sensor #/sensors/overlap-sensor))
will match any task of the form (yes? foo), if and only if foo is a spinoff of #/sensors/overlap-sensor.
From the implementation standpoint, agents do not really operate independently but instead are controlled through a centralized agent interpreter. This interpreter is in charge of creating agents for the initial tasks, finding templates to match tasks and creating the new tasks specified by the templates, and so on recursively. The interpreter is also in charge of determining what subset of these agents are to be active at any time.
The interpreter is cyclic, that is, it consists of a process that repeatedly examines and updates the structure of agents. There are a number of different ways such an interpreter could work. For instance, it could pick a single agent to activate on each cycle, or pick a single agent on each level, or activate as many agents simultaneously as it can. To be true to the distributed form of the anthropomorphic metaphor, we have chosen the latter, even though the single-agent-at-a-time methods might be more tractable. So a single major cycle of agent activity consists of activating as many agents as are appropriate, and, if any actions are proposed, resolving conflicts and executing them. This section describes the internal mechanics of agent activation and control. For an extended example of the consequences of such activity, see section 5.3.5.
Activation is the process of making an agent check its goal (if any) and take necessary action. Agents are activated in a top-down process, starting from the top-agent and working down to the worker agents. Activating one agent may result in the creation of subagents and their subsequent activation.
When an agent is activated, it first performs several checks. First, if the agent has already completed, nothing is done. This does not necessarily mean that each agent can run only once, since the completion state of an agent can be reset (see below). If the agent is not complete, it checks whether it may already be satisfied (if it is a goal) and whether or not its precondition is met (if it has one). After passing these checks, an agent has determined both that it needs to run and that it can.
At this point if it is a primitive agent it runs its action. Otherwise it expands itself and marks its subordinate agents for later activation. Expansion is the process of creating subagents for an agent. This involves different processes for different types of agents. For agents with domain-specific tasks, expansion involves finding templates that match the task and using them to create subagents. For special tasks, the process varies but most typically involves making one subagent per clause of the task. For the god task, expansion involves collecting all the top-level tasks and making a subagent for each. Each agent is expanded at most one time.
The process of agent interpretation is essentially iterative. The system activates some set of agents, they perform their tasks, and the process is repeated. In the earlier systems this process was relatively simple, with an anima-based driver that clocked each agent independently, with a global conflict resolution phase. The dynamic agents system is significantly more complex and requires a more complex driver. I have found it useful to think of three different levels of cycle for the different levels of agent activity:
Microcycles are useful mostly for the purpose of user stepping, and macrocycles only make sense for constraint-like problems where all the top-level tasks are goals. The millicycle is really the fundamental unit of dynamic agent activity, and when the system is being driven by an anima (see 4.6.1) it is essentially performing a millicycle per anima clock.
An agent can succeed or fail at various points in its activity. Success or failure halts the agent activity and signals the agent's boss agent, which will take action dependent upon its task. Agents succeed when:
Agents fail when:
Lisp errors may occur due to bugs in the specification of primitive tasks, of course, but they may also be generated by general templates being applied in situations where they don't work. For instance, an agent that attempts to satisfy the task (= a (* b c)) by setting b equal to (/ a c) will get a Lisp error (and thus fail) if c happens to be zero. When this happens, the Lisp error is caught by the agent interpreter, the agent is marked failed, and other methods are tried. This means that the user can be rather free in specifying methods.
The "task-specific conditions" mentioned above refer to the way in which agents react to success or failure for different special tasks. For instance, the failure of an agent whose boss is an and agent will cause the boss to fail as well. In the case where the boss is an or agent, however, the failure will cause a different subordinate of the boss to be activated during the next millicycle. What happens next depends on the parent's action type. For instance, if a child of an agent with an and special action (which we will call an and agent for short) fails, then the parent agent will fail as well. If a child of a script agent succeeds, it makes the next sequential child the current one so that it will be activated on the next agent cycle.
Agent success and failure persists across cycles but may be reset in some circumstances, allowing the agent to attempt to run again. These circumstances include when a successful agent's goal becomes unsatisfied (a goal conflict, see 5.2.6.2) or when a failed agent has its determination increased due to sibling failures.
This section describes the vocabulary of control constructs that are used to create special and primitive tasks, and how they are interpreted by the agent system. The interpretations of other types of tasks (that is, domain tasks) are specified by templates. Special tasks allow tasks to be combined in different ways, and in some sense represent different "managerial styles" or ways of accomplishing a complex task by parceling it out to subordinate agents. Some tasks activate all their subordinates at once, while others activate them one at a time. Of the latter, some specify a fixed order of activation while others don't care. Some tasks are goals that can be satisfied or not, while others are just actions. These distinctions are somewhat confusing, but each task represents a different strategy for accomplishing a complex task. Examples of special tasks in use may be seen in section 5.4 and elsewhere.
These special tasks serve to combine several subordinate tasks in various ways.
(AND goal*), (OR goal*)
These special task types are duals of each other in many respects. And and or tasks are goals, and their satisfaction is a function of the satisfaction of their subtasks (which must also be goals). An and agent activates all of its subagents simultaneously, and expects them all to be satisfied eventually. If any of them fail, the and agent fails. An or agent activates its subagents one at a time, in an unspecified order, choosing another if one fails and only failing if all subagents fail.
(ALL <task>*), (ONE <task>*)
All and one are similar to and and or, but are actions rather than goals, and can have actions as their subtasks. An all agent activates all of its subagents, in parallel, and completes successfully when all of the subagents complete successfully. A failed subagent will cause it to fail. one acts like or in activating subtasks one at a time in arbitrary order, but requires only one successful subtask to succeed. In other words, whereas and and or pay attention to satisfaction, all and one only care about success.
(SCRIPT <task>*)
Script tasks are actions. A script causes its subordinate tasks to be activated one at a time, in the order specified. Each task must complete successfully before the next task is begun. Scripts succeed when the last task is done and fail if any subtask fails.
(TRY <task>*)
Try is similar to script, in that subtasks are activated one at a time and in the specified order. However, only one of the subtasks needs to succeed for the try task to succeed. In other words, try tries running each subtask until one succeeds, at which time it succeeds itself. Roughly, try is to script as or is to and.
(AND-SCRIPT <goal>*)
This special task combines the semantics of and with the sequential properties of script. Like the former, and-script tasks must be satisfiable goals and their subtasks must be as well. But unlike and, and like script, they activate their subordinates one at a time, in the order specified by the task.
The difference between and-script and script is that the former requires that its tasks remain satisfied after they are completed. That is, once a subagent of a script is finished, it no longer cares about its goal, but all steps of an and-script up to the current step must remain satisfied even after they are completed. If they become unsatisfied, the and-script fails (there is no or-script because its behavior would be identical to the more general try construct).
(REPEAT <task>)
REPEAT tasks are actions that never complete, and thus cause their inner task to remain activated indefinitely. Generally, REPEAT tasks are used as the expansion of goals, so that the inner task will be executed only until the goal is satisfied. REPEAT is most useful for actions that achieve a goal only after multiple iterations. For an example, see the template for GET-TO tasks in section 5.2.5.3.
The REPEAT construct allows for iteration at the agent level. Iteration in primitive actions (that is, at the Lisp level) is discouraged, because it blocks other agents from running. Using REPEAT allows the iteration to be interleaved with other agent actions.
(DO <lisp>*)
Primitive tasks are specified using the do task type. Primitive tasks are handled by worker agents that have no subordinates and always complete immediately. They can fail due to Lisp errors or by coming into conflict with a more determined agent. While primitive tasks can specify the execution of arbitrary Lisp programs, they are expected to be simple and fast, and will typically involve nothing more complicated than sending an object a message, or changing the value of a slot or two.
Some special tasks are for the internal use of the system, and are not meant to be used in user-specified tasks and templates.
(ONEOF task*)
oneof tasks are used only internally: they cannot appear in user-specified tasks or templates. They act essentially like one tasks, but are generated by the system when multiple subagents are required for a single domain task. So for instance, a goal of (= @/a @/b) would generate two subtasks corresponding to the two obvious ways to make an equality constraint be true:
(do (setf @/a @/b)) (do (setf @/b @/a))
Because domain tasks can have only one subagent, a oneof task and subagent is created to intervene between the equality constraint and the two methods. Here an outline notation is used to show the relationship between an = constraint, its subordinate oneof task, and two further subordinates:
a1: (= @/a @/b)
a2: (oneof <a3> <a4>)
a3: (do (setf @/a @/b))
a4: (do (setf @/b @/a))
Note that since oneof tasks are used only internally, they are able to refer directly to their subagents. In actuality the treatment of equality is somewhat more complicated; see section 5.2.5.1 for more details.
(GOD)
The GOD special task is used internally by the system for the top agent. It gathers together all the top-level tasks, makes them into subagents, and otherwise acts essentially like an all task.
Domain tasks are interpreted according to templates; that is, the user specifies an interpretation for them. This section presents some detailed examples of domain tasks and the templates that interpret them.
Numerical constraints are expressed as algebraic relations. For example, one way to express a task to maintain the relationship between Fahrenheit and centigrade temperature representations looks like this:
T1: (= @^/Fahrenheit
(+ 32.0 (* 1.8 @^/centigrade)))
Equality constraints are usually handled by templates that propose two subagents: one that proposes to make the equality constraint hold by making the expression on the left-hand side be equal to the one on the right, and the inverse. These tasks are expressed by means of the <== operator, known as one-way equality. This operator has the same declarative meaning as =, that is, it is satisfied if its two arguments are numerically equal. Its procedural meaning is that equality can only be achieved by altering left hand side to match the right. A similar construct, <=equal, is available for non-numeric values. The basic definition of one-way equality is provided by the following set of templates:
(deftemplate (<== ?a ?b) :satisfied (= ?a ?b) :precondition '(settable? '?a) :action `(do (setf ?a ?b))) (deftemplate (= ?a ?b) :name =left :action '(<== ?a ?b)) (deftemplate (= ?a ?b) :name =right :action '(<== ?b ?a))
The temperature conversion task would result in the two subtasks:
T3: (<== @^/Fahrenheit
(+ 32.0 (* 1.8 @^/centigrade)))
T4: (<== (+ 32.0 (* 1.8 @^/centigrade))
@^/Fahrenheit)
If the left-hand side of a one-way equality constraint is settable, it can be expanded into a worker agent by the first template shown above. Settable-ness is defined by the settable? function, and is true of anything that can be a legitimate first argument to the Common Lisp setf macro. @^/Fahrenheit is settable, so T3 can be expanded into:
T5: (do (setf @^/Fahrenheit (+ 32.0 (* 1.8 @^/centigrade)))
T4, however, has a left-hand side that is not settable. This does not mean the task is hopeless, however! Other templates can match it and transform it into subtasks that will eventually allow action to be taken:
(deftemplate (<== (+ ?b ?c) ?a) :name +right :action '(<== ?c (- ?a ?b)))
This template says that a one-way equality task that is trying to change the value of a sum ((+ ?b ?c)) can be transformed into a new task that sets one of the items being summed (in this case, ?c). The template will match T4 and generate a new subtask:
T6: (<== (* 1.88 @^/centigrade)
(- @^/Fahrenheit 32.0))
In effect, the template has performed an algebraic transformation on T4. This process of transformation continues, controlled by other templates which have forms similar to the +right template, until it results in a runnable worker agent. In this case, the penultimate task, which will expand directly into a worker agent, is:
T11: (<== @^/centigrade
(/ (- @^/Fahrenheit 32.0) 1.8))
A rewriting system like this poses a danger of generating a non-terminating chain of transformed tasks, either through looping or through infinite expansion. The built-in set of templates for handling numerical constraints avoids this problem by ensuring that templates always generate new tasks whose left side is a sub-part of the left side of the original task. Since each transformation must produce a new task whose left side is strictly smaller than the starting task, the process of transformation must eventually terminate.
Geometrical constraints ultimately turn into numerical constraints of the type shown above. The combination of the template pattern language and LiveWorld's object facilities allow them to be expressed as higher-level relationships.
For example, the (rectangle <actor>) form of goal is heavily used in graphic constraint problems such as the graphic version of the temperature converter. The dimensions of LiveWorld actors are directly controlled by the four slots xpos, ypos, xsiz and ysiz. The rectangle constraint defines two additional slots, bottom and right, and enforces geometric consistency among the resulting set of six slots. Rectangle does not by itself put any constraint on the appearance of an actor, instead it allows other constraints to be placed on any one of a rectangle's sides or dimensions. It should also be noted that rectangle constraints can be applied to any actor, or indeed anything with the appropriate slots. For instance, it makes sense to give ovals a rectangle constraint. The constraint actually means "enforce consistency on an object's rectangular bounding box."
The rectangle constraint is defined by the following template:
(deftemplate (rectangle ?r)
:satisfied
(and (= (ask ?r :right) (+ (ask ?r :xpos) (ask ?r :xsiz)))
(= (ask ?r :bottom) (+ (ask ?r :ypos) (ask ?r :ysiz)))))
This means that an unsatisfied rectangle task will expand into an and task which will in turn expand into two equality tasks.
Geometric constraints can also express inter-object relationships. The within constraint specifies that one object should lie entirely within another:
(deftemplate (within ?a ?b)
:satisfied (and (>= (ask ?a :xpos) (ask ?b :xpos))
(<= (ask ?a :right) (ask ?b :right))
(>= (ask ?a :ypos) (ask ?b :ypos))
(<= (ask ?a :bottom) (ask ?b :bottom))))
A within task expands to an and subtask with four subtasks of its own. Each of these enforces a numeric relationship. When >= and <= tasks are unsatisfied, they are expanded into equality tasks. That is, if the task (>= a b) is encountered and unsatisfied, the system will attempt to enforce it by trying to equate a and b. This technique obviously is incomplete, in that it only tries a very small subset of the possible ways to make the constraint true. However, it produces reasonable interactive behavior in the case of the within constraint. If the user drags an object constrained to be within another, the agents will do nothing as long as the constraint is satisfied. If the object goes outside the boundaries of the surrounding object, the surrounding object will be moved as if bumped and dragged.
Note that the two objects constrained by a within task must also have rectangle constraints defined so that their bottom and right slots are defined and maintained properly.
Figure 5.10: A world combining numerical and geometrical tasks. The conversion task (T1 in the text) appears in the task object within temperature. Within the centigrade bar, task-1 asserts that the bar is a rectangle while task constrains its vertical size to be equal to the computed centigrade temperature.
Tasks and templates from behavioral domains tend to make more use of the repeat construct, reflecting the fact that the actions that satisfy goals in this domain generally do not satisfy immediately, as they do in the more abstract domains above. Instead, they achieve their goal only by repeated application. A simple example:
(deftemplate (get-to ?creature ?place)
:satisfied (eq (ask (ask ?creature :overlap-sensor) :other) ?place)
:action '(repeat
(script
(head-towards ?creature ?place)
(do (ask ?creature :forward 10)))))
This template defines a goal called get-to, that expects to have actors match its pattern variables. The goal is satisfied when its two actor arguments are in contact, as defined by the creature actor's overlap-sensor. This template generates a subagent with a repeat task. This means that the innermost task (the script) will be repeated until the get-to task is satisfied. The script first attempts to satisfy the head-towards goal, and when it is satisfied will proceed to activate the do agent, which will move the creature forward. The script task ensures that forward motion only happens if the head-towards goal is satisfied, that is, only if the creature is facing the target. The fact that the repetition is outside of the script ensures that the head-towards goal will remain monitored and if the target object moves, the creature will realign itself before moving forward. By contrast, a goal of the form:
(script (head-towards ?creature ?place) (repeat (do (ask ?creature :forward 10))))
would adjust the heading once, and then go forward indefinitely with no further course corrections.
There are two types of conflict that can occur during the execution of a DA system. The first, slot conflict, occurs when two or more agents attempt to set a slot to different values. The second, goal conflict, occurs when a successful action results in another agent's goal becoming unsatisfied. These two types of conflict represent different constraints on agent activity. Slot conflict models the physical impossibility of an object being in two states at once or taking simultaneous actions that are physically incompatible (for instance, an actor cannot move in two different directions at once). Goal conflict, on the other hand, reflects the fact that agents will often interfere with each other's goals, and that either compromises must be reached or some agents will remain unsatisfied.
Each major cycle might result in many worker agents attempting to take action. This raises the possibility that they might come into conflict. As in Simple Agents, all the actions of worker agents are ultimately expressed as changes to the values of slots, and so slot conflict is defined as more than one agent trying to set a slot to incompatible values. The DA system uses techniques similar to the two-phase clock technique used in the simpler agent systems. Under this technique, the actions of worker agents are not actually performed when the agent is activated but instead get deferred and turned into proposals for each slot.
At the end of each major cycle, therefore, a conflict resolution procedure is required to determine which slots have conflicting proposals and which agents shall prevail. This involves collecting all the slots that have proposals, all the worker agents that have made proposals, computing sets of agents that are in conflict, and for each set, picking an agent to prevail. This is done by comparing the determination of the agents in the conflicting set. The agent thus selected gets to make its proposals take effect, and is marked as successful, while the losing agents fail.
In some cases, it is important to detect conflicts between agents that do not necessarily get activated during the same major cycle. This is the case for agents that are jointly underneath an and agent, for instance.
When an agent's proposal is realized, the slots that are changed record which agent provided the value, and the current clock tick. When the persistent-slot-values switch is on, this data is used in future cycles. In this case, in addition to any proposals suggested by agents running in the current cycle, the prevailing value and the agent that set it are also compared in the conflict resolution stage. This essentially means that in order to change a slot value, an agent must have a higher determination than the last agent to successfully set that slot's value.
Goal conflict occurs when the action of one agent causes another agent, previously marked as satisfied, to become unsatisfied. When this happens, the newly-unsatisfied agent is reset, that is, its completion state is revoked so that it can run again. In addition, it is marked as the victim of a conflict, which causes no additional processing but causes the graphic representation of the agent state to be an "angry" icon rather than the less descriptive "unsatisfied" icon.
The intent of the goal-conflict handling mechanism is to allow these "angry" goals to have another chance to satisfy themselves. In the most usual case, the goal was originally satisfied without taking any action, so it had not asserted its control over any slots. Now that the conflicting agent has run, when the original agent runs again it is likely to encounter slot-conflicts with the agent that caused the goal-conflict. The slot-conflict mechanism is more specific, and gives the conflicting agents a chance to search for non-conflicting methods of attaining their goals.
Each agent has a determination value between 0 and 1 that is used to resolve conflicts. The metaphorical interpretation of determination is a measure of how much the agent wants to be successful, and how strongly it will "press its case" when coming into conflict with other agents. An agent's determination value can depend on a number of factors:
The default determination value is 1. Agents that have subordinates pass the determination down to them according to their type. and-type agents, that require all of their subordinates to be successful, will give each subordinate the same determination as itself. or-type agents (which include or and oneof agents) will split their determination among their subordinates.
More precisely, an OR-type agent's determination is split up among those subordinates that have not failed. When a subordinate does fail, the determinations of its remaining siblings are recalculated.
Figure 5.11: How agents implement local propagation of constraints.
The effect of this determination calculation in constraint-type domains is roughly to implement local propagation of known states. A fully known state, in this interpretation, is a slot that is being held to a value by an agent with a determination of 1. A constraint agent that supervises several different methods will initially give each method a determination less than 1. If a method tries to set a slot that has been locked (that is, set by a highly-determined agent) it will fail. If all methods fail, the system tries to determine which agents have failed permanently (for reasons other than conflict) and which still have a chance for succeeding if their activation is increased. Then each of the latter class is given a chance to run with the full determination of its parent.
Figure 5.11 illustrates a typical sequence of events that make up a propagation. When slot1 is set by an agent with a high determination (step 1), it causes the goal agent to become unsatisfied (step 2). The goal agent activates its subordinates, and while the first one now fails where previously it might have succeeded (step 3), the second one succeeds (step 4) because it alters a different slot, which might result in further propagation. For a detailed example of how this method of propagation works in practice, see section 5.3.5.