A Geometric Semantics for
Agent Interaction Protocols
Peter McBurney
Department of Computer Science
University of Liverpool
Liverpool L69 7ZF
[email protected]
(Joint work with Simon Parsons, Brooklyn College, CUNY, New York.)
Presentation to:
Condensed Matter Physics Group
Imperial College, London
29 October 2003
We are on the verge of a revolution . . .

Computational devices and systems will soon be:
–
–
–
–

Everywhere
Interconnected
Always active
Intelligent and autonomous.
Software systems will thus be:
–
–
–
Situated
• Responsive to and influential upon their environment
Open
• Computational entities will enter and leave these environments continually
Autonomous
• Entities and systems will be goal-directed and exhibit autonomous behaviour
• Systems and sub-systems will have multiple threads of control, not one.
Agent Interaction Protocols
2
Autonomous intelligent software agents


It helps to conceive of computer systems as consisting of interacting
autonomous entities.
A software agent is a computational entity with (some degree of):
–
–
–
–

Social awareness
Proactive behaviour towards defined goals
Reactive behaviour in response to its environment
Decision-making autonomy.
(Wooldridge & Jennings 1995)
Some applications:
–
–
–
–
–
Air Traffic Control systems (agents representing aircraft and controllers)
Electronic commerce (agents representing buyers, sellers, others)
Management of utility networks (telecoms, electricity, etc)
Provisioning of complex products and services (e.g. telecoms services)
Management of fleets (vehicles, satellites, SCADA devices, etc).
Agent Interaction Protocols
3
Two key research problems:

How to design agents
–

How to design Multi-Agent Systems (MAS)
–
–

The most common approach is based on the Philosophy of Intention and Rational
Agency (Bratman, Pollock)
• e.g In the BDI model, agents are assumed have three types of mental states:
Beliefs, Desires, and Intentions.
• Considerable work has focused on formalizing these models using dialects of
modal logic (epistemic, temporal, deontic, etc) or formalisms adopted from
argumentation theory.
How may agents interact with one another?
How may they make joint decisions?
I will consider agent interaction languages in this talk.
Agent Interaction Protocols
4
How to humans interact?

By means of language
–

Types of Agent Communications Languages:
–
–
–

So, an obvious first step to designing agent interaction mechanisms is to consider
the design of artificial languages for agent interaction.
Generic ACLs
Dialogue Game Protocols
Auction Mechanisms.
Following the philosophy of language, agent languages designers usually
distinguish between two layers of communicated messages:
–
–
The topics of conversation (which may be represented in a suitable logical
language)
– eg “It is raining”
The illocutions which communicate something about these topics, eg
– QUESTION(raining)
– INFORM(raining)
– DEMAND(raining).
Agent Interaction Protocols
5
Generic ACLs
Two major proposals:

USA DARPA’s Knowledge Query and Manipulation Language (KQML)
–
–
–

Arose from attempts to merge multiple knowledge bases
Focus was information-sharing between knowledgeable agents.
www.cs.umbc.edu/kqml/
Foundation for Intelligent Physical Agents ACL (FIPA ACL)
–
–
–
–
Arose from an automated purchase transaction system at France Telecom
Focus was negotiation of tasks between expert agents
FIPA is a computer industry standards body for agent technologies.
www.fipa.org
Agent Interaction Protocols
6
FIPA Agent Communications Language
(FIPA ACL)

FIPA ACL has 22 illocutions
–
–

e.g. inform, query-if, request, agree, refuse.
Each has a defined syntax:
(inform
:sender (agent-identifier:name j)
:receiver (agent-identifier:name i)
:content
“weather (today, raining)”
:language Prolog)
The origins of FIPA ACL in knowledge-sharing and contract negotiations are
apparent:
–
–
–
–
11 of the 22 illocutions concern requests for or transmissions of information
4 involve negotiation (e.g. cfp, propose, reject-proposal)
6 involve performance of action (e.g. refuse, request)
2 involve error-handling of messages (e.g. failure).
Agent Interaction Protocols
7
Problems with FIPA ACL

