A complete distributed constraint optimization method for non-traditional pseudotree arrangements

ABSTRACT

Distributed Constraint Optimization (DCOP) is a general framework that can model complex problems in multiagent systems. Several current algorithms that solve general DCOP instances, including ADOPT and DPOP, arrange agents into a traditional pseudotree structure. We introduce an extension to the DPOP algorithm that handles an extended set of pseudotree arrangements. Our algorithm correctly solves DCOP instances for pseudotrees that include edges between nodes in separate branches. The algorithm also solves instances with traditional pseudotree arrangements using the same procedure as DPOP.

We compare our algorithm with DPOP using several metrics including the induced width of the pseudotrees, the maximum dimensionality of messages and computation, and the maximum sequential path cost through the algorithm. We prove that for some problem instances it is not possible to generate a traditional pseudotree using edge-traversal heuristics that will outperform a cross-edged pseudotree. We use multiple heuristics to generate pseudotrees and choose the best pseudotree in linear space-time complexity. For some problem instances we observe significant improvements in message and computation sizes compared to DPOP.

REFERENCES

• 1: J. Liu and K. P. Sycara. Exploiting problem structure for distributed constraint optimization. In V. Lesser, editor, Proceedings of the First International Conference on Multi-Agent Systems, pages 246--254, San Francisco, CA, 1995. MIT Press.
• 2: 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
• 3: 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]
• 4: A. Petcu. Frodo: A framework for open/distributed constraint optimization. Technical Report No. 2006/001 2006/001, Swiss Federal Institute of Technology (EPFL), Lausanne (Switzerland), 2006. http://liawww.epfl.ch/frodo/.
• 5: A. Petcu and B. Faltings. A-dpop: Approximations in distributed optimization. In poster in CP 2005, pages 802--806, Sitges, Spain, October 2005.
• 6: A. Petcu and B. Faltings. Dpop: A scalable method for multiagent constraint optimization. In IJCAI 05, pages 266--271, Edinburgh, Scotland, Aug 2005.
• 7: Adrian Petcu , Boi Faltings , David C. Parkes, MDPOP: faithful distributed implementation of efficient social choice problems, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160895]
• 8: G. Ushakov. Solving meeting scheduling problems using distributed pseudotree-optimization procedure. Master's thesis, École Polytechnique Fédérale de Lausanne, 2005.
• 9: M. Yokoo, E. H. Durfee, T. Ishida, and K. Kuwabara. Distributed constraint satisfaction for formalizing distributed problem solving. In International Conference on Distributed Computing Systems, pages 614--621, 1992.
• 10: Makoto Yokoo , Edmund H. Durfee , Toru Ishida , Kazuhiro Kuwabara, The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.673-685, September 1998 [doi>10.1109/69.729707 ]

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 satisfaction and optimization, multiagent coordination