Protocol Conformance for Logic-based Agents

1 Introduction

A protocol specifies the "rules of encounter" governing a di­ alogue between two or more communicating agents [Rosen­ schein and Zlotkin, 1994]. It specifies which agent is allowed to say what in any given situation. It will usually allow for several alternative utterances in every situation and the agent in question has to choose one according to its strategy. The protocol is public, while each agent's strategy is private. Pro­ tocols can help to define a suitable standardised semantics for agent communication languages in order to allow actual interoperability in open environments. Instead of being re­ lated to some (virtually inaccessible) private mental state of the agent as proposed by KQML [Labrou and Finin, 1998] and FIPA [2002], the meaning of a dialogue move refers to some publicly agreed and verifiable conversational state. For in­ stance, one may equate the meaning of a dialogue move with the set of possible responses to this dialogue move as defined by the public protocol [Pitt and Mamdani, 1999]. Of course, this does not disqualify the idea of a private semantics, but simply emphasises that standardisation cannot be achieved at this level. Following these ideas, Pitt and Mamdani [1999] have established the notion of a layered semantics for agent communication languages which integrates both private and public levels, and each agent must implement both of them to actually be able to converse with other agents.

When considering interactions that are not necessarily co­ operative (typically negotiation), it cannot be safely assumed that agents will always follow the rules of encounter specified by a particular protocol. It is then crucial to provide proper means of evaluating how well agents are adapted to these pro­ tocols, in a sense that has to be precisely defined in the context of the interaction. In this paper, we introduce three different levels of conformance (weak, exhaustive, and robust confor­ mance) and show that a logical representation of the protocols for logic-based agents greatly facilitates determining (both a priori and at runtime) whether or not these agents behave in conformance to the protocols. We also show how to enforce conformance at runtime for such agents and suggest a pre­ liminary definition for the notion of protocol competence, an attempt to measure how well an agent is adapted to a given protocol beyond the basic requirements of conformance.

The remainder of this paper is organised as follows. In Section 2 we introduce a new formalism for the representa­ tion of protocols based on if-then-rules. Section 3 motivates the introduction of our three levels of conformance. Abduc­ tive logic programming has recently been used as a basis for defining (private) strategies for agents negotiating over the distribution of resources [Sadri et a/., 2001] . Section 4 intro­ duces these agents, illustrates how to check protocol confor­ mance for them, and shows how the agents themselves can ensure their conformance without requiring any extra reason­ ing machinery. Section 5 concludes the paper.

2 Representing Protocols

In this paper, we will assume some restrictions on the kind of dialogues that we want to deal with. The dialogues we are considering only involve two agents which sequentially al­ ternate dialogue moves. These restrictions (notably avoiding concurrency) allow us to concentrate on a particular class of protocols, namely those representable by means of determin­ istic finite automata (DFAs), of which there are numerous ex­ amples to be found in the literature [Pitt and Mamdani, 1999; Dignum and Greaves, 2000]. Our aim for this section is to in­ troduce a protocol representation formalism based on simple if-then-rules and to show that it is adequate to represent the kinds of protocols that we are interested in here.

We recall here that a DFA consists of (i) a set of states (in­ cluding an initial state, and a set of final states), (ii) a set of events, and (iii) a transition function 5 which maps pairs of states and events to states. Figure 1 shows an example, taken from [Pitt and Mamdani, 1999]. Events are occurrences of dialogue moves; states are the possible stages of the conversation. The protocol, entitled "continuous update protocol", aims at continuously updating the other agent about the value of some proposition. Note that it is always the same agent A (the initiator) who informs the other agent B. The legal communicative behaviour of both agents is captured by such a protocol. We make this notion of legality precise in the fol­ lowing definition:

Definition 1 (Legality) Given a DFA with transition func­ tion o, a dialogue move P is a legal continuation wrt. a state S if! there exists a stateS' such that S' = o(S, P) .

We shall refer to legal inputs (respectively outputs) for an agent X as those legal continuations where X is the receiver (respectively the utterer) of the dialogue move.

Protocols such as that of Figure 1 can alternatively be rep­ resented as sets of if-then-rules which specify the set of cor­ rect responses for a particular incoming dialogue move. For example, to express that agent B could react to an inform move sent by A either by sending an acknowledgement or by terminating the dialogue, we may use the following rule:

