Topic 6: Communication and Interaction Protocols

Topic 5: Communication and Negotiation Protocols Communication and ACLs direct vs. indirect communication speech act theory ACLs - KQML / FIPA-ACL Negotiation protocols contract-net protocol auction protocols Notation - AUML 1. Communication and ACLs communication the basis for any interaction effected through signals

Indirect communication Message passing information available for all direct exchange no direct communication common language simple architecture conversation - sequences of

messages Agent Agent Agent Agent Blackboard Agent Agent Agent A Message Agent B (Sender) (Receiver) Direct communication message passing some of the challenges distributed systems

brokering, naming services, discovery, infrastructure for sending messages heterogeneous entities language, developer, execution environment, multi-agent systems objects agents why something different? messages speech acts an example MAS with cognitive of practical reasoning agents

focus on mental states messages must have a meaning to other agents e.g. agent 1 sends message to agent 2: doSomething(x) must be semantically clear what does this mean to agent 2 ? how should/could he respond ? agent 1 asks agent 2 to do x ? part of negotiation protocol ? agent 1 tells agent 2 to do x ? assuming a commitment ? agent 1 relies on the fact that agent 2 will do x ? part of task allocation ? agent 1 will do x ? does agent 2 think agent 1 is waiting for a reply ? what is x ? a task ? a question ? the name of an agent ? does agent 1 asks agent 2 to perform task itself, or just make sure the result is achieved what must agent 2 do with the result ?

heterogeneity, openness, consequence agents must be endowed with capabilities to understand and reason upon the meaning and content of messages Agent Communication ability to exchange information requires 1. 2. 3. 4. ability to physically exchange information common understanding common language interaction strategies / protocols Agent Communication ability to exchange information requires 1. ability to physically exchange information high-level

communication low-level communication (tcp-ip, http, smtp, ) 2. common understanding 3. common language 4. interaction strategies / protocols Agent Communication ability to exchange information requires 1. ability to physically exchange information 2. common understanding exchanging knowledge requires mutual understanding 2 keys translation between languages sharing semantic content - each agent has implicit assumptions on its own semantics - translation must preserve semantics! to share knowledge, we must have a common semantics

can be shared via common ontologies 3. common language 4. interaction strategies / protocols Agent Communication ability to exchange information requires 1. ability to physically exchange information 2. common understanding 3. common language incorporates two types of languages content language communication language Agent Communication Language 4. interaction strategies / protocols Agent Communication Languages (ACL)

Agents are typically defined at a high level an ACL should support intentional communication the intentional descriptions use concepts such as: beliefs, goals, intentions, commitment the language should not define protocols such as transport protocols high level coordination protocols constraints on valid exchanges Speech Act Theory speech act theory views human speech actions (John Austin, 1962) as in an attempt to influence three parts of speech locution

illocution perlocution physical utterance the intended meaning the action that results from the locution use performatives to identify illocutionary force example: Please be quiet! locution the actual performance of the act illocution the purpose of the utterance perlocution the consequences of the utterance ACLs: FIPA ACL

Foundation for Intelligent Physical Agents - http://www.fipa.org/ 1995 since 2005: IEEE Computer Society standards organization promotes agent-based technology and the interoperability of its standards with other technologies o standardisation of agent-related issues FIPA-OS FIPA infrastructure architecture ... FIPA-ACL

similar to KQML consists of a set of message types and the description of their pragmatics that is, the effects on the mental attitudes of the sender and receiver agents. describes every communicative act with both a narrative form and a formal semantics based on modal logic. separates the outer language (the intended meaning of the message) from the inner language (content language). ACL Message performative content comm.information (inform :sender agent1 :receiver hpl-auction-server :content (price (bid good02) 150) :in-reply-to round-4 :reply-with bid04 :language sl :ontology hpl-auction ) FIPA ACL: performatives

FIPA ACL: semantics in SL the Semantic Language SL (Semantic Language) can represent propositions, objects, and actions formal semantics < message ; precondition ; rational effect > message precondition rational effect the content of the message on the situation (mental state) of the sender intended effect on mental state of receiver FIPA - Communicative Acts (1) inform

