Trading off solution cost for smaller runtime in DCOP search algorithms

ABSTRACT

Distributed Constraint Optimization (DCOP) is a key technique for solving multiagent coordination problems. Unfortunately, finding minimal-cost DCOP solutions is NP-hard. We therefore propose two mechanisms that trade off the solution costs of two DCOP search algorithms (ADOPT and BnB-ADOPT) for smaller runtimes, namely the Inadmissible Heuristics Mechanism and the Relative Error Mechanism. The solution costs that result from these mechanisms are bounded by a more meaningful quantity than the solution costs that result from the existing Absolute Error Mechanism since they both result in solution costs that are larger than minimal by at most a user-specified percentage. Furthermore, the Inadmissible Heuristics Mechanism experimentally dominates both the Absolute Error Mechanism and the Relative Error Mechanism for BnB-ADOPT and is generally no worse than them for ADOPT.

REFERENCES

• 1: Syed Ali , Sven Koenig , Milind Tambe, Preprocessing techniques for accelerating the DCOP algorithm ADOPT, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082631]
• 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: A. Gershman, A. Meisels, and R. Zivan. Asynchronous forward-bounding for distributed constraints optimization. In Proceedings of ECAI, pages 103--107, 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: 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]
• 6: R. Marinescu and R. Dechter. AND/OR branch-and-bound for graphical models. In Proceedings of IJCAI, pages 224--229, 2005.
• 7: 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]
• 8: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In Proceedings of IJCAI, pages 1413--1420, 2005.
• 9: I. Pohl. First results on the effect of error in heuristic search. Machine Intelligence, 5:219--236, 1970.
• 10: W. Yeoh, A. Felner, and S. Koenig. BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. In Proceedings of the Distributed Constraint Reasoning Workshop, 2007.

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

Keywords:
agent cooperation, distributed problem solving