Note that variables are implicitly universally quantified, ex­ cept those that only appear on the righthand side of an impli­ cation, which are existentially quantified. In general, in this representation, dialogue moves are instances of the schema

where X is the utterer, Y is the receiver (X =f. Y), D the iden­ tifier of the dialogue, and T the time when the move is uttered. Subject is the type of the dialogue moves, i.e. a performa­ tive (such as end) of the communication language, possibly together with a content (as in inform(P)). We shall mostly use the abbreviated form P(T) to dialogue moves, omitting the parameters not relevant in the discussion. For the sake of simplicity, we will assume that the start of the protocol is triggered by some external event START-it is possible to conceive this as the result of some meta-level negotiation pro­ cess to agree on a particular protocol. The start signal START is sent by the system to exactly one agent and exactly once during a dialogue. Similarly, a dialogue ends once one of the agents sends the signal STOP to the system. Dialogue inputs for the agents are either dialogue moves sent by other agents or a START signal sent by the system.

Going back to the example of Figure 1, we observe that this automaton in fact represents two subprotocols, one for the initiator, and one for its partner. We will refer to these two subprotocols asP A and PB . They can be translated into a set (composed of two subsets) of if-then-rules as illustrated in Table 1. In general, given a protocol P, we shall refer to the subprotocol guiding the behaviour of agent o: asP a·

This example suggests that we can simply translate proto­ cols into if-then-rules where we have a single performative on the lefthand side. We call protocols that permit such a straightforward translation shallow. Shallow protocols corre­ spond to DFAs where it is possible to determine the next state of the dialogue on the sole basis of the previous event. Of course, this is not always the case since it may be necessary to refer to the current state of the dialogue to determine the new state (think of two transitions with the same label leav­ ing two different states and leading to two different states). In principle, any automata-based protocol can be transformed into a protocol that is shallow in this sense (by simply renam­ ing any duplicate transitions). In fact, we have observed that many of the automata-based protocols proposed in the multia­ gent systems literature happen to be shallow already or could at least be made shallow by renaming only a small number of transitions.

Now suppose P1 , . .. , Pn are the dialogue moves of our communication language (including START and STOP). In the light of the above remarks, we will more generally trans­ late DFAs into two sets of rules ofthe form

where the righthand side of the rule defines the possible con­ tinuations wrt. the protocol after the input Pi (that we will sometimes refer to as the trigger of the rule). To ensure that this protocol is well-formed, we will require that the two sets of rules meet some requirements (R1-R5): there has to be at least one rule with START on the lefthand side in the protocol, and START may never occur on the righthand side (R1a, ini­ tial); there is at least one rule with STOP on the righthand side and STOP never occurs on the lefthand side (R 1 b, final) ; any dialogue move occurring on the righthand side ofthe first sub­ protocol also occurs on the lefthand side of the second one, and vice versa (R2, matching); every subprotocol includes the additional rule

to avoid concurrent moves (R3, non-concurrency); for each rule occurring in a subprotocol, if X is the receiver and Y the utterer of the dialogue move occurring on the lefthand side, it must be the case that X is the utterer and Y the receiver of every dialogue move occurring on the righthand side (R4, al­ ternating); all dialogue moves occurring on the lefthand side of the rules of each subprotocol are distinct from each other (R5, distinct triggers).

The meaning of each rule which appears in a protocol is intuitively clear: it specifies for any expected dialogue move the set of correct responses the agent may utter in reply. The following definitions make these notions more precise:

Definition 2 (Expected inputs) The set of expected inputs for an agent o: wrt. a protocol P is defined as:

Table 1: The continuous update protocol as a set of if-then-rules

Definition 3 (Correct responses) The set of correct re­ sponses for an agent a wrt. a protocol Panda dialogue move Pj is defined as:

Intuitively it is not sufficient for a dialogue move to be merely expected in order to be considered legal; it is also necessary that the move takes place at the right moment in the history of the dialogue. But note that it follows from the property of matching (R2) that the set of legal inputs for an agent at a certain stage of a dialogue is a subset of its expected inputs.

3 Levels of Conformance

