Transcript then

Multi-Agent Systems
Lecture 5
University “Politehnica” of Bucarest
2003 - 2004
Adina Magda Florea
[email protected]
http://turing.cs.pub.ro/blia_2004
Coordination mechanisms and
strategies
Lecture outline
1 Coordination strategies
2 Modeling coordination through AND/OR
graphs
3 Modeling coordination by shared mental
states
4 Joint action and conventions
1 Coordination strategies

Coordination = the process by which an agent reasons about
its local actions and the (anticipated) actions of others to try to
ensure the community acts in a coherent manner
Coordination
Collectively
motivated agents
common goals
Cooperation to
achieve common goal
Self-interested
agents
own goals
Coordination for
coherent behavior
Neutral to one another
disjunctive goals
Competitive
conflicting goals
3



Perfect coordination ???
Centralized coordination ?
Distributed coordination



Model
Protocol
Communication

Tightly coupled interactions - distributed search

Complex agents - distributed planning, task sharing,
resource sharing

Cooperative
Heterogeneous agents - interaction protocols: Contract
Net, KQML conversations, FIPA protocols

Dynamic interactions - Meta-level information exchange,
commitments and conventions

Complex interactions - organizational structure to
reduce complexity


Neutral or
Conflict of interests - interaction protocols: voting, competitive
Unpredictable interactions - social laws
auctions, bargaining, market mechanisms, extended
Contract Net, coalition formation
4
2 Modeling coordination
through AND/OR graphs


Activities of the agents represented as a search
through an AND/OR goal graph
AND/OR goal graph augmented with a
representation of dependencies:
 between goals
 primitive goals and resources needed to solve them
 Interdependencies
 weak or strong
 uni-directional or bi-directional
 Joint goals - a team of agents decide to pursue a
common goal in a cooperative manner
 Joint goals must be mapped into individual goals
5
AND/OR goal graph
with dependencies
between goals
and shared
resources
Agent1
Agent2
G10
G20
AND
G11
….
G12
G1
OR
G1,2m
G1m,1
DATA/
d11
Resources
Find vehicle tracks
in a narrowly
defined region
AND
G2p,2
G2p,1
G2m,2
OR
Identify the types
of vehicle present
based on sensory
data
G2t
k
OR
G11,2
….
G2p
AND
G11,1
Find the most consistent
explanation of sensory data
AND
AND
G1m,1,1
G1m,1,2
G2p,1,3
d1j
d2j+1
G2p,1,4
G2p,2,2
d2z
6
The AND/OR goal graph allows activities requiring coordination to be
clearly identified:
 define the goal graph, including dependencies
 assign particular regions of the graph to appropriate agents
 control decisions about which areas to explore
 traverse the graph
 ensure that successful traversal is reported




The entire graph structure need not be fully elaborated in order for
the problem solving to begin; it may be constructed as the problem
solving progresses
Developing the graph may involve negotiation, resolution of conflicts,
etc.
Construction of the graph may involve top-down elaboration based
on higher level goals or a bottom-up process driven by data, or a
mixture of the two
The structure may be static or may evolve dynamically from a
composite view of the current goal structures of several agents
7
3 Modeling coordination by
shared mental states
 Based on the view of intentional stance agents
 Example of intentional coordinated action
3.1 Collective mental states
(a) Common knowledge




EGp aiGKaip
- shared knowledge
Every member in G knows EGp
E2Gp  EG(EGp)
Every member knows that every member knows that every …
Ek+1Gp  EG(EKGp)
k1
Common knowledge
CGp  p  EGp  E2Gp  …  EkGp  ...
Every member in group G knows p
8
(b) Mutual belief




EGp aiGaiBelp - Every one in group G believes p - shared belief
E2Gp  EG(EGp)
Ek+1Gp  EG(EKGp) k1
MGp  EGp  E2Gp  …  EkGp  …
- Mutual belief
 Perfectly shared mental state but mutual beliefs (as common knowledge)
can not be guaranteed because communication between agents is not reliable
in terms of delivery and delay
(c) Joint intentions (Levesque & Cohen, 1990)
C1) each agent in the group has a goal p
aiG aiIntp (and cf goal-intentions compatibility aiIntp  aiDesp)
C2) each agent will persist with this goal until it is mutually believed that p
has been achieved or that p cannot be achieved
aiG aiInt (A Fp)  A ( aiInt(A Fp) 
(MG(Achieve p)  MG(Achieve p)))
C3) conditions (C1) and (C2) are mutually believed
MG(C1)  MG(C2)
9
Commitments
Formal:
 Blindly committed agent
xInt(A Fp) A (xInt(A Fp)  xBelp)
 Single-minded committed agent
xInt(A Fp) A (xInt(A Fp)  (xBelp  xBel(E Fp)))
 Open-minded committed agent
xInt(A Fp) A (xInt(A Fp)  (xBelp  xDes(E Fp)))
Informal: Commitments may be seen as pledges about beliefs and actions
(d) Joint commitments
Agents in the group:
the state of joint commitment is distributed

have a joint goal
the group becomes jointly committed

agree they wish to cooperate
to achieve the goal (joint goal)
Joint intentions can be seen as a joint commitment to a joint action
while in a certain shared mental state
10
4 Joint action and
conventions
4.1 Conventions
An agent should honor its commitments provided the
circumstances do not change.
Conventions = describe circumstances under which an
agent should reconsider its commitments
An agent may have several conventions but each
commitment is tracked using one convention
11

Commitments provide a degree of predictability so that
the agents can take future activity of other agents in
consideration when dealing with inter-agent
dependencies  the necessary structure for predictable
interactions

Conventions constrain the conditions under which
commitments should be reassesed and specify the
associated actions that should be undertaken: retain,
rectify or abandon the commitment  the necessary
degree of mutual support
12
4.2 Specifying conventions
Reasons for re-assessing the commitment

commitment satisfied

commitment unattainable

motivation for commitment no longer present
Actions
R1: if commitment satisfied or
commitment unattainable or
motivation for commitment no longer present
then drop commitment
 But such conventions are asocial constructs; they do not specify
how the agent should behave towards the other agents if:
– it has a goal that is inter-dependent
– it has a joint commitment to a joint goal
13
Social Conventions
Invoke when:
Inter-dependent goals

local commitment dropped
 local commitment satisfied
 motivation for local commitment no longer present
R1: if local commitment satisfied or
local commitment dropped or
motivation for local commitment no longer present
then inform all related commitments
Invoke when:
Joint commitment to a joint goal

status of commitment to joint goal changes
 status of commitment to attaining joint goal in the team context changes
 status of commitment of another team member changes
R1: if status of commitment to joint goal changes or
status of commitment in the team context changes
then inform all other team members of the change
R2: if status of commitment of another team member changes
then determine whether joint commitment is still viable
14
4.3 An example of joint action and conventions
GRATE System (Generic Rules and Agent model Testbed
Environment, Jennings, 1994)
ARCHON
electricity distribution management
cement factory control
Electricity distribution management of the traffic network

distinguish between disturbances and pre-planned maintenance operations
 identify the type (transient or permanent), origin and extend of faults when they
occur
 determine how to restore the network after a fault
3 agents
AAA - the Alarm Analysis Agent
 perform diagnosis to different levels
