Transcript SIF8072 Distributed Artificial Intelligence and

Lecture 5: Agent Communication
SIF8072
Distributed Artificial Intelligence
and
Intelligent Agents
http://www.idi.ntnu.no/~agent/
13 February 2003
Lecturer: Sobah Abbas Petersen
Email: [email protected]
Lecture Outline
•
What is an Agent Communication Language (ACL)?
•
Speech Acts
•
ACLs
–
KQML and KIF
–
FIPA ACL
•
Ontologies and The Semantic Web
•
Summary
2
References - Curriculum
•
Wooldridge: ”Introduction to MAS”,
–
•
Chapter 8
T. Finin, Y. Labrou, J. Mayfield. ”KQML as an Agent
Communication Language”. In: J. Bradshaw (ed). Software
Agents, AAAI Press/MIT Press, 1997, pp. 291-316.
•
Not curriculum:
-
Y. Labrou,T. Finin and Y. Peng, ”Agent Communication Languages: The Current
Landscape”, IEE Intelligent Systems, 1094-7167, 1999.
3
Agent Communication Language
An Agents Communication Language
(ACL) provides agents with a means of
exchanging information and knowledge.
…
4
What distinguishes ACLs?
• Earlier attempts at seamless exchange of information and knowledge
between applications:
– e.g. Remote Procedure Calls, Remote Method Invocation, CORBA
• Differences between the above and ACLs are:
– Semantic complexity
– ACLs can handle propositions, rules and actions instead of simple objects
with no semantics associated with them.
– An ACL message describes a desired state in a declarative language,
rather than a procedure or a method.
5
Agent Communication
• Agents have conversations (as opposed to exchange single
messages), e.g.
– Task-oriented
– Negotiations
• A higher level conceptualisation of an agent’s strategies
drive an agent’s communicative behaviour.
• Message type of agents : Speech Acts
6
Speech Acts 1
• Communication in MAS is inspired by speech act theory.
• Speech act theories are pragmatic theories of language, i.e.
theories of language use:
– they attempt to account for how language is used by people every
day to achieve their goals and intentions.
• The origin of speech act theories are usually traced to the
work of the philosopher John Austin.
7
Speech Acts 2 - Austin
• Austin noticed that some utterances are like ”physical
actions” that appear to change the state of the world. e.g.
– Declaring war
– ”I now pronounce you man and wife”
• In general, every thing we utter is uttered with the intention
of satisfying some goal or intention.
 A theory of how utterances are used to achieve intentions
is a speech act theory.
8
Speech Acts 3 - Austin
•
Austin distinguished 3 different aspects of speech acts:
1.
Locutionary act - act of making an utterance
•
2.
Illocutionary act – action performed in saying something
•
3.
e.g. saying ”please make some tea” ’
e.g. he requested me to make some tea
Perlocution – effect of the act
•
e.g. he got me to make tea
9
Speech Acts 4
Types of Speech Acts
•
Searle identified 5 different types of speech acts:
Speech Act Type
Description and Example
Representatives or
Assertives
Informing
e.g. ”It is raining”.
Directives
Speaker tries to make the hearer do something
e.g. ”Please close the window”
Commisives
Commits the speaker to future action
e.g. ”I will close the window”
Expressives
Speaker expresses a mental state
e.g. ”Excuse me”, ”congratulations”
Declaratives
Effect some changes
e.g. ”I name this city Trondheim”
10
Speech Acts 5 - Components
•
In general, speech acts can be seen to have 2 components:
1.
A performative verb
•
2.
e.g. Request, inform
Propositional content
•
Speech Act
e.g. ”the window is closed”
Please close the
door
Performative request
Content
the door is closed
The door is closed
Is the door
closed?
inform
inquire
the door is closed
the door is closed
11
Speech Acts 6 – Plan-based Theory
•
How does one define the semantics of speech acts? When can one
say someone has uttered, e.g. a request or an inform?
•
How can the properties of speech acts be represented such that
planning systems could reason about them?

Speech acts are treated as physical actions.

