Transcript Document

Agent Communications
• Necessity
• Communication languages
• Communication architectures
Motivation for Agent Communication
”Language is a very difficult thing to put into words” –
Voltaire
1.
Communication is required for cooperation between agents
2.
Societies can perform tasks no individual agent can
3.
Communicating agents need only know a ”common language”
4.
Supports heterogenous agents
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
Component steps of communication
Speaker
Hearer
 Intention
 Generation
 Synthesis
Syntax
 Perception
Semantics
 Analysis
Pragmatics
 Disambiguation
 Incorporation
3
Artificial Communication
in a multi-agents system
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
4
ACL
• Agent Communication Language (ACL) is based on
speech-act theory .
• Speech Acts
...speaking a language is performing speech acts, acts such
as making statements, giving commands, asking questions,
making promises, and so on. - John Searle
Speech Acts
• 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 Austin’s 1962 book, How to Do Things
with Words
Theory of Speech Acts
J. Austin - How to do things with words, 1962, J. Searle - Speech acts, 1969
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"
locution
illocution
content
prelocution: door closed (hopefully!)
Illocutionary aspect - several categories
 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 Ruritania
 Expressives, which express emotions and evaluations: I am happy
7
The Speech Act Model
An utterance is a spoken word or
string of spoken words. At the
simplest level, to utter is simply to
say a word with no particular
forethought or intention to
communicate a meaning.
Propositional Utterance is a more
meaningful type of utterance makes
reference to or describes a real or
imaginary object.
An illocutionary utterance is spoken
with the intention of providing
information, soliciting answers to
questions, giving praise, and so on
Perlocutionary utterances, on the
other hand, do attempt to effect a
change.
ACLs – communication as action
- communicative acts
- standard formats for the exchange of messages
KQML and KIF
• The best known ACL is KQML, developed by
the ARPA knowledge sharing initiative
KQML is comprised of two parts:
– the knowledge query and manipulation language
(KQML)
– the knowledge interchange format (KIF)
KQML
• KQML is an ‘outer’ language, that defines various
acceptable ‘communicative verbs’, or
performatives
Example performatives:
– ask-if (‘is it true that. . . ’)
– perform (‘please perform the following action. . . ’)
– tell (‘it is true that. . . ’)
– reply (‘the answer is . . . ’)
Categories of KQML performatives
1.
2.
3.
4.
5.
6.
7.
Basic Query performatives
Multi-response query performatives
Response performatives
Generic Informational performatives
Generator performatives
Capability performatives
Networking performatives
1. Query performatives:
ask-one, ask-all, ask-if, stream-all,...
(ask-one :sender joe
(tell :sender willie
:receiver ibm-stock
:receiver joe
:reply-with ibm-stock
:reply-with block1
:language PROLOG
:language KIF
:ontology NYSE-TICKS
:ontology BlockWorld
:content (price ibm ?price) )
:content (AND (Block A)(Block B)
(stream-all
:sender willie
:receiver ibm-stock
:content (price ?VL ?price ) )
(standby
:content (stream-all
A
:content (price ?VL ?price) )
stream-all(P)
A
tell(P1)
tell(P2)
eos
A
(On A B)) )
ask-all(P)
ask-one(P)
B
B
tell(P)
tell(P1,P2,...)
B
13
2. Generator performatives:
standby, ready, next, rest, discard, generate,...
3. Response performatives:
reply, sorry ...
insert(P)
A
4. Generic informational performatives:
tell, untell, insert, delete, ...
5. Capability performatives:
advartise, subscribe, recommend...
delete(P)
B
tell(P)
A
untell(P)
B
6. Network performatives:
register, unregister, forward, route, ...
Facilitator
In fact, KQML contains only 2 types of illocutionary acts:
assertives and directives
+ facilitator and network-related performatives (no
necessarily speech acts)
14
Facilitator agent
= 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
ask(P)
matchmaking between information providers and clients
providing mediation and translation services
A
tell(P)
subscribe(ask(P))
A
B
tell(P)
tell(P)
B
recommend(ask(P))
advertise(ask(P))
reply(B)
recruit(ask(P))
advertise(ask(P))
ask(P)
A
B
tell(P)
A
ask(P)
B
tell(P)
15
KQML Examples I
AB - (tell (> 3 2))
AB - (perform (print ”hello” t))
BA – (reply done)
AB - (ask-if (> (size chip1) (size chip2) ))
BA – (reply true)
AB - (subscribe (position ?x ?r ?c))
BA – (tell (position chip1 8 10))
BA – (tell (position chip2 8 46))
BA – (tell (position chip3 3 64))
AB - (unsubscribe (position ?x ?r ?c))
KQML Examples II
(ask-one :content (geoloc TRD (?long ?lat))
:ontology geo-model3)
(ask-all
:content ”price(IBM, [?price, ?time])”
:receiver stock-server
:language standard-prolog
:ontology NYSE-TICS)
KIF – Knowledge Interchange Format
KIF is a language for expressing message
content
Used to state:
• Properties of things in a domain (e.g., “Noam
is chairman”)
• Relationships between things in a domain (e.g.,
“Amnon is Yael’s boss”)
• General properties of a domain (e.g., “All
students are registered for at least one course”)
KIF examples - I
Terms:
(size chip1)
(+ (sin theta)(cos theta))
(if (> theta 0) theta (-theta))
(setofall ?x (above ?x chip1))
Sentences:
(Prime 565762761)
(> (sin theta) (cos phi))
(not (> (sin theta) 0)))
(> (* (width chip1) (length chip2))(*(width chip1)(length chip2)))
(=> (> ?x 0) (positive ?x))
KIF Examples - II
Definitions:
(defrelation leq(?x ?y) := (not (> ?x ?y)))
(defrelation natural(?x) := (and (integer ?x) (>= ?x 0)))
Procedures:
(progn (fresh_line t)(print ”Hi!”)(fresh_line t))
Meta-Knowledge:
(believes John ’(material moon jarlsberg))
(=> (believes John ?p) (believes Mary ?p))
Rules:
(<<= (flies ?x)(bird ?x))
KQML Statement Structure
•
KQML Statements consists of
1. A performative
2. Parameters and context information
General syntax:
(KQML-performative
:sender word
:receiver word
:language word
:ontology word
:content expression
...)
• A formal specification of a set of terms is
known as an ontology
• The knowledge sharing effort has
associated with it a large effort at defining
common ontologies
- software tools like ontolingua
Ontologies
Person
Ontology = a specification of objects, concepts, and
reationships in a particular domain; it comprises a
Empl
Stud
Pupil
vocabulary, a domain theory and a conceptual
schemata to describe organization and
interpretation
IBM_E Sun_E
An ontology is more than a taxonomy of classes,
it must also describe relationships
Joe
Alice
x (Block x)  (PhysicalObject x)
Instead of (Block A)
(InstanceOf A Block)
(Class Block)
Hierarchy
(Class PhysicalObjects)
(SubclassOf Block PhysicalObjects)
 x,y,z (InstanceOf x y)  (SubclassOf y z) 
