Agent Communication in Multi Agent Systems

Agent Communication in Multi Agent Systems

Agent Communication in Multi Agent Systems Reference Weiss Chapter 2 Wooldridge Chapter 8 Multiple agent systems There are cases of single independent agents Multiple agents are more typical Networks and interconnected systems This discussion involves analysis and design of multi agent environments Environment provide computational infrastructure Protocols for agents to communicate Protocols for agents to interact Example of Comm Protocol

Example of a comm protocol Propose a course of action Accept a course of action Reject a course of action Retract a course of action Disagree with proposed course of action Counter propose course of action Interaction between A1 and A2

A1 proposes a course of action to A2 A2 evaluates the proposal and does one of the following Sends acceptance to A1 Sends counter proposal to A1 Sends disagreement to A1 Sends rejection to A1 Lost update problem Process synchronization is critical Shared variable v, is read by p1 and processed. Process p2 updates v.

Process p1 updates v. p2 updates are lost Serialization Communication: Object vs. Agent OO: Communication as Method Invocation Two objects O1 and O2. Object O1 has a public method m1. Object O2 communicates with O1 by invoking m1, i.e. O2 executes O1. m1(arg); arg is argument communicated by O2 2 to O1. In effect O2 controls execution of O1. In agent environment the agents are autonomous and hence this is not acceptable. Agents communicate to influence the other agent. Why Multi Agent Systems? Info is geographically distributed

Info arch is large and complex Many components, concepts, large data volume, complex interconnections Multi modal info Text, database, voice, images, video Static, dynamic, probabilistic How to deal with complexity? Potential ways to deal with complexity Modularity, distribution, abstraction, intelligent info processing (find and modify) DAI / Agents Develop agents independently, make agents autonomous Computational agents are distributed

Application programs, Active info resources available globally, Wrappers for legacy systems, On-line services Properties of Multi Agent Env Infrastructure including comm and interaction protocols No centralized controller (designer) Support autonomy Agents may cooperate or compete Properties of MAS Properties Range of values

Design Autonomy Platform, interaction protocol, language, internal arch Communication Infrastructure Blackboard (shared mem) or Message passing; Synch or Asynch; Push or Pull; Point-to-point, Multicast, or Broadcast Directory services Yellow or white pages Message Protocol KQML, CORBA, HTTP, HTML

Security Timestamp / Authentication Operations Support Archiving / Redundancy / Restoration / Accounting From Table 2.1 in [1] Communications Relies on Syntax (structure of comm at the symbol level) Semantics (what the symbols denote) Pragmatics (interpretation of the symbols) Semantics + Pragmatics leads to understanding of the meaning of the

communication Agents must understand and be understood Dimensions of Meaning Descriptive vs Prescriptive Describe phenomena vs prescribe behavior Descriptions are good for humans, what about agents? ACL are designed to communicate behavior and activities Personal vs Conventional meaning Agents should use conventional (standards). But what about context? Semantics vs Pragmatics

Pragmatics specifies how communication is used. Environment. Context Contextuality Context of the present state of the communicator. Environment and history of actions. Communicating agent. Identity of the communicator. Coverage smaller languages are better suited for agent communication Cardinality: single message interpreted differently than a broadcast message. Agent Communication Coordination requires the agent to predict behavior of the

other agents in the system requires good models Coord Competition Negotiation Cooperation Planning Centralized Plnng Distributed Plnng Coherence achieve global coherence without centralized control Economic markets are good at determining price, but not necessarily provides optimal resource allocation from Herb Simon Message Types Agents must be capable to participate in a dialog Potential agent role Active, passive or both Master, slave or peer Passive agents Accept info (assertions), Accept query and send a reply (assertion)

From the comm network there is no difference between an unsolicited assertion or an assertion in reply to a query Active agents Issue queries, issue assertions Control subagents, Monitor environment Speech act theory is the basis of the inter agent communication Views natural language as actions requests, suggestions, commitments, and replies. Locution the spoken (physical) utterances Illocution intended meaning of the spoken utterance Perlocution action resulting from the locution Agent Capabilities Basic Agent Receives assertions Receives queries

Sends assertions Sends queries Passive Active Agent Agent Peer Agent

Table 2.3 from [1] Inter Agent Message Types Communicative Action Illocutionary Force Expected Result Assertion Inform Acceptance

Query Question Reply Reply Inform Acceptance Request Request Explanation