The language implicitly assumes eternal connections between the agents
–
–

As befits a language for knowledge-sharing, the semantics impose sincerity:
–

–
There are no illocutions for contesting statements, or for requesting or giving
reasons for claims, or for structuring dialogue.
The participants incur no dialectical obligations.
The language does not readily support self-transformation
–

Agents cannot utter beliefs they do not hold.
As befits a language for contract negotiations, the underlying (implicit)
argumentation theory is simplistic.
–

Where are the illocutions for entering and leaving dialogues?
Where are the illocutions for permitting or contesting participation?
How may an agent express a change of its beliefs?
The absence of an explicit argumentation theory causes a state-space
explosion:
–
–
Any illocution may follow any other: Disruptive behavior is not precluded.
Dialogue Game Protocols have been proposed as a solution to this problem.
Agent Interaction Protocols
8
Dialogue Game Protocols


“Games” between two or more participants where each “moves” by making
utterances, subject to some rules.
Origins in Philosophy
–
–
–
–

Aristotle and medieval philosophers
Revived for the study of supposedly fallacious reasoning (Hamblin 1970,
MacKenzie 1979)
Proof theory for intuitionistic & classical logic (Lorenzen 1959)
Applied to quantum physics (Mittelstaedt 1979).
Within computer science, applied to:
–
–
–
–
–
Modeling human dialogues in computational linguistics
Software development processes
Modeling legal reasoning
Man-machine dialogues (e.g. for automated tutoring systems)
Protocols for agent dialogues.
Agent Interaction Protocols
9
A DG Protocol is defined in terms of:

A language of statements (the topics of the dialogue)
–

A set of illocutions instantiated with the statements
–

Usually expressed in some logical language (e.g. propositional logic, FOL, etc).
eg assert(p), accept(p), contest(p).
Combination rules, defining the circumstances in which each instantiated
illocution may be uttered
–
eg It may not be possible to assert a statement and then its negation.

Termination Rules, defining the circumstances in which dialogues terminate.

Rules for creating and combining commitments
–
–
Commitment Stores: publicly-accessible sets of statements, holding the
commitments incurred by participants.
Dialogic and external (semantic) commitments, and rules for their combination.
Agent Interaction Protocols
10
An influential typology of dialogues
Doug Walton and Erik Krabbe (1995) have proposed a typology of human dialogues, based
on: the information known to participants at commencement; their respective
objectives; and the purpose(s) of the dialogue.






Information-seeking dialogues
– One participant seeks the answer to a question which it believes another knows.
Inquiry dialogues
– All participants collaborate to find the answer to a question which no one knows.
Persuasion dialogues
– One participant seeks to persuade other(s) to endorse a statement.
Negotiation dialogues
– Participants seek to divide a scarce resource.
Deliberation dialogues
– Participants collaborate to decide a course of action in some situation.
Eristic dialogues
– Participants quarrel to vent perceived grievances, as a substitute for physical
fighting.
Agent Interaction Protocols
11
Formal Dialogue-Game Protocols

Agent interaction protocols have been designed for:
–
–
–
–

Inquiry dialogues (McBurney & Parsons 2001)
Persuasion dialogues (Dignum, Dunin-Keplicz & Verbrugge 2000)
Negotiation dialogues (Amgoud, Parsons & Maudet 2000; Sadri, Toni & Torroni
2001; McBurney, van Eijk, Parsons & Amgoud 2003)
Deliberation dialogues (Hitchcock, McBurney & Parsons 2001).
These protocols are more constrained than are generic Agent
Communications Languages
–
–
Rules govern combinations of locutions: agents usually cannot say just anything at
anytime.
Usually, the protocol is designed with a specific purpose in mind, and informed by
an explicit theory of argument.
Agent Interaction Protocols
12
Example locutions in a Dialogue Game
Protocol
Locutions for a deliberation dialogue (to jointly decide a course of action):









