Paul Kearney
paul.kearney@sharp.co.uk
Technical Report SLE/DIS/97-01
January 1997
SHARP Laboratories of Europe
Ltd.
Edmund Halley Road
Oxford Science Park
Oxford OX4 4GA
United Kingdom
Copyright ©1997 SHARP Laboratories of Europe Ltd.
| Signature | Date | ||
| Chief Scientist | |||
| Signature | Date | ||
| Manager |
Executive summary
At the FIPA meeting held in Tokyo in October 1996, I proposed that FIPA should define the syntax and semantics of an inter-agent message language to be used to implement an extra layer of "intelligent" control to augment existing and projected multimedia content delivery services working over public networks. The language would be used to exchange information on the availability of services and content, negotiate over terms and conditions, etc., then when agreement is reached, authorise delivery. The requirement is general across all classes of distributed information system. However, I regard the priority to be Internet applications using HTTP. In terms of the Call for Proposals, the technology area is Agent/Agent Communication (5.3.2, 5.3.3, 5.3.4) and the application area is Personal Assistant.
This note proposes the following for consideration by FIPA as the basis of the standard:
It is not currently a fully-defined candidate standard, but I believe that its can be developed into one within the timescale of FIPA 1. I hope that others in the agent and distributed information systems communities will collaborate in this development process, including those working on the semantics of and ontologies for inter-agent languages.
This report is divided into three major
sections. The first gives an introduction and summary. The second
is an updated version of the original internal report describing
the DIAL concepts [Kearney (1992a)]. These basic concepts have
been used in a number of in-house demonstrators and prototypes,
the most recent and most relevant of these being the ITA
(Information Trading Agents). The third major section describes
relevant aspects of the implementation of this prototype within
the DIAL framework.
Contents
1. Introduction & summary
2. The DIAL language
2.1 Model
2.2 Agents and the inter-agent language
2.3 Basic message structure
2.4 Message body
2.4.1 Speech act categories
2.4.2 Sentences
2.4.3 Time
2.5 Dialogues
2.5.1 Basic points
2.5.2 Dialogue vocabularies
2.5.3 Side effects and constraints
2.6 Message header
2.6.1 Agent naming scheme
2.7 Message sequences
2.8 Messages about messages
2.9 Example 1: Voter demonstrator
3. Information Trading Agents
3.1 Overview
3.2 Model - general
3.3 Document model
3.3.1 Document content descriptors
3.3.2 Hyperlinks
3.4 Agent model
3.4.1 Competence attribute
3.4.2 Best match attribute
3.4.3 Buy and sell actions
3.5 Messages
3.6 Dialogues, message sequences and negotiation
Proposal for standard Inter-Agent Communication Language
Paul Kearney
At the FIPA meeting held in Tokyo in October
1996, I proposed that FIPA should define the syntax and semantics
of an inter-agent message language to be used to implement an extra
layer of "intelligent" control to augment existing and
projected multimedia content delivery services working over
public networks. The language would be used to exchange
information on the availability of services and content, negotiate
over terms and conditions, etc., then when agreement is reached,
authorise delivery. The requirement is general across all classes
of distributed information system. However, I regard the priority
to be Internet applications using HTTP. In terms of the Call for Proposals,
the technology area is Agent/Agent Communication (5.3.2,
5.3.3, 5.3.4) and the application area is Personal Assistant.
My views on standardisation in this area can also be found in [Kearney
(1996)].
Figure 1: Interactions between different types of agent
Agents are required in:
Figure 2: Personal agent in end-user software
I assume for now, that agents are static and inter-agent communication is by message-passing. Analogous issues do also arise in the case of mobile agents, however, and I believe that the model proposed below could be extended to support both in an integrated fashion.
This note proposes the following for consideration by FIPA as the basis of the standard:
It is not currently a fully-defined candidate standard, but I believe that its can be developed into one within the timescale of FIPA 1. I hope that others in the agent and distributed information systems communities will collaborate in this development process, including those working on the semantics of and ontologies for inter-agent languages.
DIAL is in the broad family of speech act message languages, which are used in many multi-agent systems. The ideas presented here were first documented in 1992 [Kearney (1992a, b)], but have been refined through experience with a number of demonstrators and prototypes developed within Sharp Laboratories of Europe. These prototypes were mostly written in an in-house Prolog-based agent toolkit (DAOS), and the concrete syntax for the messages was also based on that of Prolog. However, the importance of DIAL lies not in any particular syntax, but in providing a definite framework for the semantics of inter-agent messages. The DIAL model can readily be mapped onto most concrete message syntaxes.
The best-known speech-act language is KQML/KIF combination [Finin, T et al (1994), Labrou (1996), Genesereth, M R and Fikes, R E (1992)]. KQML defines a structured syntax for inter-agent messages. It allows the bodies of the messages to be written in a language of the designerís choice, with this language being named in the message. KIF is one such language for the bodies of the messages. Other speech act languages are tied to specific agent programming languages, e.g. Agent0 [Shoham (1993)], or are specific to a particular application.
One problem with all of these is that while syntax is well defined, the semantics is highly application-specific. Some of the languages are mathematically formal, and so allow higher-level symbols to be defined in terms of the language primitives. Work is also on-going by others (e.g. [Smith and Cohen (1996)]) to define the semantics of speech acts in terms of agentsí mental states (beliefs, goals, etc.).
DIAL is intended to complement these by providing a simple, flexible practical model for grounding the messages in the real world. The abstract notation used in this paper could be re-represented in a variety of concrete forms (e.g. KQML). DIAL is intended to be sufficiently expressive to enable a first generation of interoperable agent systems, and also expandable to cope with the requirements of more sophisticated systems of the future. The ideas are quite general, but the application of most interest currently involves exchange of documents or services among open communities of peer agents across public networks such as the Internet.
The remainder of this note is divided into two major sections. The following one is an updated version of the original internal report describing the DIAL concepts [Kearney (1992a)]. These basic concepts have been used in a number of in-house demonstrators and prototypes, the most recent and most relevant of these being the ITA (Information Trading Agents). The final major section describes relevant aspects of the implementation of this prototype within the DIAL framework.
The DIAL view of the world is basically an object-oriented one. The domain of discourse is made up of objects with attributes and actions they can perform. Objects with similar attributes and actions are grouped into classes in the usual way. Most object are passive in the sense that they only perform their actions upon explicit instruction from the autonomous entities (agents, people, etc.) which own them. Agents are a special kind of object with the following characteristics:
These messages generally are used to pass or request information about objects, or to request that agents perform actions or achieve goal states. DIAL has an agent model to the extent that is necessary to provide a clear semantics for messages. There is no requirement that agents are implemented in terms of this model, but they must compose and interpret the messages as if they were.
DIAL follows Shoham to some extent in viewing an agent's mental state as being made up of beliefs and commitments. In DIAL, when we talk about an agent's beliefs (collectively) we mean its model of the world (composed of agents and other objects), which generally is imperfect and incomplete. When we talk about individual beliefs, however, we mean statements about the agent's model. It is not necessarily the case that the model is a database of belief statements. Also we do not distinguish between facts and beliefs an agent's view of the world is always subjective and prone to uncertainty.
Similarly, commitments are statements about an agent's intentions, which also include reference to an agent on behalf of which the actions will be carried out. Commitments are expressed in terms of actions which the agent intends to perform or states (of the world) which the agent intends to achieve.
In DIAL, a domain ontology consists of a set of class definitions for objects (including agents) and possibly specific instance definitions. The emphasis is on creating a domain model which matches the real world well, and so can be understood unambiguously. The attributes should correspond to concrete attributes of the real objects in question. This is a less formal, but more pragmatic approach than is adopted in logic-based inter-agent languages.
The inter-agent language defines the legal messages which can be sent between agents in the context of a particular dialogue. All the agents fully participating in the dialogue must be able to interpret the legal messages and respond appropriately (according to their own rules of behaviour). It is thus a communication language not a programming language.
The relationship between agents and the inter-agent language is similar to that between objects and interface protocols in object-oriented programming (OOP). In OOP, the interface protocol for a class defines the messages which objects of that class must handle, but does not specify what the object does on receiving a given message. Other objects need only know the interface protocol, the internal details can remain hidden and can safely be changed without affecting the correct working of the program.
Rigid messages such a used in object-oriented systems are not sufficiently expressive or flexible for negotiation between agents, however. Instead, we need a message language with a grammar and vocabulary, like a simplified version of human language. Our inter-agent language is based on speech acts. Speech act theory recognises that utterances (acts of communication) are more than just statements with a truth value, they are performed in order to achieve some effect. Our language makes the intended effect explicit by using speech act categories (illocutionary points) as operators on sentences.
As in OOP, there is a clear separation between the legality of a message, and the mechanism which an agent uses to interpret and act on it. The same message can be handled in different ways by agents with different architectures or rules of behaviour.
The inter-agent language defines as far as possible the meaning of the message, it is up to the receiving agent to determine its significance in the context of its own beliefs, goals and plans, and its knowledge of the sending agent. This interpretation may be naive ó statements accepted as true, requests obeyed, etc. ó or more sophisticated, with an evaluation the plausibility of statements, trustworthiness of the sender, compatibility with its own goals, etc. The message in itself does not determine the subsequent actions of the receiving agent, it is the agent's interpretation of the message that is important.
To emphasise and summarise these last points:
ï ideally, the inter-agent language defines an unambiguous meaning for any legal message, which is independent of the sending and receiving agents
ï agents are in general autonomous. The meaning of a message as defined by the language, does not determine the response of the receiving agent, nor does it specify the motives of the sender.
Conceptually, a message is a triplet with the following components (remember, however, that this is not a concrete syntax definition):
Message header ó this describes the sender and the intended recipient, and also contains a unique identifier which enables this message to be referred to unambiguously. The way in which the identifier is not defined here. It could, for example, be based on the time of sending, a sequence number, or a combination of the two. Other 'administrative' information can also be viewed as part of the message header.
Dialogue descriptor ó this describes the dialogue (a collection of messages on the same topic) of which the message forms a part so it can be interpreted in context. The descriptor identifies the dialogue class ó enabling the receiving agent to know the nature of the dialogue and hence which specialised vocabulary is used ó as well as the particular instance.
Message body ó this is a set of utterances. An utterance is a set of sentences qualified by a speech act category. Each sentence is composed from operators, predicates and nouns defined in the basic language vocabulary or in the specialised vocabulary of the dialogue class.
As an illustration of a message here is one taken from the voter example at the end of this section:
voter(jim)->(id)voter(fred) : voting_session(n) : [inform([vote of voter(jim) = for])]
which is in the form header:dialogue descriptor:body. It is a message from the agent voter(jim) to voter(fred). It is part of a dialogue of class voting_session, and its purpose is to pass the information that voter(jim)'s vote is for the proposition.
These will each now be described in more detail. The message body is described first as it is the most important to understand.
A message body is a non-empty set of utterances. An utterance is a non-empty set of sentences qualified by a speech act category. Although the body and the utterances are formally sets, they will frequently have only one element. A message with a multi-element body is equivalent to separate single-element messages which are otherwise identical. Similarly a multi-element utterance is equivalent to a set of single-element utterances:
{c({s1, s2, s3})} ¤ {c({s1}), c({s2}), c({s3})}
where c is a speech act category and the si are sentences.
In the following explanation, single-element sets are usually assumed. For convenience, we use c(s1) as a shorthand for c({s1}).
We use a small set of speech act categories are based closely on Searle's illocutionary points, but we have altered the names to make reading the utterances easier. Hence:
inform ó message contains statements about the agent's beliefs
request ó it asks for some action to be performed or goal state achieved (i.e. asks the receiving agent to take on a commitment)
agree ó it states that the agent intends to do the specified actions (i.e. it is a statement about the agent's commitments)
declare ó the message changes the world by being sent (as in pronouncing a couple married)
(We have no category corresponding to Searle's expressive point). In practice, we have found that there is no great advantage in distinguishing declare from inform , and so declare could be dropped. It is also possible to model agree as a variant of inform.
It is also necessary to introduce negative versions of the above: uninform, unrequest, unagree and undeclare.
Here is an illustration, using and informal notation, of how speech act categories modify the meaning of sentences:
A->B:inform( X = 10 ) ó A tells B that A believes X=10
A->B:request (make(X=10)) ó A asks B to make X = 10 true
A->B:request (inform(X=10)) ó A asks B Does X = 10?
A->B:agree(make(X=10 )) ó A tells B that A intends X = 10 to become true
A->B:agree(inform(X=10 )) ó A tells B that A will inform B whether it believes X=10
A->B:declare( X=10 ) ó A changes the value of shared variable X to 10
Note that this is an informal example only.
It is possible that future versions of the language will allow different degrees of force to be associated with utterances through the speech act category ó for example request with strength 0.7 that something should be done. We do not do this at present, however.
The simplest examples of sentences are object and action descriptions. An object description is used in the inform types of message. It consists of a class name and a number of attribute values which will normally include an identifier for the object. The values can be specified either as a list of attribute-value pairs, or else as a position-sensitive sequence of values. In an inform message, an object description is a statement that the sending agent believes that an object as described exists.
An action description is used in the request and agree types of message. It consists of the name of the action and a sequence of argument values. In a request message, the description identifies an action which the sender requests the recipient to perform. Clearly, the action should be one that the recipient can perform. An agree message informs the recipient that the sender intends to perform the described action. Note that all agents can perform actions corresponding to each of the types of speech act message, so that, for example, an agent can request that another agent inform it of the state of some object.
There is also a special action, make, which takes as its argument a sentence describing a partial world state (e.g. an object attribute value). This denotes an action which achieves the specified partial state.
Sentences can also be formed from predicates whose arguments are object attributes and their values. Sentences may be modified and combined by means of operators. We have defined a small number of core predicates and operators, which are adequate for present purposes. Our intention is to add to them as required in the future. Application specific predicates and operators may also be defined as part of a dialogue vocabulary.
= (equals) this takes two attribute arguments and refers to the equality of their values in (by default) the current world state.
… (contains) this takes two attribute arguments. If they are sets, then the relationship is set-subset.
OE (element of) this takes two attribute arguments, the second of which is a set of simpler attributes
All of these may optionally take an extra argument specifying the agent to which they refer. When this argument is omitted, it is assumed that informs, declares and agrees, refer to the sending agent, while requests refer to the receiving agent.
not ó reverses the meaning of the following sentence
exclusive ó within an inform, this means that not only is the following statement asserted, but any alternatives are refuted. This can be useful where the predicate is a one to many relationship, for example containsó exclusive(X OE Y) means that X is the only element of Y. By default sentences are not exclusive.
become ó this indicates that the following sentence refers to a future state.
Þ (implies) ó this is a binary operator indicating that the second sentence follows from the first. In dialogues considered so far it is mainly useful as part of a request in bargaining. It is used to construct requests such as If you turn left then I will turn right.
Note: this is the most fluid and least well defined area of the language currently. There are still combinations of speech act category, predicate and operator the semantics of which are unclear.
There are a number of special attributes:
? ó which denotes a value which is being investigated
_ ó the value of the attribute is not important
undefined ó the value has not been established
unknown ó the value cannot be established (yet)
dialogue ó the dialogue of which the message is a part
sender ó the sender of the message
recipient ó the recipient of the message.
DIAL assumes that all agents have a common notion of time (i.e. they have access to a global clock, or else each have consistent internal clocks). We have found it useful to follow the example of Shoham's Agent0 in qualifying speech acts with a time. Where the message concerns a belief, the time refers to the time at which the statement was believed. Where the message concerns an action, the time is when (the earliest time) the action is requested / intended to be performed.
We intend that complex temporal issues can be dealt with using modal operators to qualify the meaning of sentences if they are required. One issue that definitely is important in practice is that of times which qualify conditional commitments, which can be used to express offers of services. For example, A may tell B that it will perform action X (send a document, say) if B agrees to do Y (pay a fee, for example). There is no obligation on B to reply, so how long does A stay committed to this offer? Alternatives include establishing conventions that offers are valid for a fixed time, and stating explicitly a time after which the offer expires.
A dialogue is basically a conversation among a group of agents. It can also be thought of as a set of connected messages discussing a particular topic. A dialogue has a number of attributes, such as the identities and roles of the participants, the stage of a negotiation, etc., which distinguish it from other dialogues. Since an agent may be participating in several dialogues at one time it is important that an incoming message identifies which one it is part of. An important part of the dialogue descriptor is therefore the dialogue identifier, which is a unique symbol.
The other element of the descriptor is the dialogue class name, which may be qualified by a context name. To participate in a dialogue, agents must have some shared understanding of the subject under discussion, including an agreed set of terms to use. Rather than try to define a general model covering all possible discussion topics, we group dialogues into classes according to topic. A dialogue class is a prototypical description of the vocabulary and structure of a conversation on a particular topic. Specifying the dialogue class in a message enables the receiving agent to interpret the message using the correct vocabulary.
Optionally, a class definition may specify a set of contexts ó often these will correspond to stages in the conversation, though this is not necessarily the case, and no ordering is defined. Each context also has a vocabulary, the vocabulary available within a particular context of a dialogue being the union of the dialogue and context vocabularies.
Provisionally, the notation for the dialogue descriptor is:
<class name>(<dialogue id>)
or
<class name>(<dialogue id>) : <context name>
Vocabularies will now be discussed in more detail.
Associated with each dialogue class is a vocabulary which defines the language elements used (in addition to the core elements) to construct sentences within instances of that class. A vocabulary consists of declarations of vocabulary entries. The three sorts of vocabulary entry are: predicates, operators and nouns. Predicates and nouns may be typed.
Operators and predicates were discussed adequately above. Here we concentrate on the nouns. Nouns can be attributes (which have a value) or actions (which do not). Things can have any of the usual data types. Both attributes and actions may take arguments.
Nouns are usually grouped into objects. Each object will typically represent a real (or conceptual) object in the domain being discussed. Attributes of objects are usually called slots. In the usual way of object or frame systems, class declarations define the structure of objects within that class. Things may be declared with a class name as their type, and also as set of <class name>..
Things may be given initial or default values. Where the value is an object, this means declaring an instance of the relevant class. We have not defined a special abstract syntax for nouns. As standard object/frame concepts are used, and because our agent toolkit has a frame system, we use a pseudo-code version of the toolkit's frame language.
Choosing whether to represent a noun as a attribute or as an action can be tricky sometimes. As a general principle, if it is important that agents participating in the dialogue know the results of an action or just that the action has been performed, it is better to represent the results of the action as an attribute. Invisible side effects should be avoided if at all possible.
It can seem artificial to do this in some circumstances, however. In other cases, there might be more than one effect of an action making side effect unavoidable. We therefore introduce the idea of constraints between nouns. A constraint expresses a relationship between nouns such that a change in one noun (or doing one action) necessarily brings about a change in, or performance of, the other. At present we have not defined a way of expressing such constraints, but they can be written in English, pseudocode in more formally in Z.
Agents and special objects:
Agents can be regarded as active objects. In terms of the language usage, their main distinguishing feature is that they are potential sources and recipients of messages.
Agents are defined as being owned by and having responsibility for objects. An agent is responsible for an object, in the sense that it can be assumed to know (or be able to find out) information about the object and to be able to alter it and perform actions on it. Ownership by implies responsibility for an object. The distinction is that an agent is only owned by one object, and the name of that object forms part of the agent's name. Each agent has an owned_by slot whose value (if any) is the object owning that agent. It also has a responsibility slot whose value is a set of objects.
Naming conventions for agents are discussed in the section on message identifiers.
As mentioned earlier, the message header has (at least) three components: the name of the sender, the name of the recipient, and a unique identifier. When sending a message, an agent only needs to specify the intended recipient ó the other components are generated by the system. An agent's name is also a description of its specialisation. If the recipient's name is only partially specified, than the message is sent either to all agents fitting that description or to any agent fitting the description. The naming scheme will now be described in more detail.
Agents engaged in a dialogue must have some common model of the domain being discussed so that the meaning of messages is consistently understood. At the same time, all agents do not need to know about all domains. We have developed the following model to help define the semantics of agent dialogues.
All agents potentially in the population can be classified according to an extendible hierarchy of overlapping classes (this is similar to the idea of class hierarchies in object-oriented languages allowing multiple inheritance). There are currently two main hierarchies,
ï function ó dealing with the type of role the agent plays
ï owner ó dealing with the real world or logical entity (user, resource, etc.) for which the agent is responsible
Basically, membership of a class implies a competence in communicating about a subject, i.e. the dialogue classes it can handle. Any contradictions arising from multiple inheritance can be dealt with in the usual ways.
The name of an agent should reflect its dialogue competence, so the full name must include the most specific classes the agent belongs to. Since the intersection of these classes may have more than a single member, the full name must also include an instance identifier. For simplicity, we make this unique within the agent population. NB the class description is still required, as the instance identifier will not be known to other agents before establishing a dialogue, and in effect also changes with time (strictly speaking it identifies the process embodying the agent rather than the agent itself).
full name = class1 x class2 x ......... x id
We also want to use partially specified names:
ï the id may be unspecified
ï position in one or more hierarchies may be omitted
ï a more general position in a hierarchy may be specified.
We then need to distinguish whether we are talking about any or all agent(s) fitting the partial description. The simplest way of dealing with this in the name is to have symbols for any and all as pseudo identifiers.
The current syntax is somewhat imperfect, being a generalisation of an ad hoc solution. It has the form:
function.id(owner)
or simply
function.id
if the agent has no owner. We assume that function and owner are leaf nodes of the class hierarchy, and that an agent is an instance of only one sub-class of function and optionally one sub-class of owner.
Just as in human conversations, some utterances require a reply. Agents are required to follow the following conventions:
inform: no reply necessary. Note that no 'acknowledgement of receipt' message is required, as confirmation of delivery of a message can be supplied by the underlying agent communication mechanism. Information supplied can later be retracted using an uninform message.
request (for information): if the information is available already, or can be calculated in a short time, an inform message specifying the information is sent. If the information is not currently available, but the agent is willing to supply it at a later time it can reply with an agree to send it. If the agent cannot supply the information it sends an inform containing the unknown noun. As weaker statement it could instead send an unagree to send the information.
request (for action): the reply is either an agree or an unagree to do the action
agree: usually no reply necessary. Work needs to be done to define the sequence of messages associated with conditional requests and offers, however, (that is request and agree messages containing the implies operator).
declare: no reply necessary
There are times when messages themselves must be discussed, for example when a message could not be understood. In such cases the message itself is used as the dialogue description. There is thus an implicit message dialogue class. Its vocabulary represents the message as an object. The major components of the message are represented as slots, and there is an extra slot, error_status, indicating the degree to which the message has been understood by the recipient.
There is plenty of scope for making the message dialogue vocabulary richer, for example enabling reasons to be given why a message was not understood. We expect to extend the vocabulary in the future.
Note: the language was defined after the Voter demonstrator was implemented. Consequently, this explains how the language could be used to define a voting dialogue rather than describing the messages used by the demonstrator.
Voter dialogue vocabulary
Here is the dialogue definition written in a pseudocode based on the frame language of our agent toolkit and Prolog.
Dialogue_definition voting_session
/*
A voter is a subclass of agent with extra attributes: vote,
comment, and negotiation_status. The value of vote is by default
undecided, but may be changed to for or against. Comment is the
latest comment text entered by the owner of the voter. A voter
starts off with negotiation status = out. This status becomes in
when it joins the voting session, and becomes out again when it
leaves the session or the session is terminated by the organiser.
*/
class voter is_a agent
slots:
vote : default : undecided
vote : require : in_list([for, against, undecided])
comment : require : comment_record
negotiation_status : default :
out
negotiation_status : require : in_list([in, out])
endclass voter
/*
An originator is a subclass of voter with responsibility for the
voting session. By default its negotiation status is in.
*/
class originator is_a voter
slots:
responsibility : default : [dialogue]
negotiation_status : default : in
endclass originator
/*
A voting_session is an object which has an originator, a set of
participants, a proposal to be voted on, sets of votes for and
against, a session_status (open or closed), and a set of comments
from the various participants.
*/
class voting_session
slots:
originator : require : instance_of(originator)
participants : require : set_of(instance_of(voter))
proposal : require : string
for : require : set_of(instance_of(voter)))
against: require : set_of(instance_of(voter)))
session_status : require : in_list([open, closed])
comments : require : set_of(type(comment_set_element))
endclass voting_session
/*
A comment record as held by a voter consists of a string (the
comment text) and an integer representing the earlier comment (if
any) to which this one refers (0 if no specific reference).
*/
type(comment_record, [S, I] ) :- string(S), (integer(I); unspecified(I)).
/*
A comment set element as held by the voting session consists of a
string (the comment text), the voter whose comment it is, a
unique integer, and an integer representing the earlier comment
(if any) to which this one refers (0 if no specific reference).
*/
type(comment_set_element, [S, V, I1, I2] ) :- string(S), instance_of(voter, V), integer(I1), integer(I2)).
A voting session
A voting session begins when one voter agent takes out a new dialogue id and declares the corresponding session open.
voter(fred)->voter.all(_):voting_session(n):[declare([session_status of dialogue = open])]
Then the other voters are invited to participate.
voter(fred)->voter.all(_):voting_session(n):[request([make(negotiation_status of recipient= in)])]
Two voters agree to participate,
voter(jim)->voter(fred):voting_session(n):[inform([negotiation_status of sender = in])]
voter(pete)->voter(fred):voting_session(n):[inform([negotiation_status of sender = in])]
and one declines.
voter(harry)->voter(fred):voting_session(n):[unagree([make(negotiation_status of sender = in)])]
Fred then sends the proposal,
voter(fred)->voter(jim):voting_session(n):[inform([proposal of dialogue = "Meeting tomorrow?"])]
voter(fred)->voter(pete):voting_session(n):[inform([proposal of dialogue = "Meeting tomorrow?"])]
and informs everyone of who the participants are
voter(fred)-><participants>:voting_session(n):[inform([participants
of dialogue = [voter(fred),
voter(jim), voter(pete)]])]
There is then an exchange of comments. These must go via fred, as they must be allocated an integer for future reference. For example
voter(jim)->voter(fred):voting_session(n):[inform([comment of voter(jim) = ["I am busy all morning", 0]])]
voter(fred)-><participants>:voting_session(n):[inform([ ["I am busy all morning", voter(jim), 10, 0] OE comments of dialogue])]
The participants vote on the proposal. For example
voter(jim)->voter(fred):voting_session(n):[inform([vote of voter(jim) = for])]
voter(fred)-><participants>:voting_session(n):[inform([ voter(jim) OE for of dialogue])]
When all the votes are cast, the proposer declares the voting session closed.
voter(fred)-><participants>:voting_session(n):[declare([
session_status of dialogue = closed])]
This section describes the DIAL-based message language used in a recent proof-of-concept prototype system. The agents in this system (Information Trading Agents, ITAs) collectively form a distributed hypermedia information system comparable to the Internet World-Wide Web, but more suitable for mobile personal electronics, and with a number of added features. The underlying model is one of a market for services ó in general an agent is both a provider of, and a customer for, services. The agents buy and sell information services from each other in the form of multimedia documents. In order to deliver the documents, they use a hypothetical document transfer service which must be paid for. For the prototype we adopted a ësender paysí convention similar to normal postal or telephone services. The agent selling a document must therefore take the cost of transmission into account when charging for an information service. The characteristics of this service and the ësender paysí convention are not intrinsic to this work, however. In a real system we would envisage HTTP over the Internet to be the document delivery service. In this case the real monetary marginal cost would be e.g. telephone connection plus fees charged by the access provider.
The selling agent sets its offer price according to both the estimated value of the transaction and the costs. Thus, if the document transfer gives a positive benefit to its user, the offer price may be below the transfer cost, it may be zero, or may even be negative. The basic transaction mechanism, therefore, supports a range of document-transfer scenarios:
ï commercial information service ó charge = costs + mark-up
ï loss-leader ó charge = costs - discount
ï e-mail ó charge = zero
ï promotional material ó negative charge set as an incentive.
Negotiations over a transaction may be initiated by either the provider of, or the customer for, the service. This is done by requesting that the other agent buys or sells a document/service. A specific price may or may not be mentioned at this point. The agent receiving the offer evaluates it in its own context, and (after consulting the user if necessary) replies according to whether or not the offer is acceptable. If certain of the offer terms were not precisely specified (notably the price), then the reply firms up the terms which constrain acceptance. For example, if the purchase offer price is unspecified, but the deal is acceptable provided the price is at least 10p, then the reply states this price (or maybe a slightly higher one to allow scope for haggling). If the reply is positive, then the originator checks the terms, confirms acceptance (if necessary), and the transaction can proceed. If the reply is negative, then an improved offer may be made (in which case the procedure is repeated).
As well as negotiating the purchase of services, the ITAs can exchange information. Information, for example on the existence, location, content, etc., of a document may be sent unsolicited (as an ëadvertisementí, say, or to provide a tip to a colleague), or else may be sent in reply to a request. Agents use information exchanged in this way to learn about the existence, location, etc. of documents of potential interest, and also about useful sources of such documents. As an example of how the agents use this information consider the mechanism by which an ITA responds to a user-request to find a document corresponding to a particular content profile. First the ITA checks whether a document matching this profile exists within the agentís own database. Then it checks whether it knows of the existence of such a document elsewhere. If neither of these turns up anything useful, the ITA checks whether it knows of any other agents who are likely to hold such a document, and asks for their documents which match the profile best. If no such agent is known, then the ITA queries the directory agent to see if it knows of any suitable sources. Once a document is identified, purchase negotiations can proceed as above.
The prototype also included an ëenvironment agentí, occupying a special role. Unlike the other agents, it would have no directly corresponding agent in a real system. It provides a control panel as a convenient means of operating the prototype, and also performs miscellaneous functions in the role of agents not explicitly represented in the prototype. In particular it acts as the service directory agent, and also feeds documents into the system as if they were originated by a wider community of users. The control panel is used to create new agent processes and to broadcast operator commands (go, pause, restart etc.). Because of its special status, the environment agent is known informally as ëgodí, a name which was retrospectively interpreted as an acronym for Global On-line Directory.
Personal ITAs have class ëtraderí and names of the form trader(N), where N is the name of an imaginary human user (for example, tom). Service ITAs are of class ëresourceí names of the form resource(N) (for example resource(guardian) is a rudimentary electronic newspaper).
To a good approximation, resource agents are ITAs with a restricted set of behaviour rules and no graphical user interface. A resource agent sends messages to the environment agent (acting here as a directory service) informing it of the resource agentís ëcompetenceí (a summary description of the subject matter held in its database), and of its ërootí document. By convention, the root is a text document giving an overview of the services offered, and containing hyperlinks to other documents held in its database. Otherwise, a resource agent behaves passively ó it will respond to requests for information and purchase offers from other agents, but will not initiate any interactions.
ITAs have a more complex set of behaviours. As well as responding in a similar way to the resource agents, an ITA will initiate interactions, both spontaneously, and as a result of instructions from its user. Spontaneous behaviours include:
ï periodically requesting acquaintances (i.e. other ITAs it knows about) for their competences;
ï periodically selecting a acquaintance and informing it about a document held in its database;
ï periodically selecting a document possession of which is estimated to be to the advantage of its user, and making a purchase offer based on its estimated value;
ï deleting the least valuable documents in its possession whenever the agentís database is overfull.
User-initiated behaviours include:
ï making an offer to sell a document to another user;
ï making an offer to buy a document from another user. The user request typically follows a search instruction, or else is initiated by the user clicking on a highlighted word when reading a text document containing hyperlinks;
ï searching based on a content profile as described above.
The main objects in the domain model are the ITAs, the databases they control, and the documents which are stored and transmitted. The databases are only mentioned implicitly in dialogues, however. Much of the communication involves exchange of descriptions of document objects. The main additional attributes of ITAs are:
Prolog was used as the implementation language for this system, and the syntax employed for object descriptions is that of a Prolog term, with the functor being the class name, and the order of arguments determining the attributes they describe. Similarly, a term-based syntax was used for agent attributes, with the functor being the attribute name, the first argument being the agent name, and the remaining arguments being the attribute parameters and value. Hence:
attr1(trader(x), y) is equivalent to attr1 of trader(x) = y
In addition to the standard actions (sending of speech-act messages), agents have:
Note that matching buy and sell actions are necessary for a document transfer to proceed.
In reasoning and communicating about documents, agents make use of document record objects. A document record has the following attributes:
ï location, i.e. which agentís database the document is (believed to be) in;
ï a document content descriptor (see below);
ï a unique document identifier;
ï originator (usually the author);
ï document media type (currently one of: text, audio, video, bitmap);
ï document size;
ï hyperlinks to other documents (see below).
Further fields will probably be defined in the future.
Note that we distinguish between documents and copies, in that several copies of the same document may exist (probably in different locations), with the same identifier. The content of these copies is identical.
Associated with each document is a set of attribute-value pairs which describes the nature of the document content in terms of its degree of relevance to specified topics. Such a set is termed a document content descriptor. The attribute component of a pair is a symbol denoting a topic; the value component is a number in the interval [0, 1] the degree to which the document is relevant to that topic (effectively it expresses degree of membership of the fuzzy set denoted by the topic symbol). In the first instance, this set is assumed to be created with the document, much as a set of keywords is used to describe a book or paper. It is likely, however, that in a real product, the description would be computed using one of several algorithms which exist for this sort of task. There is no restriction limiting the total relevance of a document summed over various subjects, and it is quite possible for a document to have maximum relevance to several topics. The set of topics is arbitrarily large
The hyperlinks field of a document descriptor contains a list of pairs, the second elements of which are descriptors of other documents connected in some way to the current document. The first element of a pair is a tag, represented as either an integer or a Prolog atom. It will be seen later that the tags can be used to provide a user-friendly method by which a user may request document related to the one he/she is viewing.
ITAs have the following attributes and actions
An agentís competence is a measure of the overall quality of its document database. It has the form competence(Agent, Clist, Cmag), where Clist is very similar to a document content descriptor, except that the numerical value associated with each topic may be greater than 1, and Cmag is the sum of the numerical values. Clist is intended to reflect the amount of information on the cited topics held in the database of Agent. At present it is calculated by summing the document content descriptors of all the documents in the database. It is likely that improved methods of calculation will be devised in the future.
This is a dynamically calculated attribute (a method which returns a value): best_match(Agent, Content profile, Document record, Degree). Typically, an agent will request to be informed of another agentís best match, specifying a content profile. Such a query causes a search of the database looking for the document currently held which matches most closely the content-descriptor-style Content profile. The completed best match attribute descriptor is then sent back to the first agent.
buy ó buy(Agent1, Agent2, Document, Price), meaning Agent1 buys the document described by Document from Agent2 for Price. Execution of this action involves accepting delivery of the document from the network;
sell ó . sell(Agent1, Agent2, Document, Price), meaning Agent1 sells the document described by Document to Agent2 for Price. Execution of this action involves Agent1 issuing a start_service instruction to the equipment agent to initiate the document transfer.
This pair of actions are examples of what we term reciprocal actions. These are useful when an act requires the participation of two agents. These must both perform matching ëhalfí actions before the full action may proceed. In this case, two agents must perform matching buy and sell actions before the full document transfer is completed.
In the prototype, each agent is responsible for adjusting its money as appropriate when a sale takes place. A real system might involve broking agents can be used as independent monitors to ensure honest trading. Participants in a reciprocal action involving payment could register the terms of its agreement with the broking agent. A pair of reciprocal actions would constitute a binding contract witnessed by the broking agent, which could possibly also be used as a clearing-house for electronic funds transfer.
Were HTTP to be used as the document transfer mechanism, the buy action would cause an HTTP request to be sent, while a sell action would authorise a document to be sent in response to a specific request.
Message bodies actually used in the prototype are of the form:
inform@Time:Fact sentence
meaning I inform the Destination agent that I believe that Fact is /was/will be true at Time, or
request@Time:Action
meaning I request the Destination agent to perform Action at Time, or
agree@Time:Action
meaning I commit to the Destination agent to perform Action at Time, or
unagree@Time:Action
meaning I have no commitment to the Destination agent to perform Action at Time.
The buy and sell actions need some further comment because of their reciprocal nature. A request sent by B to A for A to buy (sell) a document from (to) B for a specified price is an offer from B to sell (buy) the document to A and implies a commitment by B to proceed on these terms should A send a matching agree message. This would be long-winded to spell out explicitly in messages, so we just state that this is implied by the designation of buy and sell as reciprocal. A similar message with an unspecified price is an invitation for A to make a reciprocal offer. Likewise, an agree to buy or sell is a statement of commitment to proceed should a matching request be (or have been) received.
The prototype did not in fact use any explicit dialogues. This is because of the limited scope of the prototype, and because it is an important part of our philosophy to increase generality by relying on message semantics (trying to make each message meaningful independent of assumptions about preceding and subsequent messages) rather than explicit dialogue state. Quite varied and complex ënegotiationsí can be generated naturally from common sense rules of behaviour defined in terms of individual messages and a small amount of agent mental state information. In retrospect, however, it might have been better to group messages relating to a specific document purchase negotiation by marking messages with a negotiation dialogue instance identifier.
The simplest message ësequencesí in common use are isolated informs, which require no acknowledgement. The meaning of an inform message is clear, and is the same whether it is sent unsolicited or as a in response to a request ó the sending agent believes the sentence to be true at the time stated. The most common inform asserts the existence and location of a document by means of a description of a document object. In the unsolicited case, the location will typically be the sending agent, and the motivation will typically be the hope that the receiving agent will be sufficiently interested in the document to wish to acquire it at some stage in the future. A typical example of a request for a document inform is a ëbest matchí request, where the requesting agent is looking for a document which best fits a particular profile. Otherwise the requesting agent might want to know, say, the location of a copy of the document.
Suppose, then, that an agent has been informed of the existence of a document, and decides it might like to acquire it. It has two basic alternative ways forward. Firstly, it can calculate a price it would be willing to pay (perhaps erring on the low side), and request that the owning agent sell the document at this price. The agent receiving this request then replies with either an agree or an unagree, using the same sentence as in the request. The second alternative is to leave the price unspecified to invite an offer. The receiving agent calculates a price it would be willing to sell at (possibly erring on the high side), and replies with a request to buy specifying this price (or else with an unagree to sell). The original agent then either agrees or unagrees to buy. If agreement has not been reached, then further rounds of negotiation can be conducted in the same way. Note that the whole negotiation could also have been initiated by the agent owning the document with a request to buy. An example negotiation message sequence is shown in Table 1.
| sent by A to B | sent by B to A | Notes |
| inform(document(id = doc1, ....)) | A informs B of the existence and characteristics of doc1. | |
| request(sell(A, B, document(id = doc1), ?)) | B requests terms on which A will sell B doc1 | |
| request(buy(B,A, document(id = doc1), 10)) | A calculates selling price and request B to buy the doc1 at this price | |
| agree(buy(B,A, document(id = doc1), 10)) | B assesses this price to be consistent with its subjective evaluation and agrees to buy | |
| A and B have exchanged matching request/agree to buy so transaction proceeds. |
Table 1: Example negotiation. Syntax has been simplified and unnecessary detail omitted.
It should be apparent, then that flexible and varied message sequences can be constructed from simple messages and response conventions without complex dialogue state information. It was mentioned above, that messages in the prototype system were not even tagged with a dialogue instance, and this worked fine for the scenarios demonstrated. Complications may arise in practice, however, because of the conditionality implicit in the reciprocal buy and sell actions. Consider an agree to sell, for instance. This means I will sell you the document on these terms if you request / have requested me to do so. However, it is not clear whether this commitment applies to only the first request received or to all, whether it stands forever unless revoked with an unagree, and so on. Possible solutions include:
On the whole, I favour the last of these.
References
[Finin, T et al (1994)]. Specification of the KQML agent-communication language (Draft dated February 9th 1994), DARPA Knowledge Sharing Initiative External Interfaces Working Group.
[Genesereth, M R and Fikes, R E (1992)] Knowledge Interchange Format Version 3.0 Reference Manual, Interlingua Working Group of the DARPA Knowledge Sharing Initiative. (see links in http://logic.stanford.edu/kif/)
[Gibbins et al (1993)] The World Economy Game, Peter Gibbins, Paul Kearney, Arvindra Sehmi, Robert Smith, SLE Technical Report SLE/IT/93-4, also presented at IJCAI93 Workshop on Artificial Economics
[Kearney (1992a)] Definition of inter-agent language, Paul Kearney, SLE Technical Report SLE/IT/92-3
[Kearney (1992b)] A naïve agent model, Paul Kearney, SLE Technical Report SLE/IT/92-4
[Kearney et al (1994)] Kearney, P J, Sehmi A and Smith, R M (1994). Emergent behaviour in a multi-agent economic simulation in 11th European Conference on Artificial Intelligence, ECAIí94, Proceedings (Ed Cohn, A G), Wiley.
[Kearney (1996)] Personal agents: A walk on the client side, presented at Real-World Applications of Intelligent Agent Technology seminar London, June 1996, Unicom and at the IBC Seminar on Intelligent Agents, London June 1996. An earlier version was presented at the IEE Professional Group C3 Colloquim on Intelligent Agents and their applications, April 1996. Digest No: 1996/101 http://www.sharp.co.uk/pk/unicom/Unicom.htm
[Labrou (1996)] Proposed KQML specification document, Yannis Labrou, University of Maryland Baltimore County. http://www.cs.umbc.edu/~jklabrou/thesis.html
[Shoham (1993)] Agent-oriented programming, Yoav Shoham, AI Vol 60, No 1, p51
[Smith and Cohen (1996)] Towards a semantics
for an agent communication language based on speech acts, Ira
A Smith and Philip R. Cohen, Oregon Graduate Institute