Multi-HDCS: solving DisCSPs with complex local problems cooperatively.

Lee, David; Arana, In�s; Ahriz, Hatem; Hui, Kit

Abstract

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.

Citation

LEE, D., ARANA, I., AHRIZ, H. and HUI, K. 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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2010 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2010)
• Start Date: Aug 31, 2010
• End Date: Sep 3, 2010
• Acceptance Date: Sep 30, 2010
• Online Publication Date: Sep 30, 2010
• Publication Date: Dec 31, 2010
• Deposit Date: Sep 17, 2010
• Publicly Available Date: Sep 17, 2010
• Publisher: IEEE Computer Society
• Peer Reviewed: Peer Reviewed
• Volume: 2
• Article Number: 5614767
• Pages: 295-302
• ISBN: 9781424484829
• DOI: https://doi.org/10.1109/WI-IAT.2010.141
• Keywords: Distributed constraint satisfaction; Local search; Hybrid algorithms for distributed problem solving
• Public URL: http://hdl.handle.net/10059/525
• Contract Date: Sep 17, 2010