AgenTalk Overview

Conceptual Introduction to AgenTalk

1. Background
2. Design Policy
3. Functions of AgenTalk
4. Verification of AgenTalk Functions
5. Conclusion

1. Background

In multiagent systems, achieving coordination among autonomous agents is a major problem. In general, agents coordinate their actions by exchanging messages. We view a sequence of these interactions among agents as a coordination process, and we call a high-level protocol used in a coordination process a coordination protocol.

In the field of distributed artificial intelligence, several protocols for achieving coordination have been proposed: the contract net protocol for task allocation [1], the multistage negotiation protocol for resource allocation under global constraints [2], just to name a few. These protocols have been further customized to suit various application domains. For example, the DSP (Distributed Scheduling Protocol) for the Enterprise system [3] is an application of the contract net protocol for task allocation among workstations connected by a local area network.

AgenTalk, our proposed language for describing a coordination protocol, introduces an inheritance mechanism into the protocol description. Using this inheritance mechanism, protocol designers can incrementally design new protocols based on existing protocols, and application designers can implement customized protocols to suit each application based on existing domain independent protocols.

2. Design Policy

AgenTalk is not meant to be a formal specification language, but a programming language capable of implementing protocols and agents that behave following the protocols. In addition, AgenTalk is mainly concerned with the interactions among agents; it is not concerned with the detailed implementation of an agent. Therefore, various agent models such as a blackboard or a production system can be used to implement an agent. The design policies of AgenTalk are as follows.

