Convegno Italiano di Logica Computazionale (CILC’05)
Roma, 21-22 Giugno 2005
Social Behavior of Agents
and Stable Models
Francesco Buccafurri and Gianluca Caminiti
DIMET, Università degli Studi
“Mediterranea” di Reggio Calabria
MAS & Logic Programming
Agents
 Logic Programs
Desires/Requests 
Fixpoints
The behavior of one agent can depend on
that of the other agents.
Social Ability: interaction enables
reasoning on agents’ mental states.
CILC'05, Roma, 21-22 Giugno 2005
2
Social-Oriented Reasoning/0
A
a1
|A| = N
CILC'05, Roma, 21-22 Giugno 2005
3
Social-Oriented Reasoning/1
A
a1
head ← [l,h]{body}
CILC'05, Roma, 21-22 Giugno 2005
4
Social-Oriented Reasoning/3
l  |S|  h
A
S
a1
head ← [l,h]{body}
CILC'05, Roma, 21-22 Giugno 2005
5
Social-Oriented Reasoning/4
l  |S|  h
A
S
a1
head ← [l,h]{body}
CILC'05, Roma, 21-22 Giugno 2005
6
Social-Oriented Reasoning/4
l  |S|  h
A
S
a1
head ← [l,h]{body}
CILC'05, Roma, 21-22 Giugno 2005
7
Social-Oriented Reasoning/5
A
a2
a1
head ← [a2]{body}
CILC'05, Roma, 21-22 Giugno 2005
8
Social-Oriented Reasoning/5
A
a2
a1
head ← [a2]{body}
CILC'05, Roma, 21-22 Giugno 2005
9
Social-Oriented Reasoning/5
A
a2
a1
head ← [a2]{body}
CILC'05, Roma, 21-22 Giugno 2005
10
Social-Oriented Reasoning/6
A
a1
head ← [l1,h1]{body1, [l2,h2]{body2}}
CILC'05, Roma, 21-22 Giugno 2005
11
Social-Oriented Reasoning/6
A
l1  |S1|  h1 l2  |S2|  h2
S2 S1
S1
S2
a1
head ← [l1,h1]{body1, [l2,h2]{body2}}
CILC'05, Roma, 21-22 Giugno 2005
12
Example 1: a Wedding Party
P1
(Agent1)
party ← [ N/2 - 1, ]{party}
P2
(Agent2)
okay(party) ←
okay(drive) ← party
P3
party
←
[Agent
]{party,
not
drive}
2
(Agent3)
P4
(Agent4)
empty program
CILC'05, Roma, 21-22 Giugno 2005
13
Example 1: Intended Models
• {},
• {partyP1, partyP2, driveP2},
• {partyP1, partyP2, partyP3}.
CILC'05, Roma, 21-22 Giugno 2005
14
Example 2: a P2P Scenario
download(X) ← [min, ]{
share(X),
[1,]{not incomplete(X)}
}, file(X)
okay(share(X)) ← [0.33*N, ]{
share(X),
[0.1*N,0.2*N]{high_bw}
}, file(X)
CILC'05, Roma, 21-22 Giugno 2005
15
Syntax: Social Rules
h ← body
body = b1, …, bm, s1, …, sk (m ≥ 0, k ≥ 0)
• h - literal or okay(p)
• bi (1 ≤ i ≤ m) - (possibly NAF) literal
• sj (1 ≤ j ≤ k) - (possibly NAF) SSC
SOLP program = set of social rules
SOLP collection = set of SOLP programs
CILC'05, Roma, 21-22 Giugno 2005
16
Syntax: SSC
[selection_condition]{body}
[l, h]
[selection_condition]
[agent_id]
Warning: [1, 1] ≠ [id].
Note: SSCs can be nested.
CILC'05, Roma, 21-22 Giugno 2005
17
Semantics: Autonomy
P - SOLP program
Var(P) - atoms occurring in P
AP - autonomous reduction of P
ATP - extends classical TP to social rules
AFP(P) = set of autonomous fixpoints of P
CILC'05, Roma, 21-22 Giugno 2005
18
Semantics: SOLP Collection
C ={P1, ..., Pn} - a SOLP collection
Social Interpretation for C - I = IP … IP
1
n
IPj - a labeled interpretation for PjC (1 ≤ j ≤ n)
Candidate
Social
Interpretations
for
C
–
U(P1, …, Pn) = {F1P1… FnPn| FiAFP(Pi),
1 ≤ i ≤ n}
CILC'05, Roma, 21-22 Giugno 2005
19
Semantics: literals
C ={P1, ..., Pn} - a SOLP collection
I - a social interpretation for C
aVar(Pi), PiC
(resp. not a)
is true w.r.t. I
if
aPiI
(resp. aPiI)
CILC'05, Roma, 21-22 Giugno 2005
20
Semantics: SSCs
C ={P1, ..., Pn} - a SOLP collection
I - a social interpretation for C
[selection_condition]{body} is true w.r.t. I
if a set of agents exists s.t.
1) selection_condition holds, and
2) body is true w.r.t. I
CILC'05, Roma, 21-22 Giugno 2005
21
Semantics: Social Rules
C ={P1, ..., Pn} - a SOLP collection
I - a social interpretation for C
h ← body - a social rule r of PC
r is true w.r.t. I if either:
• h is true w.r.t. I, or
• body is false w.r.t. I.
CILC'05, Roma, 21-22 Giugno 2005
22
Semantics: Social Models
C ={P1, ..., Pn} - a SOLP collection
I - a social interpretation for C
IU(P1, …, Pn) is a social model of C
if rP1… Pn, r is true w.r.t. I
CILC'05, Roma, 21-22 Giugno 2005
23
Translation: Overview
C ={P1, ..., Pn} - a SOLP collection
Goal: to build a single logic
program J(C) whose
stable models are in 1:1
correspondence with the
social models of C.
CILC'05, Roma, 21-22 Giugno 2005
24
Translation: Step-by-step