Inform Agreement Permission Inform Agreement Refusal Inform Agreement Offer/Bid Inform

Agreement Inform Offer/Bid Command Acceptance Agreement Proposal Confirmation Retraction Denial Table 2.4 from [1] Communication Protocol

Typical levels Lowest level: interconnection Middle level: format, syntax of the info being transferred Top level: meaning or semantics of the info Binary: one sender, one receiver N-ary: Broadcast, Multicast one sender, N receivers Data structure Sender Receiver (s) Languages in the protocol Encoding and decoding functions Actions to be taken by the receiver

Knowledge Query and Manipulation Language (KQML) Protocol for info and knowledge exchange Structure (KQML-performative :sender :receiver :language :ontology :content ) Keywords (preceded by :) can be in any order. Others

reply-with, in-reply-to Message can be understood by agents assuming language and ontology knowledge KQML: Inter Agent & Agent Program Communication KQML Agent KQML Agent Application Program

KQML Modes of Communication query Client reply Server Synch: Blocking query wait for reply query Client next next handle reply

Server reply Server maintains state: individual replies on request subscribe Client reply reply reply Asynch: nonblocking subscribe results in replies Server Knowledge Interchange Format

Formal syntax for knowledge representation Example: Block A on Block B. (tell :sender :receiver :language :ontology :content Agent1 Agent2 KIF Blocks-World (AND (Block A) (Block B) (On A B))) Nested KQML (forward :from :to

:sender :receiver :language :ontology :content Agent1 Agent2 Agent1 Agent3 KQML KQML-ontology (tell :sender Agent1 :receiver Agent2 :language KIF :ontology Blocks-World :content (AND (Block A) (Block B) (On A B))))

Forward:from = Content:sender = Agent1 Forward:to = Content:receiver = Agent2 Forward:receiver = Agent3 KQML performatives Basic query (evaluate, ask-one, ask-all,) Multiresponse query (stream-in, stream-all,..) Response (reply, sorry,) Generic info (tell, achieve, cancel, untell, unachieve, ) Generator (standby, ready, next, rest,) Capability-definition (advertise, subscribe, monitor,) Networking (register, unregister, forward,

broadcast,) Knowledge Interchange Format (KIF) Proposed standard for intelligent agents, expert systems, databases Examples (salary xxx-yy-zzzz designer 40000) (> (* (width chip1) (length chip1)) (* (width chip2) (length chip2))) Example KQML dialog (evaluate :sender A :language KIF :reply-with q1

:receiver B :ontology :content (val (reply :sender B :language KIF :in-reply-to q1 :receiver A :ontology motors :content (= (torque m1) (scalar 12 kgf))) motors (torque m1)))

Note: q1 is query reference number From Figure 8.2 in [2] Example KQML dialog (stream-about :sender :language :reply-with (tell :sender :in-reply-to (tell :sender : in-reply-to (eos :sender : in-reply-to

A KIF q1 :receiver B :ontology :content (val B q1 :receiver A :content (= (torque m1) (scalar 12 kgf))) B q1 :receiver A :content (= (status m1) normal))

B q1) :receiver A motors (torque m1))) stream-about: S wants all relevant answers in Rs Virtual Knowledge Base. Output is streamed. eos ends the stream From Figure 8.2 in [2] FIPA ACL (inform :sender :receiver :content

:language :ontology ) agent1 agent2 (price good2 s1 hpl-auction 150) FIPA=Foundation of Intelligent Physical Agents

Message structure is similar to KQML Message attribute fields is also similar to KQML FIPA performatives are different than KQML 20 performatives Inform tells the receiver to believe the message content; implies that sender also believes the message Ontologies Specification of the objects, concepts and relationships In the Block World example, BLOCK represents a concept and ON is a relationship Each agent must represent its knowledge using the vocabulary of a specific ontology Note KQML specifies the Ontology How are Ontologies co-ordinated? Ontologies for ACL

Represent part of the world. Shared virtual world, which provide the terms for communication. If 2 agents agree on the upper nodes of a taxonomy, then these agents can focus on the language content in this context. Agent Interaction Protocols Interaction implies conversation Objective: Ensure achievement of overall goals, Coherence across agents Retain agent autonomy Shared goals, common tasks, reduce conflicts, pool knowledge and evidence Agent Interaction Protocols (contd)