confirm the action of agreeing to perform some action, possibly in the future cancel the action of accepting a previously submitted proposal to perform an action agree the action of telling another agent that an action was attempted but the attempt failed accept-proposal

the sender informs the receiver that a given proposition is false, where the receiver is known to believe, or believe it likely that, the proposition is true. failure the sender informs the receiver that a given proposition is true, where the receiver is known to be uncertain about the proposition. disconfirm the sender informs the receiver that a given proposition is true. the action of cancelling some previously request'ed action which has temporal extent (i.e. is not instantaneous) cfp the action of calling for proposals to perform a given action. FIPA - Communicative Acts (2)

inform-if inform-ref the action of asking another agent whether or not a given proposition is true. query-ref the action of submitting a proposal to perform a certain action, given certain preconditions. query-if the sender of the act (e.g. i) informs the receiver (e.g. j) that it perceived that j

performed some action, but that i did not understand what j just did. propose a macro action for sender to inform the receiver that an object corresponds to a definite descriptor (e.g. a name). not-understood a macro action for the agent of the action to inform the recipient whether or not a proposition is true. the action of asking another agent for the object referred to by an expression. refuse the action of refusing to perform a given action, and explaining the reason for the refusal. FIPA - Communicative Acts (3)

reject-proposal request the sender wants the receiver to perform some action as soon as some proposition becomes true and thereafter each time the proposition becomes true again. request-whomever the sender wants the receiver to perform some action when some given proposition becomes true. request-whenever the sender requests the receiver to perform some action. One important class of

uses of the request act is to request the receiver to perform another communicative act. request-when the action of rejecting a proposal to perform some action during a negotiation. the sender wants an action performed by some agent other than itself. The receiving agent should either perform the action or pass it on to some other agent. subscribe the act of requesting a persistent intention to notify the sender of the value of a reference, and to notify again whenever the object identified by the reference changes. ACLs: KQML Knowledge Query Manipulation Language (KQML) KQML has 3 layers

content - ignored by KQML messages message determines interaction types supplies performative & content may describe ontology, etc. communication low level communication parameters

sender, receiver, unique message ID 1. Communication ACLs 2. Negotiation protocols Basic protocols contract-net protocol auction protocols Negotiation protocols / Market-based Mechanisms iterative communication among a group of agents in order to reach a mutually accepted agreement on something.. every day approach in resolving conflicts needed:

a set of options a utility function every option has a price and benefit this function evaluates the worth of an option to an agent. a negotiation protocol multiple stages or steps in the negotiation process eventually the process must either terminate or converge to a solution The Contract Net Protocol introduced by R.G.Smith in 1980 studied extensively with several variations in subsequent years.

how it works a manager breaks the problem into several interacting sub-problems looks for a contractor selects the suitable contractor assigns a sub-problem monitors the progress of the overall solution a contractor bids for work accepts a task it has a binding agreement to complete the task according to the agreed terms and completes the task undertaken.

recursively, the contractor can be a manager for the task it has undertaken. Basic assumptions: the problem has a well defined structure for decomposing coarse-grain decomposition is possible there are enough contractors waiting to do the announced tasks The Contract Net Protocol I have a problem! manager announcement (b) Task Announcement (a) Recognising the problem manager

manager bids (c) Bidding Potential contrators Award task Potential contrator (d) Award Contract The Contract Net Protocol ACL messages Applicability of Contract Net The Contract Net is a high-level communication protocol

a way of distributing tasks dynamically decentralized / situated a means of self-organization for a group of agents but limited (mostly for well-defined hierarchies of tasks) not scalable re-allocation ? Auctions an auction takes place between goal: an agent known as the auctioneer

a collection of agents known as the bidders for the auctioneer to allocate the good to one of the bidders typically the auctioneer desires to maximize the price bidders desire to minimize price Auction Parameters goods can have private value public / common value correlated value winner determination may be first price second price

bids may be open cry sealed bid bidding may be one shot ascending descending Example Auction protocols English auction parameter values Dutch auction

