Multi-HDCS: solving DisCSPs with complex local problems cooperatively.
MetadataShow full item record
LEE, D., ARANA, I., AHRIZ, H. and HUI, K., 2010. Multi-HDCS: solving DisCSPs with complex local problems cooperatively. In: Proceedings of IEEE/WIC/ACM International Conference on Web Intellligence and Intelligent Agent Technology (WI-IAT 2010). 31 August – 3 September 2010.
We propose Multi-HDCS, a new hybrid approach for solving Distributed CSPs with complex local problems. In Multi-HDCS, each agent concurrently: (i) runs a centralised systematic search for its complex local problem; (ii) participates in a distributed local search; (iii) contributes to a distributed systematic search. A centralised systematic search algorithm runs on each agent, finding all non-interchangeable solutions to the agent’s complex local problem. In order to find a solution to the overall problem, two distributed algorithms which only consider the local solutions found by the centralised systematic searches are run: a local search algorithm identifies the parts of the problem which are most difficult to satisfy, and this information is used in order to find good dynamic variable orderings for a systematic search. We present two implementations of our approach which differ in the strategy used for local search: breakout and penalties on values. Results from an extensive empirical evaluation indicate that these two Multi-HDCS implementations are competitive against existing distributed local and systematic search techniques on both solvable and unsolvable distributed CSPs with complex local problems.