USC Distributed Constraint Optimization Problem (DCOP) Repository
maintained by Mohit Goenka
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.
ADOPT with preprocessing and valued constraints (newest version of ADOPT)
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.
Multi-criteria ADOPT (MCA)
E. Bowring, M. Tambe, M. Yokoo. "Multiply Constrained Distributed Constraint Optimization” In AAMAS, 2006.
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 )
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.
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.
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.
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.
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.
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).
 
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.
Sensor net and graph coloring datasets
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.
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.
MC-DCOP Graph Coloring Datasets
 
 
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
Adopt FAQ by Jay Modi
Results from S. Ali, S. Koenig, M. Tambe. “Preprocessing techniques for accelerating the DCOP algorithm ADOPT.” In AAMAS, 2005.
 
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:
Yin, Zhengyu (2008). USC DCOP Repository [ http://teamcore.usc.edu/dcop/ . Los Angeles, CA: University of Southern California, Department of Computer Science.
 
Or, for BiBTeX:
@misc{Yin:2008 ,
author = "Zhengyu Yin",
year = "2008",
title = "{USC} DCOP Repository",
institution = "University of Southern California, Department of Computer Science"
}
 
Please contact Mohit Goenka ( mgoenka@usc.edu ) if you have any questions about the contents of this page.