parameter values open-cry descending (first price) First-Price Sealed-Bid Auctions parameter values first price open cry ascending

sealed bid one-shot auction first price English Auctions Dutch Auctions 4. Notation - Agent UML a proposal for an agent-oriented modeling language Pros: Contras: Likely standardization on UML 2.0 Accepted by FIPA UML dialect, not necessarily compatible

AUML AUML class diagram AUML interaction diagrams esp. AUML sequence diagrams http://www.fipa.org/repository/ips.php3 FIPA TC C 2000 Specifies 11 Protocol Specifications http://www.fipa.org/repository/ips.php3 FIPA Request Interaction Protocol Specification 2. FIPA Query Interaction Protocol Specification 3. FIPA Request When Interaction Protocol Specification 4. FIPA Contract Net Interaction Protocol Specification 5. FIPA Iterated Contract Net Interaction Protocol Specification 6. FIPA English Auction Interaction Protocol Specification 7. FIPA Dutch Auction Interaction Protocol Specification 8. FIPA Brokering Interaction Protocol Specification 9. FIPA Recruiting Interaction Protocol Specification 10. FIPA Subscribe Interaction Protocol Specification

11. FIPA Propose Interaction Protocol Specification 1. Summary communication indirect (later) vs. direct communication message-based communication ACLs --> speech act theory Negotation protocols Notation - AUML

Recently Viewed Presentations

  • Who are you?

    Who are you?

    the brain (entrainment occurs between people, you and your pets and the earth) ... Yoga, meditation, music, hypnosis, holosync. Creative expression. Prioritising being over doing, love over fear. Getting in the 'flow' changes your brain waves to slow alpha .....
  • Chapter 25 - Suspending the Great Writ

    Chapter 25 - Suspending the Great Writ

    Arial Arial Narrow Tahoma Wingdings Blends Chapter 25 - Suspending the Great Writ Habeas Corpus Types of Detentions The Habeas Corpus Petition The (Anti-)Suspension Clause Suspension of the Writ Merryman, 17 F. Cas. 144 (C.C.D. Md. 1861) Lincoln's Response Ex...
  • Earth and Space Science

    Earth and Space Science

    Main Layers of the Earth: Crust. Mantle . Core. The Crust. Hard , solid, and strong. Cooler than other layers. Thinner beneath the oceans and made of basalt. Thicker beneath the continents and made of granite. The Mantle. Composed of...
  • Human Relations Approach - My Illinois State

    Human Relations Approach - My Illinois State

    Newcomer Information Seeking Tactics Proactive roles More than passive Actively seeking information to adapt to roles and culture Information seeking strategies (p.156) -Social costs and also a need to reduce uncertainty Role Development Processes Role Taking Role Making Role Routinization...
  • Determining the viability of the early-time method in clay soils

    Determining the viability of the early-time method in clay soils

    Figure from (Grote et al, 2003) showing the groundwave measurements they used to map changes in SWC. Schematic of a GPR survey. ... Explain that the TDR calibration was likely off for this field site. Figure out why the axes...
  • Trigonometry

    Trigonometry

    t = sin(x) = ½ when t = sin(x) = 1 when So the solutions are * * Find the radian measure equivalent of 210° x y 1 is the angle of rotation x y 1 is the angle of...
  • Title

    Title

    Basic Overview. 2017-2018. Welcome to DESE's training for Grade-Level Assessments. The trainings are divided into several shortpresentations. You will be responsible for watching the sessions that apply to your role in testing. In this session we will give a basic...
  • Proces zdravstvene njege Ivana Gusar,dipl.ms. 2010/ 2011. 1

    Proces zdravstvene njege Ivana Gusar,dipl.ms. 2010/ 2011. 1

    Proces zdravstvene njege Ivana Gusar,dipl.ms. 2010/ 2011. Svaka intervencija medicinske sestre usmjerena je rješavanju pacijentovog problema Proces donošenja odluka može biti različit Odlučivanje može biti: Intuitivno - ne postoji jasno i svjesno obrazloženje za odluku Prihvaćanje savjeta drugih - osoba...