Transcript Slides

Ben-Gurion University of the Negev
Department of Computer Science
Distributed Search by Agents with
Personal Preferences
Alon Grubshtein
Before we begin…
Ben-Gurion University of the Negev
Department of Computer Science
In this talk:
Constraint
Reasoning
Distributed
Computing
Distributed
Constraint
Reasoning
Multi Agent
Systems
Ben-Gurion University of the Negev
Department of Computer Science
Sometime back in 2006
I can use it to work on my
You
Letscan
write
even
a distributed
write programs
agentfor
to
Check
calendar!!!
out this great
Who phone
needs aI got
automate meeting
it… coordination
computer with such phones?
Ben-Gurion University of the Negev
Department of Computer Science
Constraint reasoning (centralized)
A Constraint Reasoning problem:
• Variables
• Domains
• Constraints (relations)
A solution concept (target objective)
Ben-Gurion University of the Negev
Department of Computer Science
Examples
Ben-Gurion University of the Negev
Department of Computer Science
What’s in a constraint?
Two important classes of problems:
• Constraint Satisfaction (CSP)
𝐷𝑖1 × … × 𝐷𝑖𝑘 → 0,1
• Constraint Optimization (COP)
𝐷𝑖1 × … × 𝐷𝑖𝑘 → ℝ+
Ben-Gurion University of the Negev
Department of Computer Science
Constraint algorithms
How do we find a solution?
Enumerate feasible outcomes
Backtracking / Branch and Bound
Intelligent backtracking
Pre processing, forward checking and
heuristics
• Local search algorithms
•
•
•
•
Ben-Gurion University of the Negev
Department of Computer Science
From centralized to distributed
The problem itself is distributed
across computational nodes – agents:
• Privacy
• “Difficulty”
Ben-Gurion University of the Negev
Department of Computer Science
Constraint reasoning (distributed)
Distributed Constraint Reasoning (DCR)
problem:
•
Agents
•
•
•
Variables
Domains
Constraints (relations)
Ben-Gurion University of the Negev
Department of Computer Science
From centralized to distributed
• Computation on separate entities
• Communication via messages
• Each agent knows only a small portion of
the problem
• Allows for parallel computation
DISTRIBUTED =/= PARALLEL
Ben-Gurion University of the Negev
Department of Computer Science
DCR algorithms
Ben-Gurion University of the Negev
Department of Computer Science
Local Search for “real” problems
• Computationally hard
• Simplistic myopic algorithms
(“local search”/“adaptive heuristics”)
• Example, DSA:
1. Pick a random assignment
2. While (stop condition):
a.
b.
Send assignment to all neighbors (receive)
If can improve local state by changing assignment:
change with probability p
Ben-Gurion University of the Negev
Department of Computer Science
A simple MAS example
Coordinating a meeting (e.g., seminar):
•
•
•
•
•
•
Two alternatives: Morning or Evening
More participants – better
Prof. Lynn does not care when
If students disagree - morning
Alice prefers morning
Anna prefers evening
Prof. Lynn
Alice
Anna
Anna M
Alice
E
Anna M
Alice
E AliceAnna M
E
M
5
1
M
5,3
1,0
M
3
0
E
0
2
E
0,2
2,4
E
2
4
Ben-Gurion University of the Negev
Department of Computer Science
Solving as a DCOP
Alice
Anna
M
Alice
Bob
M
E
M
5 8, 3
1 1, 0
E
0 2, 2
2 6, 4
Alice
Ben-Gurion University of the Negev
Department of Computer Science
Anna
Cost:
M
8
E
E
1
M
2
E
6
Standard model solutions
• Easiest solution:
Disclose preferences
• An alternate approach:
Add unary constraints
• Problem: Can prove that this approach will
fail on some instances
Ben-Gurion University of the Negev
Department of Computer Science
How its done these days
The PEAV formulation:
hard constraints
x1
x21
x
y
a
3
6
b
7
5
A1
x1
x2
x2 1
A2
x1 2
x12
mirror variables
x2
x
y
a
4
1
b
2
8
•Modified search space
 Can’t be used with many local search algorithm!
