Multi-HDCS: solving DisCSPs with complex local problems cooperatively.
Lee, David; Arana, Inés; Ahriz, Hatem; Hui, Kit-Ying
Xiangji Jimmy Huang
Ali A. Ghorbani
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 agents 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.
|Start Date||Aug 31, 2010|
|Publication Date||Dec 31, 2010|
|Publisher||New Publisher Required|
|Institution Citation||LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y. 2009. Multi-HDCS: solving DisCSPs with complex local problems cooperatively. In Huang, X.J., Ghorbani, A.A., Hacid, M.-S. and Yamaguchi, T. (eds.) Proceedings of the 2010 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2010), co-located with the 2010 IEEE/WIC/ACM international conference on web intelligence (WI 2010), and the joint conference workshops (WI-IAT Workshops 2010), 31 August - 3 September 2010, Toronto, Canada. Los Alamitos: IEEE Computer Society [online], volume 2, article number 5614767, pages 295-302. Available from: https://doi.org/10.1109/WI-IAT.2010.141|
|Keywords||Distributed constraint satisfaction; Local search; Hybrid algorithms for distributed problem solving|
LEE 2010 Multi-HDCS solving DisCSPs
You might also like
Dynamic agent prioritisation with penalties in distributed local search.
Plan recommendation for well engineering.
Multi-Hyb: a hybrid algorithm for solving DisCSPs with complex local problems.