No-commitment branch and bound search for distributed constraint optimization

ABSTRACT

We present a new polynomial-space algorithm for solving Distributed Constraint Optimization problems (DCOP). The algorithm, called NCBB, is branch and bound search with modifications for efficiency in a multiagent setting. Two main features of the algorithm are: (a) using different agents to search non-intersecting parts of a search space concurrently, and (b) communicating lower bounds on solution cost every time there is a possibility the bounds might change due to changed variable assignments. The first leads to a better utilization of computational resources of multiple participating agents, while the second provides for more efficient pruning of search space.Experimental results show that NCBB has significantly better performance than another polynomial-space algorithm, ADOPT, on random graph coloring problems. Under assumptions of cheap communication it also has comparable performance with DPOP despite using only polynomial memory as opposed to exponential memory for DPOP.

REFERENCES

• 1: Syed Ali , Sven Koenig , Milind Tambe, Preprocessing techniques for accelerating the DCOP algorithm ADOPT, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082631]
• 2: K. Hirayama and M. Yokoo. Distributed partial constraint satisfaction problem. In Principles and Practice of Constraint Programming, pages 222--236, 1997.
• 3: E. L. Lawler and D. E. Wood. Branch-and-bound methods: A survey. Operations Research, 14(4):699--719, 1966.
• 4: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 5: Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
• 6: A. Meisels, E. Kaplansky, I. Razgon, and R. Zivan. Comparing performance of distributed constraints processing algorithms. In Proc. of DCR Workshop, AAMAS, 2002.
• 7: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, v.161 n.1-2, p.149-180, January 2005 [doi>10.1016/j.artint.2004.09.003]
• 8: A. Petcu and B. Faltings. An efficient constraint optimization method for large multiagent systems. In Proc. of the LSMAS Workshop, AAMAS, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

General Terms:
Algorithms

Keywords:
cooperative distributed problem solving in agent system