Preprocessing techniques for accelerating the DCOP algorithm ADOPT

ABSTRACT

Methods for solving Distributed Constraint Optimization Problems (DCOP) have emerged as key techniques for distributed reasoning. Yet, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have successfully been used to speed up algorithms for centralized constraint satisfaction problems. This paper introduces a framework of different preprocessing techniques that are based on dynamic programming and speed up ADOPT, an asynchronous complete and optimal DCOP algorithm. We investigate when preprocessing is useful and which factors influence the resulting speedups in two DCOP domains, namely graph coloring and distributed sensor networks. Our experimental results demonstrate that our preprocessing techniques are fast and can speed up ADOPT by an order of magnitude.

REFERENCES

• 1: Stefano Bistarelli , Rosella Gennari , Francesca Rossi, Constraint Propagation for Soft Constraints: Generalization and Termination Conditions, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.83-97, September 18-21, 2000
• 2: Joseph Culberson , Ian Gent, Frozen development in graph coloring, Theoretical Computer Science, v.265 n.1_2, p.227-264, 08/28/2001 [doi>10.1016/S0304-3975(01)00164-5]
• 3: John Davin , Pragnesh Jay Modi, Impact of problem centralization in distributed constraint optimization algorithms, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082633]
• 4: R. Dechter and I. Meiri. Experimental evaluation of preprocessing techniques in constraint satisfaction problems. In IJCAI, pages 271--277, 1989.
• 5: O. Hansson, A. Mayer, and M. Valtorta. A new result on the complexity of heuristic estimates for the A* algorithm. Artificial Intelligence, 55(1):129--143, 1992.
• 6: K. Hirayama and M. Yokoo. Distributed partial constraint satisfaction problem. In CP, pages 222--236, 1997.
• 7: Hyuckchul Jung , Milind Tambe, Performance models for large scale multiagent systems: using distributed POMDP building blocks, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860623]
• 8: Victor Lesser , Milind Tambe , Charles L. Ortiz, Distributed Sensor Networks: A Multiagent Perspective, Kluwer Academic Publishers, Norwell, MA, 2003
• 9: Rajiv T. Maheswaran , Milind Tambe , Emma Bowring , Jonathan P. Pearce , Pradeep Varakantham, Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.310-317, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.257]
• 10: 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]
• 11: 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]
• 12: 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
• 13: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, An asynchronous complete method for distributed constraint optimization, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860602]
• 14: 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]
• 15: Paul Scerri , Jay Modi , Wei-Min Shen , Milind Tambe, Are multiagent algorithms relevant for real hardware?: a case study of distributed constraint algorithms, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952543]
• 16: Thomas Schiex, Arc Consistency for Soft Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.411-424, September 18-21, 2000
• 17: N. Schurr, S. Okamoto, R. Maheswaran, P. Scerri, and M. Tambe. Evolution of a teamwork model. In R. Sun, editor, Cognition and Multi-Agent Interaction: From Cognitive Modeling to Social Simulation, page (to appear). Cambridge University Press, 2005.
• 18: Marius-Calin Silaghi , Djamila Sam-Haroud , Boi Faltings, Consistency Maintenance for ABT, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.271-285, November 26-December 01, 2001
• 19: R. Wallace. Enhancements of branch and bound methods for the maximal constraint satisfaction problem. In AAAI, pages 188--195, 1996.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
distributed constraint optimization