where:



open_dialogue(Pi, q?)
enter_dialogue(Pj, q?)
propose(Pi, type, t)
assert(Pi, type, t)
prefer(Pi, a, b)
ask_justify(Pj, Pi, type, t)
move(Pi, action, a)
retract(Pi, locution)
withdraw_dialogue(Pi,q?)
Pi, Pj are participating agents
type  {question, goal, constraint, perspective, fact, action, evaluation}
and there are various constraints on, and impacts of, utterance of these locutions.
(Hitchcock, McBurney & Parsons 2001)
Agent Interaction Protocols
13
Example (continued)

For this protocol, the purpose is joint practical reasoning:
–
–

For a group of participants to jointly decide on an action, or course of action, in
some situation
Or, at least, to decide if they have a joint responsibility for such a decision.
The theory of argument made explicit was Harald Wohlrapp’s retroflexive
argumentation model (1998)
–
–
Here, proposed actions and suggested justifications are both modified iteratively,
in the light of reflections on each.
For example:
• The law should allow euthanasia, since this would permit people in terminal
pain to die.
• But such a law could be abused by (say) evil doctors or relatives.
• Thus the law should allow euthanasia only under some conditions, for example,
that two independent doctors agree.
• Etc.
Agent Interaction Protocols
14
Auction mechanisms

The simplest communications protocols are the mechanisms of commerce:
–
–
–
–

At the simplest, these involve illocutions for:
–
–
–

Auction mechanisms
Mechanisms for negotiations
Cake-cutting algorithms, etc.
Called “Game-Theoretic Mechanisms” in AI.
Proposing a deal (a division of some scarce resource)
Accepting or rejecting a proposed deal
(And possibly also) Entering and leaving the interaction.
Because of the rise of e-commerce, these mechanisms have been much
studied within Computer Science/AI of late.
–
See “Agent-Mediated e-Commerce” Workshop series (Springer).
Agent Interaction Protocols
15
Examples of GT protocols

Auction Mechanisms
–
–
–

Combinatorial auctions
–

Bidders may bid on any combination of a set of items.
Continuous Double Auctions (k-CDA)
–
–
–

English (ascending) auctions
Dutch (descending) auctions
Vickrey (second-price) auctions.
Multiple buyers and sellers make bids and asks (respectively)
Transaction price is a function (with parameter k) of bid and ask prices
Used in most organized stock and commodity exchanges.
Monotonic Concession Protocol
–
–
–
2+ participants
Participants may propose (make an offer), counter-propose, accept a proposal, or
withdraw.
Proposals must always concede, relative to previous proposals.
Agent Interaction Protocols
16
Relationship between types of interaction
protocols
Generic ACLs
Dialogue
Game
Protocols
Increasing
expressiveness
Game Theoretic
(Auction)
Mechanisms
Increasing constraints
on utterances
Agent Interaction Protocols
17
Key Research Challenges

Defining the philosophies underlying agent societies
–

Automation of Inquiry, Deliberation and Command dialogues
–
–

We have defined protocols for the conduct of these dialogues.
Key challenge: How are possible hypotheses/action-options generated?
Developing a formal, mathematical theory of interaction protocols
–
–

e.g. Argumentation theories; philosophies of democracy; etc.
To understand the space of protocols in its entirety, and to understand the
relationship between two or more protocols.
Currently under development
• Johnson, McBurney & Parsons
• Drawing on Category Theory and Algebraic Topology.
Understanding the relationships between local and global properties
–
How to achieve dialogue-level properties (e.g. fast termination) using only local
levers (e.g. locution-combination rules)?
Agent Interaction Protocols
18
Semantics for ACLs

Linguistic theory distinguishes between:
–
–
–

Within mathematical logic, the Wittgenstein-Tarskian view of semantics is
as a mapping from the legal formulae or sentences of a logical language to
truth-values.
–
–

