1. Interaction Protocols

Ongoing conversations between agents often fall into typical patterns. In such cases, certain message sequences are expected, and, at any point in the conversation, other messages are expected to follow. These typical patterns of message exchange are called protocols. A designer of agent systems has the choice to make the agents sufficiently aware of the meanings of the messages, and the goals, beliefs and other mental attitudes the agent possesses, that the agent’s planning process causes such protocols to arise spontaneously from the agents’ choices. This, however, places a heavy burden of capability and complexity on the agent implementation, though it is not an uncommon choice in the agent community at large. An alternative, and very pragmatic, view is to pre-specify the protocols, so that a simpler agent implementation can nevertheless engage in meaningful conversation with other agents, simply by carefully following the known protocol.

This section of the specification details a number of such protocols, in order to facilitate the effective inter-operation of simple and complex agents. No claim is made that this is an exhaustive list of useful protocols, nor that they are necessary for any given application. The protocols are given pre-defined names: the requirement for adhering to the specification is:

Requirement 8: An ACL compliant agent need not implement any of the standard protocols, nor is it restricted from using other protocol names. However, if one of the standard protocol names is used, the agent must behave consistently with the protocol specification given here.

Note that, by their nature, agents can engage in multiple dialogues, perhaps with different agents, simultaneously. The term conversation is used to denote any particular instance of such a dialogue. Thus, the agent may be concurrently engaged in multiple conversations, with different agents, within different protocols. The remarks in this section which refer to the receipt of messages under the control of a given protocol refer only to a particular conversation.

1. Specifying when a protocol is in operation

Notionally, two agents intending to use a protocol should first negotiate whether to use a protocol, and, if so, which one. However, providing the mechanism to do this would negate a key purpose of protocols, which is to simplify the agent implementation. The following convention is therefore adopted: placing the name of the protocol that is being used in the :protocol parameter of a message is equivalent to (and slightly more efficient than) prepending with an inform that i intends that the protocol will be done (i.e., formally, I_i Done( protocol-name )). Once the protocol is finished, which may occur when one of the final states of the protocol is reached, or when the name of the protocol is dropped from the :protocol parameter of the message, this implicit intention has been satisfied.

If the agent receiving a message in the context of a protocol which it cannot, or does not wish to, support, it should send back a refuse message explaining this.

Example:

(request :sender i
:receiver j
:content some-act
:protocol fipa-request
)

2. Extending UML for the Specification of Interaction Protocols

1. Introduction

1. Requirements

1. Elements for the Specification of IPs

In the following section we present as well the elements supported by UML as well as the new elements which are added to UML to define interaction protocols. such that the presentation is self-contained. We avoided a distinction between existing notations and the extensions to obtain a unified description of the specification formalism.

For the description of interaction protocols we extend the existing diagram type of sequence diagrams and use notations from other diagrams as much as possible. The new notation is presented in the following way. Mostly some motivation for the introduction of the constructs is given. Second we show the notation and define afterwards the semantics of it. We give an informal, formal and meta-model oriented semantics of the constructs.

0. Object-Constraint Language

• n..m is a constraint, with n Î N , m Î N È { * }, the asterix denotes arbitrary times
• * and n are constraints with n Î N
• deadline and broadcast are constraints
• content(CA) is a pre-defined operation
• received(CA) is a pre-defined operation
• kind_received(CA) is a pre-defined operation
• (- to be completed -)

1. Roles

1. Threads of Interaction

In interaction protocol defines the steps in which the communicative acts are send between different agents. The sending can be done either in parallel or as a choice between different communicative acts. Receiving different messages can result in different answers to a special communicative act, i.e. the behavior of an agent depends often on the incoming messages. Therefor the thread of interaction, i.e. of processing incoming messages has to be split up into different threats of interaction. A lifeline (denoted as a doted vertical line) is associated with either a role or an agent instance with or without a distinguished role.



It shows the duration of the conversation between two or more agents.

Example

for role Seller for agent instance Retailer-1

for agent instance Retailer of distinguished roles Seller and buyer

 

 

An associated thread of interaction is denoted as



A thread of interaction can be split up as follows

and

describing a AND split of the threats of interaction, i.e. are performed in AND-parallelism style.

OR-parallelism of the threads of interaction is defined as

and

XOR-parallelism of the threads of interaction is defined as

and

 

(- to be done: formal semantics, meta-model semantics -)

An interruption of the vertical boxes describes a change of the threat of interaction, denoted as



2. Defining Messages

Communicative acts are defined by UML class diagrams. For the definition of communicative acts we only define attributes and no operations in the class diagram. To allow in the specification formalism beyond FIPA communicative acts e.g. KQML constructs or other communicative acts, we define an abstract class CA which is super-class of FIPA communicative acts (class FIPA-CA), KQML communicative acts (KQML-CAs),... . For each CA we define a sub-class with appropriate content. These class definitions are used in protocol schemes, where the contents area known these communicative acts are instances of theses classes. The class hierarchy looks like follows.