•Requires more space
Ben-Gurion University of the Negev
Department of Computer Science
Introducing ADCOPs
Different preferences on outcomes are
not part of the standard model…
Asymmetric constraints
Formally:
𝐷𝑖1 × … × 𝐷𝑖𝑘 → ℝ𝑘+
Captures the idea that each agent has a personal
“table” with costs/gains of each outcome
Ben-Gurion University of the Negev
Department of Computer Science
ADCOPs
• ADCOPs:
• At least as expressive as existing model
• Succinct representation
• Used with existing local search algorithms
Ben-Gurion University of the Negev
Department of Computer Science
ADCOP Local Search (quality)
12000
DCOP
ADCOP
10000
9000
Solution Cost
0
Solution Cost
Solution Cost
11000
MCS-MGM
8000
507000
100
150
200
0
50
100
Cycles
150
Cycles
GCA-MGM
200
ACLS
MGM2
6000
MGM
5000
DSA
4000
3000
2000
0
20
40
60
80
100
Cycles
Ben-Gurion University of the Negev
Department of Computer Science
120
140
160
180
200
Constraint
Reasoning
Distributed
Computing
Distributed
Constraint
Reasoning
Multi Agent
Systems
Ben-Gurion University of the Negev
Department of Computer Science
Rethinking agents joint objective
Difference in best and worst gains – Meeting Scheduling Problem
70
60
% Quality
50
40
30
Normalized
Utilitarian
20
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Number of meetings
Ben-Gurion University of the Negev
Department of Computer Science
24
25
26
27
28
29
30
Agreeing on an outcome
(what is a fair solution?)
• Game Theory defines stable points:
𝑈𝑖 𝑥𝑖∗ , 𝑥−𝑖 ≥ 𝑈𝑖 𝑥𝑖 , 𝑥−𝑖
• Assumptions:
1. Self interested
2. Rational (some knowledge)
Ben-Gurion University of the Negev
Department of Computer Science
Graphical Games
• ADCOPs are Games played on a Graph
• Closely related to Graphical Games
• ADCOPs:
Anna M
Alice
E
 No knowledge assumed
 Agents are cooperative
 An even more succinct representation
M
5,3
1,0
E
0,2
2,4
• Can use DCR techniques to solve a
game theoretic multi agent problem!
Ben-Gurion University of the Negev
Department of Computer Science
Asynchronous Nash BackTracking
(ANT)
• Transform a MAS to a Distributed
Constraint Problem
Two symmetric
constraints
Three asymmetric
constraints
• A distributed, asynchronous, nonbinary, asymmetric search
Ben-Gurion University of the Negev
Department of Computer Science
ANT
•
•
•
•
A satisfaction problem
Inspired by ABT (ABT-1ph)
A solution always exists
Guaranteed to find an epsilon NE:
𝑈𝑖 𝑥𝑖∗ , 𝑥−𝑖 + 𝜖 ≥ 𝑈𝑖 𝑥𝑖 , 𝑥−𝑖
• More efficient than other distributed
GG solvers
Ben-Gurion University of the Negev
Department of Computer Science
Constraint
Reasoning
Distributed
Computing
Distributed
Constraint
Reasoning
Multi Agent
Systems
Ben-Gurion University of the Negev
Department of Computer Science
The quality of a stable solution
• A stable solution is not necessarily a
good one…
A2 \ A1
Cooperate
Defect
Cooperate
Defect
4,4
6,0
0,6
1,1
• Why is that?
• Competitive solution for cooperative
agents?
Ben-Gurion University of the Negev
Department of Computer Science
Agreeing on an outcome
(what is a fair solution?)
Stable points: Nash (pure/mixed),
Bayesian, Strong, Correlated, …
Utilitarian, Egalitarian,
Leximin,…
Ben-Gurion University of the Negev
Department of Computer Science
A different approach
assume cooperation but try to incentivize
agents by examining personal goals
• “Cost of Cooperation”
• Baseline search
Ben-Gurion University of the Negev
Department of Computer Science
The Cost of Cooperation (CoC) criteria:
The difference in an agent’s gain from the worst
equilibrium (from its point of view) outcome and
from cooperatively solving the problem
Non positive CoC solutions
U2(x)
Nash equilibrium solutions
Pareto front
Optimal solution
(max sum)
U1(x)
Possible solutions
Ben-Gurion University of the Negev
Department of Computer Science
A simple P2P example
C2
u2=high
aF2
aS5
u1=low
=med
aFS1
aF3
aS6
a8
C1
a4
Ben-Gurion University of the Negev
Department of Computer Science
a7
• Agents only interact with neighbors
(unknown topology)
• An agent’s gain is lowered when exerting
resources on sharing (S)
• Gain is maximized if an agent can free
ride the efforts of other agents (F)
• Gain is lowest if no one shares
Competitive and Cooperative solutions
A Bayesian stable solution
(possible)
0
F
a2
Cooperative Solution
1
0
F
a5
2
1
S
0.3
F
F
a1
a3
S
a6
a8
1
1
a
F
4
0
Fa
a
F
0.3
a
F
Ben-Gurion University of the Negev
Department of Computer Science
a
S
3
a
F
6
0.3
8
0.3
a
F
7
0
5
a
S
1
1
a
F
1
4
a
F
7
1
1
Cost of Cooperation solution
0.3
S
a2
Sa
0.3
5
Fa
Fa
1
0
Fa
3
Sa
6
1
8
1
a
F
4
0
0.3
Sa
7
0.3
• An improvement can be guaranteed
(proved) for a set of interactions!
Ben-Gurion University of the Negev
Department of Computer Science
Applied to network games
Maximizing utilities
Ben-Gurion University of the Negev
Department of Computer Science
ADCOP (CoC)
35
Constraint
Reasoning
Distributed
Computing
Distributed
Constraint
Reasoning
Multi Agent
Systems
Ben-Gurion University of the Negev
Department of Computer Science
Limits of the CoC approach
• So far we have seen several solutions:
Fully cooperative (Utilitarian)
Stable (Epsilon Nash Equilibrium)
A combination:
Non positive Cost of Cooperation
• However…
A2 \ A1
Up
Down
Left
Right
2,5
6,1
4,1
0,3
Ben-Gurion University of the Negev
Department of Computer Science
NO Cost of Cooperation solution!
A framework for partial cooperation
• Agents gain is different
• Do not “improve cooperatively”
• Define cooperation with respect to
some baseline solution
• Agents must agree on the baseline
(may need to apply a simple search
algorithm).
Ben-Gurion University of the Negev
Department of Computer Science
Modes of cooperation
• Define modes of cooperation within an
Interaction Process:
 Non-Cooperative (NC) – agents are driven
