Transcript Document

Multi-Agent Systems
Chapter 2
Adapted (with permission) from
Adina Magda Florea
[email protected]
Candy Quiz
(not for points, just for candy)
• What do each of the following mean?
•
•
•
•
•
•
•
KQML
ACL
Ontology
Illocution
KSE
FIPA
KIF
2
Candy Quiz
(not for points, just for candy)
• What do each of the following mean?
• KQML Knowledge Query Manipulation Language
• ACL Agent Communication Language
• Ontology specification of objects, concepts and
relationship
• Illocution intended meaning - performative
• KSE Knowledge Sharing Efort
• FIPA Foundation for Intelligent Physical Agents
• KIF Knowledge Interchange Format
3
1. The nature of communication
Human communication
 Communication is the intentional exchange of information brought
about by the production and perception of signs drawn from a shared
system of conventional signs (AIMA, Russell&Norvig)  language
 Communication seen as an action (communicative act) and as an
intentional stance (want something to happen)
Component steps of communication
Speaker
Hearer
 Intention
 Generation- create
 Synthesis- organize
Syntax-how structured
 Perception
Semantics-symbol meaning
 Analysis
Pragmatics-interpretation
 Disambiguation
 Incorporation
4
Artificial Communication
 low-level language vs high-level languages
 direct communication vs. indirect communication
Computer communication
 shared memory

message passing
Agent communication/ MAS communication
Communication in MAS = more than simple communication,
implies interaction
The environment provides a computational infrastructure
where interactions among agents take place. The
infrastructure includes protocols for agents to communicate
and protocols for agents to interact
5
Communication protocols = enables agents to
exchange and understand messages
Interaction protocols = enable agents to have
conversations, i.e., structured exchanges of
messages. Can trace series of responses.
Aim  Communication enables agents to:
coordinate their actions and behavior
attempt to change state of the other agents
attempt to get other agents perform actions
6
Communication infrastructure
blackboard (shared memory) or message-based
connected or connection-less (email)
 point-to-point (1), multicast (some), broadcast (all)
push or pull (information given to you or requested)
synchronous or asynchronous
Dimensions of Meaning
(think of examples of each)
• Descriptive/Prescriptive: describe phenomenon vs
proscribe behavior (I am cold)
• Personal/conventional: different meaning to
individual
• Semantics/Pragmatics: interpreted differently than
intended: mental states
• Contextuality: cannot be understood in isolation
• Coverage: language express necessary concepts
• Identity: meaning is dependent on individual
• Cardinality: private message interpreted
differently than public message
8
2. Indirect communication
Reactive agents
2.1 Signal propagation - Manta, A. Drogoul 1993
 An agent sends a signal, which is broadcast into the environment, and
whose intensity decreases as the distance increases
 At a point x, the signal may have one of the following intensities (why?)
V(x)=V(x0)/dist(x,x0)
V(x)=V(x0)/dist(x,x0)2
Agent A

(stimulus triggers
behavior P)

x0 Stimulus
Topological differences
lead to social differences
Agent B
(stimulus triggers
 behavior P)
2.2 Trails - L. Steels, 1995
agents drop "radioactive crumbs" making trails
an agent following a trail makes the trail faint until it disappears
9
2.3 Blackboard systems, Barbara Hayes-Roth, 1985
Cognitive agents
 Blackboard = a common area (shared memory) in which agents





can exchange information, data, knowledge
Agents initiates communication by writing info on the blackboard
Agents are looking for new info, they may filter it
Agents must register with a central site for access authorization
Blackboard = a powerful distributed knowledge paradigm
Agents = Knowledge sources (KS)
events
KS
Blackboard
Control
Pending KS Activations
KS
KS
KS
10
3. Direct communication
Sending messages = method invocation
 The Actor language
– an Actor executes a sequence of actions in reply to
the received message
 Exchange of partial plans
– distributed planning
ACL = Agent Communication Languages
communication as action - communicative acts
11
3.1 Agent Communication Languages
 Concepts (distinguish ACLs from RPC, RMI or CORBA, ORB):
 ACLs handle propositions, rules, and actions instead of objects with no