Taking for granted that agents share the same language of communication, we are now going to define three different levels of conformance to a protocol. Note that we define these notioris on the basis of the observable conversational behaviour of the agents (i.e. what they utter) without making further assumptions on how they actually come to generate these utterances. We start with the notion of weak confor­ mance:

Definition 4 (Weak conformance) An agent is weakly con­ formant to a protocol P iff it never utters any illegal dialogue moves (wrt. P).

The following theorem shows that, in the context of our shal­ low protocols, the concept of legality is reducible to that of correctness, meaning that we can avoid to inspect the legality of the input and thus avoid to deal with the complete dialogue history.

Theorem 1 An agent that never utters an incorrect response in reply to an expected input of a shallow protocol Pis weakly conformant to P.

Proof. (sketch) For shallow protocols, the current dialogue state is uniquely identifiable given the latest move in the dialogue. Hence, the notions of correct response and legal move coincide, i.e. an agent that never utters an incorrect response will never choose an illegal continuation and will therefore be weakly conformant to the protocol. D

It is clear that any application governed by a protocol at least requires the level of weak conformance--otherwise it would not make sense to define a protocol in the first place. The notion of weak conformance captures that the agent does not utter any illegal moves, but does not actually require that the agent utters any dialogue move at all. For interactions where "silent moves" are undesirable, a stronger version of confor­ mance is usually required. We make this idea precise with the notion of exhaustive conformance:

Definition 5 (Exhaustive conformance) An agent is ex­ haustively conformant to a protocol P iff it is weakly con­ formant to P and it will utter at least one legal output move for any legal input ofP it receives.

Exhaustive conformance is certainly what is intuitively ex­ pected in most interactions-it is indeed often preferred to avoid considering silent moves as part of a protocol, at least to avoid confusion with lost messages. One may then argue that exhaustive conformance should be the minimum require­ ment for any interaction. We believe, however, it is worth making the distinction between weak and exhaustive confor­ mance. The first reason is that there are examples where the Jack of response can be considered to be part of the protocol. In such circumstances, it can be sufficient to design a weakly conformant agent, provided that silent moves will not have undesirable consequences. For instance, in a Dutch auction process "when there is no signal of acceptance from the other parties in the auction (other agents in the negotiation) the auc­ tioneer makes a new offer which he believes more acceptable (by reducing the price). Here, because of the convention (pro­ tocol) under which the auction operates, a lack of response is sufficient feedback for the auctioneer to infer a Jack of ac­ ceptance." [Jennings et al., 1998]. In this case, the agent can safely be designed to react appropriately only to the proposals it is ready to accept. But if we consider recent argumentation­ based protocols inspired by dialectical models it is sometimes assumed that "silence means consent" [Amgoud et al., 2000]. In this case, a lack of response can commit the receiver to some propositions-this is a typical case where it is crucial that agents are exhaustively conformant. The second reason for our distinction of weak and exhaustive conformance is that they are conceptually different since weak conformance only involves not uttering (any illegal moves), while exhaus­ tive conformance involves uttering (some legal move) . This implies substantially different approaches when the issues of checking and enforcing conformance are raised, as we shall see below.

Another important problem of agent communication is the need to deal with illegal incoming messages, and to react ap­ propriately to recover from such violations. For instance, any FIPA-compliant communicative agent has to integrate a per­ formative not-understood as part of its language [FIPA, 2002]. This motivates us to introduce the following notion of robust conformance:

Definition 6 (Robust conformance) An agent is robustly conformant to a protocol P iff it is exhaustively conformant to P and for any illegal input move it will utter a special dia­ logue move (such as not-understood).

Robust conformance goes a step further than exhaustive con­ formance since it requires that an appropriate response is ut­ tered also in reply to illegal moves. Technically, this neces­ sitates that the agent is able to identifY the legality of an in­ coming dialogue move, i.e. it needs to be able to check con­ formance wrt. the other agent's subprotocol.

Note also that in the case where all agents in the society are known to be weakly conformant, it is theoretically un­ necessary to deal with robust conformance (since no agent will ever utter an illegal move). Such an assumption would, however, somewhat contradict the "spirit" of an open soci­ ety. We should also point out that in dialogues with a very high contingent of illegal utterances the additional not­ understood moves may in fact burden communication channels unnecessarily and simply ignoring illegal moves would in fact be a better strategy.