whereby the FIPA communicative acts are defines as follows:



(- to be completed wrt. the actual definition of the CAs -)

Moreover we allow to define subclasses of the communicative acts classes restricting some attributes by constraints. Instance of these constrainted communicative acts have to satisfy these constraints (weaker and stronger preconditions)

(- to be described in detail; weaker / stronger precondition; Believe, Desire, Intention, action refinements, refinement of conditions wrt. the class hierarchy -)

Example:



 

3. Sending Messages

One main issue of interaction protocols is the definition of communicative pattern, especially messages have to be defined which are sent from one agent to another. This sending can be done in different ways, e.g. with different cardinalities, depending on some constraints or using AND-, OR or XOR-parallelism.

 

,

The horizontal arrow describes that an agent instance or a role A-1 is sending the communicative act CA, being a subclass of the standard CAs, to an agent instance or a role A-2. The communicative act can written either above or under the arrow. If we deal with a concrete instance of a communicative act according to a special CA we denote it the second way and third way.

Asynchronous and synchronous message exchange are described using different kinds of arrows. Synchronous messages, i.e. the agent is blocked until it receives some answer to this message, are denoted as . Asynchronous messages, i.e. the agent can process other tasks while waiting for a response to this message, are denoted as . In the following picture we use the arrow for synchronous message exchange, but these figures can also be read with the asynchronous arrow.

Example:

with

A special case is when an agent instance or role sends a communicative act or instance of a communicative act to itself, called self-delegation, this is denoted as



4. Sending of Messages – Detailed View

• { broadcast } denotes a broadcast of a message to all agents
• { n .. m } denotes that the communicative act CA can be send n up to m times, n Î N , m Î N È { * }, the asterix denotes arbitrary times.
• { n } and { * } denotes that the communicative act CA can be send n times and arbitrary times, respectively.
• { deadline } denotes that the communicative act CA has to be received before the deadline. deadline is defined according to ISO 8601.

1. Defining Parallelism and Choices of Messages

Usually in real world applications the communication between different agents can be performed in parallel. Moreover having e.g. a look at the FIPA-request-protocol, an agent can response to a "request" with "refuse", "not-understood" or "agree". Therefore we have to describe moreover AND-, OR- and XOR-parallelism.

AND-parallelism of different messages is defined as

, and

OR-Parallelism is defined as

, and

XOR-Parallelism is defined as

, and

Note, these constructs can be combined unless contradictory information. Moreover the arrows can be within one parallelism used in both directions.

Examples

 

for short

for short

 

for short

 

2. Defining Sub-Protocols

Specifications should be constructed in a modular way. The definition of sub-protocols allows one way of structuring specifications. The reuse of specification parts increase the readability to a some extend.

Named sub-protocols with some protocol inside are defined as follows:

 

named sub-protocol or unnamed sub-protocols

 

The semantics of sub-protocols is the semantics of the involved protocol with the difference that the name of the sub-protocol can be used as an abbreviation in other protocol definitions.

Example



3. Usage of Sub-Protocols

The definition of sub-protocols allow the reuse of specification parts and increase the readability. Defined sub-protocols can be used at any place in a protocol definition.

If a sub-protocol is defined as



the usage of this sub-protocol can look as follows (guard and constraint are optional):



 

The semantics of sub-protocols is the expansion of the sub-protocol notation by the definition of the sub-protocol, i.e. in this example.



We have to identify the used roles and agent instances within the sub-protocol with the roles and agents of the actual protocol. Therefor the constraints have to be extended allowing new operations, like

{ identify(A-1, A’-1), identifiy(A-2, A’-2),... }

identifies the roles and agent instances used in the sub-protocol with theses roles and agent instances of the complete protocol.

Example

4. Defining Repetition and Recursion for Sub-Protocols

Constraint can either be

• a OCL-constraint, i.e. the sub-protocol is executed if the OCL-constraint evaluates to true or
• { n .. m } denotes that the sub-protocol can be repeated n up to m times, n Î N , m Î N È { * }, the asterix denotes arbitrary times.
• { n } and { * } denotes that the sub-protocol can be repeated n times and arbitrary times, respectively.

1. Defining Parallism and Choices on (Sub-)Protocols

(Sub-)Protocols can as well be combined using some parallelism or choices, therefore we allow the notion of AND-, OR and XOR-parallelism as well to the definition of parallelism of (sub-)protocols. Instead of the communicative act the notation of (sub-)protocol, i.e. e.g. for the XOR case.



2. Nested Protocols