Actions are characterised via preconditions and postconditions.
12
Speech Acts 7
Plan-based Theory Example
•
Semantics for request: request(s,h,)
•
Pre:
–
s believes h can do 
(you don’t ask someone to do something unless you think that they can do it)
–
s believes h believes h can do 
(you don’t ask someone unless they believe they can do it)
–
s believes s wants 
(you don’t ask someone unless you want it!)
•
Post:
–
h believes s believes s wants 
(the effect is to make them aware of your desire)
13
Agent Communication Language
(ACL)
Agenti
Goal G
Agentj
Intent I
Performative
Convert to
transport
form
Message
Convert to
transport
form
ACLs allow agents to
effectively communicate
and exchange
knowledge with other
agents.
Message delivery/transportation service
14
Three Important Aspects
Syntax
1.How the symbols of communication are
structured.
Semantics
2. What the symbols denote.
Pragmatics
3. How the symbols are interpreted.
(Meaning is a combination of semantics and pragmatics.)
15
Communication Levels
Semantics
Meaning of the information
Syntax
Format of information being transferred
Communication
Method of interconnection
16
Requirements for an ACL
• Syntactic translation between languages
Syntactic
• Semantic content preservation among
applications
Semantic
– The concept must have a uniform meaning across
applications.
• Ability to communicate complex attitudes
Communication
about their information and knowledge.
– Agents need to question, request, etc.
– Not about transporting bits and bytes.
17
Origins of ACLs
• Knowledge Sharing Effort (KSE), funded by ARPA
– Central concept: knowledge sharing requires communication, which
in turn requires a common language. KSE focused on defining that
common language.
 KQML: Knowledge Query and Manipulation Language
– Language for both message formatting and message handling protocols.
 KIF: Knowledge Interchange Format