associated semantics
An ACL message describes a desired state in a declarative language, rather
than a procedure or method invocation
ACLs are mainly based on BDI theories: BDI agents attempt to
communicate their BDI states or attempt to alter others BDI state
ACLs are based on Speech Act Theory
Agent behavior and strategy drive
ACL
communication and lead to conversations
Content language
Ontology
12
Ontology =formal definition of a body of knowledge. The
most typical ontology used in building agents involves a
structural component. Essentially a taxonomy of class and
subclass relations coupled with definitions and relationships
between things. (Jim Hendler)
An ontology is analogous to a data base organization, not the
contents of the database.
Example: To express the idea that a block is a physical object
we might use the FOPL expression:
x (Block x)  (PhysicalObject x)
To state relationships between classes:
x,y,z (instanceOf x y ) (subclassOf y z) (instanceOf x z)
To define a relationship On(X,Y)
(domain On PhysicalObject)
(range On PhysicalObject)
Origins of ACLs
Knowledge Sharing Effort - DARPA, 1990
 External Interface Group - interaction between KBS - KQML
 Interlingua – language for communicating between independent
agents. KIF (not designed as a language to be used by humans)
 Shared, Reusable Knowledge Bases –
 Ontolingua (set of tools written in Lisp for analyzing and
translating ontologies. Uses KIF parser and syntax checker.
Web-based)
14
Theory of Speech Acts
J. Austin - How to do things with words, 1962,
J. Searle - Speech acts, 1969
Treats communication as an action – made to further agent’s intentions
Changes world in a way analogous to physical actions
Need formal representation so planning systems can reason about
them.
A speech act has 3 aspects:
 locution = physical utterance by the speaker
 illocution = the intended meaning of the utterance by the speaker

(performative)
prelocution = the action that results from the locution
Alice told Tom: "Would you please close the door“
15
Human Communication: Intent
may be ambiguous
• Colleague states “I am cold”
• What is the meaning?
• For computers, state performative (KQML)
or Communicative Act (FIPA) so no
ambiguity (except in content itself).
16
Illocutionary aspect - several categories
(According to speech act theory)
 Assertives, which inform: the door is shut
 Directives, which request: shut the door, can pelicans fly?
 Commissives, which promise something: I will shut the door
 Permissive, which gives permission for an act: you may shut the
door
 Prohibitives, which ban some act: do not shut the door
 Declaratives, which causes events: I name you king of Cache
Valley
 Expressives, which express emotions and evaluations: I am happy
17
KQML – Knowledge Query and Manipulation
Language
A high-level, message-oriented communication language and
protocol for information exchange, independent of content syntax
(KIF, SQL, Prolog,…) and application ontology
KQML separates:
 semantics of the communication protocol (domain independent)
 semantics of the message (domain dependent)
