Skip to main content

Research Repository

See what's under the surface

Advanced Search

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

Lee, David; Arana, Inés; Ahriz, Hatem; Hui, Kit-Ying

Authors

David Lee

Inés Arana

Hatem Ahriz

Kit-Ying Hui



Contributors

Xiangji Jimmy Huang
Editor

Ali A. Ghorbani
Editor

Mohand-Said Hacid
Editor

Takahira Yamaguchi
Editor

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.

Start Date Aug 31, 2010
Publication Date Dec 31, 2010
Publisher New Publisher Required
Article Number 5614767
Pages 295-302
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
DOI https://doi.org/10.1109/WI-IAT.2010.141
Keywords Distributed constraint satisfaction; Local search; Hybrid algorithms for distributed problem solving

Files





You might also like



Downloadable Citations

;