Proceedings

PC-DPOP: A New Partial Centralization Algorithm for Distributed Optimization

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 167-171.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Fully decentralized algorithms for distributed constraint optimization often require excessive amounts of communication when applied to complex problems. The OptAPO algorithm of Mailler and Lesser uses a strategy of partial centralization to mitigate this problem. We introduce PC-DPOP, a new partial centralization technique, based on the DPOP algorithm of Petcu and Faltings. PC-DPOP provides better control over what parts of the problem are centralized and allows this centralization to be optimal with respect to the chosen communication structure. Unlike OptAPO, PC-DPOP allows for a priory, exact predictions about privacy loss, communication, memory and computational requirements on all nodes and links in the network. Upper bounds on communication and memory requirements can be specified. We also report strong efficiency gains over OptAPO in experiments on three problem domains.

  1. [Davin and Modi, 2005] John Davin and Pragnesh Jay Modi. Impact of problem centralization in distributed constraint optimization algorithms. In AAMAS '05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pages 1057-1063, New York, NY, USA, 2005. ACM Press.
  2. [Dechter, 2003] Rina Dechter. Constraint Processing. Morgan Kaufmann, 2003.
  3. [Kask et al., 2005] Kalev Kask, Rina Dechter, and Javier Larrosa. Unifying cluster-tree decompositions for automated reasoning in graphical models. Artificial Intelligence, 2005.
  4. [Maheswaran et al., 2004] Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, and Pradeep Varakantham. Taking DCOP to the real world: Efficient complete solutions for distributed multi-event scheduling. In AAMAS-04, 2004.
  5. [Maheswaran et al., 2006] R.T. Maheswaran, J.P. Pearce, E. Bowring, P. Varakantham, and M Tambe. Privacy loss in distributed constraint reasoning: A quantitative framework for analysis and its applications. JAAMAS, 2006.
  6. [Mailler and Lesser, 2004] Roger Mailler and Victor Lesser. Solving distributed constraint optimization problems using cooperative mediation. Proceedings of Third International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2004), 2004.
  7. [Mailler and Lesser, 2005] Roger Mailler and Victor Lesser. Asynchronous partial overlay: A new algorithm for solving distributed constraint satisfaction problems. Journal of Artificial Intelligence Research (JAIR), 2005. to appear.
  8. [Marinescu and Dechter, 2005] Radu Marinescu and Rina Dechter. AND/OR branch-and-bound for graphical models. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI-05, Edinburgh, Scotland, Aug 2005. IJCAI
  9. [Modi et al., 2003] P. J. Modi, W. M. Shen, and M. Tambe. An asynchronous complete method for distributed constraint optimization. In Proc. AAMAS, 2003.
  10. [Petcu and Faltings, 2005] Adrian Petcu and Boi Faltings. DPOP: A scalable method for multiagent constraint optimization. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI-05, Edinburgh, Scotland, Aug 2005.
  11. [Petcu et al., 2006] Adrian Petcu, Boi Faltings, and David Parkes. M-DPOP: Faithful Distributed Implementation of Efficient Social Choice Problems. In Proceedings of the International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS-06), Hakodate, Japan, May 2006.
  12. [Schiex et al., 1995] Thomas Schiex, Hélène Fargier, and Gerard Verfaillie. Valued constraint satisfaction problems: Hard and easy problems. In Proceedings of the 15th International Joint Conference on Artificial Intelligence, IJCAI-95, Montreal, Canada, 1995. IJCAI
  13. [Yokoo et al., 1992] Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. Distributed constraint satisfaction for formalizing distributed problem solving. In International Conference on Distributed Computing Systems, pages 614-621, 1992.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards