Transcript SIF8072 Distributed Artificial Intelligence and Intelligent Agents

Lecture 4: Coordination
Working Together
SIF8072
Distributed Artificial Intelligence
and
Intelligent Agents
http://www.idi.ntnu.no/~agent/
6 February 2003
Lecturer: Sobah Abbas Petersen
Email: [email protected]
Lecture Outline
1. Recap from last week – CDPS and CNET
2. Coordination techniques
1. Common coordination techniques
2. Coordination based on human teamwork
3. Teamwork
2
References - Curriculum
•
Wooldridge: ”Introduction to MAS”,
–
•
Chapter 9, chapter 4
N. R. Jennings. ”Coordination Techniques for
Distributed Artificial Intelligence”, in: G. M. P. O'Hare,
N. R. Jennings (eds). Foundations of Distributed
Artificial Intelligence, John Wiley & Sons, 1996, pp.
187-210.
3
References – Recommended Reading
•
Not curriculum:
–
E. H. Durfee, ”Distributed Problem Solving and Planning”, in
Multiagent Systems (G. Weiß ed.), MIT Press, Cambridge, MA.,
1999, pp. 121-164.
–
H. Nwana, L. Lee, N. R. Jennings. ”Coordination in Software Agent
Systems”, The British Telecom Technical Journal, Vol. 14, No. 4, 1996,
pp. 79-88.
–
R. Davis and R. G. Smith, ”Negotiation as a Metaphor for Distributed
Problem Solving”, (A. H. Bond and L. Gasser eds.) Readings in
Distributed Artificial Intelligence, Morgan Kaufmann Publishers, 1988,
pp. 333-356.
4
Coordination
”The process by which an agent reasons about its
local actions and the (anticipated) actions of
others to try and ensure that the community acts
in a coherent manner.”
Jennings,1996
5
Coordination Example
Consider an interaction between two robots, A and B,
operating in a warehouse. The robots have been designed
by different companies, and they are stacking and
unstacking boxes to remove certain goods that have been
stored in the building. They need to coordinate their
actions to share the work load and to avoid knocking
into each other and dropping the boxes.
6
Cooperative Distributed Problem
Solving (CDPS)
1.
Problem
decomposition
Ref: Smith & Davis, 1980
2.
Subproblem
solution
3.
Answer
synthesis
7
Task and Result Sharing
• Task sharing:
Task 1
– when a problem is decomposed
into subproblems and allocated
Task 1.1
Task 1.2
Task 1.3
to different agents.
• Result sharing:
– When agents share information
A1
A2
A3
relevant to their subproblems.
8
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
9
…..Task Allocation
10
Result Sharing
• Problem solving proceeds by agents cooperatively
exchanging information as the solution is developed.
• Results may be shared:
– proactively - one agent sends another agent some information
because it believes that the other will be interested in it.
– reactively – an agent sends information to another in response to a
request.
A1
A2
A3
11
The Coordination Problem
• Managing the
interdependencies between the
activities of agents. e.g.
– You and I both want to leave the
room. We independently walk
towards the door, which can only
fit one of us. I graciously permit
you to leave first.
12
Coordination Techniques
• Organisational Structures
• Meta-level Information Exchange
– e.g. Partial Global Planning (PGP), (Durfee)
• Multi-agent Planning
• Norms and social laws
• Coordination Models based on human teamwork:
– Joint commitments (Jennings)
– Mutual Modelling
13
Organizational Structures
• A pattern of information and control relationships between
individuals.
• Responsible for shaping the types of interactions among
the agents.
• Aids coordination by specifying which actions an agent
will undertake.
• Organisational structures may be:
– Functional
– Spatial
14
Organizational Structure Models
• A pattern for decision-making and communication
among a set of agents who perform tasks in order
to achieve goals. e.g.
– Automobile industry
• Has a set of goals: To produce different lines of cars
• Has a set of agents to perform the tasks: designers, engineers,
salesmen
Reference: Malone 1987
15
Alternative Coordination Structures 1
Product Hierarchy
Product Manager 2
Product Manager I
Designer
Engineer
Salesman
Designer
Engineer
Salesman
16
Alternative Coordination Structures 2
Functional Hierarchy
Product Manager (several products)
Design
Manager
Engineering
Manager
Designers
Engineers
Sales
Manager
Salesmen
17
Alternative Coordination Structures 3
Centralised Market
Product Manager 2
Product Manager 3
Design
Manager
Engineering
Manager
Sales
Manager
Designers
Engineers
Product Manager 1
Functional
Managers
Salesmen
18
Alternative Coordination Structures 4
Decentralised Market
Product Manager 1
Designers
Product Manager 2
Engineers
Product Manager 3
Salesmen
19
Comparison of Organization
Structures
Production
cost
Coordination
cost
Vulnerability
cost
Product
hierarchy
H
L
H-
Funtional
hierarchy
L
M-
H+
Centralised
market
L
M+
H-
Decentralised
market
L
H
L
20
Organizational Structures Critique
• Useful when there are master/slave relationships in the
MAS.
• Control over the slaves actions – mitigates against benefits
of DAI such as reliability, concurrency.
• Presumes that atleast one agent has global overview – an
unrealistic assumption in MAS.
21
Let’s take a minute……
• Can you think of a situation in your everyday life
where organisation structures are a way of
coordinating your activities?
• Discuss with your neighbours.
22
Coordination Techniques
• Organisational Structures
 Meta-level Information Exchange
 e.g. Partial Global Planning (PGP), (Durfee)
