A Protocol-Based Semantics for an Agent Communication Language

1 Introduction

The growing ease of network connectivity of comput­ ers provided the enabling technology for the agent paradigm. From the computing perspective, agents are autonomous, asynchronous, communicative, distributed and possibly mobile processes. From the AI perspec­ tive, they are communicative, intelligent, rational, and possibly intentional entities.

The common feature of communication has deter­ mined that some kind of message passing between agents is required. To provide inter-operability between het­ erogeneous agents, a commonly understood agent com­ munication language (ACL) is used: examples include KQML [Finin et al., 1995], Arcol [Breiter and Sadek, 1996], and FIPA's ACL [FIPA, 1997] . To ensure that it is commonly understood, a formal semantics for the ACL is required. From the AI perspective, the semantics has typically been characterised in terms of speech act theory and framed in terms of the intentional stance, i.e. mentalistic notions such as beliefs, desires and intentions [Cohen and Levesque, 1995; Breiter and Sadek, 1996; FIPA, 1997].

An intentional formalisation of an ACL semantics of­ ten involves the axiomatisation of the felicity condi­ tions of Searle and the conversational maxims of Grice. Grice's analysis of conversational implicatures was un­ derpinned by the sincerity condition to support the co-operativity principle. For agents to converse co­ operatively (e.g. for negotiation, co-ordination, etc.), the sincerity condition is a reasonable requirement, but is often hard-wired into the semantics as a feasibility pre­ condition on performing a simple speech act, e.g. KQML tell and FIPA inform. Thus an agent believes what it says and only says what it believes.

However, by defining the meaning of a performative in isolation through an axiomatisation that implicitly ex­ pects the performative to be used in conversation, there is a risk of being exclusive. In isolation, we could moti­ vate the behaviour of a sincere agent by the axiom:

Here B, D and I are respectively the beliefs , desires (goals) and intends modalities, and DONE is an oper­ ator on actions. This axiom therefore states that if the agent s believed ¢ and wanted another agent r to believe ¢, then s would generate the intention to inform r of ¢ , after which action r may also come to believe ¢. Alter­ natively we could define the behaviour of a 'rapacious' agent by the axiom:

This axiom states that if s desires (wants) 1/J and believes that doing A will achieve 1/J then s will intend to do A. If 1/J = Br¢, the same communication occurs (A is < s, inform(r, ¢) >),without shaving an explicitly held belief in¢.

Any formalisation of communication based on the mental states of the participants must deal with what is fundamentally a process of revision and updating of those states. It is unlikely that a single set of axioms will cover all eventualities because communication is in­ herently context-dependent. What works in one appli­ cation may be inappropriate in another. Furthermore, intentionality is concerned with agent internals and a communicative act is an external phenomenon: mental attitudes can only give a possible reason for and not the definitive meaning of the performative. Therefore there are considerable limitations of intentionality as a basis for defining the semantics of an ACL (cf. [Singh, 1998]).

This paper develops an alternative semantic frame­ work for an ACL from the computing perspective, with an emphasis on protocols. Mental attitudes are used now to link what an agent 'thinks ' about the message content to what it 'does' in response to receiving that message.

2 A Layered Semantics

Consider the situation illustrated in Figure 1. It shows two agents, each embedded in an environment, which partially overlap. However, rather than communicating by changing the environments, they can communicate by using speech acts and the ACL protocols.

Environment

Figure 1: Communicating Agents

We identify three layers of semantics here:

• The content level semantics, which is concerned with interpreting and understanding the content of a message, and is internal to an agent;
• u The action level semantics, which is concerned with replying in appropriate ways to received messages, and is · external to the agents;
• 111 The intentional semantics, which is concerned with making a communication in the first place, and with replying, and again is internal to the agent.

We would argue that the current FIPA ACL semantics for example, is level 3, and because it is internal to an agent, its usefulness in standardisation has been ques­ tioned [Wooldridge, 1998; Singh, 1998]. The only part of the communication that is amenable to standardis­ ation is the observable tip of the iceberg: namely the communication itself. Note that this properly includes ontologies, so that there may be a standard interpreta­ tion, but the actual interpretation of the content of the message is once again internal to the agent.

