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 variations of the ADOPT and incomplete algorithms for solving DCOP.  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.

 

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 © American Association for Artificial Intelligence ( FLAIRS 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
Multi-criteria MGM2 + Original MGM2 (also includes [MC-]MGM1) (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
Asynchronous Simulation Toolkit (DALO-k and DALO-t).	Christopher Kiekintveld, Zhengyu Yin, Atul Kumar, Milind Tambe. "Asynchronous Algorithms for Approximate Distributed Constraint Optimization with Quality Bounds" , In AAMAS, 2010.	here
Random Graph Generator with K-OPT and T-OPT Bound Solver	Christopher Kiekintveld, Zhengyu Yin, Atul Kumar, Milind Tambe. "Asynchronous Algorithms for Approximate Distributed Constraint Optimization with Quality Bounds" , In AAMAS, 2010.	here
k-optimal and t-optimal bounds generator	This program (written in JAVA) can compute k-optimal and t-optimal bounds given a specific graph. It only outputs LP model file. So to solve it, you must have glpsol. It's an open source LP solver which can be found here: http://www.go.dlr.de/pdinfo_dv/glpk.html To start, you may look at LFPGenerator.java (which generates a bunch of random graphs and computes the average bound).	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
MC-DCOP Graph Coloring Datasets	R.T. Maheswaran, J.P. Pearce, M. Tambe. “On K-Optimal Distributed Constraint Optimization Algorithms: New Bounds and Algorithms” In AAMAS, 2008.	here

 

 

References

Manish Jain, Matthew Taylor, Milind Tambe, Makoto Yokoo. “DCOPs Meet the RealWorld: Exploring Unknown Reward Matrices with Applications to Mobile Sensor Networks” In International Joint Conference on Artificial Intelligence (IJCAI), 2009. Matthew E. Taylor, Manish Jain, Prateek Tandon, Milind Tambe. “Using DCOPs to Balance Exploration and Exploitation in Time-Critical Domains” In Proceedings of the IJCAI 2009 Workshop on Distributed Constraint Reasoning (DCR 2009). Matthew E. Taylor, Manish Jain, Yanquin Jin, Makoto Yooko, and Milind Tambe. “When Should There be a “Me” in “Team”? Distributed Multi-Agent Optimization Under Uncertainty” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2010. Supplemental Material          k3.pdf

Software DCEE Python Simulator Code, Version 0.9. 2/5/2010

 

Other material

 

Document	Download
Adopt presentation slides by Jay Modi	PPT PS PDF PDF (B&W)
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{Yin:2008 ,

author = "Zhengyu Yin",

year = "2008",

title = "{USC} DCOP Repository",

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

}