===============

A Framework for Local Algorithms used in Distributed Constraint Optimization Problems.

About

The package offers a modular framework for developing iterative approximate best-response algorithms for solving DCOPs and several algorithm implementations. [1]

• DSA (Distributed Stochastic Algorithm, variants A and B) [1,3]
• DSAN (Distributed Simulated Annealing) [2]
• JSFP-I (Joint Strategy Fictitious Play with Inertia) [4]
• WRM-I (Weighted Regret Monitoring with Inertia) [1,5]

The research based on the Cuilt framework is published in a short [6] and long [7] form. Further research that explores combining algorithms with rank information based on a modification of the PageRank algorithm [8] is detailed in two more publications [9,10].

Usage

Ensure Java 8 is used for the compilation and install SBT, as described in the README file of the "signal-collect" project.

The project has the following dependencies:

• signal-collect
• signal-collect-torque (only for the evaluation on a cluster)
• signal-collect-slurm (only for the evaluation on a cluster)

Follow the compilation instructions in the "signal-collect" README.

After cloning the repository, go to the project folder and start SBT on the command line. Use the "assembly" command in SBT to generate a .jar file with dependencies.

To generate an Eclipse project, use the "eclipse" command on the SBT prompt and then follow the description in the "How to Develop in Eclipse" section of the "signal-collect" README.

Note

Before submitting a job to a Torque or Slurm host, it is imperative to re-run "assembly" in SBT in order to have the last version of the .jar file run.

Bibliography:

• [1] Archie C. Chapman, Alex Rogers, Nicholas R. Jennings and David S. Leslie (2011). A unifying framework for iterative approximate best-response algorithms for distributed constraint optimization problems. The Knowledge Engineering Review, 26, pp 411-444. doi:10.1017/S0269888911000178.
• [2] Arshad, Silaghi, 2003. "Distributed Simulated Annealing and comparison to DSA", In Proceedings of the 4th International Workshop on Distributed Constraint Reasoning, Acapulco, Mexico
• [3] Zhang, Wang, Wittenburg, 2002. "Distributed stochastic search for constraint satisfaction and optimization: Parallelism, phase transitions and performance", In Proceedings of AAAI-02 Workshop on Probabilistic Approaches in Search, 2002, pp. 53–59
• [4] Marden, Jason R., Gürdal Arslan, and Jeff S. Shamma. "Joint strategy fictitious play with inertia for potential games." Automatic Control, IEEE Transactions on 54.2 (2009): 208-220.
• [5] Arslan, G., Marden, J. R. & Shamma, J. S. 2007. "Autonomous vehicle-target assignment: a game theoretical formulation". ASME Journal of Dynamic Systems, Measurement and Control 129, 584–596.
• [6] C.M. Verman, Philip Stutz, Robin Hafen, Abraham Bernstein (2016). "Cuilt: a Scalable, Mix-and-Match Framework for Local Iterative Approximate Best-Response Algorithms", In: 22nd European Conference on Artificial Intelligence, IOS Press Ebooks.
• [7] C.M. Verman, Philip Stutz, Robin Hafen, Abraham Bernstein (2016). "Exploring Hybrid Iterative Approximate Best-Response Algorithms for Solving DCOPs", In: International Workshop on Optimisation in Multi-agent Systems
• [8] Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). "The PageRank citation ranking: Bringing order to the web", In: Stanford InfoLab.
• [9] Andreas Flückiger, C.M. Verman, Abraham Bernstein (2016). "Improving Approximate Algorithms for DCOPs Using Ranks", In: International Workshop on Optimisation in Multi-Agent Systems
• [10] C.M. Verman, Philip Stutz, Abraham Bernstein (2014). "Solving Distributed Constraint Optimization Problems Using Ranks", In: Statistical Relational AI. Papers Presented at the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI Press, Palo Alto, California.