Specifying complete multi-agent systems, the execution of a protocol can be nested with some other protocol, e.g. a broker asks a DF to get the information about some sellers. This fact has to be definable in the framework and can be used for structuring issues.



 

The first protocol between A-1 and A-2 is nested with another protocol between A-2 and A-3.

Example



3. Defining the Intention of CAs within Protocols

(- to be completed -)



4. Generic IPs

An generic interaction protocol is defined named Generic-Protocol-Name. The parameter part

• the involved agent roles or agent instances A-1, A –2,... .
• some constraints constraint-1, constraint-2,... being used within the protocol,
• a list of communicative acts CA-1, CA-2, ... with some constraints { ca-c1,...} and { ca-c2,...}, respectively.
  (- semantics has to be defined in detail -), e.g. several kinds of failure may occur, like "system down", not "authorized". This fact would be described as failure { 2 }, i.e. two different instances of failure are allowed in the protocol.
• a list of sub-protocols sub-protocol-1, sub-protocol-2 with some constraints { sp-c1,...} and { sp-c2,...}, respectively. The semantics is the same as described for the communicative acts.

1. Instantiation of Generic Interaction Protocols

The instantiation of a generic interaction protocol is denoted with the actual arguments.



The semantics of this construction is protocol within the generic protocol in which the parameters are substituted by the actual parameters. If a set of communicative act instances are allowed a XOR-splitting is performed as shown in the example below.

Example



with the expanded protocol looks like



2. Dependencies of Protocols

(- to be written -)

1. Examples – FIPA 97 IPs

Since the notation is not stable, only a view examples are given for the old interaction protocols.

1. FIPA-request-Protocol

 

 

2. FIPA-query-Protocol
3. FIPA-request-when-Protocol
4. FIPA-Contract-Net
5. FIPA-iterated-contract-net protocol

Has to be defined

6. FIPA-auction-english-protocol

 

2. Future Work

1. Protocol Description Notation

• Boxes with double edges represent communicative actions.
• White boxes represent actions performed by initiator.
• Shaded boxes are performed by the other participant(s) in the protocol.
• Italicised text with no box represents a comment.

1. Defined protocols

0. Failure to understand a response during a protocol

Whilst not, strictly speaking, a protocol, by convention an agent which is expecting a certain set of responses in a protocol, and which receives another message not in that set, should respond with a not-understood message.

To guard against the possibility of infinite message loops, it is not permissible to respond to a not-understood message with another not-understood message!

1. FIPA-request Protocol

The FIPA-request protocol simply allows one agent to request another to perform some action, and the receiving agent to perform the action or reply, in some way, that it cannot.

The UAML representation of this protocol would be as follows:





Figure 3 — FIPA-Request Protocol

2. FIPA-query Protocol

In the FIPA-query protocol, the receiving agent is requested to perform some kind of inform action. Requesting to inform is a query, and there are two query-acts: query-if and query-ref. Either act may be used to initiate this protocol. If the protocol is initiated by a query-if act, it the responder will plan to return the answer to the query with a normal inform act. If initiated by query-ref, it will instead be an inform-ref that is planned. Note that, since inform-ref is a macro act, it will in fact be an inform act that is in fact carried out by the responder.

The UAML representation of this protocol would be as follows:



 



Figure 4 — FIPA-Query Protocol

3. FIPA-request-when Protocol

The FIPA-request-when protocol is simply an expression of the full intended meaning of the request-when action. The requesting agent uses the request-when action to seek from the requested agent that it performs some action in the future once a given precondition becomes true. If the requested agent understands the request and does not refuse, it will wait until the precondition occurs then perform the action, after which it will notify the requester that the action has been performed. Note that this protocol is somewhat redundant in the case that the action requested involves notifying the requesting agent anyway. If it subsequently becomes impossible for the requested agent to perform the action, it will send a refuse request to the original requestor.

The UAML representation of this protocol would be as follows:





Figure 5 — FIPA-request-when protocol

4. FIPA-contract-net Protocol

This section presents a version of the widely used Contract Net Protocol, originally developed by Smith and Davis [Smith & Davis 80]. FIPA-Contract-Net is a minor modification of the original contract net protocol in that it adds rejection and confirmation communicative acts. In the contract net protocol, one agent takes the role of manager. The manager wishes to have some task performed by one or more other agents, and further wishes to optimise a function that characterises the task. This characteristic is commonly expressed as the price, in some domain specific way, but could also be soonest time to completion, fair distribution of tasks, etc.