3 Generic Semantics for Performatives

We define a standard semantics for performatives by an input-output relationship at the action level (level (ii) above). We define the meaning of a speech act (as in­ put) as the intention to perform another speech act (as output). In computing this functional relationship we can take into account the agent's mental state, without proscribing. that state or how it should be implemented.

We base the relationship on how the object-level con­ tent of a message induces a change in the information state of the receiver, and how the meta-level action de­ scriptor of a message (the performative itself) induces a response from the receiver. Our proposal is that the semantics of performatives can be characterised in these terms, and that this is the semantics that should be spec­ ified for a standard agent communication language. This means specifying, for the content, what it 'means ' for an agent (receiving a message) to add its interpretation of that content to its current information state; and for the speech act, the space of possible responses an agent may make, one of which it is committed to make.

For the specification that follows in this section, let c and u be sets of integers , and let b. , contenLmeanings, and speech_acts be, respectively, possibly infinite sets of agent information states, the agent 's interpretation of the content of a message, and speech acts .

An ACL is defined by a 3-tuple < Perf, Prot , reply> where Perf is a set of perfomative names, Prot is a set of protocol names, and reply is a partial function given by:

For the FIPA ACL, for example, Perf would be the set of all FIPA ACL performatives, and Prot would be the set of all FIPA ACL protocols, used for negotiations, calls-for-proposals, etc., for example:

Note we include a null performative which is a 'do nothing' (no reply) performative (cf. silence as used in Smith et al. [1998]), and require an empty protocol no_protocol: agents can communicate using one-shot speech acts irrespective of a particular protocol.

Each element of Prot names a finite state diagram. Then reply is a (partial) function from performatives , protocols and protocol states to the power set of per­ formatives . This states for each perfomative, 'uttered' in the context of a conversation following a specific pro­ tocol, what performatives are acceptable replies. The reply function can be constructed from inspection of the protocol state diagrams, and vice versa, although more formal characterizations are possible (e.g. [Kuwahara et al., 1995]).

This 3-tuple is standard for all agents using the ACL. To fully characterise the semantics, we need three further functions which are relative to an agent a, and specify what an agent does with a message, not how it does it:

adda :

selecta :

conva :

Perf x Prot x contenLmeanings x b. -t b.

p(Perf) x b. -t speech_acts

cr-+u

Here, add a is agent a's own procedure for computing the change in its information state from the content of an in­ coming message using a particular performative 'uttered' in the context of a particular protocol. add a then con­ verts a's (a-type) information state into a new (a-type) information state. selecta is agent a's own procedure for selecting a performative from a set of performatives (valid replies) , and from its current information state generating a complete speech act for this performative which will be its (intended) reply. Finally, we require that agents keep track of the state of each conversation in which it is involved, and uniquely identify each conver­ sation with some identifier, i.e. an agent may be involved in more than one conversation and uses the identifier to distinguish between them. conv a then maps a conversa­ tion identifier onto the current state of the protocol be­ ing used to conduct the conversation. (Note that FIPA ACL has message attributes (reply-with, in-reply-to and conversation-id) to serve such purposes, but they are not accommodated in the formal semantics.)

An agents communicates with (and communicates in­ formation to) an agent r via a speech act. This is repre­ sented by:

This is saying that s does (communicates with) perfor­ mative perf with content C in language L using ontology 0, in the context of a conversation identified by i which is following protocol p, at the time of sending tsnd.

Define a function f which for any speech act sa returns the performative used in that speech act. The meaning of a speech act is then given by:

This defines the meaning of the speech act by sender s to be an intention of receiving agent r to per­ form some other speech act. The performative used in the speech act as the response is selected from reply(perf ,p, convr(i)), i.e. it is constrained to be one of the performatives allowed by the protocol. The speech act is generated from r's information state at the time of selection ~r,t"""' and the state of the conversation i according to the protocol p, using r's selectr function:

This states that r's information state after receiving the message is the result of adding, using r's own procedure addr, r's own interpretation (content meaning) of the content C in language L using ontology 0 to its database at the time of receipt, ~r,t,.,".