4 Logic-based Agents

We are now going to consider the case of a specific class of agents based on abductive logic programming that have re­ cently been used in the context of negotiation scenarios [Sadri eta/., 200 1]. The communication strategy S of such an agent (which forms part of its so-called knowledge base K) is repre­ sented as a set of integrity constraints of the following form:

On receiving dialogue move P at time T, an agent imple­ menting this rule would utter P' at time T + 1, provided con­ dition C is entailed by its (private) knowledge base. Again, variables are understood to be implicitly quantified in the same way as our protocol-rules.

4.1 Checking Conformance

There are different ways of checking conformance. One way is to check conformance on-the-fly, i.e. to check step by step that every dialogue move uttered by an agent is conformant to the protocol. Another way-much more interesting when one has to design an agent to take part in an interaction-is to check conformance a priori, i.e. to check conformance by examining the specification of the agent rather than an actual dialogue. In general, this is a difficult task, because (i) the behaviour of the agent depends on some hardly tractable no­ tions (e.g .. beliefs and intentions), and (ii) conformance may depend on the history of the dialogue. We are now going to discuss some simple sufficient conditions for weak confor­ mance (in the context of the logic-based agents introduced earlier) that may be checked a priori.

To begin with, we introduce the notion of response space. Intuitively, the response space of an agent specifies the possi­ ble moves that the agent can make when using a given strat­ egy S, without considering the specific conditions relating to its private knowledge base.

Definition 7 (Response space) The response space of an agent with strategy S (henceforth noted S*) wrt. a commu­ nication language .C is defined as the following set:

That is, the response space is, essentially, the set of protocol­ constraints we get by first dropping all private conditions C and then conjoining implications with identical antecedents by collecting the corresponding consequents into a single dis­ junction. The reason why we define the disjunction of the empty set as j_ will become clear when we consider the next theorem, which offers a very simple way to check weak con­ formance a priori for a logic-based agent. In particular, it avoids dealing with the dialogue history, and it does not make any assumptions on the content of the agent's knowledge base (except to require that it is possible to extract the response space, as previously described).

Theorem 2 Let P be a protocol and let S* be the response space of an agent A wrt. the language .C of moves occurring in P . If S* I= P, then agent A is weakly conformant toP.