• Multi-agent Planning
• Norms and social laws
• Coordination Models based on human teamwork:
– Joint commitments (Jennings)
– Mutual Modelling
23
Meta-level Information Exchange
• Exchange control level information about current priorities
and focus.
• Control level information
– May change
– Influence the decisions of agents
• Does not specify which goals an agent will or will not
consider.
• Imprecise
• Medium term – can only commit to goals for a limited
amount of time.
24
Partial Global Planning (PGP) 1
• A DAI testbed – Distributed Vehicle Monitoring Testbed
(DVMT) – to successfully track a number of vehicles that
pass within the range of a set of distributed sensors
(agents).
• Each agent monitors a
Agenti
Vehicle
track
dedicated area
• There could be overlapping
areas
Overlapping
area
Agentj
25
Partial Global Planning (PGP) 2
• Main principle: cooperating agents exchange information
in order to reach common conclusions about the problem
solving process.
• Why is planning partial?
– The system does not generate a plan for the entire problem.
• Why is planning global?
– Agents form non-local plans by exchanging local plans and
cooperating to achieve a non-local view of problem solving.
26
Partial Global Planning (PGP) 3
•
Starts with the premise that tasks are inherently decomposed.
•
Assumes that an agent with a task to plan for might be unaware as to
what tasks other agents might be planning for and how those tasks
are related to its own.
•
No individual agent might be aware of the global tasks or states.
•
Purpose of coordination is to develop sufficient awareness.
27
Partial Global Planning (PGP) 4
•
PGP involves 3 iterated stages:
1. Each agent decides what its own goals are and
generates short-term plans in order to achieve them.
2. Agents exchange information to determine where
plans and goals interact.
3. Agents alter local plans in order to better coordinate
their own activities.
28
Partial Global Planning (PGP) 5
•
Partial Global Plan: a cooperatively generated
datastructure containing the actions and interactions of a
group of agents.
•
Contains:
–
Objective – the larger goal of the system.
–
Activity map – what agents are actually doing and the results
generated by the activities.
–
Solution construction graph – a representation of how the agents
ought to interact in order to successfully generate a solution.
29
Partial Global Planning (PGP) 6
• A DAI testbed – revisited.
Agenti
Vehicle
track
j
i
Overlapping
area
Agentj
30
Coordination Techniques
• Organisational Structures
• Meta-level Information Exchange
– e.g. Partial Global Planning (PGP), (Durfee)
 Multi-agent Planning
