An asynchronous complete method for distributed constraint optimization

ABSTRACT

We present a new polynomial-space algorithm, called Adopt, for distributed constraint optimization (DCOP). DCOP is able to model a large class of collaboration problems in multi agent systems where a solution within given quality parameters must be found. Existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while operating both efficiently and asynchronously. Adopt 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. Adopt obtains these properties via a distributed search algorithm with several novel characteristics including the ability for each agent to make local decisions based on currently available information and without necessarily having global certainty. Theoretical analysis shows that Adopt provides provable quality guarantees, while experimental results show that Adopt is significantly more efficient than synchronous methods. The speedups are shown to be partly due to the novel search strategy employed and partly due to the asynchrony of the algorithm.

REFERENCES

• 1: Y. Hamadi, C. Bessiere, and J. Quinqueton. Backtracking in distributed constraint networks. In European Conference on Artificial Intelligence, 1998.
• 2: K. Hirayama and M. Yokoo. Distributed partial constraint satisfaction problem. In G. Smolka, editor, Principles and Practice of Constraint Programming, pages 222--236. 1997.
• 3: An Approach to Over-constrained Distributed Constraint Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.135, July 10-12, 2000
• 4: Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
• 5: J. Liu and K. Sycara. Exploiting problem structure for distributed constraint optimization. In Proceedings of International Conference on Multi-Agent Systems, 1995.
• 6: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 7: P. Mesequer and M. A. Jiménez. Distributed forward checking. In Proceedings of CP-00 Workshop on Distributed Constraint Satisfaction, 2000.
• 8: Pragnesh J. Modi , Hyuckchul Jung , Milind Tambe , Wei-Min Shen , Shriniwas Kulkarni, A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.685-700, November 26-December 01, 2001
• 9: T. Schiex, H. Fargier, and G. Verfaillie. Valued constraint satisfaction problems: Hard and easy problems. In International Joint Conference on Artificial Intelligence, 1995.
• 10: W.-M. Shen, B. Salemi, and P. Will. Hormone-inspired adaptive communication and distributed control for conro self-reconfigurable robots. IEEE Transactions on Robotics and Automation, 2002.
• 11: Marius-Calin Silaghi , Djamila Sam-Haroud , Boi Faltings, Asynchronous Search with Aggregations, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.917-922, July 30-August 03, 2000
• 12: M. Tambe. Towards flexible teamwork. Journal of Artificial Intelligence Research (JAIR), 7:83--124, 1997.
• 13: Makoto Yokoo, Distributed constraint satisfaction: foundations of cooperation in multi-agent systems, Springer-Verlag, London, 2001
• 14: Weixiong Zhang , Lars Wittenburg, Distributed breakout revisited, Eighteenth national conference on Artificial intelligence, p.352-357, July 28-August 01, 2002, Edmonton, Alberta, Canada

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms

Keywords:
constraint satisfaction/optimization, multi-agent coordination