Each SOLP program is rewritten as a
classical one, P’, where the SSCs are
represented by special literals.

Conventions on atom names are used
in order to know which program a
given atom comes from.

All the SSCs in C are rewritten as
sequences of DLPA aggregate
functions in a logic program S.
CILC'05, Roma, 21-22 Giugno 2005
25
Translation: Final Result
J(C) = (PC P’)  S
Feasible in polynomial time
The logic program J(C) selects,
among all the candidate social
interpretations for C, those w.r.t.
which all the SSCs in C are true.
CILC'05, Roma, 21-22 Giugno 2005
26
Translation: Theorem
C ={P1, ..., Pn} - a SOLP collection
SOS(P1, ..., Pn) - the social models of C
J(C) = (PC P’)  S
A one-to-one correspondence exists
between the social models in
SOS(P1, ..., Pn) and the stable
models of J(C).
CILC'05, Roma, 21-22 Giugno 2005
27
Social Models & Joint Fixpoints
COLP* program = logic program +
okay rules
COLP program  desires/consents of
a single agent
Semantics of a set of COLP programs
(Joint Fixpoint Semantics*): common
agreement among the agents.
*F. Buccafurri and G. Gottlob. Multiagent Compromises, Joint Fixpoints
and Stable Models, volume 2407 of LNCS and LNAI. Springer, 2002
CILC'05, Roma, 21-22 Giugno 2005
28
Social Semantics extends JFP
From:
COLP programs
(JFP Semantics)
To:
SOLP programs
(Social Semantics)
Feasible in polynomial time
CILC'05, Roma, 21-22 Giugno 2005
29
Social Models & JFP: Theorem
P1, ..., Pn - COLP programs
Q1, ..., Qn - SOLP programs
(the translation of P1, ..., Pn)
A one-to-one correspondence exists
between the Joint Fixpoints of
P1, ..., Pn and the social models of
SOS(Q1, ..., Qn).
CILC'05, Roma, 21-22 Giugno 2005
30
SOS Existence: Theorem
Problem SOSn
Instance: A SOLP collection P1, ..., Pn
Question: Is SOS(P1, ..., Pn)  ?
Theorem
The problem SOSn is NP complete.
CILC'05, Roma, 21-22 Giugno 2005
31
Conclusions

SOcial Logic Programming
(SOLP) enables social behavior
among a community of agents.

SOLP extends COLP.

Complexity results.
CILC'05, Roma, 21-22 Giugno 2005
32
Finally…
Thank You!
CILC'05, Roma, 21-22 Giugno 2005
33