A hybrid approach to solving coarse-grained DisCSPs.
MetadataShow full item record
LEE, D., ARANA, I., AHRIZ, H. and HUI, K-Y., 2009. A hybrid approach to solving coarse-grained DisCSPs. In: Proceedings of the Eighth International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 09), 10-15 May 2009. Budapest: IFAAMAS. Pp. 1235-1236.
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.