(InstanceOf x z)
Ontology editors frame-based KR systems that allow the
user to define an ontology and its components: classes,
instances, relationships, and functions
Person
Man
Empl
Joe
Woman
Stud
Alice
22
KQML Agent naming
•
System for mapping agents into names is important in
most ACLs
KQML assumes that names are local
•
–
–
•
•
A can register with B under the name Alice
A can register with C under the name Albert
Doesn’t preclude the use of a central Agent Name Server,
an architecture used by most systems
What gets registered under a name? Contact information
like:
name(amundbot, tcpip, [cavenan.idi.ntnu.no,80]).
name(amundbot,smtp,[[email protected])
name(amundbot,http,[www.jfipa.org:80/])
Facilitators - I
Agents performing various (useful) communication services
1.
2.
3.
4.
5.
Maintain registry of service names
Forward messages to named services
Route messages based on content
Provide ”matchmaking”
Provide mediation and translation services
Routers
•
•
•
•
•
•
Content-independent message routers
Each KQML-agent is associated with its own
separate router process
Router handles all outgoing/incoming ACL messages
Outgoing messages can specify a particular agent
address (to agent or router)
Message can specify a description of context
Delivery of messages is not guaranteed
Other ACLs
•
•
Telescript – supports mobile computing
FIPA ACL – competing/extending KQML
•
FIPA vs KQML
–
–
–
–
–
Both are based on speech act
Different set of performatives
FIPA has a more formal basis
FIPA can describe interaction protocols
FIPA is probably becoming the standard ACL
FIPA’s Agent Communication Language Specifications
• More recently, the Foundation for Intelligent Physical
Agents (FIPA) started work on a program of agent
standards — the centerpiece is an ACL
• Basic structure is quite similar to KQML:
– performative
20 performative in FIPA
– housekeeping
e.g., sender, etc.
– content
the actual content of the message
FIPA Example
(inform
:sender
:receiver
:content
:language
:ontology
)
agent1
agent5
(price good200 150)
sl
hpl-auction
FIPA
“Inform” and “Request”
• “Inform” and “Request” are the two basic
performatives in FIPA. All others are macro
definitions, defined in terms of these.
• The meaning of inform and request is defined
in two parts:
– pre-condition
what must be true in order for the speech act to
succeed
– “rational effect”
what the sender of the message hopes to bring
about
“Inform”
• For the “inform” performative…
The content is a statement.
Pre-condition is that sender:
– holds that the content is true
– intends that the recipient believe the content
– does not already believe that the recipient is aware
of whether content is true or not
“Request”
• For the “request” performative…
The content is an action.
Pre-condition is that sender:
– intends action content to be performed
– believes recipient is capable of performing this
action
– does not believe that receiver already intends to
perform action
What 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’s goal is pursued by making available in a timely
manner, internationally agreed specifications that
maximise interoperability across agent-based
applications, services and equipment.
http://www.fipa.org/
Who is FIPA?
•
•
•
•
FIPA operates through the open international
collaboration of member organisations, which are
companies and universities active in the agent field.
Companies: Alcatel, Boeing, British Telecom, Deutsche
Telekom, France Telecom, Fujitsu, Hitatchi, HP, IBM,
Fujitsu, Hewlett Packard, IBM, Intel, Lucent, NEC,
NHK, NTT, Nortel, Siemens, SUN, Telia, Toshiba, etc.
Universities and Research Institutes: GMD, EPFL,
Imperial, IRST, etc.
Government Agencies: DARPA
FIPA Encodings and package
Fipa supports three main types of syntax encoding:
1. Extensible Markup Language – XML
2. Proprietary Binary format
3. Lisp-like format
•
Separates between Envelopes and Messages
Example - XML-encoded FIPA ACL
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
<?xml version="1.0"?>
<envelope>
<params index="1">
<to>
<agent-identifier>
<name>[email protected]</name>
<addresses>
<url>http://foo.com/acc</url>
</addresses>
</agent-identifier>
</to>
<from>
<agent-identifier>
<name>[email protected]</name>
<addresses>
<url>http://bar.com/acc</url>
</addresses>
</agent-identifier>
</from>
<acl-representation>fipa.acl.rep.xml.std</acl-representation>
<date>20000508T042651481</date>
<encrypted>no encryption</encrypted>
<received >
<received-by value="http://foo.com/acc" />
<received-date value="20000508T042651481" />
<received-id value="123456789" />
</received>
</params>
</envelope>
Binary encoded FIPA XML
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
0xfe 0x00 0x97 0x12 0x20 0x31 0x11 0x06 0x19 0x15 0x37 0x62 0x59
0x20 0x02 0x03 0x02
‘r’ ‘e’ ‘c’ ‘e’ ‘i’ ‘v’ ‘e’ ‘r’ ‘@’ ‘f’ ‘o’ ‘o’ ‘.’ ‘c’ ‘o’ ‘m’ 0x00
0x02 ‘h’ ‘t’ ‘t’ ‘p’ ‘:’ ‘/’ ‘/’ ‘f’ ‘o’ ‘o’ ‘.’ ‘c’ ‘o’ ‘m’ ‘/’ ‘a’
‘c’ ‘c’ 0x00 0x01 0x01 0x02 ‘s’ ‘e’ ‘n’ ‘d’ ‘e’ ‘r’ ‘@’ ‘b’ ‘a’ ‘r’ ‘.’
‘c’ ‘o’ ‘m’ 0x00 0x02 ‘h’ ‘t’ ‘t’ ‘p’ ‘:’ ‘/’ ‘/’ ‘b’ ‘a’ ‘r’ ‘.’ ‘c’
‘o’ ‘m’ ‘/’ ‘a’ ‘c’ ‘c’ 0x00 0x01 0x01 0x08 ‘n’ ‘o’ ‘ ’ ‘e’ ‘n’ ‘c’ ‘r’
‘y’ ‘p’ ‘t’ ‘i’ ‘o’ ‘n’ 0x00 0x0a ‘h’ ‘t’ ‘t’ ‘p’ ‘:’ ‘/’ ‘/’ ‘b’ ‘a’
‘r’ ‘.’ ‘c’ ‘o’ ‘m’ ‘/’ ‘a’ ‘c’ ‘c’ 0x00 0x20 0x31 0x11 0x06 0x19 0x15
0x37
0x62 0x59 0x20 0x03 ‘1’ ‘2’ ‘3’ ‘4’ ‘5’ ‘6’ ‘7’ ‘8’ ‘9’ 0x00 0x01
Shortcomings of current ACLs
•
•
•
•
•
•
Intentional level description: which mental attitudes,
what definitions?
Problems with mental attitudes: from theory to practice
Can all desirable communication primitives be modeled
after speech acts? Should they?
Flexible description of agents’ capabilities and
advertising of such capabilities.
How can we test an agent’s compliance with the ACL?
Ease of extending an ACL
Conclusions of Current ACLs
•
Agent Communication Languages have
a common basis – speech act
•
Syntax is well specified, but current
research is on describing semantics
Motivation for KIF
(Knowledge Interchange Format)
http://logic.stanford.edu/kif/dpans.html
•
•
Creating language for development of intelligent
applications
Creating language for common interchange format
Note:
•
KIF is not intended for interaction with humans
•
KIF is not intended to be internal representation for
knowledge within computer programs
KIF Features
1.
2.
3.
4.
Prefix version of 1st order predicate calculus (logic)
Declarative semantics
Logically comprehensive
Provides representation of knowledge about representation of
knowledge
Additional features:
•
Translatability
•
Readability
•
Usability
KIF General Overview
Variables:
•
?singlevar, @sequence
Operators:
Term Operators: listof, if, ..
Sentence Operators: not, and, /=, ...
Rule Operators: =>>, ..
Definition Operators: defobject, deffunction
Constants:
object, function, relational, logical
Expressions:
Word or a finite sequence of words (i.e. Sentences)
Agent Vocabularies
•
Agents should use words consistently
Open-ended Dictionary
•
Each word has:
–
–
•
English description for understanding by humans
KIF (or alternative) for understanding by computers
Dictionary would contain multiple ontologies for many areas
Ontology Inference Layer – OIL
http://www.ontoknowledge.org/oil/
•
•
•
OIL is used to specify and exchange ontologies
Three roots of OIL:
1.
Description Logics
2.
Frame-based Systems
3.
Web-standards: XML and RDF
Small, not too expressive (as possibly the case with Ontolingua)
OIL Example
ontology-container:
title: ”african animals”
subject: ”animal, food, vegetarians”
description: ”example ontology describing african animals”
Language ”en-uk”
Source http://www.url.com/
ontology-definitions:
slot-def: eats
inverse: is-eaten-by
class-def: animal
class-def: plant
Terminology of Agent Communication
Speech Act – Formal subset of natural language representing actions
ACL – Agent Communication Language
FIPA - Foundation for Intelligent Physical Agents
KQML – Knowledge Query and Manipulation Language
Ontology – ”World Model”, formal description of agent domain
Encoding – syntactic representation of ACL messages
ACC – Agent Communication Channel (FIPA)
KSE – Knowledge Sharing Effort
KIF – Knowledge Interchange Format
Router – entity that sends incoming messages in correct ”direction”
Facilitator – An agent that includes a Router
Semantics on the Web - terminology
Semantic Web
RDF – Resource Decription Framework
OIL – Open Inference Layer
XML/XML Schema
Ontolingua
OKBC – Open Knowledge Base Connectivity
DAML – DARPA Agent Markup Language
DAML-S – Service description language based on DAML
UDDI – Universal Description, Discovery and Integration
WSDL – Web Services Description Language
SHOE – Simple HTML Ontology Extensions
ebXML – e-business XML
Exercise
• Read the paper: kqml-acl.pdf
Present your understanding of the paper in
10-15 minutes in next lecture.