by their own goals and act rationally.
Can serve as a baseline solution
 Guaranteed Personal Benefit (GPB) – agents
seek an agreement and may take irrational
steps.
 Guarantees a Pareto improvement
 λ-cooperation – agents agree to a bounded
loss from their NC gain (up to some
predefined λ)
Ben-Gurion University of the Negev
Department of Computer Science
Local Search and Partial Cooperation
Maintain threshold/guarantee:
1. Incorporate with distributed “anytime”
 Can use any LS algorithm
 Focus on exploration
2. Tailor an algorithm
 maintain invariant (begins in a “legal” state)
Ben-Gurion University of the Negev
Department of Computer Science
Evaluation
Three key parameters:
1. Compromise levels (lambda)
2. Agents’ degree
3. Costs distribution
24000
23000
Solution Cost
22000
Goods-MGM
21000
AGC
20000
MGM
19000
MGM2
18000
MCS-MGM
GCA-MGM
17000
16000
0
500
1000
Cycles
Ben-Gurion University of the Negev
Department of Computer Science
1500
2000
Constraint
Reasoning
Distributed
Computing
Distributed
Constraint
Reasoning
Multi Agent
Systems
Ben-Gurion University of the Negev
Department of Computer Science
SUMMARY & CONCLUSIONS
Ben-Gurion University of the Negev
Department of Computer Science
Summary
DCSP/DCOP
Utilitarian
(Minimal sum of costs)
Multi Agent
Problem
Stable
ε-Nash Equilibrium
Asymmetric
Constraints
Non positive Cost
of Cooperation
Partial
Cooperation
Ben-Gurion University of the Negev
Department of Computer Science
Conclusions
• Three points (‘up and down the ladder of
abstraction’):
1. How to model the problem
2. How does the model effect the means to find a
solution
3. What is a solution?
• Rethinking basic assumptions
• Applying well established models to
simple realistic settings can reveal many
of its shortcoming
Ben-Gurion University of the Negev
Department of Computer Science
Journal publications:
•
Arnon Netzer, Alon Grubshtein and Amnon Meisels, “Concurrent Forward Bounding”, Artificial Intelligence, Vol. 193,
pp. 186-216, 2012.
•
Roie Zivan, Alon Grubshtein and Amnon Meisels, “Hybrid Search for Dynamically changing CSPs”, Constraints, special
issue on constraint satisfaction for planning and Scheduling, Vol. 16, num. 3, pp. 228-249, 2011.
•
Alon Grubshtein and Amnon Meisels, “Cost of Cooperation for Scheduling Meetings”, Journal of Computer Science and
Information System (ComSIS), Vol. 7, num. 3, pp. 551-567, 2010.
Conference and workshops publications :
•
Alon Grubshtein and Amnon Meisels, “Finding a Nash Equilibrium by Asynchronous Backtracking”, 18th Intl. Conf. on
Principles and Practice of Constraint Programming (CP’12), pp. 925-940, Quebec city, Canada, Oct. 2012.
•
Alon Grubshtein, Roie Zivan and Amnon Meisels, “Partial Cooperation in Multi Agent Local Search”, 20th European Conf.
on Artificial Intelligence,pp.378-383, Montpellier France, Aug. 2012
•
Roie Zivan, Alon Grubshtein, Michal Friedman and Amnon Meisels, “Partial Cooperation in Multi Agent Search”,
(Extended Abstract) Proc. 11th intern. Conf. Autonom. Agents Multi agent Sys. (AAMAS’12), Valencia, Spain.
•
Alon Grubshtein and Amnon Meisels, “A Distributed Cooperative Approach for Optimizing a Family of Network
Games”, Proc. of the 5th Intern. Symp. on Intelligent Distributed Computing (IDC’11), Delft, the Netherlands, pp. 49-62,
October 2011.
•
Alon Grubshtein and Amnon Meisels, “A Distributed Cooperative Approach for Optimizing a Network Game”, Proc. 13th
Intern. Workshop on Dist. Constraints Reasoning (DCR’11), Barcelona, Spain, June 2011.
•
Alon Grubshtein, Nir Herschorn, Arnon Netzer, Guy Rapaport, Guy Yaffe and Amnon Meisels, “The Distributed
Constraints (DisCo) Simulation Tool”, Proc. 13th Intern. Workshop on Dist. Constraints Reasoning (DCR’11), Barcelona,
Spain, June 2011.
•
Alon Grubshtein and Amnon Meisels, “Cooperation Mechanism for a Network Game”, Proc. 3rd Intern. Conf. Agents and
AI (ICAART’11), Rome, Italy, pp. 336-341, January 2011.
•
Alon Grubshtein, Tal Grinshpoun, Amnon Meisels and Roie Zivan, “Local Search for Distributed Asymmetric
Optimization”, Proc. 9th intern. Conf. Autonom. Agents Multi agent Sys. (AAMAS’10), Toronto, Canada, pp. 1015-1022,
May 2010.
•
Arnon Netzer, Amnon Meisels and Alon Grubshtein, “Concurrent Forward Bounding for DCOPs”, Proc. 12th Intern.
Workshop on Dist. Constraints Reasoning (DCR’10) at AAMAS’10, Toronto, May 2010.
•
Alon Grubshtein, Nurit Gal-Oz, Tal Grinshpoun, Amnon Meisels and Roie Zivan, “Manipulating Recommendation Lists
by Global Considerations”, Proc. 2nd Intern. Conf. Agents and AI (ICAART’10),pp. 135-142, Valencia, Spain, January 2010.
•
Alon Grubshtein and Amnon Meisels, “Cost of Cooperation for Scheduling Meetings”, Proc. 3rdIntern.Symp. Intell. Dist.
Comp. (IDC’09), Vol. 237, pp. 227-236, Ayia Napa, Cyprus, October 2009.
•
Alon Grubshtein, Tal Grinshpoun, Amnon Meisels and Roie Zivan, “Asymmetric Distributed Constraint Optimization”,
Proc. 11th Intern. Workshop on Dist. Constraints Reasoning (DCR’09) at IJCAI-09, Pasadena CA, July 2009.
•
Ehud Gudes, Nurit Gal-Oz and Alon Grubshtein, “Methods for Computing Trust and Reputation While Preserving
Privacy”, Proc. Data and App. Security XXIII, 23rd Ann. IFIP WG 11.3 Working Conf. (DBSEC’09), Vol. 5645, pp. 291-298,
Montreal, Canada, July 2009.
•
Amir Gershman, Alon Grubshtein, Amnon Meisels and Roie Zivan, “Scheduling Meetings by Agents”, Proc.7thintern.
Conf. Practice and Theory Auto. Timetabling (PATAT’08), Montreal, August 2008.
Ben-Gurion University of the Negev
Department of Computer Science