Transcript then

Multi-Agent Systems
Lecture 7
University “Politehnica” of Bucarest
2005 - 2006
Adina Magda Florea
[email protected]
http://turing.cs.pub.ro/blia_06
Working together - cont
Lecture outline
1 Modeling coordination by shared mental
states
2 Joint action and conventions
1 Modeling coordination by
shared mental states
Collective mental states
(a) Common knowledge
 Every member in group G knows p
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  ...
3
(b) Mutual belief

EGp aiGaiBelp - Every one in group G believes p shared belief

E2Gp  EG(EGp)

Ek+1Gp  EG(EKGp)

MGp  EGp  E2Gp  …  EkGp  …
k1
- Mutual belief
4
(c) Joint intentions (Levesque & Cohen, 1990)
C1) each agent in the group has a goal p
aiG aiIntp
Modal operators of temporal logic
p U q - p is true until q becomes true - until
Xp - p is true in the next moment - next
Pp - p was true in a past moment - past
Fp - p will eventually be true in the future - eventually
Gp - p will always be true in the future – always
Ap - at a particular time moment, p is true in all paths emanating from that
point - inevitable p
Ep - at a particular time moment, p is true in some path emanating from
that point - optional p
5




s is true in each time point (situation) and on all path
r is true in each time point on a single path
p will eventually be true on a single path
q will eventually be true on all path
s
r
s
r
s
p
s
q
AGs
EGr
r
s
q
F - eventually
G - always
A - inevitable
E - optional
AFq
EFp
s
r - Alice is in Italy
s – Paris is the capital of France
s
q
p -Alice visits Paris
q - it is spring time
6
(c) Joint intentions - cont
C1) each agent in the group has a goal p
aiG aiIntp
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)
F - eventually
G - always
A - inevitable
E - optional
7
(d) Joint commitments
Agents in the group:

have a joint goal

agree they wish to cooperate

the group becomes jointly committed 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
8
3 Joint action and
conventions
3.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
9

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
10
3.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
11
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
12
3.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
13
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
14
(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)
15
(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
16
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)))
17
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
18
(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
………..
19
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.
20