next up previous
Next: Formal Definition Up: Conversation Protocols Previous: Conversation Protocols

Conceptual Model

 

Conceptually, we decompose a CP into the following elements (see Figure 3): a finite state control, an input list, a pushdown list, and a finite set of transitions.

First, the finite state control contains the set of states representing the communication state of the interagent's customer during an ongoing conversation. We shall distinguish several states based on the communicative actions that they allow: send, when only the utterance of performatives is permitted, receive, when these can be only received, and mixed, when both the utterance and reception are feasible.

The utterances heard by an interagent during each conversation are stored into an input list. In fact, this input list is logically divided into two sublists: one for keeping the utterances' performatives, and another one for storing their predicates. It is continuously traversed by the interagent in search of a tex2html_wrap2337 pair which can produce a transition in the finite state control. Notice that the continuous traversing the input list differs from the one employed by classic FSAs whose read only input tapes are traversed from left to right (or the other way around).

Let us consider a particular CP related to an ongoing conversation. We say that an utterance is admitted when it is heard by the interagent and subsequently stored into the input list. Admitted utterances become accepted when they can cause a state transition of the finite state control. Then they are removed from the input list to be forwarded to the corresponding addressee, and thereupon the corresponding transition in the finite state control takes place. Notice that all utterances are firstly admitted and further on they become either accepted or not. Therefore, the input list of each CP keeps admitted utterances that have not been accepted for dispatching yet. From now on, these criteria will be taken as the message sending and receiving semantics used in Section3.5*.

The context of each conversation can be stored and subsequently retrieved thanks to the use of a pushdown list. Such context refers to utterances previously sent or heard, which later can help, for example, to ensure that a certain utterance is the proper response to a previous one. For instance, an utterance in the input list --represented in a KQML-like syntax-- will be processed only if its sender, receiver and the value of the keyword :in-reply-to match respectively the receiver, sender and value of the keyword :reply-with of the topmost message on the pushdown list.

Finally, each transition in the finite set of transitions of a CP indicates: i) what utterance can be either sent or received to produce a move in the finite state control; and ii) whether it is necessary to store (push) or retrieve (pop) the context using the pushdown list.

 

  figure1436


Figure 2: Transition

Each arc of the finite state control is labeled by one or more transition specifications. The structure of a transition specification is shown in Figure 2: a transition from state i to state j occurs whenever an utterance with polarity x, performative p, and predicate d is found in the input list and the state of the pushdown list is Z. In such a case, the chain of stack operations indicated by op is processed. In order to fully specify a transition, the following definitions and criteria must be observed:

 

  figure1462


Figure 3: Partial view of the CP DBP used by trading interagents in the Fishmarket.

For instance, Figure 3 depicts the CP employed by a trading interagent to allow its customer (buyer agent Akira) to participate in a bidding round open by the auctioneer agent as explained in Section 2. Notice that the performatives of the utterances considered in the figure follow the syntax of Table 1, and the predicates within such utterances belong to the list in Table 2. This simple example illustrates the use of the pushdown list: i) for saving the state of the bidding round (round number, good in auction, list of buyers, etc.); and ii) for ensuring that whenever a request for bidding is dispatched, the bid conveyed to the auctioneer will be built by recovering the last offer pushed by the trading interagent onto the pushdown list.

   table1473
Table 1: Types of performatives following Cohen and Levesque[11] (extracted from Parunak[5])

   table1486
Table 2: Trading Interagent Predicates


next up previous
Next: Formal Definition Up: Conversation Protocols Previous: Conversation Protocols

World Wide Web
Wed Mar 10 11:44:57 MET 1999