David Lee
Multi-HDCS: solving DisCSPs with complex local problems cooperatively.
Lee, David; Arana, In�s; Ahriz, Hatem; Hui, Kit
Authors
Dr Ines Arana i.arana@rgu.ac.uk
Associate Dean for ESCD
Dr Hatem Ahriz h.ahriz@rgu.ac.uk
Principal Lecturer
Dr Kit-ying Hui k.hui@rgu.ac.uk
Lecturer
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.
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
Conference Name | 2010 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2010) |
---|---|
Conference Location | Toronto, Canada |
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 |
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 |
Files
LEE 2010 Multi-HDCS solving DisCSPs
(251 Kb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Detection of false command and response injection attacks for cyber physical systems security and resilience.
(2020)
Conference Proceeding
Predicting permeability based on core analysis.
(2020)
Conference Proceeding
The use of machine learning algorithms for detecting advanced persistent threats.
(2019)
Conference Proceeding
Downloadable Citations
About OpenAIR@RGU
Administrator e-mail: publications@rgu.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search