Directed soft arc consistency in pseudo trees

ABSTRACT

We propose an efficient method that applies directed soft arc consistency to a Distributed Constraint Optimization Problem (DCOP) which is a fundamental framework of multi-agent systems. With DCOPs a multi-agent system is represented as a set of variables and a set of constraints/cost functions. We focus on DCOP solvers that employ pseudo-trees. A pseudo-tree is a graph structure for a constraint network that represents a partial ordering of variables. Most pseudo-tree-based search algorithms perform optimistic searches using explicit/implicit backtracking in parallel. However, for cost functions taking a wide range of cost values, such exact algorithms require many search iterations, even if the constraint density is relatively low. Therefore additional improvements are necessary to reduce the search process. A previous study used a dynamic programming-based preprocessing technique that estimates the lower bound values of costs. However, there are opportunities for further improvements of efficiency. In addition, modifications of the search algorithm are necessary to use the estimated lower bounds.

The proposed method applies soft arc consistency (soft AC) enforcement to DCOP. In the proposed method, directed soft AC is performed based on a pseudo-tree in a bottom up manner. Using the directed soft AC, the global lower bound value of cost functions is passed up to the root node of the pseudo-tree. The value of each cost function is also reduced. As a result, the original problem is converted to an equivalent problem which is efficiently solved using common search algorithms. The performance of the proposed method is evaluated by experimentation. The results show that it is more efficient than previous methods that estimate the lower bound of costs. Moreover, the proposed method is efficient for approximation algorithms that use bounded errors.

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: B. Awerbuch. A new distributed depth-first-search algorithm. Information Processing Letters, 20(3):147--150, 1985.
• 3: Martin Cooper , Thomas Schiex, Arc consistency for soft constraints, Artificial Intelligence, v.154 n.1-2, p.199-227, April 2004 [doi>10.1016/j.artint.2003.09.002]
• 4: A. Farinelli , A. Rogers , A. Petcu , N. R. Jennings, Decentralised coordination of low-power embedded devices using the max-sum algorithm, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 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: 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
• 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: 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]
• 10: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In 9th International Joint Conferece on Artificial Intelligence, pages 266--271, 2005.
• 11: Adrian Petcu , Boi Faltings, ODPOP: an algorithm for open/distributed constraint optimization, Proceedings of the 21st national conference on Artificial intelligence, p.703-708, July 16-20, 2006, Boston, Massachusetts
• 12: T. Schiex. A note on csp graph parameters. Technical report 1999/03, INRA, 1999.
• 13: Thomas Schiex, Arc Consistency for Soft Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.411-424, September 18-21, 2000
• 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
• 15: Weixiong Zhang , Guandong Wang , Zhao Xing , Lars Wittenburg, Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks, Artificial Intelligence, v.161 n.1-2, p.55-87, January 2005 [doi>10.1016/j.artint.2004.10.004]
• 16: R. Zivan. Anytime local search for distributed constraint optimization. In Twenty-Third AAAI Conference on Artificial Intelligence, pages 393--398, 2008.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
constraint reasoning, distributed constraint optimization problem, multi-agent systems, soft arc consistency