Distributed constraint optimization with structured resource constraints

ABSTRACT

Distributed constraint optimization (DCOP) provides a framework for coordinated decision making by a team of agents. Often, during the decision making, capacity constraints on agents' resource consumption must be taken into account. To address such scenarios, an extension of DCOP- Resource Constrained DCOP- has been proposed. However, certain type of resources have an additional structure associated with them and exploiting it can result in more efficient algorithms than possible with a general framework. An example of these are distribution networks, where the flow of a commodity from sources to sinks is limited by the flow capacity of edges. We present a new model of structured resource constraints that exploits the acyclicity and the flow conservation property of distribution networks. We show how this model can be used in efficient algorithms for finding the optimal flow configuration in distribution networks, an essential problem in managing power distribution networks. Experiments demonstrate the efficiency and scalability of our approach on publicly available benchmarks and compare favorably against a specialized solver for this task. Our results extend significantly the effectiveness of distributed constraint optimization for practical multi-agent settings.

REFERENCES

• 1: P. Bertoli, A. Cimatti, J. Slanley, and S. Thiebaux. Solving power supply restoration problems with planning via symbolic model checking. In ECAI, pages 576--580, Lyon, France, 2002.
• 2: E. Bowring , M. Tambe , M. Yokoo, Multiply-constrained distributed constraint optimization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160897]
• 3: Anton Chechetka , Katia Sycara, No-commitment branch and bound search for distributed constraint optimization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160900]
• 4: Rina Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 5: Eugene C. Freuder, A sufficient condition for backtrack-bounded search, Journal of the ACM (JACM), v.32 n.4, p.755-761, Oct. 1985 [doi>10.1145/4221.4225]
• 6: Amir Gershman , Amnon Meisels , Roie Zivan, Asynchronous Forward-Bounding for Distributed Constraints Optimization, Proceeding of the 2006 conference on ECAI 2006: 17th European Conference on Artificial Intelligence August 29 -- September 1, 2006, Riva del Garda, Italy, p.103-107, May 22, 2006
• 7: J. Griffin and S. Puller. Electricity deregulation: choices and challenges. University of Chicago Press, Chicago, 2005.
• 8: T. Hadzic, A. Wasowski, and H. Andersen. Techniques for efficient interactive configuration of distribution networks. In IJCAI, pages 100--105, Hyderabad, India, 2007.
• 9: A. Kumar, A. Petcu, and B. Faltings. H-DPOP: Using hard constraints for search space pruning in DCOP. In AAAI, pages 325--330, 2008.
• 10: 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]
• 11: R. Mailler and V. Lesser. Asynchronous partial overlay: A new algorithm for solving distributed constraint satisfaction problems. JAIR, 25:529--526, 2006.
• 12: T. Matsui, H. Matsuo, M. Silaghi, K. Hirayama, and M. Yokoo. Resource constrained distributed constraint optimization with virtual variables. In AAAI, pages 120--125, 2008.
• 13: 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]
• 14: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In IJCAI, Edinburgh, Scotland, Aug 2005.
• 15: S. Thiebaux and M. Cordier. Supply restoration in power distribution system - a benchmark for planning under uncertainty. In ECP, pages 85--96, 2001.
• 16: S. Thiebaux, M. Cordier, O. Jehl, and J. Krivine. Supply restoration in power distribution system - a case study in integrating model-based diagnosis and repair planning. In UAI, pages 525--532, 1996.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
distributed constraint optimization, power restoration