• Norms and social laws
• Coordination Models based on human teamwork:
– Joint commitments (Jennings)
– Mutual Modelling
31
Multi-agent Planning 1
• Agents generate, exchange and synchronise explicit plans
of actions to coordinate their joint activity.
• They arrange apriori precisely which tasks each agent will
take on.
• Plans specify a sequence of actions for each agent.
• It is a trade-off between specificity and reactive.
32
Multi-agent Planning 2
•
Two basic approaches:
1. Centralised – plans of individual agents analysed by a
central coordinator to identify interactions.
2. Distributed – a group of agents cooperate to form a:
1.
Centralised plan
2.
Distributed plan
33
Multi-agent Planning 3
• Distributed Planning for centralised plans:
– e.g. Air traffic control domain (Cammarata)
• Aim: Enable each aircraft to maintain a flight plan that will
maintain a safe distance with all aircrafts in its vicinity.
• Each aircraft send a central coordinator information about its
intended actions. The coordinator builds a plan which specifies
all of the agents’ actions including the ones that they should
take to avoid collision.
34
Multi-agent Planning 4
•
Distributed Planning for distributed plans:
–
Individual plans of agents, coordinated dynamically.
–
No individual with a complete view of all the agents’
actions.
–
More difficult to detect and resolve undesirable
interactions.
35
Multi-agent Planning 5
• Critique:
– Agents share and process a huge amount of information.
– Requires more computing and communication resources.
• Difference between multi-agent planning and PGP:
– PGP does not require agents to reach mutual agreements
before they start acting.
36
Multi-agent Planning 6
• Sometime Plans can also become obsolete very quickly.
i.e. Short life-span.
37
Let’s take a minute……
• Can you think of a situation where multi-agent
planning will not be appropriate?
• Discuss with your neighbours.
38
Comparing Common
Coordination Techniques
high
Multi-agent
Planning
high
P
r
e
d
i
c
t
a
b
i
l
i
t
y
Meta-level
Information
Exchange
Organisation
Structures
low
more
R
e
a
c
t
i
v
t
y
low
I
n
f
o
E
x
c
h
a
n
g
e
less
39
Coordination Techniques
• Organisational Structures
• Meta-level Information Exchange
– e.g. Partial Global Planning (PGP), (Durfee)
• Multi-agent Planning
 Norms and social laws
• Coordination Models based on human teamwork:
– Joint commitments (Jennings)
– Mutual Modelling
40
Social Norms and Laws 1
• Norm: an established, expected pattern of behaviour.
– e.g. To queue when waiting for the bus (not always in Norway!!)
• Social laws: similar to Norms, but carry some authority.
– e.g. Traffic rules.
• Social laws in an agent system can be defined as a set of constraints:
– Constraint => E’, ,
• E’  E is a set of environment states
•   Ac is an action, (Ac is the finite set of actions possible for an agent)
 if the environment is in some state e  E’, then the action  is forbidden.
41
Social Norms and Laws 2
obliged
Process
incoming
call
• Example: Feature
obliged
interaction in
obliged
Incoming
call screening
telecommunications
Incoming
call answer
obliged
• Uses deontic logic
forbidden
Forward
call
(model obligations)
forbidden
Forward #1
Accept
call
forbidden
Recall
obliged
Forward #1
42
Coordination Techniques
• Organisational Structures
• Meta-level Information Exchange
– e.g. Partial Global Planning (PGP), (Durfee)
• Multi-agent Planning
• Norms and social laws
 Coordination Models based on human teamwork:
– Joint commitments (Jennings)
– Mutual Modelling
43
Coordination & Cooperation 1
• Can we have coordination without
cooperation?
– ”A group of people are sitting in a park. As a
result of a sudden downpour, all of them run to
a tree in the middle of the park because it is the
only source of shelter.”
44
Coordination & Cooperation 2
• How does an individual intention towards a goal
differ from being a part of a team (a collective
intention towards a goal)?
 Responsibility
– e.g. You and I are lifting a heavy object.
Individual goal  team responsibility
45
Coordination Based on Human
Teamwork
• Some agent coordination models are inspired by human
teamwork models, e.g. Joints intentions (Jennings).
• Intentions are central to the concept of practical reasoning.
 Practical reasoning = deliberation + means-end reasoning
– Deliberation – deciding what state of affairs to achieve
– Means-end reasoning – deciding how to achieve these states of
affairs
46
Mutual Modelling
• Build a model of the other agents – their beliefs
and intentions.
 Put ourselves in the place of the other