3 (conceptual) layers
Describes low level
communication
parameters:
- identity of sender and
receiver
- a unique id associated
with the communication
Content
Communication
Message
Core of KQML
- identity of the network
protocol with which to deliver
the message
- speech act or performative
Optional
- content language
- ontology
18
Syntax
LISP-like list of attribute/value pairs
(tell
(ask-one :sender joe
:receiver ibm-stock
:reply-with ibm-stock
:language PROLOG // of content
:ontology NYSE-TICKS // define terminology
:content (price ibm ?price) )
1. Query performatives: ask-one, ask-all
:sender willie
:receiver joe
:reply-with block1
:language KIF
:ontology BlockWorld
:content (AND (Block A)(Block B)
(On A B)) )
(want all answers to question), ask-if, streamall (multiple response version of ask-all)
A
ask-one(P)
B
(stream-all
:sender willie
:receiver ibm-stock
:content (price ?VL ?price ) )
(standby
:content (stream-all
:content (price ?VL ?price) )
ask-all(P)
A
tell(P)
tell(P1,P2,...)
B
stream-all(P)
A
B
tell(P1)
tell(P2)
eos
19
2. Generator performatives:
standby (be ready to respond), ready, next, rest, discard, generate,...
3. Response performatives:
reply, sorry ...
4. Generic informational performatives:
insert(P)
A
tell (I know it), untell,
insert (add to your VKB), delete, ...
5. Capability performatives:
advertise, subscribe, recommend...
delete(P)
B
tell(P)
A
untell(P)
B
6. Network performatives:
register, unregister, forward, route, ...
Facilitator
20
Knowledge Sharing Effort KSE
• Darpa funded in 1990
• Resulted in
– KQML
– KIF (knowledge interchange format) looks like
first order logic (and, or, forall, exists) cast into
Lisp-like notation
• Used for content part of KQML message
21
Example of KQML Dialog
(evaluate :sender A :receiver B :language KIF
:ontology motors
:reply-with q1
:content (val (torque m1))
(reply
:sender B :receiver A :language KIF
:ontology motors :in-reply-to q1
:content (= (torque m1) (scalar 12 kgf))
22
Another example of KQML
(stream-about // multiple responses wanted
:sender A :receiver B :language KIF :ontology motors
:reply-with q1 :content m1)
(tell :sender B :receiver A :in-reply-to q1
:content (=(torque m1) (scalar 12 kgf))
(tell :sender B :receiver A :in=reply-to q1
:content (= (status m1) normal))
(eos :sender B :receiver B :in-reply-to q1) //end of stream
23
In the next KQML example
• A advertises that it is willing to accept
subscriptions related to m1.
• B responds by subscribing
• A sends message sequence about m1
• A untells the previous fact and gives new
information
• eos ends the stream of messages
24
(advertise :sender A :language KQML :ontology K10
:content (stream-about :language KIF
:ontology motors :content m1)))
(subscribe :sender B :receiver A :reply-with s1
:content (stream-about :language KIF :ontology
motors : content m1))
(tell :sender A :receiver B :in-reply-to s1
:content (=(torque m1)(scalar 12 kgf)))
(tell :sender A :receiver B :in-reply-to s1
:content (=(status m1) normal))
(untell :sender A :receiver B :in-reply-to s1
:content (=(torque m1)(scalar 12 kgf)))
(tell :sender A :receiver B :in-reply-to s1
:content (=(torque m1)(scalar 15 kgf)))
(eos :sender A :receiver B :in-reply-to s1)
25
Facilitator agent
F
= an agent that performs various useful communication services:
maintaining a registry of service names (Agent Name Server)
forwarding messages to named services
routing messages based on content
matchmaking between information providers and clients
providing mediation and translation services
F
subscribe(ask(P))
A
recommend(ask(P))
tell(P)
B
tell(P)
F
advertise(ask(P))
reply(B)
A
ask(P)
B
tell(P)
F
recruit(ask(P))
advertise(ask(P))
ask(P)
A
B
tell(P)
A wants to get all suitable
agents to respond to ask(P).
B has told F it can do
ask(P). F tells B to tell A
26
Semantics of KQML (Labrou & Finin)
Use preconditions and post conditions that govern the use of a performative + the
final state for the successful performance of the performative
Uses propositional attitudes: belief Bel(A,P), knowledge Know(A,S),
desire Want(A,S), intentions Int(A,S)
Preconditions: the necessary states for an agent to send a performative and
for the receiver to accept it and successfully process it; if the preconditions do
not hold, the most likely response is error or sorry
Postconditions - describe the state of the sender after successful utterance of
a performative and of the receiver after the receipt and processing of a
message
Completion condition - the final state after a conversation has taken place
and that the intention (associated with the performative that started the
conversation) has been fulfilled
27
tell(A,B,X)
A states to B that A believes the content X to be true, Bel(A,X)
Pre(A): Bel(A,X)  Know(A, Want(B, Know(B,S))) no unsolicited info
Pre(B): Int(B, Know(B,S))
where S may be any of Bel(B,X) or Bel(B,X)
Post(A): Know(A, Know(B, Bel(A,X)))
Post(B): Know(B, Bel(A,X))
Completion: Know(B, Bel(A,X))
advertise(A,B,M)
A states to B that A can and will process the message M from B, if it receives one
commisive act
Pre(A): Int(Proc(A,M))
Pre(B): NONE
Post(A): Know(A, Know(B, Int(A, Proc(A,M)))
Post(B): Know(B, Int(A, Proc(A,M)))
Completion: Know(B, Int(A, Proc(A,M)
28
Criticisms of KQML
• not fixed performatives – different
implementations don’t interoperate
• transport mechanisms (ways of getting a
message from A to B) not precisely defined
• semantics not rigorous – not adhered to
• missing commissives (make commitment)
• performative set too large and ad hoc
Resulted in FIPA
29
3.3 FIPA - ACL
Foundation for Intelligent Physical Agents, 1996
Goal of FIPA = make available specifications that maximize interoperability across
agent-based systems. SL formal language
Syntax similar to KQML
(inform :sender Agent1
:receiver Agent2
:content (price good2150)
:in-reply-to round-1
: reply-with bid03
FIPA communicative acts
: language S1
Informatives
:ontology hp-auction
- query_if, subscribe, inform, inform_if
:reply-by 10
confirm, disconfirm, not_understood
:protocol offer
Task distribution
:conversation-id conv-1 )
- request, request_whenever, cancel, agree,
refuse, failure
Negotiation
- cfp (call for proposal - initiate), propose,
accept_proposal, reject_proposal
30
FIPA - Semantics
SL (Semantic Language) - a quantified, multi-modal logic, with modal operators:
B  - belief
D  - desire
U  - uncertain belief – neither believes  or its negatation, but believes  more
likely than its negation.
PG  - persistent goal, but will not necessarily plan to bring it about
Bif  - agent believes  or disbelieves 
Uif  - agent has an uncertain belief of  or an uncertain belief of ¬ 
Given that one of the most frequent and serious criticisms of KQML is the lack
of adequate semantics, it is not surprising that the developers of FIPA felt it
important to give comprehensive formal semantics to their language.
31
The semantics of a communicative act is specified as a set of SL's formulae that
describe:
Feasibility preconditions - the necessary conditions for the sender - the sender is
not obliged to perform the CA
Rational effect - the effect that an agent can expect as a result of performing the
action; it also typically specifies conditions that should hold true of the recipient
The receiving agent is not required to ensure that the expected effect
comes about
The sender can not assume that the rational effect will necessary follow
Semantics of inform:
<i, inform(j, )>
Pre: Bi   Bi (Bifj   Uifj )
Post: Bj 
32
Syntax of request:
<k, request(j, )>
Pre: Bk Agent( ,j)   BkIj(Done )
Post: Done()
Agent( ,j) means that the agent of action  is j (j is the
one who can perform the action)
Done( ) means that the action has been done
Effect: agent k is requesting agent j to do action  and
agent k believes that the agent to do the action is j and
it believes that j does not currently intend to do the
action. The effect is that j will do it.
33
Using ACLs in MAS
Any MAS that is to use an ACL must provide:
a finite set of APIs for composition, sending, and receiving ACL
messages
an infrastructure of services that assist agents in naming,
registration, and basic facilitation services (finding other agents that
can do things for your agent)
code for every reserved message type that takes the action
prescribed by the semantics for the particular application;
the code depends on the application language, the domain, and the
details of the agent system using the ACL
34
History of DAML (one possible content language)
HTML defines grammar for interspersing
documents with markup commands.
HTML is fixed – can’t introduce tags
Suppose you want to sell CDs and put price
information on the web.
HTML can markup with layout information, but
browsers won’t know how to interpret content.
What is price? What is title?
XML was developed to provide semantic markup –
helps computers to process information in document
by allowing user defined tags.
DAML (Darpa markup language) is based on XML
35
4. Communication content

Content languages
–
–
–
–
–
–
–

KIF
Prolog
Clips
SQL
FIPA-SL, FIPA-CCL, FIPA-KIF
DAML
XML Xtensible Markup Language
ACL
Content language
Ontology
Ontologies
DARPA Agent Markup Language
The DAML Program officially began in August 2000.
The goal of the DAML effort is to develop a language
and tools to facilitate the concept of the Semantic Web.
36
Interaction protocols
enable agents to have conversations, i.e.,
structured exchanges of messages
Finite automata
Conversations in KQML
Petri nets - more in distributed planning lecture
FIPA IP standards:
– FIPA-query, FIPA-request, FIPA-contract-net,
Finite state automata
Nodes represent states
Arrows represent actions
COOL, Barbuceanu,95
A:B<<ask(do P)
B:A<<accept(do P)
proposeS(P)
B:A<<refuse(do P)
acceptR(P)
rejectR(P)
B:A<<fail(do P)
B:A<<result(do P)
counterR(P)
counterS(P)
Winograd, Flores, 1986
acceptS(P)
rejectS(P)
38
Conversations in KQML
Use Definite Clause Grammars (DCG) formalism for the specification of
conversation policies for KQML performatives
DCGs extend Context Free Grammars in the following way:
non-terminals may be compound terms
the body of the rule may contain procedural attachments, written as "{" and "}" that
express extra conditions that must be satisfied for the rule to be valid
Ex: noun(N)  [W], {RootForm(W,N), is_noun(N)}
S  s(Conv, P, S, R, inR, Rw, IO, Content), {member(P, [advertise, ask-if]}
s(Conv, ask-if, S, R, inR, Rw, IO, Content) 
[ask-if, S, R, inR, Rw, IO, Content] |
[ask-if, S, R, inR, Rw, IO, Content], {OI is inv(IO)},
r(Conv, ask-if, S, R, _, Rw, OI, Content)
r(Conv, ask-if, R, S, _, inR, IO, Content) 
[tell, S, R, inR, Rw, IO, Content] |
problem(Conv, R, S, inR, _, IO)
Labrou, Finin, 1998
39
Petri nets
Ferber, 1997
Petri net = oriented graph with 2 type of nodes:places and transitions;
there are moving tokens through the net - representation of dynamic aspect of processes.
Stores state.
Tokens are moved from place to place, following firing rules.
A transition T is enabled if all the input places P of T contains a token
A marking (state) is a distribution of tokens over places.
A wants to do P,
A cannot do P
B does not want
to do(P)
DA
DB
Request do(P)
B is willing
to do(P)
Refuse do(P)
AR1
Accept/request do(P)
AR2
Fail to do(P)
BR
Completed(P)
Impossible
to do(P)
Notification of end(P)
FA1
FB
Failure
FA2
Satisfaction
40
References
M. Huhns, L. Stephens. Multiagent systems and societies of agents. In Multiagent Systems - A Modern
Approach to Distributed Artificial Intelligence, G. Weiss (Ed.), The MIT Press, 2001, p.79-120.
M. Wooldrige. Reasoning about Rational Agents. The MIT Press, 2000, Chapter 7
Y. Labrou, T. Finin. Semantics and conversations for an agent communication language. In Readings in
Agents, M. Huhns & M. Singh (Eds.), Morgan Kaufmann, 1998, p.235-242.
J. Ferber - Multi-Agent Systems. Addison-Wesley, 1999, Chapter 6
T. Finnin, R. Fritzson - KQML as an agent communication language. In Proc. of the Third International
Conference on Information and Knowledge Management (CIKM'94), ACM Press, 1994.
M. Singh. Agent communication languages: Rethinking the principles. IEEE Computer, Dec. 1998, p.4047.
Y. Labrou, T. Finnin, Y. Peng. Agent communication languages: The current Landscape. IEEE Computer,
March/April 1999, p. 45-52.
FIPA97. "Agent Communication Language" Specification FIPA, 11/28/97
DARPA KSE
KQML
KIF
Ontolingua
FIPA
DAML
http://www-ksl.stanford.edu/knowledge-sharing/
http://www.cs.umbc.edu/kqml/
http://logic.stanford.edu/kif/
http://www-ksl-svc.stanford.edu:5915/&service=frame-editor
http://www.fipa.org/
http://www.daml.org/
41