USC Distributed Constraint Optimization Problem (DCOP) Repository

In a DCOP, cooperative agents, each in control of one or more variables, work together to optimize a set of constraints that exist upon the variables.  This page contains DCOP datasets and two variations of the ADOPT algorithm for solving DCOPs.  ADOPT is a polynomial space algorithm that is guaranteed to find an optimal solution, or a solution within a user-specified distance from the optimal, while allowing agents to execute asynchronously and in parallel.

 

News

Ninth International Workshop on Distributed Constraint Reasoning (DCR) was held at CP-07.

Software

 

Software	References	Download
Original ADOPT	P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “ADOPT: Asynchronous distributed constraint optimization with quality guarantees.” Artificial Intelligence Journal(AIJ). 161:149–180, 2005 P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “ An asynchronous complete method for distributed constraint optimization.” In AAMAS, 2003.	here
ADOPT with preprocessing and valued constraints (newest version of ADOPT)	S. Ali, S. Koenig, M. Tambe. "Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT.” In AAMAS, 2005. R.T. Maheswaran, M. Tambe, E. Bowring, J.P. Pearce, P. Varakantham. “Taking DCOP to the Real World : Efficient Complete Solutions for Distributed Event Scheduling.” In AAMAS, 2004.	here
Multi-criteria ADOPT (MCA)	E. Bowring, M. Tambe, M. Yokoo. "Multiply Constrained Distributed Constraint Optimization” In AAMAS, 2006.	here
CSAA (Constraint Satisfaction Ant Algorithm) provided by Koen Mertens	K. Mertens, and T. Holvoet, CSAA: A distributed ant algorithm framework for constraint satisfaction, Proceedings of the 17th International Florida Artificial Intelligence Research Society Conference (Barr, V. and Markov, Z., eds.), pp. 764-769, 2004 pdf ps © American Association for Artificial Intelligence ( FLAIRS proceedings ) K. Mertens, and T. Holvoet, CSAA: A constraint satisfaction ant algorithm framework, Adaptive Computing in Design and Manufacture VI (Parmee, I.C., ed.), pp. 285-294, 2004 pdf ps © Springer ( ACDM proceedings )	here
Original MGM2	Implementation of 2-optimal algorithms in R.T. Maheswaran, J.P. Pearce, and M. Tambe, "Distributed Algorithms for DCOP: A Graphical-Game-Based Approach," in Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS), San Francisco, CA, September 15-17, 2004, pp. 432-439.	here
Original MGM2 + Multi-criteria MGM2 (Extended by Christopher Portway on top of Zvi Topol's implementation)	Extention of MGM2 (see above) to cover multiply-constrained graphs, specifically resourse and utility constraints. In a paper to appear in Ninth International Workshop on Distributed Constraint Reasoning (DCR) at CP-07.	here
MGM3 and SCA3 (implemented by Zvi Topol)	New 3-optimal algorithms based on 2-optimal algorithms in R.T. Maheswaran, J.P. Pearce, and M. Tambe, "Distributed Algorithms for DCOP: A Graphical-Game-Based Approach," in Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS), San Francisco, CA, September 15-17, 2004, pp. 432-439.	here

 

Datasets

 

Dataset	References	Download
Graph coloring datasets	P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “ADOPT: Asynchronous distributed constraint optimization with quality guarantees.” Artificial Intelligence Journal(AIJ). 161:149–180, 2005 P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “An asynchronous complete method for distributed constraint optimization.” In AAMAS, 2003.	here
Sensor net and graph coloring datasets	S. Ali, S. Koenig, M. Tambe, “Preprocessing techniques for accelerating the DCOP algorithm ADOPT.” In AAMAS, 2005.	here
Meeting scheduling and sensor net datasets	R.T. Maheswaran, M. Tambe, E. Bowring, J.P. Pearce, P. Varakantham, “Taking DCOP to the real world: efficient complete solutions for distributed event scheduling.” In AAMAS, 2004.	here
Graph coloring, randomized, and high-stakes UAV datasets	R.T. Maheswaran, J.P. Pearce, M. Tambe. “Distributed algorithms for DCOP: a graphical-game-based approach.” In PDCS, 2004.	here

 

Other material

 

Document	Download
Adopt presentation slides by Jay Modi	PPT PS PDF PDF (B&W) HTML
Adopt FAQ by Jay Modi	here
Results from S. Ali, S. Koenig, M. Tambe. “Preprocessing techniques for accelerating the DCOP algorithm ADOPT.” In AAMAS, 2005.	here

 

If you publish a paper using datasets obtained from this page, please include an acknowledgement in your paper, so that others can also find the datasets here.

Example:

 

Or, for BiBTeX:

@misc{Portway:2008 ,

author = "Christopher P. Portway",

year = "2008",

title = "{USC} DCOP Repository",

institution = "University of Southern California, Department of Computer Science"

}