Transcript Multi-Agent System

Multi-agent Systems, Communication
and Coordination
Multi-Agent Systems Course
Koen Hindriks
Delft University of Technology, The Netherlands
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
GOAL So Far
•
•
•
•
•
•
mental states (beliefs, goals)
mental state conditions & macros
action specifications, built-in actions
action rules
environment & perception
modules
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Outline (today)
• Intro Multi-Agent Systems (MAS)
• Coordination in MAS
• Specifying a MAS in GOAL
• Communication in GOAL
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Multi-Agent Systems (MAS)
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Multi-Agent System
Intersecting spheres of influence of multiple agents acting in an environment
A1
Agents
A3
A2
A4
Environment
Intersecting spheres:
•Action perspective: may interfere, change same parts of environment
•Perception perspective: agents may have different views on environment
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Multi-Agent System
Various approaches to coordinate activity of multiple agents
A1
Agents
A3
A2
A4
Environment
Various coordination techniques have been proposed, main ideas:
• Communication protocols impose structure on agent communication
• Add organization structure on top of multi-agent system
Note: Without explicit agent communication still implicit communication
possible via environment if perception spheres overlap
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Multi-Agent System
Not all agents need to be ‘connected’ to the environment
A3
A1
Agents
A2
A4
Environment
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Kinds of multi-agent systems
• Cooperative versus competitive
– Agents have a common goal of solving a problem together or compete
for resources.
• Homogeneous versus heterogeneous
– All agents have the same abilities and decision logic, or agents have
different abilities.
• Interaction protocols
– Which agents can talk to which other agents?
• Organizational structure
– Agents may be organized in various ways (with a leader, or not,
different roles, etc.)
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Example – Search and Rescue
• Search & Rescue
– Unknown environment (map may be unreliable or
absent)
– Search for victims
– Providing aid to victims
– Aim to minimize time to provide aid to all victims.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Example – Package Delivery
• Package delivery
– Known environment (map)
– Initial and target location of packages known
– Aim to minimize delivery time of all packages.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Advantages of MAS
• Complete tasks quicker through shared effort.
• Achieve tasks otherwise not possible. A MAS
provides solutions in situations where action
is spatially and temporally distributed.
• A MAS can be distributed over machines
across a network.
• A decentralized MAS does not suffer from the
"single point of failure" problem.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Cooperation & Coordination
Maaike Harbers, Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Examples of Cooperation
http://cacm.acm.org/news/98755-how-football-playing-robots-have-the-future-of-ai-at-their-feet/fulltext
Maaike Harbers, Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Cooperation Challenges
• Cooperation yields more effective (e.g., quicker)
solutions to a problem…
• But…
1. Avoid duplication of effort.
2. Avoid interference, i.e. harmful interactions.
3. Avoid communication overhead, i.e., need to share
information with as few messages as possible.
4. Need to synchronize behaviors.
• Coordination needed to address challenges
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
What is coordination?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Coordination problems
• Without coordination, what would happen here?
• What is the problem: duplication of effort,
interference, communication overhead,
synchronization?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Coordination problems
• And what would
happen here?
What is the problem: duplication of effort, interference,
communication overhead, synchronization?
http://www.wired.com/gadgetlab/2010/06/dance-dance-revolution-20-robots-think-they-can-dance/
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Coordination problems
• And what would
happen here?
What is the problem: duplication of effort, interference,
communication overhead, synchronization?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Coordination problems
• And what would
happen here?
Player A / Player
B
Defect
Cooperate
Defect
2,2
5,0
Cooperate
0,5
3,3
Prisoner's dilemma
Two persons are being questioned in separate rooms
by the police. Each of them can either admit to a crime
(defect) or not (cooperate).
Outcomes for actors A and B depend on the combination of A's and B's action.
What is the problem: duplication of effort, interference,
communication overhead, synchronization?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Need to be smart
• And what would
happen here?
The wise men problem
A king wishing to know which of his three wise men is the wisest, paints a white
spot on each of their foreheads, tells them at least one spot is white, and asks
each to determine the color of his spot. …
What is the problem: duplication of effort, interference,
communication overhead, synchronization?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Types of coordination
• Implicit coordination
e.g., flocking behavior
• Explicit coordination
exchange of messages
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Aspects of joint activity
Coordinating behavior makes
multiple agents act like a team, they
perform a joint activity.
Klein, G., Feltovich, P., Bradshaw, J. M., & Woods, D. D. (2005). Common ground and coordination in joint activity.
Organizational Simulation. W. B. Rouse and K. R. Boff. New York City, NY, John Wiley.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
A. Criteria: example
Making an assignment together
• No intention – no assignment or two assignment
• No interdepencence – each making one half of the
assignment without seeing the other half
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
B. Requirements for joint activity
• Interpredictability
– Need to be able to accurately predict what others will do
– Not just actions, but the coordination itself
• Common ground
– Pertinent mutual knowledge, beliefs, and assumptions about
others’ skills and capabilities
– Joint activity is guided by signaling and coordination devices
• Directability
– Capacity for modifying the actions of the other parties as
conditions and priorities change
– Responsiveness of each participant to the influence of the others
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
B. Requirements: example
Football team
• Interpredictability – predict where team members will be
on the field and who will be available
• Common ground – who is keeper, who defends, who
attacks
• Directability – keeper
tells others where
to stand during a
corner
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
C. Choreography of joint activity
• Three phases (functional breakdown)
• coordinating tasks is coordinating subtasks
• subtasks have an entry, body and exit phase
• Signaling transitions
• within and between phases
• Coordination devices
• serve to increase interpredictability
• examples are organizational structure, convention, communication
protocol
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
C. Choreography: example
Traffic
• Three phase actions
-
entering a road
being on the road
leaving a road
• Signaling transitions
-
turn signal
• Coordination devices
-
organizational structure, convention, communication protocol
to discuss…
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Coordination structures
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Organizational structure
from Bradshaw
et al.
Koen Hindriks, Birna vanadapted
Riemsdijk
Multi-agent
systemen
Organizational structure in BW4T
• Notion of ‘role’ is central
• Possible roles in BW4T?
• searcher
• deliverer
• manager
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Notion of ‘role’ is central
organization
goals
determine
agent
roles
performed by
agents
Organizational
perspective
Koen Hindriks, Birna van Riemsdijk
agent
goals
determine
agent
roles
performed within
society
Agent
perspective
Multi-agent systemen
Conventions
Coordination
by convention
solution
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Conventions in BW4T
• A group of agents
• Each agent is able to
solve the BW4T task
individually
• Agents do not take into
account that there are
other agents
• What happens?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Example of conventions in BW4T
• Do not enter rooms that are occupied
• If you know about a block that can be delivered,
deliver that block
• If someone intends to deliver a particular block, do
not try to deliver that
block as well
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Conventions in organizational
structure
If a searcher finds a block,
it must report that to the
manager
adapted from Bradshaw et al.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Communication in BW4T
• A group of agents
• Each agent is able to
solve the BW4T task
individually
• Agents take into account
that there are other agents
• Agents do not
communicate
• What happens?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Implicit coordination in BW4T
• And what would
happen here?
Room
1
Room
2
Robot 2
Robot 1
Robots do NOT communicate. How do they choose a
room?
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Specifying a MAS
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
MAS Specification
In GOAL, a .mas file is a recipe for launching a
multi-agent system, specifying:
• which environment will be launched,
• how many agents will be launched,
• the agent names for agent processes
• which agents are connected to environment
• which .goal file(s) is (are) used to create an
agent.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
MAS Specification
A .mas file is a recipe for launching a MAS:
• which environment will be launched
environment{
env = "blocksworld.jar".
init = [configuration="bwconfigEx1.txt"].
}
• environment started by jar file,
• some of which may be initialized using the
init command (check out environment doc).
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
MAS Specification
A .mas file is a recipe for launching a MAS:
• which agent files will be used
agentfiles {
"coffeemaker.goal".
"coffeegrinder.goal".
}
• agent file defines a possible agent type.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
MAS Specification
A .mas file is a recipe for launching a MAS:
• which agent processes will be created
launchpolicy {
launch maker:coffeemaker.
launch grinder:coffeegrinder.
}
• a launch policy specifies when, which and how
many agent processes will be created.
• launch maker:coffeemaker. launches one
agent process called maker using the agent file
referenced by coffeemaker (coffeemaker.goal).
• does not connect agent to an environment.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
MAS Specification
A .mas file is a recipe for launching a MAS:
• which agent processes will be created
launchpolicy {
when entity@env do launch elevator : file1.
}
• a conditional launch rule is triggered by the
environment:
whenever a controllable entity becomes available
in the environment, an event is generated.
• the agent created by the launch part of the rule is
connected to that entity.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
MAS Specification
A .mas file is a recipe for launching a MAS:
• additional checks in launch rule
launchpolicy {
when [type=car,max=3]@env do launch elevator:file1.
}
• this launch rule can only be applied if there is an
available entity of type car, and the rule can be
applied at most 3 times.
Remark: launch rules are applied in linear order.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
MAS Specification: Example
A .mas file is a recipe for launching a MAS:
agentfiles {
"coffeemaker.goal".
"coffeegrinder.goal".
}
launchpolicy {
launch maker:coffeemaker.
launch grinder:coffeegrinder.
}
• environment section may be empty, in that case mas
is run without an environment.
• agentfiles and launchpolicy must be non-empty.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Agent Identity and Other Agents
How does an agent know it is not alone?
• The names of all agents generated by GOAL are
inserted in the belief base of all other agents.
• For example, agent(tarzan) is inserted in the
belief base of agent jane when tarzan is created.
How is an agent able to differentiate itself from other
agents? I.e. how does agent jane know she is not
tarzan?
• Upon creation, the fact me(<name>) where name is
the agent’s name is inserted in the belief base of
that agent.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Communication in GOAL
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Communication: Primitives
• Communication primitives:
– send(<recipients>, <content>)
– sendonce(<recipients>, <content>)
• Example: Tarzan sends Jane a message:
– send(jane, meeting(date(1,2,2010),
time(12,0), duration(1,0), [jane,
tarzan]))
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
GOAL Agent Architecture
• The basis of communication in GOAL is a simple
mailbox semantics.
Agent
message
percept
Process
message
Beliefs
Process
percepts
Goals
Action
Rules
Environment
Real or simulated
world of events
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
action
Communication: Semantics
Action: send(<recipients>, <content>)
• ground send action can always be performed, i.e.
precondition is true,
• assume agent sender sends message to recipients
• then GOAL puts
sent(<recipients>, <content>)
in the mailbox of sender,
• agents that receive message put
received(sender, <content>)
NB: keep in mind it may take some time
in their mailbox.
before agent b receives the message.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Communication: Semantics
Action: sendonce(<recipients>, <content>)
• same as send(<recipients>, <content>), but
• sendonce action can only be performed if the
mailbox of the sending agent does not contain:
sent(<recipients>, <content>)
i.e. precondition is:
not(sent(<recipients>, <content>)
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Using Messages in Mailbox
The facts in the mailbox can be used like any other facts in the
belief base of an agent.
That is,
• sent(<recipient>, <content>) and
• received(name, <content>)
can be used in:
– in conditions in action rules
– clauses in the knowledge or beliefs section
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Using Messages in Mailbox
• After receiving a message from tarzan, agent
jane will have:
received(tarzan, meeting(date(1,2,2010),
time(12,0), duration(1,0), [jane,tarzan]))
in her mailbox.
• Consequently, jane will believe:
bel(received(tarzan, meeting(date(1,2,2010),
…, …, [jane,tarzan])))
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Processing Message Pattern
• Inserting received information into belief base and
removing received message:
if bel(received(A,Proposition)) then
insert(Proposition) +
delete(received(A,Proposition))
• Removing received message cleans up the mailbox
and makes sure that the action rule is not applied
repeatedly (even after the received info is outdated).
• Using received messages in mental state conditions
other than for processing the message, and using
them in knowledge base, gives less readable code.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Message Types
• GOAL supports three message types, called
moods:
– declarative, typically used to inform
Example: The time is 2 o'clock
operator: ‘:’ : send(jane, :time(14,0))
– imperative, typically used to indicate a goal
Example: I want the door to be closed!
operator: ‘!’ : send(jane, !door(closed))
– interrogative, typically used to ask a question
Example: How much milk is left?
operator: ‘? : send(jane, ?amountMilk(_))
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Message Types
Mood operators are translated to Prolog predicates in
mailbox:
– declarative: no predicate
received(tarzan, time(14,0))
– imperative: imp
received(tarzan, imp(door(closed)))
– interrogative: int
received(tarzan, int(amountMilk(_)))
See programming guide, section 6.5.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Agent Selectors
First argument of a send action is called an agent
selector, which can be:
•An agent name: send(jane, …)
•A variable (to be instantiated): send(Person, …)
•A list of selectors:
send([jane,tarzan,Person], …)
•A quantor:
– send(self, …) : message sent to agent itself
– send(all, …) : message sent to all agents (incl. itself)
– send(allother, …) : message sent to all other agents
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Sending messages to oneself
• Messages sent to oneself change the agent’s
own mental state! Sending messages to
oneself has special meaning.
• Changes are different for different moods:
– send(self, :fact) inserts fact in belief base
– send(self, !fact) adopts fact as goal and
deletes fact from belief base.
– send(self, ?fact) deletes fact from belief base
N.B.: Do not use messages to self as an alternative way of
updating the agent’s beliefs and goals!
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Selecting agents to send to
• Suppose agent wants to send to all other
agents that are producers of milk that it wants
to have milk.
Q: Write an action rule which achieves this:
– Use predicates have/1 and producerOf/2.
A: if a-goal(have(milk)),
bel(agent(X), producerOf(X, milk))
then send(X, !have(milk))
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen
Organisation
• Tutorial this week:
– Assignment 4: team agent for BW4T
• Exam:
– Specification of material to study will be posted on
blackboard.
– Example exams will be made available.
Koen Hindriks, Birna van Riemsdijk
Multi-agent systemen