Explicit state representation of an agent in a protocol:
One way to describe a protocol is to define a message class (such as Task Announcement in the contract net protocol) and its message handler. However, it was difficult to define a message handler without explicitly defining states in a coordination protocol. In order to counter this, an extended finite state machine is used as a basis to describe coordination protocols in AgenTalk. The extended finite machine is a finite state machine extended to allow variables and is often used to describe communication protocols. Its representation is called a script in AgenTalk. Using this model, states of a coordination protocol can explicitly be defined, and actions of an agent can easily be defined for each state.
Incremental protocol definition:
By introducing an inheritance mechanism in the definition of a script as in an object-oriented language, a protocol can be incrementally defined by inheriting a definition of an existing script. An example showing a use of the inheritance mechanism is described in a later section.
Conflict resolution between coordination processes:
A single agent may be simultaneously involved in multiple coordination processes (e.g., different task allocation processes) having some interactions between them (e.g., the agent's resources are shared). By allowing multiple scripts to be executed in an agent and supporting communication between these scripts, a conflict resolution mechanism between coordination processes can be described.

3. Functions of AgenTalk

3.1 Script Definition

A script represents the state transition of an agent in a coordination process. A script consists of a set of states, an initial state, a set of state transition rules, and a set of variables called script variables. It also has a set of functions called script functions, which are local to a script, and a script from which the definitions are inherited (Fig.1).

Fig.1: Script Components

The components of an inherited script are treated as if they are locally defined. Each state is associated with a name; if the inheriting script has a locally defined state with the same name, the state defined in the inherited script is overridden in the inheriting script. In addition, each state transition rule is associated with a state. When a state is overridden in the inheriting script, rules associated with the overridden state are only inherited when this is explicitly specified. In this case, transition rules associated with the state are effectively the union of inherited rules and locally defined rules.

3.2 Protocol Customization

An agent can view a script as a set of special procedures. When an agent decides to follow a certain protocol, this agent invokes a corresponding script. On the other hand, from the viewpoint of a script, the agent should provide an agent function which is to be called from state transition rules contained in a script (Fig. 2). Thus, with different agent functions, the same script can result in different behaviors of agents. When an agent function is not defined in the agent that has invoked the script, a script function with the same name is called instead. This allows a script function to provide the default behavior of a script. In other words, a script can be customized by re-defining only its script functions, while inheriting all the other components of a script.

Fig. 2: Script vs. Agent

3.3 Execution Model

A state transition rule consists of a condition part and an action part. The condition part describes conditions that must be satisfied for the rule to be fired. The following conditions can be stated: (1) message arrival, (2) conditions on script variables, and (3) timeout. The action part describes procedures to be executed when the rule is fired. The following procedure can be stated: (1) transition to a state, (2) invocation of a script, (3) updating script variables, and (4) calling agent functions.

When a script is invoked, a context is created to hold the values of the script variables for each script invocation. The state transition to the initial state then occurs, and the following loop is entered. First, a rule whose condition part is satisfied is selected from the active state transition rules, which are the state transition rules defined in a current state of invoked scripts. The action part of the selected rule is then executed. When another script is invoked from the action part of a state transition rule, a child context is created. The script doing the invoking is called the parent script, and the invoked script is called the child script. (Fig. 3). Note that when a new script is invoked, active state transition rules are added, not replaced. Unlike a subroutine call, the execution of the parent script is basically not suspended.

Fig. 3: Script Invocation

When there exist multiple state transition rules whose condition parts are satisfied, the rule in the most recently invoked (child) script is selected. The motivation behind this mechanism is that when there are no state transition rules to be fired in child scripts, a parent script can do some background chores.

By invoking multiple scripts from a (top-level) script, multiple coordination processes in an agent can be represented. In addition, script variables in a parent script (context) can be accessed from state transition rules in child scripts. In other words, child scripts corresponding to coordination processes can communicate with each other via the script variables in the parent script (context). This allows conflict resolution among coordination processes in an agent to be described. Since state transition rules are fired one at a time (that is, rules in parent and child scripts are not fired concurrently), we need not consider mutual exclusion when accessing script variables in a parent script (context).

A script can also be viewed as procedural knowledge for an agent to attain a certain goal. In this sense, a script can also be used to describe a behavior of an agent itself.

In addition, multiple script execution mechanism in AgenTalk can also be utilized to implement a meta-level control mechanism. Let us suppose that, when an agent is started, the top-level script is invoked. This top-level script can be viewed to provide a meta-level control of protocols. That is, the top-level script will invoke scripts of domain-level protocols as necessary. By using the agent function interface, the top-level script itself can be customized for each agent. In addition, the top-level script can be extended inheriting the definition of a basic top-level script.

4. Verification of AgenTalk Functions

In order to verify that AgenTalk has enough functions, the contract net protocol and its extensions are described in AgenTalk.

4.1. Contract Net Protocol (Manager)

Task allocation in the contract net protocol is performed as follows. An agent (manager) with a task to be executed broadcasts a Task Announcement message. An agent that is willing to execute the task sends a Bid message. The manager agent selects an agent (contractor) to which the task is to be allocated and sends an Award message to it.

Let us describe the behavior of a manager that follows the contract net protocol using AgenTalk. New message classes such as Task Announcement are defined, and then, the script for the manager is defined. The state transition of the manager is shown in Fig. 4.

Fig. 4: State Transition of a Manager in the Contract Net Protocol

The current version of AgenTalk is implemented in Common Lisp; functions and macros defined in Common Lisp are readily available. In AgenTalk, the define-script macro declares a script with its script variables, its initial state, and a script to inherit. The define-script-state macro defines each state in a script. This macro also defines a state transition rule in the state. Using these macros, the cnet-manager script can be written as shown in Fig. 5. This script is invoked when the task to be allocated is generated.

(define-script cnet-manager (task)
  :initial-state start
  ;;bid-queue holds Bid messages received.
  ;;contract-id holds a current contract-id.
  :script-vars (bid-queue contract-id))

(define-script-state (start cnet-manager)
  ;;:on-entry is executed each time this state is entered.
  ;;! denotes the agent-function call.  In this example,
  ;;announce-task sends a Task Announcement message and returns the contract-id.
  ;;$ denotes script-variable access.
  :on-entry 
  (progn (setf ($ contract-id) (! announce-task ($ task)))
         (goto-state 'announced)))

(define-script-state (announced cnet-manager)
  :rules 
  ;; wait for a Bid message with the same contract-id.
  ((:when (msg bid :contract-id !($ contract-id))
    :do 
    (if (! send-award-immediately-if-possible msg ($ bid-queue))
        (goto-state 'success)
        (push msg ($ bid-queue))))
   ;; check a timeout condition.
   (:when (timeout (task-expiration task))
    :do (if (! send-award-if-possible ($ bid-queue))
            (goto-state 'success)
            (goto-state 'failure)))))

(define-script-state (success cnet-manager)
  :on-entry (exit-script))

(define-script-state (failure cnet-manager)
  :on-entry (exit-script))

Fig. 5: Example Script of a Manager in the Contract Net Protocol

4.2 Contract Net Protocol (Contractor)

Let us consider the behavior of a (potential) contractor when a Task Announcement arrives. When the contractor can execute a task contained in the Task Announcement, it only needs to send a Bid message. However, the contractor may want to divide the task into subtasks and allocate each subtask to a different agent; a task allocation process will then be started for each subtask generated.

This behavior can be described in AgenTalk as follows. First, a top-level script for a contractor is defined; it invokes the cnet-contractor script when an appropriate Task Announcement message arrives (Fig. 6). The cnet-contractor script then checks if it is necessary to divide the task into subtasks. If so, the cnet-manager script is invoked for each subtask. When all the task allocations for subtasks are completed (success state), a Bid message in response to the original Task Announcement message is sent (Fig. 7).

Fig. 6: State Transition of a Contractor Top-level

Fig. 7: State Transition of a Contractor in the Contract Net Protocol

4.3 Extending the Contract Net Protocol

As an extension to the basic contract net protocol, a special message class called Directed Award is used when an agent to which a task is to be allocated is known beforehand. The agent receiving the Directed Award message responds with either an Acceptance message or a Refusal message. The state transition of the manager incorporating this extension (cnet-manager-with-direct-award) is shown in Fig. 8. The figure shows that the definition of this script inherits a large part of the definition from the cnet-manager script. The sample script is shown in Fig. 9.

Fig. 8: Extension of the Contract Net Protocol with a Directed Award

(define-script cnet-manager-with-directed-award (task contractor)
  :initial-state check-directed-award
  :inherits-from cnet-manager)

(define-script-state (check-directed-award cnet-manager-with-directed-award)
    :on-entry (if (! direct-award-made-p )
                  (goto-state 'directed-award-made)
                  (goto-state 'start)))

(define-script-state (directed-award-made cnet-manager-with-directed-award)
    :script-vars-used (contract-id)
    :rules
    ((:when (msg acceptance :contract-id !contract-id)
      :do (goto-state 'success))
     (:when (msg refusal :contract-id !contract-id)
       :do (goto-state 'failure))))

Fig. 9: Example Script of a Manager in the Extended Contract Net Protocol

4.4 Multistage Negotiation

The multistage negotiation protocol can be regarded as a generalization of the contract net protocol. In the contract net protocol, Task Announcement, Bid, and Award are basically used to allocate tasks [2]. In contrast, the multistage negotiation protocol introduces repetitive information exchanges among agents to satisfy global constraints. The multistage negotiation protocol has the following characteristics.

Messages such as Task Announcement can be canceled by a Cancel message. Messages for finalizing an allocation (Commit) and acknowledging it (Committed) are added in the example shown here.
Multiple negotiation processes exist in one agent and conflicts among them need to be resolved.

Let us consider how the multistage negotiation protocol can be described in AgenTalk. After new message classes are defined, the script of the manager in the extended contract net protocol (cnet-manager-with-directed-award) is further extended for the multistage negotiation protocol (msn-manager in Fig. 10). (Note that the original protocol [2] assumed that only Directed Award is used, i.e., Task Announcement is not used. The example shown here is a more generalized version.) The state where the allocation succeeds (success state) in the contract net protocol corresponds to tentative allocation in the multistage negotiation protocol. After the tentative allocation is completed, the manager sends a Commit message to the contractor and tries to finalize task allocation. If a Committed message is returned, the allocation is finalized. However, if a Cancel message is received, a transition to the failure state occurs. When the failure state is reached, another task allocation can be tried; how this retry is performed is described in the parent script invoking the msn-manager script.

Fig. 10: Further Extension of the Contract Net Protocol

The contractor script for the multistage negotiation protocol also needs to handle Cancel messages, because a Task Announcement message itself can be canceled. This script inherits from the cnet-contractor script and adds state transition rules which cause the state transition to the failure state when a Cancel message arrives.

There might exist multiple negotiation processes having conflicts over the use of resources in an agent. To counter this, a conflict resolution mechanism can be described using the mechanism that script variables in a parent script (context) can be accessed from a child script (context), which corresponds to each negotiation process.

5. Conclusions

A basic outline of AgenTalk, which is designed for describing multiagent coordination protocols, was presented. Its design policies were discussed, and its capability was demonstrated through a description of the contract net protocol and the multistage negotiation protocol.

AgenTalk is being developed, and its preliminary version runs with Allegro Common Lisp on Unix workstations and Macintosh Common Lisp, where agents communicate over TCP/IP (Fig. 11). The software is available at http://www.cslab.tas.ntt.jp/at/. The programming interface for handling messages was also developed in the C language, which enables communications between agents and programs written in C (Fig. 12).

Fig. 11: Architecture of an AgenTalk-based Agent

Fig. 12: Network-based Application

References:

[1] Smith, R. G.: The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, IEEE Trans. Comput., Vol. 29, No. 12, pp. 1104-1113 (1980)

[2] Conry, S. E., Kuwabara, K., Lesser, V. R., and Meyer, R. A.: Multistage Negotiation for Distributed Constraint Satisfaction, IEEE Trans. Systems, Man, and Cybernetics, Vol. 21, No. 6, pp. 1462-1477 (1991)

[3] Malone, T. W., Fikes, R. E., Grant, K. R., and Howard, M. T.: Enterprise: A Market-like Task Scheduler for Distributed Computing Environments, in Huberman, B.~A. ed., The Ecology of Computation, pp. 177-205, Elsevier Science Publishers (1988)