Co-ordination Co-operation Contract Net Blackboard Negotiation AIGA Co-ordination Protocols Reason for co-ordination: better utilization of resources, avoid duplication, maintain coherence Timely updates, agent synchronization Distribute control and data

Disadv: System state is distributed Adv: Reduce points of bottleneck Goal graph Relates goals and resources Identifies dependencies Assignment of goals to agents Manage graph traversal and report results Co-operation Protocol Supports decomposition and distribution of tasks (divided and conquer)

Avoid overloading of critical resources Task assigned to agents with matching skills Master / slave relationships in task assignment Minimize communication and synchronization cost: spatial and semantic proximity Migrate tasks if necessary Redundancy and fault tolerance Task distribution approaches Market mechanisms: price, utility Contract net

Credibility, belief management Static plans: task to resource map Task Assignment Agent 1 Spatial Agent 2 Agent 3 Functional Radiologist Neurologist Pedatrician

Internist Cardiologist Contract Net Manager wants to find contractors Contractors role

Announce task (RFP) Receive bids Award contracts Results, task accomplishment Get RFP Evaluate capability Respond (Bid, No Bid) Perform task Report results Manager assess contractor capability Distributed computing implications

Structure Contract Net Structure the bid Addressee Capability requirements Task abstraction Bid spec Expiration Contractor response Capability Capacity Pricing

Multi level interaction Contractor capability and capacity assessment Manager as a prime contractor Negotiation Synchronization Blackboard Specialized Knowledge Sources (KS) Multiple approaches to problem solution

Knowledge representation is KS controlled Control transfer Data exchange Synchronization Blackboard Architecture Blackboard Executing Activated KS Events Control Components Pending KS

Activations Distributed Memory Systems? Granuality? Library Of KSs Negotiation Goes through a cycle Offer Evaluation

Identify agreements Identify disagreements Repeat with counter offer Granularity, efficiency, stability

Recently Viewed Presentations

  • What next?!!

    What next?!!

    Community/Place Based Education . Personalized Learning - Harrisburg, SD & Oakes, ND. 16 Habits of the Mind taught for student self-directed learning 2-5. 7-11 year olds MIXED skills, standards based. Not including k-1…yet! STEM Academies & classes. Project Based Learning....
  • ASTROPARTICLE PHYSICS - University of Warwick

    ASTROPARTICLE PHYSICS - University of Warwick

    atmospheric neutrinos are "astroparticle physics" but have contributed more to understanding of neutrinos than to astrophysics. similar situation for solar neutrinos. long-baseline neutrino experiments can do low-energy neutrino astrophysics "for free" (and vice versa) Nucleon decay. many detector technologies useful...
  • 7th World Congress of Biological Psychiatry, 1-6 July

    7th World Congress of Biological Psychiatry, 1-6 July

    Symposium ERP and EEG Studies in Psychosis Task Demand in Schizophrenia: Auditory Multichannel ERPs Jürgen Kayser, Gerard E. Bruder, Craig E. Tenke
  • E Government - University of Missouri-St. Louis

    E Government - University of Missouri-St. Louis

    Database Students Faculty Administration Structured System Analysis & Design Methods (SSADM) Systems Analysis and Design * Logical Data Modeling (LDM): Identify, model and document data requirements Entity (Required business information) Relationships between entities.
  • Globus Virtual Workspaces - Fermilab

    Globus Virtual Workspaces - Fermilab

    FNAL, January 2009 Kate Keahey ([email protected]) University of Chicago Argonne National Laboratory Cloud Computing Everything-as-a-Service The Quest Begins Code complexity Resource control "Workspaces" Dynamically provisioned environments Environment control Resource control Hardware implementations vs virtualization A Brief History of Nimbus Nimbus...
  • Food security - Green Economist

    Food security - Green Economist

    Global Food Issues How environmental, secure and fair is our global trade system in food?
  • Log onto Twitter and take our poll and submit questions ...

    Log onto Twitter and take our poll and submit questions ...

    What is a standardized test. A Standardized test is a test that is given in a consistent or "standard" manner. Standardized tests are designed to have consistent questions, administration procedures, and scoring procedures. When a standardized test is administrated, is...
  • Hypothesis testing QuickTime and a TIFF (Uncompressed) decompressor

    Hypothesis testing QuickTime and a TIFF (Uncompressed) decompressor

    Hypothesis testing Hypothesis testing Want to know something about a population Take a sample from that population Measure the sample What would you expect the sample to look like under the null hypothesis?