Proof Let S* be the response space of agent A wrt. the lan­ guage .C of protocol P. Then for every rule P =} P1 V · · · V Pn in P, S* will contain an implication P =} P{ v . .. V P:r, (with the same antecedent P)-and possibly a number of ad­ ditional implications for dialogue moves in the language .C that do not occur as triggers in P. (All the antecedents of the implications inS* are distinct.) Now supposeS* I= P holds. Observe that a formula of the form P =} P1 V · · · V Pn in P can only be the consequence of an implication in S* with the same antecedent P. But P =} P1 V · · · V Pn will only follow from P =} P{ V · · · V P:r, provided we have {P{, ... , P:r,} <;;;; {P1, . .. , Pn}·

In other words, whenever S* I= P holds, then S* will have the shape of a protocol that is a "syntactic restriction" of the protocol P, possibly together with a number of irrelevant rules (with triggers not present in P). Furthermore, by construction, any agent will be weakly conformant to the "protocol" represented by its response space. Hence, agent A will also be weakly conformant to P, because any dialogue continuation that would be legal wrt. S* would certainly have to be legal wrt. P. D

The opposite direction of Theorem 2 does not hold, because, looking at the form of strategies, it is clear that private con­ ditions may prevent the agent from uttering a particular dia­ logue move. In other words, it could be the case that S* f!= P but that the agent is still weakly conformant to P because of its specific knowledge base.

The same argument prevents us from having a theorem similar to Theorem 2 in the case of exhaustive conformance (and of course for robust conformance). Here we would have to look more precisely at how dialogue moves are actually being generated. The basic idea would be to check that, for every expected input in the protocol, the disjunction of the conditions C related to this move in the agent's strategy is entailed by the agent's knowledge base.

4.2 Enforcing conformance

Even when Theorem 2 is not applicable and an agent cannot be proven to be weakly conformant a priori, it is still pos­ sible to constrain the agent's behaviour in such a way as to simply prevent it from uttering illegal moves. The problem of enforcing conformance (referred to as regimentation by Jones

tell( X, a, inform(P) , D, T) 1\ -friend( a, X) tell( X , a, inform(P) , T) /\ friend( a, X) tell(X, a, ack, D, T) tell( X, a, question(P), T) /\friend( a, X) tell( X, a, end, D , T) tell( X, a, inform(P) , D , T) 1\ enemy( a, X) tell( X, a, inform(P) , D , T) /\ friend( a, X) =? tell(a, X, end,D ,T+l) =? tell(a, X,ack,D,T+l) =? tell(a,X,ack,D,T+l) =? tell( a, X , inform(P) , D, T+l) =? STOP(a,X, D,T+l) =? tell(a, X ,end, D,T+l) =? tell(a,X,ack,D,T+l) s, { s, l tell( X, a, inform(P) , D, T) 1\ -friend( a, X) 1\ -.enemy( a, X) tell( X, a, ack, D, T) =? tell(a,X,challenge(P),D,T+l) =? tell(a ,X,ack, D ,T+l) tell( X, a, challenge( F), D, T) tell( X , a, end, D , T) =? tell( a, X , end, D , T+l) =? STOP( a, X, D, T+l)

and Sergot [1993]) is then to try to find easy (and hopefully automatic) ways to ensure that an agent will always be con­ formant to a given protocol.

We will now show how a simple filtering function may be defined in the context of our logic-based agents. Since this relies on the concrete behaviour of our agents, this re­ quires some details about the operational model which un­ derlies these agents. By a generated response we now mean a response produced by the abductive IFF proof procedure of Fung and Kowalski [ 1997]. In our case, the abducibles are the dialogue move(s) that the agent will actually generate as the consequence of the observation of another agent's dialogue move (see [Sadri eta/., 2002] for details).

Theorem 3 An agent generating its dialogue moves wrt. the knowledge base K UP will be weakly conformant to P.

Proof (sketch) Let us assume that P(T) is a legal input (wrt. protocol P) that our agent receives, and that P' (T + 1) is a move generated as a response by the agent. Since the move is legal, it is expected in P. The proof procedure will produce a tree and each branch of this tree will have one of the correct responses Pi (T + 1) together with the constraints of the dialogue strategy and the additional condition of non­ concurrency (R3). Now if P' ( T + 1) is a generated response of the proof procedure, P' (T + 1) must also be a conjunct on one of these branches. But such a branch will evaluate to false if P' (T + 1) =f. Pi (T + 1), precisely because of the condition of non-concurrency. This means that the procedure will never generate an incorrect response. Therefore, by Theorem 1, our agent will be weakly conformant to P. D

Thus the filtering function is provided by the protocol itself. This result has very practical consequences. For instance, be­ fore entering an interaction, an agent can ensure its weak con­ formance to the public protocol which regulates the interac­ tion (and thereby avoid possible penalties imposed by soci­ ety), by adding the protocol to its own knowledge base. Now, while we can prevent an agent from uttering illegal dialogue moves, it is difficult to see how we could force it to utter some dialogue move (exhaustive conformance) without con­ sidering its private knowledge base and modifying its private strategy. We therefore believe that exhaustive conformance cannot be enforced automatically and should ideally be en­ sured during the specification of the agent by the designer.

Note that this filtering function will not block correct re­ sponses generated by the agent, unless two or more moves are being generated at the same time. This is again due to the non-concurrency condition (R3).

We should also point out that it is possible that an agent with knowledge base K would not utter any dialogue move given a particular input P(T) , while an agent with knowl­ edge base K U P (i.e. the same agent after "downloading" the protocol P) would utter a (legal) move. This may, for in­ stance, be the case if P(T) never occurs on the lefthand side in the agent's original strategy and P includes a "determinis­ tic" protocol rule such as P(T) =? P'(T+1). Ifthis type of behaviour is not intended, we have to ensure that the commu­ nication languages of the agent and the protocol match (for instance, by adding the constraint P(T) =? _i_ to the agent's strategy for every move P that is an expected input in P).

4.3 Examples

We are now going to illustrate some of the points made ear­ lier by means of example. Consider again the continuous up­ date protocol of Table 1, and more specifically subprotocol PB. The set of constraints given in Table 2 represents two possible strategies for an agent a. Here, the ..,-operator is understood as negation as failure. We assume that the pred­ icates friend and enemy are fully defined in the knowledge base of our agent (that is, it can determine whether or not an agent X is a friend or an enemy), and we also assume that an integrity constraint stipulates that it is not possible to be at the same time friend and enemy of the same agent (friend( a, X)/\ enemy( a, X) =?_l_).

Dialogue strategy S1 relies upon the commu­ nication language £ 1 which is based on the set {inform(P), question(P), ack, end}. It is interesting to note that no rule can be triggered after a question about P if it is the case that the agent a does not consider X as a friend. However, the agent a is still weakly and exhaustively conformant to PB since this move can never be legally uttered within the protocol P by its partner (it is not a legal input for subprotocol PB).

Next consider dialogue strategy S2, which relies upon the communication language £ 2 based on the set {inform(P), challenge(P), ack, end}. Agent a is not weakly conformant to PB since, in some situations (namely, when it does not consider X as friend, neither as an enemy), it may want to challenge the initiator X. This move is not expected in the protocol P A. If the agent a decides to enforce weak conformance as described earlier in Theorem 3, it will remain si lent in the situation previously described.

Finally, let us consider an agent with the response space { P =? ..L I P E .C}, that is, an agent that never utters any dialogue moves at all. It is clear that such an agent will be weakly conformant to any protocol. This certainly suggests that the notion of conformance alone is not sufficient to eval­ uate how well an agent is adapted to a protocol.

Another application of the notion of response space could be to assess how well an agent can explore a given protocol beyond the minimal requirement of being able to conform to it. Intuitively, given a protocol P, we would expect a "compe­ tent" agent to have a response space that (almost) "covers" P, namely it has the potential to utter as many dialogue moves as the protocol allows. This would offer a notion complemen­ tary to that of conformance.

Note also that none of the agents discussed here is robustly conformant. One of the reasons for this latter remark is the fact that these agents cannot notice that the dialogue move they receive is not legal if it is an expected input (for in­ stance if their partner starts the dialogue with an ack). They would consequently react "appropriately" to these moves­ which can be quite confusing.

5 Conclusion

This paper has introduced different levels of conformance as basic notions to check and enforce that the behaviour of an agent is adapted to a public protocol regulating the interaction in a multiagent system. These notions have been explored in the context of the logic-based agents of Sadri et a!. [200 1]. Our approach starts from on an alternative representation for­ malism for communication protocols based on if-then-rules for the kinds of protocols that can be represented as DFAs. In particular, we argue that it is typically not necessary to con­ sider the history of the dialogue besides the previous move to determine the possible legal dialogue continuations (shallow­ ness). This allows us to show that a sufficient condition for an agent to be weakly conformant is to never give an incorrect response in reply to an expected input. In the context oflogic­ based agents we have used this result to propose a simple way to check a sufficient condition for weak conformance, which has the great advantage of ignoring the conditions related to the (private) knowledge base (by identifying an agent's re­ sponse space), and avoids to consider the dialogue history. We have then shown how the concrete behaviour of the IFF proof procedure can be used to define a regimentation policy to enforce weak conformance. Finally, we have illustrated these notions and their limitations by means of examples.

A number of results have previously been obtained in the context of agents based on abductive logic program­ ming, e.g. the termination of certain types of negotiation di­ alogues [Sadri eta!., 2001]. On the one hand, because we mostly ignore the details of the knowledge bases of agents and do not restrict ourselves to any specific protocol here, we cannot obtain such strong results. On the other hand, our work provides more general tools for logic-based agents com­ municating by means of (various) public protocols.

The work presented here can be extended in a number of ways. In particular, we only deal with very specific kinds of dialogues (although they can be generated by a wide range of protocols). Amongst other things, we plan to explore whether our formalism is expressive enough to capture more com­ plex dialogues, such as those taking place between more than two agents or those not representable using DFAs (e.g. dia­ logues where concurrency is allowed or where checking con­ formance requires reference to the content of a dialogue move rather than just the communicative act itself).

Acknowledgements. We would like to thank the IJCAI ref­ erees for their helpful comments. This research has been funded by the European Union as part of the SOCS project (Societies OfComputeeS), IST-2001-32530.