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 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.

 

 

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:

• the polarity of an utterance , denoted as , can take on one of two values: +, to express that the utterance is sent, or -, to indicate that the utterance is received. From this, for a given CP we define its symmetric view as the result of inverting the polarity of each transition;
• the special symbol p/* represents utterances formed by performative p and any predicate, whereas the special symbol */d stands for utterances formed by any performative and predicate d;
• when several transitions label an arc, they can be grouped into a compound transition as ;
• our model considers the following stack operations:

  push

  pushes the utterance selected from the input list onto the stack;

  pop

  pops the stack by removing the topmost utterance; and

  nop

  leaves the stack unchanged. Usually this operation is omitted in specifying transition;

• when the state of the pushdown list is not considered for a transition, it is omitted in the transition specification. In CPs, e-moves, i.e. moves that only depends on the current state of finite state control and the state of the pushdown list, are represented using the transition specification Zop.

 

 

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.

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

  
Table 2: Trading Interagent Predicates