A hybrid approach to solving coarse-grained DisCSPs

ABSTRACT

A coarse-grained Distributed Constraint Satisfaction Problem (DisCSP) consists of several loosely connected constraint satisfaction subproblems, each assigned to an individual agent. We present Multi-Hyb, a two-phase concurrent hybrid approach for solving DisCSPs. In the first phase, each agent's subproblem is solved using systematic search which generates the key partial solutions to the global problem. Concurrently, a penalty-based local search algorithm attempts to find a global solution from these partial solutions. If phase 1 fails to find a solution, a phase 2 systematic search algorithm solves the problem using the knowledge gained from phase 1. We show that our approach is highly competitive in comparison with other coarse-grained DisCSP algorithms.

REFERENCES

• 1: M. Basharu, I. Arana, and H. Ahriz. StochDisPeL Exploiting Randomisation in DisPeL. In Proceedings of 7th International Workshop on Distributed Constraint Reasoning, pages 117--132, Hakodate, Japan, May 2006.
• 2: Muhammed Basharu , Ines Arana , Hatem Ahriz, Solving Coarse-grained DisCSPs with Multi-DisPeL and DisBO-wd, Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, p.335-341, November 02-05, 2007 [doi>10.1109/IAT.2007.95]
• 3: K. Hirayama, M. Yokoo, and K. Sycara. An Easy-Hard-Easy Cost Profile in Distributed Constraint Satisfaction. Transactions of Information Processing Society of Japan, 45:2217--2225, 2004.
• 4: David Lee , Inés Arana , Hatem Ahriz , Kit-Ying Hui, A Hybrid Approach to Distributed Constraint Satisfaction, Proceedings of the 13th international conference on Artificial Intelligence: Methodology, Systems, and Applications, September 04-06, 2008, Varna, Bulgaria [doi>10.1007/978-3-540-85776-1_33]
• 5: Francesca Rossi , Peter van Beek , Toby Walsh, Handbook of Constraint Programming (Foundations of Artificial Intelligence), Elsevier Science Inc., New York, NY, 2006
• 6: M. Yokoo , K. Hirayama, Distributed Constraint Satisfaction Algorithm for Complex Local Problems, Proceedings of the 3rd International Conference on Multi Agent Systems, p.372, July 03-07, 1998
• 7: Makoto Yokoo , Katsutoshi Hirayama, Algorithms for Distributed Constraint Satisfaction: A Review, Autonomous Agents and Multi-Agent Systems, v.3 n.2, p.185-207, June 2000 [doi>10.1023/A:1010078712316]
• 8: R. Zivan and A. Meisels. Synchronous vs Asynchronous search on DisCSPs. In Proceedings of the First European Workshop on Multi-Agent Systems (EUMA), Oxford, December 2003.

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, artificial intelligence, constraint satisfaction, distributed problem solving