Note that for a speech act performed as part of a conversation identified by i, both sending and receiv­ ing agents are expected to update their respective conv mapping from conversation identifiers to current state (as defined by the protocol). The sending agent will do this on performing the speech act, the receiving agent after creating the intention to reply. This means that after a message has been sent and before it has been processed, the two parties of the conversation will (for a while) be in different states, and this can be useful in error recovery as a result of lost messages, for example.

It is possible, with a little care, to describe FIPA ACL as a 3-tuple as defined above. FIPA ACL has a small set of basic performatives and just a few protocols, most with fewer than 10 states. However, more work is re­ quired for protocols where there are more than two par­ ticipants, the sequence of speech acts is not simple turn­ taking, there are timing constraints which affect allow­ able replies, and so on. It may also be that a protocol, if not infinite, may nevertheless have a 'very large' number of states. Therefore a further generalisation of the speci­ fication may be required, by defining rules for generating speech acts between two players (i.e. a game).

To summarise, all agents should react to a speech act, and we try to constrain and predict the possible reactions with protocols. These, we argue, are the normative stan­ dard items: what an agent can do, not how it does it. adda and selecta are specifying what agent a should do, not how it should do it. However, even if an ACL with a standard external semantics can be agreed, it is unlikely to be testable as the agents are complex entities. It does impose a requirement that agents involved in a conver­ sation behave according to a protocol, but 'anti-social' behaviour may not be immediately obvious and the his­ tory of communications needs logging, and a means of auditing, policing and accountability is required. Stan­ dardising the protocols alone will not achieve this.

4 The Proper Role of Belief States

We have seen how an agent's information state (belief state) can be used to guide the selection of a response to a message, and this formed the core of our proposed semantics for the ACL. This would be a normative spec­ ification. How then do agents ·choose which speech acts to perform in the first place? It is in answer to this question that speech act theory, as originally conceived, and agent belief states, can contribute to an informative specification. We specify adda and selecta with respect to beliefs, desires and intentions, i.e. by giving an inten­ tional semantics at level (iii) of Section 2.

For example, reconsider our 'sincerity' axiom:

The 'logical operation' of this axiom is closely related to the BDI agent architecture of Kinny et al. [1995], where the combination of beliefs and desires trigger intentions. As an informative specification, it guides agent develop­ ers as to the circumstances under which inform speech acts could (or should) be performed, but does not con­ strain them to use BDI architectures.

We then provide, as an informative specification, that:

which is to say that the basic intuition behind receiving, from a sincere agent, an inform message not in the con­ text of any protocol, is just to add the content to the agent's information state. However, the implementation of adda for a particular agent a need not be so trusting, also it could do 'its own thing' in dealing with additional inferential effects, inconsistency, multiple sources of in­ formation, belief revision (non-monotonic logic) , copies of¢ (resource logics), and so on.

We illustrate this idea in the next section. We con­ clude this section with the observation that the extent to which agents wish to expose their behaviour by pub­ licising their add and select functions , also defines the extent to which this behaviour can be verified. Other­ wise, all that is required, to be compliant to a standard, for example, is that an agent should make an appropri­ ate response to a particular input, as given by the reply function , and this can be verified with relative ease.

5 A BDI Implementation

In this section, we discuss an operational model of the BDI agent architecture as suggested in [Kinny et al., 1995], enhanced to accommodate BDI-reasoning about agent- agent communication protocols based on the se­ mantics described in the previous section.

5.1 The BDI Architecture

Kinny et al. 's [1995] BDI-agent architecture consists of the modules illustrated in Figure 2. Here, the belief database contains facts about 'the world'; the desires module contains goals to be realized; the plan library consists of plans, which are sequences of actions which achieve goals; and the intention structures contains in­ stances of those plans chosen for execution (and cur­ rently being executed). The interpreter executes inten­ tions, updates beliefs, modifies goals, and chooses plans.

The interpreter execution cycle is as follows: At timet: certain goals are established, and certain beliefs are held. Event(s) occur that alter the beliefs or modify goals, and the new combination of goals and beliefs trigger ac­ tion plans. One or more action plans are selected and placed on the intention structures. An executable plan is selected and one step is executed, whereby the agent performs the action. Performing the action changes the environment and may establish new goals and beliefs, and so the interpreter execution cycle starts again.