Syntax of a language: its words, phrases, sentences and grammar
Semantics of a language: what meanings are assigned to the words, phrases &
sentences
Pragmatics of a language: how the words, phrases and sentences and are used in
conversation.
Truth Values may be viewed as mathematical objects, eg: {0,1}.
Model Theory studies the objects which are semantics for logical languages and
their relationships to one another, as abstract mathematical objects.
In Theoretical Computer Science, there are several types of semantics:
–
–
–
–
Axiomatic
Operational
Denotational
Game-Theoretic.
Agent Interaction Protocols
19
Semantics of ACLs

Considerable work on defining semantics of individual utterances

Less work on semantics of dialogues under a given protocol

No work yet on semantics of protocols

My work is intended to develop a formal semantics of protocols
–
To be able to determine if two protocols are the same or not
–
To understand the relationship between syntactic form of a protocol and the
properties of the dialogues conducted under it.
• This relationship is not continuous.
Agent Interaction Protocols
20
Axiomatic Semantics

An axiomatic semantics articulates the pre-conditions and post-conditions
of an utterance
–
–


FIPA ACL has been given a formal, axiomatic semantics using speech act
theory from the philosophy of language.
Speech acts are utterances which are intended to change the world in some
way.
–
–
–

The semantics define the pre-conditions required for an utterance to be validly
made, and the post-conditions which occur upon its utterance.
This is usually done in a formal logical language, such as First-Order Logic.
“I name this ship, The Queen Elizabeth.”
“I declare you man and wife.”
Austin 1955, Searle 1969.
The speech act semantics for FIPA ACL links utterances to the private
mental states of the participants.
–
–
–
Their Beliefs, Uncertain Beliefs, and Intentions.
This semantics has been formalized using modal epistemic logic.
Bretier, Cohen, Levesque, Perrault, Sadek (1979, 1990, 1997).
Agent Interaction Protocols
21
For example: inform

Suppose agent A informs agent B that “It is raining”.

Required Pre-conditions: Before a valid utterance by A:
• A must believe “It is raining”,
• A must not already believe that B has any belief regarding whether or not it
is raining (i.e. A must believe that B has an uncertain belief about this
matter)
and
• A must desire that B also comes to believe “It is raining”.

Post-conditions: Upon receipt by B of such an utterance by A:
• B must believe that A believes “It is raining”
and
• B must believe that A desires that B believes “It is raining”.

Note that following the utterance by A, B may or may not adopt the belief
“It is raining”.
Agent Interaction Protocols
22
Operational Semantics




An operational semantics treats the utterances in an agent interaction as
programming commands on some large, virtual machine
–
The commands acts to change the state of this virtual machine.
–
From a formal axiomatic semantics we can define an operational semantics, which
indicates the state transitions for every possible utterance.
We can therefore view the utterances as functions which cause state
transitions.
Does the virtual machine include the mental states of the interacting
agents?
An operational semantics has been defined for a dialogue game protocol for
consumer purchase negotiations.
–
McBurney, van Eijk, Parsons & Amgoud 2003.
Prior state
of machine
Utterance
Subsequent
state of machine
Agent Interaction Protocols
23
Game Semantics

To each formulae in a language is associated a game
–


A formula is considered to be true iff a designated player (usually
Proponent) has a winning strategy in the associated game.
Example: Ehrenfreucht-Fraisse games
–
–

Usually between 2 imaginary players: Proponent & Opponent
To assess whether two collections of objects are isomorphic, allow each player to
select objects in turn.
One player seeks to show the objects selected are in 1:1 relationship, the other
player that this is not so.
Used in model theory, and also recently in theoretical computer science to
give a semantics for some programming languages.
Agent Interaction Protocols
24
Denotational Semantics

Each formulae is mapped to some object in a mathematical space
–