– Langauge for expressing message content.
18
KIF 1
• Motivation: creation of a common language for
expressing properties of a domain.
– Intented to express contents of a message; not the
message itself.
– Based on first-order logic.
19
KIF 2
• Using KIF, it’s possible to express:
– Properties of things in a domain
• e.g. Michael is a vegetarian – Michael has the property of being a
vegetarian
– Relationships between things in a domain
• e.g. Michael and Janine are married – the relationship of marriage
exists between Michael and Janine.
– General properties of a domain
• e.g. Everybody has a mother.
20
KIF 3 - Example
• Relation between 2 objects:
– The temperature of m1 is 83 Celsius:
(=
(temperature m1) (scalar 83 Celsius))
• Definition of new concept:
– An object is a bachelor if this object is a man and not married:
(defrelation bachelor (?x) :=
(and (man ?x)
(not (married ?x))))
• Relationship between individuals in the domain:
– A person with the property of being a person also has the property of
being a mammal:
(defrelation (person ?x) :=> (mammal ?X))
21
KQML 1
• An “outer language” that defines a set of
performatives (communicative acts), such as ask,
reply.
e.g.
Communication
Mechanics of communication, e.g. Sender, receiver.
Performatives (message layer)
(ask-if
:sender
agenti
:receiver
agentj
Logic of communication, e.g. ask, tell.
:language Prolog
Content
Content of communication,
e.g. a KIF expression
:ontology genealogy
:content
“spouse(adam, eve)”)
22
KQML 2 - Performatives
• The idea of communication in KQML is to represent
illocutionary acts.
• Performatives form the core of the language:
– Determine the kinds of interactions one can have with KQMLspeaking agents.
– Identify the protocol to be used to deliver the message
– Signify that the content is an assertion, a query, a command or
another speech act.
– Describe how the sender would like any reply to be delivered.
23
KQML 3
Categories of Performatives
Category
Performatives
Basic Query
evaluate, ask-if, ask-one, ask-all, ask-about
Multi-response Query
stream-about, stream-all
Response
reply, sorry
Generic informational
tell, achieve, cancel, untell
Generator
standby, ready, next,rest, discard, generator
Capability-definition
advertise, subscribe, monitor, import, export
Networking
register, unregister, forward, broadcast, route
24
KQML 4 - Examples
(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)))
25
KQML 5 - Examples
(stream-about
:sender A : receiver B
:language KIF: ontology motors
:reply-with q1 :content (m1)
(tell
:sender B : receiver
:in-reply-to q1
:content (= (torque
(tell
:sender B : receiver
:in-reply-to q1
:content (= (status
(eos
:sender B : receiver
:in-reply-to q1)
A
m1) (scalar 12 kgf)))
A
m1) (normal)))
A
26
Facilitators 1
• KQML environments (may) contain facilitators that help make the
communication protocol transparent.
• Facilitators: a special class of agents that perform useful
communication services such as:
– Maintain registry of service names
– Forward messages to named services
– Routing messages based on content
– Provide matchmaking between information providers and seekers
– Provide mediation and translation services
27
Facilitators 2
Point-to-point protocol
F
A is aware that it is appropriate
tell(X)
to send a query about X to B
ask(X)
A
There are several ways to achieve
B
this via a Facilitator.
28
Facilitators 3
tell(X)
subscribe(ask(X))
Using the subscribe performative
Request that Facilitator F monitor
F
for the truth of X. If B subsequently
tell(X)
informs F that it believes X to be
true, then F can in turn inform A.
A
B
29
Facilitators 4
advertise(ask(X))
broker(ask(X))
Using the broker performative
tell(X)
F
A Asks Facilitator to find another agent
tell(X)
ask(X)
which can process a given performative.
A
B
30
Facilitators 5
advertise(ask(X))
recruit(tell(X))
Using the rercruit performative
F
Asks Facilitator to find an appropriate
ask(X)
agent to which an embedded
tell(X)
performative can be forwarded. A reply
is returned directly to the original agent.
A
B
31
Facilitators 6
recommend(ask(X))
advertise(ask(X))
Using the recommend performative
reply(B)
F
Asks Facilitator to respond with the ”name”
of another agent which is appropriate for
sending a particular performative.
ask(X)
A
tell(X)
B
32
KQML Criticism
•
Weak semantics of performatives
–
Different implementations of KQML could not interoperate.
•
Transportation mechanisms were not defined.
•
Lacked the class of performatives: commissives
–
Difficult to implement multi-agent scenarios without commissives.
•
Set of performatives was large and ad hoc.

Recently, more efforts have been made to provide formal semantics
in terms of preconditions, postconditions and completion
conditions. (ref: Labrou et. al., 1999.)
33
Who is FIPA?
•
The Foundation for Intelligent Physical Agents (FIPA)
is a non-profit association.
•
FIPA’s purpose is to promote the success of emerging
agent-based applications, services and equipment.
•
FIPA operates through the open international
collaboration of member organisations: companies,
universities and government organisations.
34
FIPA ACL 1
•
Basic structure is quite similar to KQML:
–
Performative (communicative act)
•
–
Housekeeping
•
–
20 performatives in FIPA ACL
e.g. Sender
Content
•
the actual content of the message
35
FIPA ACL 2
Message Structure
Envelope
•
Envelope:
(transport information)
–
Message body
Comprises of a collection of
parameters
(ACL message)
–
Contains atleast the
mandatory to and sender
parameters
36
FIPA ACL 3
•
Example FIPA ACL message:
(inform
:sender
agentA
:receiver
agentB
:content
(price good200 150)
:language
sl
:ontology
hpl-auction
)
37
FIPA ACL 4
Inform and Request
•
Inform and Request are the two basic performatives in
FIPA ACL. All others are macro definitions, defined in
terms of these.
•
The meaning of inform and request are defined in 2 parts:
1.
Precondition
•
2.
What must be true in order for the speech act to succeed.
Rational effect
•
What the sender of the message hopes to bring about.
38
FIPA ACL 5
Inform and Request
Inform
Request
Content
statement
action
Precondition
•Holds that the content is true.
•Intends action content to be
performed
•Intends that the recipient
believe the content
•Does not already believe that
the recipient is aware whether
content is true or not
•Believes recipient is capable
of performing this action
•Does not believe that sender
already intends to perform action
39
FIPA Message Transport Model
Agent A
Agent B
Agent Platform
Agent Platform
ACL message sent
over the Message
Transport Service
Agent Communication Channel
Agent Communication Channel
Message Transport Protocol
40
FIPA Sending Messages
•
3 options
1.
Via local ACC
2.
Via remote ACC
3.
Direct communication mechanism
Agent A
Agent B
Agent Platform
Agent Platform
3
1
Agent Communication Channel
2
1
1&2
Agent Communication Channel
41
FIPA Agent Interaction Protocol 1
•
Ongoing conversations between agents fall into typical
patterns. In such cases, certain message sequences are
expected, and at any point in the conversation, other
messages are expected to follow.

These typical patterns of message exchange are called
protocols.
(request
:sender A
:receiver B
:content some-act
:protocol fipa-contract-net
)
42
FIPA Contract Net Protocol 1
cfp
action
preconditions1
Not-understood
refuse
reason
propose
preconditions2
Deadline
for proposals
manager
reject-proposal
reason
accept-proposal
proposal
failure
reason
inform
Done(action)
Manager cancels
the contract
due to a change
cancel
reason
Potential
contractors
43
FIPA Contract Net Protocol 2
Potential
contractors
Manager
cfp
refuse
not-understood
deadline
propose
reject-proposal
accept-proposal
cancel
inform
44
Comparing KQML and FIPA ACL
•
Similarities:
•
Separation of the outer language (performative) and the inner language
(content).
•
•
Allows for any content language
Differences
•
•
Communication primitives:
•
KQML – performative
•
FIPA ACL – communicative act
Different semantic frameworks – impossible to come up with an exact
mapping or transformation between KQML and FIPA performatives.
•
KQML provides facilitator services; FIPA ACL does not.
45
Ontologies
•
“An ontology is a formal explicit specification of a shared
conceptualisation.” (Gruber 1993)
•
Why do we need an ontology?
–
•
To agree on a terminology to describe a domain.
Example of a language for defining ontologies: KIF
Common Ontology
(Interlingua)
•
Ontolingua is one of the best known
ontologies developed using KIF.
•
A web-based service intended to provide
a common platform in which ontologies
developed by different groups can be
Agent A
Agent B
Agent C
shared.
46
Ontology and Semantic Web
•
Tim Berners-Lee considers ontologies as a critical part of the work
on the Semantic Web.
•
Semantic Web: ”an extension of the current WWW, in which
information is given well-defined meaning, better enabling
computers and people to work in cooperation.” (Berners-Lee et. al.,
2001)
WWW
(medium of documents
for poeple)
Today
Ontologies
Semantic Web
(Information that can
be processed
automatically,
by agents)
Tomorrow
47
Ontology Languages for
The Semantic Web
Semantic Web
XML
RDF
RDFS
Xtensible Markup
Language
Resource Description
Framework
RDFschema
(+schema)
48
Ontology Languages 1
•
XML: allows users to add arbitrary structure to their documents,
but does not give meaning about the structures.
•
RDF: Resource Description Framework – to standardise metadata descriptions of web-based resources
•
object-attribute-value triple – A(O,V) object O has attribute A with
value V.
•
RDFS: introduces basic ontological modelling primitives.
•
÷
e.g. classes, subclasses, properties, domains and ranges.
Limitations: cannot express many types of knowledge
49
Ontology Languages 2
•
OIL – Open Interface Layer
•
DAML: DARPA Agent Markup Language – based on
XML
•
DAML+OIL – successor of OIL
50
Ontology Inference Layer - OIL
•
Requirements:
1.
Must be intuitive to the human user;

OIL incorporates the essential modelling primitives of frame-based
systems.
2.
Must have a well-defined semantics;

formal semantics inherited from Description Logics.
3.
Must have a proper link with existing web languages;

OIL has well-defined syntax in XML and it is an extension of RDF and
RDFS.
51
Summary
• Speech Acts
• ACLs
– KQML and KIF
– FIPA ACL
• Ontologies and The Semantic Web
52
Next Lecture: Agent Theory
Will be based on:
”Logics for Multiagent Systems”,
Chapter 12 in
Wooldridge: ”Introduction to MultiAgent
Systems”
53