We now describe how we envisaged the BDI architec­ ture working in conjunction with the ACL semantics, for a pair of communicating agents.

5.2 A Semantic Specification

Consider again the communicating agents in Figure 1. Suppose they are telling each other when they have changed something in the environment in which they are embedded. To ensure that their perceptions of the envi­ ronment are aligned, they will use a mutually agreed protocol, called datasync. This protocol is illustrated as a finite state diagram in Figure 3.

The idea is for one agent to inform the other agent of changes in the environment, and for this other agent to agree the change (via the acknowledge speech act ack) , or correct it via another inform speech act .

We can formalise this as part of our ACL semantics as follows , by specifying, inter alia:

The reply function therefore specifies the acceptable replies to messages sent in the context of the datasync protocol. The protocol is initiated by an inform message, and terminated (with success) by an ack message.

Ignoring for now issues like language, time, ontology and protocol, an agent designer could specify an agent a's behaviour for reacting to an inform message with con­ tent ¢ from an agent s using the datasync protocol to be:

This is only an exemplary specification in a semi­ formal notation. Note the formula ¢c denotes the com­ plement of formula ¢. It treats each of the three cases: when the content of the inform is already known, new, or contradictory. The function belief_revisea is a gloss on a's belief revision for contradictory statements ( cf. [Gal­ Hers, 1992]) , and we are not saying how the agent ensures its database is consistent (but there are algorithms for doing this, e.g. forward chaining) .

This intentional reading of informing agent a of some information can be paraphrased informally as follows (where all replies are intuitively intentions, to be con­ sistent with the ACL semantics):

• If you tell me something I already know, then I'll stay as I am;

If you tell me something I don't know, then

if it is consistent with my database ~'

I 'll add it to ~ and acknowledge it

else if it is inconsistent with ~

I'll inform you that I disagree;

If you tell me something that I disagree with, then

if I prefer your version,

I'll revise ~ and acknowledge it

else if I prefer my version

I 'll keep ~ as it is and inform you otherwise

This is of course just one formulation: the treatment of new and contradictory information may not be treated in the same way, for example. It is also easy to refine such a specification to incorporate elements of trust. Fur­ thermore, since the sincerity condition is predicated on the notion of co-operation; and all speech acts involve the receiver recognizing an intention on the part of the sender, agents are free (but not forced) to make further inferences about the other agent's beliefs and intentions. Different inferences may be more appropriate for partic­ ular types of agents in different kinds of application.

However , we can now appreciate the potential utility of intentionality for individual agents: indeed, we can even imagine 'publishing' this behavioural interface in an open system. It then becomes effectively a social commitment on the receiving agent's part (cf. [Singh, 1998]). The intriguing possibility then is that the 'stan­ dard' behaviour (sought by the FIPA97 specification) could actually be an emergent property of the system. For now, we show how this specification operates in the communicating agents example of section 2, where each agent is (at least specified as) a BDI agent.

5.3 The Semantics in Operation

In the plan library, we posit plan axiom schema of two types, which we call proactive and reactive. The two types of plan both generate intentions. The first type is the type of plan schema that triggers a dialogue, with the agent as the initiator of that dialogue. The second type is the plan schema that an agent uses to reply to messages that have been received, determining, for ex­ ample, if there were a protocol, which possible responses would conform to the protocol.

We suppose that both agents have plan axiom schema in the plan library, which for agent a (where a could be senders or receiver r, although it need not be the same for both) are:

The first plan axiom schema is proactive and states that if agent a believes ¢ and has the goal that another agent R share that belief (the preconditions for action), then agent a will form the intention to inform R of¢, using the datasync protocol. The other two plan axiom schema are reactive and determine replies. The former states that after some agent R has informed agent a of some infor­ mation ¢, if agent a believes the proposition and wants the original sender to believe this, then it will form an intention to reply with an acknowledgement. Similarly, if the informed agent disagrees with the content it will inform the originator of this. It should be clear that the latter two axioms specify the decision making for re­ sponse making in the datasync protocol if adda has been implemented as described above.

