Constitutive Rules for Agent Communication Languages

1 Introduction

We maintain that there is a distinct conceptual and functional difference between communication using an ACL (Agent Communication Language) and communi­ cation using an API (Application Programmer Inter­ face) . Method invocation (via an API) is essentially per­ locutionary, that is, the 'speech act' (the method call) is completely definable in terms of its perlocutionary effect , i.e. the further consequences or effects on the receiving (remote) object. This property makes method invoca­ tion practical for client-server distributed systems, be­ cause the execution of the remote method is transparent to the (local) caller- the data and methods of the called object may just as easily have been on the same machine as on another connected to the network. It also explains why the call semantics is so important: the fundamental difference between idempotent and at-most-once call se­ mantics is whether or not the server is maintaining state. The communicating language itself is just a conventional device for securing a natural response.

However, according to Searle's institutional theory of communication [Searle, 1969], speaking a language is to engage in a rule-governed form of behaviour. The seman­ tic structure of the language is given by a conventional characterisation of sets of constitutive rules, and 'speech acts' are acts typically performed by uttering an expres­ sion in accordance with those rules. Thus the basic unit of communication is the illocutionary act , which com­ prises the type of the act (its illocutionary force: stating, ordering, promising, etc.) and its propositional content. The meaning of each unit is given by the constitut ive rules: these are rules that both define the forms of be­ haviour and determine what that behaviour counts as. Searle contended that it was not possible to reduce the analysis of illocutionary acts to perlocutionary effects. Therefore there is a significant difference between agent communication and object invocation: the aim of this paper is to make that difference clear and suggest how to leverage it for computational advantage.

In [Searle, 1969], the characterisation of the consti­ tutive rules (in particular the preparatory and sincerity conditions) was expressed in terms of intentional states. While justifiable for natural language communication be­ tween humans, we believe that this is inappropriate for open systems of electronic agents and has misdirected standardisation efforts, e.g. FIPA (the Foundation for Intelligent Physical Agents). However, we believe that the conventional and institutional nature of communi­ cation can still be used to specify constitutive rules of interaction for such artificial systems.

The argument advanced in this paper to support that belief is as follows. Section 2 gives some preliminaries, introducing our methodology and notation. Section 3 gives some illustrative examples to motivate the speci­ fication, in Section 4, of some basic 'standard' commu­ nicative acts, and in Section 5 of a richer form of com­ munication for conversations. Section 6 concludes with a summary, a brief review of further and related work, and draws some conclusions. In particular, the emphasis on the institutional perspective of Speech Act theory, rather than on agents' beliefs, desires, or intentions, indicates that a new paradigm in designing agent communication languages offers significant computational advantages.

2 Preliminaries

In this section, we briefly describe our methodological motivation for applying the ideas of Speech Act Theory to agent communication. We then describe the notation used in the rest of the paper, in particular, the abstract representation of agents and normative relations (in par­ ticular institutional power, permission and obligation) .

2.1 Methodology