• Coordinate own activities based on this model.
• Coordination without cooperation – game-thoery
can be used.
47
Joint Intentions
• Proposed by Jennings
• Based on human teamwork models
– ”When a group of agents are engaged in a cooperative activity,
they must have a joint commitment to the overall aim as well as
their individual commitments.”
• Distinguishes between the commitment that underpins an
intention and the associated convention.
48
Joint Commitments
• Commitment – a pledge or promise (e.g. to lift the heavy
object).
– Commitment persists – if an agent adopts a commitment, it is not
dropped until for some reason it becomes redundant.
– Commitments may change over time, e.g. due to a change in the
environment
– Main problem with joint commitment:
• Hard to be aware of each others states at all times
49
Conventions
•
Convention – means of monitoring a commitment
–
e.g. specifies under what circumstances a commitment can be
abandoned.
•
Need conventions to describe when to change a
commitment:
1.
When to keep a commitment (retain)
2.
When to revise a commitment (rectify)
3.
When to remove a commitment (abandon)
50
Convention - Example
•
Reasons for terminating a Commitment:
–
Commitment Satisfied
–
Commitment Unattainable
–
Motivation for commitment no longer present
•
Rule R1:
–
If Commitment Satisfied OR
Commitment Unattainable OR
Motivation for Commitment no longer present
then
terminate Commitment.
51
Social Conventions
• Conventions describe how an agent should monitor its
commitments, but not how it should behave towards other
agents.
– Asocial
– Sufficient for goals that are independent.
• For inter-dependent goals:
– Need social conventions
• Specify how to behave with respect to the other members of the team.
52
Coordination Summary
•
CDPS: Task and result-oriented
–
•
Task-oriented: Contract Net Protocol
Coordination Techniques:
–
Organisational structures
–
Meta-level information exchange
•
e.g. Partial Global Planning
–
Multi-agent Planning
–
Social norms and laws
–
Mutual Modelling
–
Joint Intentions (Jennings)
53
Teamwork Definition
•
American Heritage Dictionary
– Cooperative effort by the members of a
team to achieve a common goal.
54
Teamwork Example
Two vehicles travelling in a convoy:
Consider two agents Bob and Alice. Bobs wants to drive
home, but does not know his way. He knows that Alice is
going near there and that she does know the way. Bob
talks to Alice and they both agree that he follows her
through traffic and that they drive together.
Ref: Cohen & Levesque, 1991
55
Teamwork 1
•
Important distinction:
–
Coordinated action that is not cooperative, e.g
•
–
Individual drivers in traffic following traffic rules
Coordinated cooperative action, e.g
•
A convoy of drivers
56
Teamwork 2
•
How does an individual intention towards a particular
goal differ from being a part of a team with a collective
intention towards a goal?
–
Responsibility towards the other members of the team.
G
•
Agents i, j and k are a team and have a
g1
g2
g3
i
j
k
common goal G.
57
Teamwork 3
•
Joint action by a team involves more than just the
union of simultaneous individual actions.
-
Joint intentions and mutual beliefs (Cohen &
Levesque, 1991)
-
Joint commitment (Jennings, 1996)
•
G
g1
i
g2
j
When a group of agents are engaged in a cooperative activity,
they must have:
g3
k
•
Joint commitment to the overall activity
•
Individual commitment to the specific task that they have been
assigned to
58
Joint Intentions (Jennings) Revisited
Social Conventions
• Team members must be aware of the convention that govern
their interactions. e.g.
G
• Both Ai and Aj must fulfill their commitments
g1 AND g2
Ai
to achieve G.
Aj
• Either Ai or Aj must fulfill their commitment.
G
g1 OR
g2
 There is a need for all agents in a team to
inform other members of the status of their
Ai
Aj
commitments!
59
Teamwork Model Based on CDPS
1.
Recognition
•
G
Agent has a goal and recognises the potential for cooperative
G
action.
g1
2.
g2
Team Formation
•
3.
Finds a group of agents that have a commitment to joint action.
Plan Formation
•
4.
Agree upon course of action, (through a process of negotiation).
Team Action
•
Execute agreed plan of joint action.
60
g3
Team Selection
•
”The process of selecting a group of agents that
have complimentary skills to achieve a given
goal(s).” (Ref: Tidhar et. al., 1996)
–
Agents exchange their skills, goals, plans,
current beliefs.
–
Done at runtime.
61
References – Recommended Reading
for Teamwork
•
Not curriculum:
–
Cohen, P. R. and Levesque, H. J., ”Teamwork”, Nous, 25, 1991.
–
Tambe, M., ”Towards Flexible Teamwork”, Journal of Artificial
Intelligence Research, Volume 7, 1997, pp. 83-124.
62
Let’s take a minute……
• Discuss with your neighbour an example of
teamwork.
63
Next Lecture: Agent Communication
Will be based on:
”Communication”,
Chapter 8 in
Wooldridge: ”Introduction to MultiAgent
Systems”
64