BAI - the Blackout Area Identifier
of precision and on different info
CSI - Control System Interface  detects the disturbance initially and then
monitors the network evolving state
15
GRATE Agent Architecture
Inter-agent
communication
CONTROL
DATA
Cooperation &
Control Layer
Communication Manager
Acquaintance
Models
COOPERATION
MODULE
Self
Model
SITUATION
ASSESMENT
MODULE
Information
store
CONTROL MODULE
Domain Level
System
Task1
Task2
Task3
16
(a) Agent behavior
1. Select goal and develop plan to achieve goal
2. Determine if plan can be executed individually or cooperatively
(a) joint action is needed (joint goal) or
(b) action solved entirely locally
3. if (a) then the agent becomes the organiser
3.1. Establish joint action - the organiser carries on the distributed
planning protocol
3.2. Perform individual actions in joint action
3.3. Monitor joint action
4. if (b) then perform individual actions
5. if request for joint action then the agent becomes team-member
5.1. Participate in the planning protocol to establish joint action
5.2. Perform individual actions in joint actions
(3.2 and 5.2 adequately sequenced)
17
(b) Establish joint action
GRATE Distributed Planning Protocol
PHASE 1
1. Organiser detects need for joint action to achieve goal G and determines that
plan P is the best means of attaining it - SAM
2. Organiser contacts all acquaintances capable of contributing to P to
determine if they will participate in the joint action - CM
3. Let L  set of willing acquaintances
PHASE 2
4. for all actions B in P do
- select agent AL to carry out action B
- calculate time tB for B to be performed
based on temporal orderings of P
- send (B, tB) proposal to A
- receive reply from A
- if not rejected then
- if time proposal modified
then update remaining actions by t
- eliminate B from P
5. if B is not empty
then repeat step 4
Agent A
1. Evaluate proposal (B, tB) against
existing commitments
2. if no conflicts then
create commitment CB to (B, tB)
3. if conflicts ((B, tB), C) and
priority(B) > priority(C)
then create CB and reschedule C
4. if conflicts ((B, tB), C) and
priority(B) < priority(C)
then
if freetime (tB+ t)
then note CB and return (tB+ t)
else return reject
18
Joint intention - Phase 1 for agent AAA
Name: Diagnose-fault
Motivation: Disturbance-detection-message
Plan: { S1: Identify_blackout_area, S2: Hypothesis_generation,
S3: Monitor_disturbance, S4: Detailed_diagnosis, S2 < S4}
Start time:
Maximum end time:
Duration:
Priority: 20
Status: Establish group
Outcome: Validated_fault_hypothesis
Participants: ((Self organiser agreed_objective)
(CSI team-member agreed_objective)
(BAI team-member agreed_objective))
Bindings: NIL
Proposed contribution:
((Self (Hypothesis_generation yes) (Detailed_diagnosis yes))
(CSI (Monitor_disturbance yes)
(BAI (Identify_blackout_area yes)))
19
Joint action - Phase 2 for agent AAA
Name: Diagnose-fault
Motivation: Disturbance-detection-message
Status: Establish plan
Start time: 19
Maximum end time: 45
Bindings: ((BAI Identify_blackout_area 19 34)
(Self Hypothesis_generation 19 30)
(CSI Monitor_disturbance 19 36)
(Self Detailed_diagnosis 36 45))
….

BAI's individual intention for producing the blackout area
Name: Achieve Identify_blackout_area
Motivation: Satisfy Joint Action Diagnose-fault
Start time: 19
Maximum end time: 34
Duration: 15
Priority: 5
Status: Pending
Outcome: Blackout_area
20
(c) Monitor the execution of joint action
Recognize situations that change commitments and impact joint
action
R1match: if task t has finished executing and
t has produced the desired outcome of the joint action
then the joint goal is satisfied
R2match: if receive information i and
i is relevant to the triggering conditions for joint goal G and
i invalidates beliefs for wanting G
then the motivation for G is no longer present
Social conventions
R1inform: if joint action has successfully finished
then inform all team members of successful completion and
see if result should be disseminated outside the team
R2inform: if motivation for joint goal G is no longer present
then inform other members of the team that G needs to be abandoned
Rules to indicate what to do if change in commitments
………..
21
References





Multiagent Systems - A Modern Approach to Distributed Artificial
Intelligence, G. Weiss (Ed.), The MIT Press, 2001, Ch.2.3, 8.5-8.7
V.R. Lesser. A retrospective view of FA/C distributed problem solving.
IEEE Trans. On Systems, Man, and Cybernetics, 21(6), Nov/Dec
1991, p.1347-1362.
N.R. Jennings. Coordination techniques for distributed artificial
intelligence. In Foundations of Distributed Artificial Intelligence, G.
O'hara, N.R; Jennings (Eds.), John Wiley&Sons, 1996.
N.R. Jennings. Controlling cooperative problem solving in industrial
multi-agent systems using joint intentions. Artificial Intelligence 72(2),
1995.
E.H. Durfee. Scaling up agent coordination strategies. IEEE
Computer, 34(7), July 2001, p.39-46.
22