Using DCOP to Model Resource Allocation: A Review of Algorithms

• Alexander R. Gularte FURG
• Diana Francisca Adamatti FURG

Resumo

Distributed Constraint Optimization Problem (DCOP) is a formalism that is widely used for coordination in multiagent systems. The advantage of applying these algorithms for multiagent coordination is due to the fact that them are distributed, robust and scalable. The aim of this work is to present a revision of the complete and incomplete algorithms, generally found in the literature and how these approaches can benefit the resource allocation in Multiagent Systems.

Referências

Apt, K. (2003). Principles of constraint programming. Cambridge University Press.

Farinelli, A., Rogers, A., Petcu, A., e Jennings, N. R. (2008). Decentralised coordination of low-power embedded devices using the max-sum algorithm. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2, AAMAS ’08, pages 639–646, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.

Ferreira Jr, P. R., Boffo, F. S., e Bazzan, A. L. (2008). Using swarm-gap for distributed task allocation in complex scenarios. In Massively Multi-Agent Technology, pages 107–121. Springer.

Kschischang, F., Member, S., Frey, B. J., e andrea Loeliger, H. (2001). Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47:498–519.

Macarthur, K. S. (2011). Multi-Agent Coordination for Dynamic Decentralised Task Allocation. PhD thesis, University of Southampton.

Mailler, R. e Lesser, V. (2004). Solving distributed constraint optimization problems using cooperative mediation. In International Conference on Autonomous Agents: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-, volume 1, pages 438–445.

Modi, P. J., Shen, W.-M., Tambe, M., e Yokoo, M. (2005). Adopt: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161(1):149–180.

Petcu, A. e Faltings, B. (2005). A scalable method for multiagent constraint optimization. In International Joint Conference on Artificial Intelligence, volume 19, page 266. LAWRENCE ERLBAUM ASSOCIATES LTD.

Rogers, A., Farinelli, A., Stranders, R., e Jennings, N. R. (2011). Bounded approximate decentralised coordination via the max-sum algorithm. Artificial Intelligence, 175(2):730–759.

Scerri, P., Farinelli, A., Okamoto, S., e Tambe, M. (2005). Allocating tasks in extreme teams. In Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pages 727–734. ACM.

Schiex, T., Fargier, H., Verfaillie, G., et al. (1995). Valued constraint satisfaction problems: Hard and easy problems. In International Joint Conference on Artificial Intelligence, volume 14, pages 631–639. Citeseer.

Stranders, R., Farinelli, A., Rogers, A., e Jennings, N. R. (2009). Decentralised coordination of mobile sensors using the maxsum algorithm. In Proceedings of the 21st international jont conference on Artifical intelligence, pages 299–304. Morgan Kaufmann Publishers Inc.

Yeoh, W. (2010). SPEEDING UP DISTRIBUTED CONSTRAINT OPTIMIZATION SEARCH ALGORITHMS. PhD thesis, UNIVERSITY OF SOUTHERN CALIFORNIA.

Yokoo, M., Ishida, T., Durfee, E. H., e Kuwabara, K. (1992). Distributed constraint satisfaction for formalizing distributed problem solving. In Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on, pages 614–621. IEEE.