Adopt Algorithm
Adopt Algorithm for Distributed Constraint Optimization
Pragnesh Jay Modi
Information Sciences Institute & Department of Computer Science University of Southern California http://www.isi.edu/~modi
Distributed Optimization Problem
“How do a set of agents optimize over a set of alternatives that have varying degrees of global quality?” Examples l allocating resources l constructing schedules l planning activities Difficulties l No global control/knowledge l Localized communication l Quality guarantees required l Limited time
2
Approach l l
Constraint Based Reasoning
– Distributed Constraint Optimization Problem (DCOP)
Adopt algorithm
– First-ever distributed, asynchronous, optimal algorithm for DCOP – Efficient, polynomial-space
l
Bounded error approximation
– Principled solution-quality/time-to-solution tradeoffs
3
Constraint Representation
Why constraints for multiagent systems? l Constraints are natural, general, simple
– Many successful applications l l
Leverage existing work in AI
– Constraints Journal, Conferences
Able to model coordination, conflicts, interactions, etc…
Key advances l Distributed constraints l Constraints have degrees of violation
4
Distributed Constraint Optimization (DCOP)
Given l Variables {x1, x2, …, xn}, each assigned to an agent l Finite, discrete domains D1, D2, … , Dn, l For each xi, xj, valued constraint fij: Di x Dj → N. Goal l Find complete assignment A that minimizes F(A) where,
F(A) = Σ fij(di,dj), xi←di,xj ←dj in A
Constraint Graph x1 x2 x3 x4
di dj f(di,dj) 1 2 2 0
x1
x1
0
0 F(A) = 0 x2 1
1
x1
1 F(A) = 4 x2 2 F(A) = 7 x2 0 x3 0 x4 x3
1
1 x4 x3
2
2 x4 5
Existing Methods
Optimization Branch and Bound
(Hirayama97)
Theoretical guarantee
?
Asynchronous Backtracking
(Yokoo92)
Satisfaction
No guarantee
Iterative Improvement
(Yokoo96)
Synchronous
Asynchronous
6
Execution Model
Pragnesh Jay Modi
Information Sciences Institute & Department of Computer Science University of Southern California http://www.isi.edu/~modi
Distributed Optimization Problem
“How do a set of agents optimize over a set of alternatives that have varying degrees of global quality?” Examples l allocating resources l constructing schedules l planning activities Difficulties l No global control/knowledge l Localized communication l Quality guarantees required l Limited time
2
Approach l l
Constraint Based Reasoning
– Distributed Constraint Optimization Problem (DCOP)
Adopt algorithm
– First-ever distributed, asynchronous, optimal algorithm for DCOP – Efficient, polynomial-space
l
Bounded error approximation
– Principled solution-quality/time-to-solution tradeoffs
3
Constraint Representation
Why constraints for multiagent systems? l Constraints are natural, general, simple
– Many successful applications l l
Leverage existing work in AI
– Constraints Journal, Conferences
Able to model coordination, conflicts, interactions, etc…
Key advances l Distributed constraints l Constraints have degrees of violation
4
Distributed Constraint Optimization (DCOP)
Given l Variables {x1, x2, …, xn}, each assigned to an agent l Finite, discrete domains D1, D2, … , Dn, l For each xi, xj, valued constraint fij: Di x Dj → N. Goal l Find complete assignment A that minimizes F(A) where,
F(A) = Σ fij(di,dj), xi←di,xj ←dj in A
Constraint Graph x1 x2 x3 x4
di dj f(di,dj) 1 2 2 0
x1
x1
0
0 F(A) = 0 x2 1
1
x1
1 F(A) = 4 x2 2 F(A) = 7 x2 0 x3 0 x4 x3
1
1 x4 x3
2
2 x4 5
Existing Methods
Optimization Branch and Bound
(Hirayama97)
Theoretical guarantee
?
Asynchronous Backtracking
(Yokoo92)
Satisfaction
No guarantee
Iterative Improvement
(Yokoo96)
Synchronous
Asynchronous
6
Execution Model