Caching schemes for DCOP search algorithms

ABSTRACT

Distributed Constraint Optimization (DCOP) is useful for solving agent-coordination problems. Any-space DCOP search algorithms require only a small amount of memory but can be sped up by caching information. However, their current caching schemes do not exploit the cached information when deciding which information to preempt from the cache when a new piece of information needs to be cached. Our contributions are three-fold: (1) We frame the problem as an optimization problem. (2) We introduce three new caching schemes (MaxPriority, MaxEffort and MaxUtility) that exploit the cached information in a DCOP-specific way. (3) We evaluate how the resulting speed up depends on the search strategy of the DCOP search algorithm. Our experimental results show that, on all tested DCOP problem classes, our MaxEffort and MaxUtility schemes speed up ADOPT (which uses best-first search) more than the other tested caching schemes, while our MaxPriority scheme speeds up BnB-ADOPT (which uses depth-first branch-and-bound search) at least as much as the other tested caching schemes.

REFERENCES

• 1: A. Chechetka and K. Sycara. An any-space algorithm for distributed constraint optimization. In Proceedings of the AAAI Spring Symposium on Distributed Plan and Schedule Management, pages 33--40, 2006.
• 2: 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]
• 3: 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
• 4: P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, SSC4(2):100--107, 1968.
• 5: Robert Junges , Ana L. C. Bazzan, Evaluating the performance of DCOP algorithms in a real world, dynamic problem, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 6: Victor Lesser , Milind Tambe , Charles L. Ortiz, Distributed Sensor Networks: A Multiagent Perspective, Kluwer Academic Publishers, Norwell, MA, 2003
• 7: 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]
• 8: 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]
• 9: R. Marinescu and R. Dechter. AND/OR branch-and-bound for graphical models. In Proceedings of IJCAI, pages 224--229, 2005.
• 10: T. Matsui, H. Matsuo, and A. Iwata. Efficient methods for asynchronous distributed constraint optimization algorithm. In Proceedings of Artificial Intelligence and Applications, pages 727--732, 2005.
• 11: 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]
• 12: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In Proceedings of IJCAI, pages 1413--1420, 2005.
• 13: A. Petcu and B. Faltings. MB-DPOP: A new memory-bounded algorithm for distributed optimization. In Proceedings of IJCAI, pages 1452--1457, 2007.
• 14: William Yeoh , Ariel Felner , Sven Koenig, BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation

Keywords:
ADOPT, BnB-ADOPT, DCOP, caching, distributed constraint optimization, distributed search algorithms