We operate on the assumption that there are aspects of human intelligence and society than can inform algo­ rithms, architectures and data structures for the design and implementation of 'better' solutions to software en­ gineering problems. The process begins with the analy­ sis of human intelligence and the expression of a theory (the process of theory formation in philosophy, psychol­ ogy, linguistics, etc. We don't presume to undertake this step ourselves). The next step is a process we might call reification: the specification of that theory in a formal language. There are two problems with this process: firstly, information loss, as parts of the theory which are intractable are eliminated; and secondly, complexity gain, as there may be theoretical assumptions which are easy to state but much harder to formalise. As a conse­ quence, the reified theory, or specification, is not a direct representation or literal specification of the original: in­ stead it has been inspired by that theory.

The process is marked in this paper. We have been analysing both Speech Act Theory [Searle, 1969], Insti­ tutional Power [Jones and Sergot, 1996], and Conven­ tional Signalling systems [Jones, 2003] . The resulting specification of - or rather, proposal for a way of specif­ ing - an agent communication language owes something to both accounts of communication (in particular, we will refer to signals and agent's signalling actions, rather than speech acts) but also looks to the extant computer implementations described in [Artikis et al., 2002]. (Such implementation of the specification is step three of our methodology, while step four is to embed that implemen­ tation back in the human context in which it originated.)

2.2 Notation: Agent Description

We assume a domain with distinguished agents a, b, etc., facts (propositions) ¢, and actions (procedures) 1r. An agent is a triple comprising (K, G, P), respectively the agent's knowledge base, goal base, and planned actions. For an individual agent a, we write:

b..a

b..a 1- ¢

b..a ""'-" ¢

b..a ~---+ 7r represents the program state of agent a, which encapsulates the agent's deliberative state;

a's current program state (knowl­ edge base) proves ¢ ( ¢ E K);

a's current program state plans that in some future program state b..a 1- ¢ (currently¢ E G);

a's program state plans action 7r (not necessarily that a plans to do 1r itself) (1r E P);

T(b..a, 1r) = 6.~ denotes a transition of a's pro­ gram state as a consequence of action 1r being performed.

Intuitively, b..a 1- ¢ can be thought of, if it is preferred, as agent a believes ¢ is true). We write b.. a 1- ( b..b 1- ¢) to denote an actual 'belief' of a itself concerning the pro­ gram state of b, which can be true (in a) independently of whether b..b 1- ¢or b..b 1- ·¢. b..a ""'-" ¢is an abstraction covering a future state of a, which may be thought of as a goal to achieve ¢ (say), and b..a ~---+ 1r is an abstraction for a plan to execute action 1r, either to be done itself or by another agent.

Note that , in a transition T(b..a, 1r) to 6.~, if a per­ formed 1r, we require that b..a ~---+ 1r and would normally expect that 6.~ ~ 1r (i.e. we are not concerned with 'accidents': we are concerned with planned, purposeful action). If b.. a 1- · ¢ and after (doing) 1r, ¢ is the case, we assume there is some process of belief revision which ensures that after the transition T(b..a, 1r), 6.~ 1- ¢ and not 6.~ 1- · ¢, i.e. that 6.~ is internally consistent.

2.3 Notation: 'Logical' Description

The characterisation of the constitutive rules for an agent communication language requires the representa­ tion of action, 'counts as' and institutional power [Jones and Sergot, 1996], and deontic relations. The notation used is as follows .

For an agent's actions, both signalling acts and (phys­ ical) acts on the environment , a relativised (to agents) £ operator is used (note that 1r here is the proposition that 7r happened):

Ea¢ a sees to it that ¢ is true

Ea7r a sees to it that 7r is performed

For reasons illustrated in the first example of the next section, we also introduce a second relativised action op­ erator C, for the idea of 'capability to verify', with intu­ itive reading (we consider the formal reading later):

Ca¢ means a is able to demonstrate (give evi­ dence) that ¢ (is true)

Ca 1r means a is able to demonstrate physical capability to perform 1r

Central to the [Jones, 2003] analysis of conventional signalling systems and the [Jones and Sergot, 1996] anal­ ysis of institutional power is the idea of counts as. The idea here is that one agent seeing to it that ¢, say, can count as, in certain contexts, as another agent - or even the institution itself - seeing to it that '1/J. This notion was formalised in [Jones and Sergot, 1996] with a rela­ tivised (to institutions) conditional connective ==>:

Such a formula is called an institutional power, whereby a seeing to it that ¢counts as (just as if) I sees to it that '1/J. This is used to formalise Searle's constitutive rules of the form "X counts as Y in context C", where Searle's context C will here be denoted by some institution I. We write:

to identify a 'named' power p denoting a specific counts as formula.

An agent a's permissions and obligations with respect to an institution I are represented by:

1PeraEa1r a is permitted to perform 7r in (by) I

IPeraEa¢ a is permitted to make¢ true in (by) I

IOblaEa7r a is obliged to (by) I to perform 7r

IOblaEa¢ a is obliged to (by) I that ¢ be true

3 Two Illustrative Examples

3.1 Example 1: TCP Slowstart

The standard TCP specification requires implementa­ tion of an algorithm called "slow start", documented in IETF RFC2001 (cf. [Stevens, 1996]) . The specification of the algorithm mandates that, on the sender's side, the first transmission consists of just one packet. If this is acknowledged successfully, then the sender can trans­ mit two packets. The sender then continues to increase the number of packets transmitted until the network ca­ pacity is reached (packets are not acknowledged success­ fully), and then throttles back. This ensures that no TCP sender overwhelms a network.

Let w be a Windows NT server, and let ¢ be the statement "I (w) implement TCP slow start algorithm as specified in IETF RFC2001 ". Let u be the signalling system (i.e. agent communication language) in which the signal ~ denotes ¢. Assume u is used for communication by institution IETF, represented by I, so that Ea~ is the action of transmitting the signal denoting ¢.

Now, suppose we want to allow agents, in particular servers (TCP senders), to assert or inform other agents that they implement the IETF (institution I) standard specifications. We also want I to be able to inspect and verify that servers do indeed implement the standard specifications correctly.

So, we can write 6-w 1-- ¢, meaning that, subjectively, from w 's perspective, ¢ is true ( w believes ¢). Sup­ pose then that w makes the assertion, in u that ¢. As per Searle ("Counts as an undertaking that [¢] repre­ sents an actual state of affairs" ([Searle, 1969]: p.66)) we want this to count as a commitment, in the context of the institution I, that it implements the slow start algorithm correctly. We interpret commitment here as an obligation to be able to verify that ¢.

Now, to capture the idea of an assertion as a commit­ ment, the institution I has the following as one of its constitutive rules, which also apply to any other server:

Thus the assertion, in I, that the server w implements the slow start algorithm, counts as an obligation, from the server to the institution, that this is a true statement.

However, and more importantly, we also want to be able to make judgements of the form either:

to say that according to the institution, ¢ is objectively (at least according to the institution) true (or not) .

Certainly this demands that 6-w 1-- ¢, as a required state, but also that w be capable of demonstrating that f:lw 1-- ¢. As it turns , because of a widespread bug in the slow start implementation in Windows NT servers, ¢ is not a true (objectively true) statement [Stevens, 1996]. Being unable to verify (if demanded to do so) that ¢, w would be in violation of its obligation if it made the assertion. (Note we have set aside the practical problem of a program verifying properties (correctness) of itself.)

3.2 Example 2: Football (Soccer)

This kind of example is common in the literature but worth examining again. Consider the institution F of football (soccer). We define a "goal" is scored when the ball has crossed a painted white line between two up­ rights and under a crossbar. Then, we can examine the situation at any given instant and determine whether or not a goal (according to F) has been scored. (In Searle's terms, the fact that a ball has crossed a line is a brute fact, the fact that by crossing the line between some sticks a goal has been scored, is an institutional fact.)

In certain games, a referee is given the power to ex­ amine the situation and decide whether or not it fits the definition of a "goal". If the referee signals that this is the case, then it is a goal (in the sense that the score of one team is incremented, etc.). Although a fairly coarse over-simplification, we could say that the referee is em­ powered by F to see to it that goals are scored. However, the referee is not permitted to signal "goal" (cannot ex­ ercise the institutional power) unless the world-to-word fit is such that the situation in the world matches the definition of the word. So if one of the players sees to it that the conditions for a goal are satisfied (implicitly, according to the rules offootball), then this counts as, in F , as initiating the referee's permission to signal "goal" .

Let us assume that the players are permitted to signal "goal" arbitrarily (of course this is not strictly the case), but because they are not empowered to create goals, if they do signal "goal", this does not count as a goal (in effect, all they can do is 'claim').

So let us have agent r who has the power of referee (i .e. agent r occupies the role of referee, which is granted certain powers by institution F). Let ~ 9 be the action of transmitting a signal in the signalling system (ACL) used by F, which denotes "goal" (e.g., whistling, saying "goal", etc.). Then, for the institution F , referee agent r, and player agents p, we have:

A situation arose in the 1966 World Cup Final between England and Germany, when the England players were claiming a goal had been scored. The England players were permitted to signal "goal", but not being empow­ ered, these signals did not count as goals . The referee was so empowered, so when he signalled "goal", it did count as a goal - even though a "goal" had not been scored. The problem, according to the characterisation above, was that the referee was exercising a power that in fact he was not permitted to. At this point, the ref­ eree should have been sanctioned according to the rules ofF: but this too is a subject for further work. How­ ever, as we see in Section 5, this is the kind of situation we expect to encounter in future multi-agents systems, where agents have powers to see to it that institutional facts are true, but have constraints on their permissions or occasions when to exercise that power.

4 Single Signalling Acts

The two illustrative examples of the previous section in­ dicate typical examples of the kind of meaning we seek for agent's illocutionary acts. In the first example, it was that the assertion counted as an undertaking that the propositional content was true (and that the asserter could verify that it was true); in the second example, that the declaration counted as the insitution seeing to that the corresponding institutional fact was true.

Motivated by this, in this section, we specify a set of constitutive rules for single, 'one off' signals, i.e. sig­ nalling actions not anticipating a reply. The specific context for this argument is as follows. For "an agent communicates by message passing", i.e. a communicative action performed by an agent, we are assuming a com­ putational model involving the point-to-point transmis­ sion (from agent a to agent b) of 'information structures' representing these messages. 'Saying' and 'hearing' are the results of, respectively, writing to and reading from some channel (e.g. a TCP/IP socket connection), or the consequences of remote method invocation (RMI) using constitutive rules rather than a conventional device.

For the operational context, we mean an open system as indicated in [Artikis et al., 2002], whereby: no sin­ gle agent has universal knowledge of the entire system, agents may have conflicting goals, internal architectures are not known, local states are individually consistent but may be globally inconsistent, and there is no central­ ized authority or control (of knowledge and behaviour). On the issue of decentralization, we take the position of local autonomy over goals, decisions and state, but that all communication is institutional [Searle, 1999].

Assume for the application that the agents are engaged in information trading or web services. We assume that the application will include finding and requesting ser­ vices, and finding and supplying information. Thus there will be some individual message exchanges (assertives, directives, etc.) and some structured exchanges (e.g. contract nets and auctions). For each individual sig­ nalling act, we give the required form (of propositional content and signalling content), the conventional inter­ pretation of the signal, and the institutional powers (if any) associated with the signal itself. Note that this is an external specification: so the conventional interpre­ tation indicates that, in the context of this particular institution, if an agent wants to convey a certain mean­ ing, then (by convention) it uses a particular signal; and if an agent witnesses a particular signal, then (by conven­ tion) a certain meaning is conveyed. We consider four of the five types of illocutionary point identified in [Searle, 1999]: assertive (assert and inform), directive (command and request), commissive and declarative.

Note that there might be some minor objections to the characterisation of the constitutive rules for the given il­ locutionary act types. However, recall that this is an ar­ tificial system of communication, that is being designed. It is not intended to be a formal characterisation of a pre­ existing system of communication, i.e. natural language, although it draws its inspiration from that source. If in turn the inspiration is not respecting the intuition, then it is easy enough to substitute signal_acLl for assert , signaLacL2 for inform, and so on, as the software will process the messages in just the same way and according to the same constitutive rules.

Searle's [Searle, 1969] formulation of rules in speech act theory included what he called preparatory condi­ tions and sincerity conditions. Preparatory conditions were extant circumstances required for a speech act to be a valid act of the associated illocutionary type; the sincerity condition was a 'psychological' expression asso­ ciated with the speech act.

Our agents do not have psychological states, but given the notation of Section 2 it is not uninteresting to con­ sider putative sincerity conditions expressed in the sig­ nals defined above. For example, if we added to in­ form the preparatory condition -,(t..a f- (t.b f- ¢)), and the sincerity condition t.a f- ¢, then these are effec­ tively FIPA inform Feasibility Preconditions FP1 and FP2 [FIPA, 1997], while the conventional interpretation is essentially the intended RE (Rational Effect). Thus it is straightforward, within the framework of constitutive rules, to get the current FIPA ACL semantics to 'drop out' as a special case.

5 Conversations: An Auction Protocol

In this section, we apply the idea of constitutive rules to a conversation, based on a variant of the English Auction protocol [Venkatraman and Singh, 1999]. One observation from the analysis here is that specifica­ tion of constitutive rules for an ACL must be sensi­ tive to time and predication, cf. [Artikis et al., 2002; Sergot, 2003].

An informal description of the auction is: the auction­ eer opens the auction for goods g at price p; bidders are empowered to bid for g at price p; after receiving a bid, the auctioneer is empowered to announce a new price p', p' > p; and if there is no bid at the new price, the auctioneer has the power to accept a bid at price p.

There are also other rules that govern the conduct of an auction, namely that: offering specific goods g for auction implies that the auctioneer either owns or is li­ censed to sell g; making a bid of p for p implies that the bidder owns p; bidding p more than once and bidding a price lower than the announced price p are meaningless actions; and the auctioneer is not empowered to accept two bids for the same g.

One way to formalise this protocol is to specify: the in­ stitutional powers of the auctioneer and the bidders; the assertions implicit in making announcements and bids; and the changing permissions of each participant as the protocol progresses which determine whether or not they are allowed to exercise their powers. There are three il­ locutionary acts: announce, bid and accept, with propo­ sitional content goods g (lot number) and price p. We assume, that all communications are broadcast, with the intended recipient b of accept messages explicitly identi­ fied in some way.

In general, the assertive force implicit in the illocu­ tionary acts is given by:

The institutional conditions element of the constitu­ tive rules are given by the following institutional powers. Note that these are unlike some of the institutional pow­ ers previously discussed in this paper, for two reasons. Firstly, these are 'power schema', in the sense that the actions of other agents will instantiate specific instances of each schema; and secondly, because they are transient rather than permanent, and each specific instance is ei­ ther initiated or terminated under certain circumstances.

The power of a bidder is given by:

while the auctioneer has two powers: firstly the power to make announcements, by announcing an auction, and secondly the power to make contracts, by accepting a bid:

I Pow a announce( G, P) d,;j Eaannounce(G, P) =?I [I announcement( a, G, P) IPowaaccept(B, G, P) d,;j Eaaccept(B,G,P) =?1 Eicontract(a,B, G,P)

Now the way it works is that if an agent has the power and performs the action, then it will count as seeing to it that the corresponding instituional fact is true. The in­ stitutional fact in turn initiates or terminate other pow­ ers (so each agent in effect has the power to empower other agents). If, initially, I Pow a announce (g , p), then:

Note [Artikis et al., 2002] formalised a specification of the contract-net protocol in terms of which powers, etc., were irritated and which were terminated by specific actions (which allowed for an event calculus specifica­ tion and direct implementation of the protocol). [Sergot , 2003] also contains an analysis of an auction protocol.

What's missing from the formalisation of conversa­ tional illocutionary acts, as opposed to the signalling acts of the previous section, is the conventional inter­ pretation (that these acts count as attempts to affect computational states in some way). It is not entirely clear what these should be (e.g. for announce, to inform b that g is for sale, to induce b to make a bid, or to in­ dicate its intention to sell g once a buyer is found); or indeed that such rules are adding anything useful in this context. We leave this for further investigation.

In addition, we could specify that agents are only per­ mitted to exercise their power, as an auctioner or a bid­ der, if they either own the goods g or the bidding price p respectively. In this way, we could circumvent the im­ plicit assertive force in the announce and bid signals, by requiring that agents seek permission to sell goods or offer bids, and are subject to sanction if they create con­ tracts without permission, which they cannot honour.

6 Summary and Conclusions

Searle [Searle, 1969] defined the semantics of illocution­ ary acts in terms of the conventional realization of se­ ries of sets of constitutive rules, and that a meaningful speech act was performed by uttering an expression in accordance with those rules. The constitutive rule sets proposed ([Searle, 1969]:p66-67) contained several condi­ tions, including the propositional content, preparatory, sincerity and essential conditions. However, a number of these rules were concerned with 'psychological' states, and the attempted formalization of such rules in multi­ modal BDI logics are far from computationally tractable.

In this paper, we have proposed to use Searle's theory of constitutive rules to define a semantics of illocution­ ary acts (signals) for an agent communication language.

The set of conditions, for a wide series of act types, in­ cludes the propositional content and form of a signalling act, the conventional interpretation (of intended perlocu­ tionary effect), the institutional conditions (expressed as a counts as formula) requiring institutional powers, and (in conversations) what deontic states are initiated or terminated by the performance of the signalling act.

There is, however, more work that is required. We have characterised the formalism used in Section 2 as a 'notation'. Ideally, the agent abstraction would define an operational model, which would be directly executable, and the 'logical' representation would be complete. For an executable operational model, we need an operational semantics, and for this purpose we are investigating la­ belled transition systems. A compiler for such rules, with an explicit link to (an implementation of) the agent ab­ straction, could then be considered.

For the logical model, we require (at least) a seman­ tics of the C operator. We recognize this is problematic, but for the kind of applications in which we are interested (where assertions of the forms "I have this right", "I rep­ resent this agency", "I can perform this service" are an­ ticipated) we feel something of this kind is required. We have interpreted Searle's meaning of an assertion ("com­ mitment to the truth of ¢/') as an obligation to be able to verify ¢, and this is not a matter of merely seeing ~o it that¢ (Ea¢). However, the work-around suggested m the previous section could eliminate the C operator.

Moreover, there are many open questions, some of which have already been indicated. The nature of the relationship between electronic institutions and deontic states of agents needs to be further elaborated, as this is central to definition of the communication model. Many problems in Section 5 stemmed from trying to analyse dynamic phenomena in an essentially static formalism, so an explicit treatment and representation of time, link­ ing to [Artikis et al., 2002; Sergot, 2003], is required. The representation of contracts, from where this work originated, also needs to be refined.

Defining ACL semantics based on Speech Act theory was first proposed for both KQML [Labrou and Finin, 1998] and FIPA [FIPA, 1997], and given in terms of an axiomatic characterisation of intentional BDI agents. We would argue that the emphasis on the intentional states rather than the institutional nature of the commu­ nication has omitted the most important component of the theory. [Greaves et al., 2001] proposed an alternative model, using the idea of conversation policies, which de­ fine fine-grained constraints on ACL usage. Another al­ ternative involves proposals primarily based on the idea of commitments, e.g. [Venkatraman and Singh, 1999; Colombetti, 2001], while Jones [Jones, 2003] proposes a conventional account of natural language speech acts based on the intentional exploitation of signalling sys­ tems. Motivated in part by the latter work, we have returned to Speech Act theory and attempted to charac­ terise constitutive rules for a system of communication between 'autonomous' agents governed by an electronic institution. Our intuition is that the interaction between this work and that of conversation policies offers some intriguing potential for further development.

In conclusion, we believe that we have a basis for de­ signing ACLs, and giving a formal characterization of the semantics of communicative acts which is powerful, ex­ pressive and flexible. Most importantly, it demonstrates the fundamental conceptual and functional difference be­ tween language-based communication and method in­ vocation, and justifies why agent-based systems offer a unique advantage over object-oriented ones.

Acknowledgements

We are grateful to the partners on the ALFEBIITE project (EU IST-1999-10298), especially Marek Sergot, Andrew Jones, Alexander Artikis and Lloyd Kamara; the members of FIPA TC Semantics; and several other commentators for their valuable input and insight.