We now logically animate this specification for a send­ ing and a receiving agent. For the sending agent s, in its belief database there are facts, such as p (implicitly B.p), and modal action schema. These state the beliefs that an agent will have after performing an action. For example, for agent s, we could have:

Here R and ¢ are any agerit and formula respectively. The post-condition of the modal action schema specifies the intended rational effect of the action which the agent will believe after doing the action (if the agent later dis­ covers it is not true, it will need to do belief revision). This formula concerns the inform performative, irrespec­ tive of the protocol it is used in.

In the desire database, there are goals. For example, if the goal of s is for r to believe p, we have Ds : BrP·

Beliefs and desires are used to trigger a plan action schema and create instances which will be executable plans. In the case of s, the following simple plan will be placed on the intention structures:

When the intention is chosen for execution by the inter­ preter, the intention is fulfilled, the belief state changes according to the appropriate instance of the action axiom schema, i.e. [s , inform(r, p)]Brp, the goal is discharged and withdrawn from the desire database, so we end up, in this case, with:

This is the situation with agent s. For agent r, who receives the message, the database prior to receipt might have been entirely empty:

Now it receives the message< s, inform(r, p, datasync) >. The interpreter of r runs its procedure addr on this input and this database; being a new conversation, the proto­ col state is 0. If addr is implemented as specified above, then r will add p to its belief database (p is not present and adding it is consistent), and generate the goal for the sender to believe that it believes it:

From the reactive plan axiom schema in the plan li­ brary, after an inform r will have the intention to send an acknowledge or an inform. The BDI interpreter is effectively applying the selectr function, and as with the sending agent beliefs and desires are used to trigger a plan action schema and create instances which will be executable plans. The appropriate intention is placed on the intention structures:

Now we see that the meaning of the speech act is indeed the intention to reply with a valid performative in the context of a protocol , as specified in sections 3 and 4.

6 Conclusions and Further Work

With growing investment in open, agent-based system design and deployment , there is a need for software stan­ dards defining the interface between agents. The FIPA standardisation body is probably the most important re­ cent development in the agents field and offers significant potential advantages for developers of open, heteroge­ neous, and interoperable agent systems.

However, there are considerable limitations of using mental attitudes for standardising the semantics of the ACL [Singh, 1998]. Intentionality is concerned with agent internals and a communicative act is an exter­ nal phenomenon: mental attitudes only give a reason for and not the meaning of the performatives. They can give guidance to developers but may be too strong a con­ straint for heterogenous agents in varying applications.

The protocols specified by FIPA can give purpose and meaning to individual performatives but only in the con­ text of a conversation that has an identifiable objec­ tive. However , there appears to be a growing consen­ sus that conversations, protocols, and social context are the important factors to consider in defining an ACL's formal semantics [Singh, 1998; Labrou and Finin, 1998; Smith et at., 1998].

Our own experience of applying the FIPA specifica­ tions suggests that interactions in a multi-agent system could be designed on the basis of the standard perfor­ matives and protocols . This work has gone one step further and formalised the normative use of performa­ tives in specific protocols. Furthermore, the relationship between what an agent 'thinks' about the content of a message to what it 'does' in response to receiving that message is formalised through informative specifications expressed in terms of beliefs, desires and intentions.

The semantic framework described here actually de­ fines a class of ACLs. The challenges ahead then include: extending an ACL specification with new protocols and performatives, and customising with intentional specifi­ cations for particular applications; describing conversa­ tion states by structures which are affected by speech acts; allowing for multi-party conversations; identifying a way for agents to publicise thier understanding and use of new performatives and protocols (so-called brown pages); and providing a mechanism for agents to discover and learn a new dialect . The issues of social behaviour and time also need to be addressed as these are both sig­ nificant factors in why and when agents communicate.

In the meantime, we have submitted this work to FIPA as a proposal for the ACL semantics in FIPA99.

Acknowledgements

This research has been undertaken in the context of the UK EPSRC/Nortel Networks joint funded project CAS­ BAh (GR/L34440) and the EU funded ACTS project MARINER (AC333). We are grateful for the construc­ tive comments of the anonymous reviewers.