E.g. Mapping logical formulae to the set {True, False} or {0,1}.
The standard semantics for modal logic languages is the Possible Worlds
semantics
–
–
–
Due to Leibniz, Kanger (1957), Kripke (1959/1962), Hintikka (1962) (and Everett
1957)
This is a collection of states of the world, at each of which some propositions are
true and some not.
Some worlds are connected by accessibility relationships, indicating (for example)
that it is possible to move from one world-state to another.
Agent Interaction Protocols
25
Negotiation and Deliberation

Deliberation Dialogues are dialogues over possible actions (or courses of
action)
–


Deliberations typically involve one or more participants making proposals for
action, which all parties then consider.
We assume that the interaction protocol enables participants to:
–
–
–
–

Negotiation dialogues are a special case of Deliberations, where the actions are
intended to divide some scarce resource.
Suggest proposals for action
Accept or reject proposals which have been suggested
Express a preference between two suggested proposals
Commit to execute a specific proposal.
We also assume that time is represented by a set common to all participants
which is countable, and that exactly one utterance occurs at each timepoint.
Agent Interaction Protocols
26
A category-theoretic semantics

At each time point t:
– We specify a proto-category representing the public utterances in the
dialogue up to that time
• Called the Dialogue (or Public) Store
• Objects: Proposed actions
• Arrows: Expressed preferences between actions.
– We specify a proto-category for each participant
• Called the Private Store of the Participant
• Objects: Possible actions under consideration by the Participant
• Arrows: Determined preferences between actions
• One distinguished object: ND (“No Deal”), representing
termination of the deliberation without an agreement on an action
being reached.

For these entities to be categories, the participants’ preferences
must be transitive.
Agent Interaction Protocols
27
Private Store: Participant 1
Private Store: Participant 2
B
A
F
D
D
ND
G
ND
C
A
F
E
Dialogue (Public) Store
B
C
A
E
D
Agent Interaction Protocols
Time t > 8
28
Current Work

Formalize this semantics, and study the mathematical properties of
these structures.
– Not much work in CT on linked sequences of categories.


Represent common deliberation and negotiation protocols in this
way.
Identify categorical constructs analogous to decision-mechanisms
in deliberations and negotiations
– Decisions internal to the participants
– Judgment aggregation decisions in the dialogue (eg voting).
Agent Interaction Protocols
29
Further reading:

Agent-Enabled Computing
–
–
–

Game-theoretic Interaction Mechanisms:
–
–

M. Luck, P. McBurney and C. Preist (2003): Agent Technology: Enabling Next
Generation Computing. AgentLink II Network of Excellence.
• Available from: www.agentlink.org
M. J. Wooldridge (2002): Introduction to Multi-Agent Systems (Wiley)
M. J. Wooldridge (2000): Reasoning About Rational Agents (MIT Press).
J. S. Rosenschein & G. Zlotkin (1994): Rules of Encounter (MIT Press)
S. Kraus (2001): Strategic Negotiation in Multiagent Environments (MIT Press).
Agent Communications Languages and Dialogue Game Protocols:
–
–
–
–
www.fipa.org
www.cs.umbc.edu/kqml/
M-P. Huget (Editor) (2003): Communication in Multi-Agent Systems: Agent
Communication Languages and Conversation Policies. (Springer, LNAI 2650).
F. Dignum (Editor) (2003): Advances in Agent Communication. (Springer LNAI
2922) (forthcoming).
Agent Interaction Protocols
30
Finally . . .
Thank you for inviting me and for listening!
Agent Interaction Protocols
31
Combining dialogues of different types

Most real human dialogues are complex combinations of primary types
–