The manager solicits proposals from other agents by issuing a call for proposals, which specifies the task and any conditions the manager is placing upon the execution of the task. Agents receiving the call for proposals are viewed as potential contractors, and are able to generate proposals to perform the task as propose acts. The contractor’s proposal includes the preconditions that the contractor is setting out for the task, which may be the price, time when the task will be done, etc. Alternatively, the contractor may refuse to propose. Once the manager receives back replies from all of the contractors, it evaluates the proposals and makes its choice of which agents will perform the task. One, several, or no agents may be chosen. The agents of the selected proposal(s) will be sent an acceptance message, the others will receive a notice of rejection. The proposals are assumed to be binding on the contractor, so that once the manager accepts the proposal the contractor acquires a commitment to perform the task. Once the contractor has completed the task, it sends a completion message to the manager.

Note that the protocol requires the manager to know when it has received all replies. In the case that a contractor fails to reply with either a propose or a refuse, the manager may potentially be left waiting indefinitely. To guard against this, the cfp includes a deadline by which replies should be received by the manager. Proposals received after the deadline are automatically rejected, with the given reason that the proposal was late.

The UAML representation of this protocol would be as follows (has to be defined as parametrized IP) :





Figure 6 — FIPA-Contract-Net

5. FIPA-Iterated-Contract-Net Protocol

The iterated contract net protocol is an extension of the basic contract net as described above. It differs from the basic version of the contract net by allowing multi-round iterative bidding. As above, the manager issues the initial call for proposals with the cfp act. The contractors then answer with their bids as propose acts. The manager may then accept one or more of the bids, rejecting the others, or may iterate the process by issuing a revised cfp. The intent is that the manager seeks to get better bids from the contractors by modifying the call and requesting new (equivalently, revised) bids. The process terminates when the manager refuses all proposals and does not issue a new call, accepts one or more of the bids, or the contractors all refuse to bid.



Figure 7 — FIPA-iterated-contract-net protocol

6. FIPA-Auction-English Protocol

In the English Auction, the auctioneer seeks to find the market price of a good by initially proposing a price below that of the supposed market value, and then gradually raising the price. Each time the price is announced, the auctioneer waits to see if any buyers will signal their willingness to pay the proposed price. As soon as one buyer indicates that it will accept the price, the auctioneer issues a new call for bids with an incremented price. The auction continues until no buyers are prepared to pay the proposed price, at which point the auction ends. If the last price that was accepted by a buyer exceeds the auctioneer's (privately known) reservation price, the good is sold to that buyer for the agreed price. If the last accepted price is less than the reservation price, the good is not sold.

The UAML representation of this protocol would be as follows:



In the following protocol diagram, the auctioneer's calls, expressed as the general cfp act, are multicast to all participants in the auction. For simplicity, only one instance of the message is portrayed. Note also that in a physical auction, the presence of the auction participants in one room effectively means that each acceptance of a bid is simultaneously broadcast to all participants, not just the auctioneer. This may not be true in an agent marketplace, in which case it is possible for more than one agent to attempt to bid for the suggested price. Even though the auction will continue for as long as there is at least one bidder, the agents will need to know whether their bid (represented by the propose act) has been accepted. Hence the appearance in the protocol of accept-proposal and reject-proposal messages, despite this being implicit in the English Auction process that is being modelled.



Figure 8 — FIPA-auction-english protocol

7. FIPA-Auction-Dutch Protocol

In what is commonly called the Dutch Auction, the auctioneer attempts to find the market price for a good by starting bidding at a price much higher than the expected market value, then progressively reducing the price until one of the buyers accepts the price. The rate of reduction of the price is up to the auctioneer, and the auctioneer usually has a reserve price below which it will not go. If the auction reduces the price to the reserve price with no buyers, the auction terminates.

The term "Dutch Auction" derives from the flower markets in Holland, where this is the dominant means of determining the market value of quantities of (typically) cut flowers. In modelling the actual Dutch flower auction (and indeed in some other markets), some additional complexities occur. First, the good may be split: for example the auctioneer may be selling five boxes of tulips at price x, and a buyer may step in and purchase only three of the boxes. The auction then continues, with a price at the next increment below x, until the rest of the good is sold or the reserve price met. Such partial sales of goods are only present in some markets; in others the purchaser must bid to buy the entire good. Secondly, the flower market mechanism is set up to ensure that there is no contention amongst buyers, by preventing any other bids once a single bid has been made for a good. Offers and bids are binding, so there is no protocol for accepting or rejecting a bid. In the agent case, it is not possible to assume, and too restrictive to require, that such conditions apply. Thus it is quite possible that two or more bids are received by the auctioneer for the same good. The protocol below thus allows for a bid to be rejected. This is intended only to be used in the case of multiple, competing, simultaneous bids. It is outside the scope of this specification to pre-specify any particular mechanism for resolving this conflict. In the general case, the agents should make no assumptions beyond "first come, first served". In any given domain, other rules may apply.



Figure 9 — FIPA-auction-dutch protocol

8. Brokering protocol



9. Recruiting protocol