e.g. Analysis of environmental risk of new technologies involves combinations of
Information-seeking, Information-Provision, Inquiry, Persuasion, Negotiation,
Deliberation, Command, and even Eristic dialogues.
There are two proposals for formalisms to represent combinations of agent
dialogues:
–
–
–
Reed’s Dialogue Frames (1998) can represent iterated, sequential & embedded
dialogues.
• This formalism is neutral regarding the syntax used in each dialogue.
McBurney & Parsons ADF (2002) can represent iterated, sequential, parallel &
embedded dialogues.
• This formalism is a dialect of Dynamic Modal Logic, and is potentially
generative, i.e. it can be used generate many types of dialogues automatically.
Both formalisms permit the incorporation of new primary types of dialogues.
Agent Interaction Protocols
32
Semantic Verification
Problem: How to verify that an agent using an ACL conforms to the (private)
semantics of that ACL?
–
i.e. How to verify that an agent really believes (or prefers or intends) what it
says it does?
Proposed Partial Solutions:

Social Semantics (Singh)
–
–

Have agents profess their beliefs and intentions publicly
Then check their subsequent utterances for consistency against these
professions.
Semantic Contestability (McBurney & Parsons)
–
–
–
Allow participants to question and contest each other’s statements
Require agents to provide justifications for assertions (of beliefs, preferences,
intentions) and allow argument over these justifications
There is a connection here with the verificationist theory of truth of Michael
Dummett and Crispin Wright.
Agent Interaction Protocols
33
Automation of ACL dialogues
Agent interactions to jointly decide use of shared resources have used:

Theories of Persuasion
–
–

Adopted from psychology (Abelson 1960, 1970):
Example: Sierra, Jennings, Noriega & Parsons 1998.
• Agents offer threats/rewards to persuade others to adopt proposals
• Acceptance/rejection based on relative positions in a social hierarchy.
Argumentation Theory
–
Parsons, Sierra & Jennings 1998.
• An agent generates a proposal by constructing an argument (a tentative
proof) for an intention it has, and communicating this to the other
participants.
• The other agents attempt to counter this argument, and only accept it if
they fail to counter it.
• Uses the Logic of Argumentation of Cancer Research UK.
Agent Interaction Protocols
34
Automation of DG dialogues (1)

Negotiation dialogue protocol of Amgoud, Parsons & Maudet 2000
–
–
–
–

7 Locutions: assert, accept, question, challenge, request, promise, refuse.
Locutions may be instantiated with propositions and arguments for propositions.
Agents vested with an argumentation mechanism, to generate arguments for
propositions and to accept or reject arguments received from other agents.
Not quite automatic.
Negotiation dialogue protocol of Sadri, Toni & Torroni 2001.
–
–
–
–
–
Based on Amgoud, Parsons and Maudet 2000.
6 Locutions: accept, challenge, request, promise, refuse, justify.
Agents co-operate to agree the use of possibly-scarce resources.
Agents vested with abductive logic mechanisms (if-then rules).
• These determine which locution should next be uttered, based on the most
recent locution uttered and the current status of the agent’s resources
knowledge base.
No theoretical grounding for these if-then rules.
Agent Interaction Protocols
35
Automation of DG dialogues (2)

A Consumer Purchase Transaction Protocol
–
–
A protocol for purchase negotiations for consumer durables, based on a standard
decision model from marketing theory (Roberts & Lilien 1993).
11 illocutions:
• open_dialogue
• enter_dialogue
• seek_info
• willing_to_sell
• desire_to_buy
• prefer
• refuse_to_buy
• refuse_to_sell
• agree_to_buy
• agree_to_sell
• withdraw_dialogue.
Agent Interaction Protocols
36
Automation of DG dialogues (2) (continued)

Based on the marketing theory decision model, we have defined semantic
decision mechanisms for the participating agents, e.g.
–
–
–

Agents vested with these decision mechanisms and using the protocol may
engage in automated dialogues.
–

Seek_Information
Provide_Information
Assess_Options, etc.
This is proven by defining an Operational Semantics for the protocol, a formal
definition of the locutions in terms of their effects on the interaction statespace.
Protocol due to:
–
McBurney, van Eijk, Parsons & Amgoud 2003.
Agent Interaction Protocols
37
Descargar

No Slide Title