David Lee
Multi-Hyb: a hybrid algorithm for solving DisCSPs with complex local problems.
Lee, David; Arana, In�s; Ahriz, Hatem; Hui, Kit-Ying
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
Ricardo Baeza-Yates
Editor
J�r�me Lang
Editor
Sushmita Mitra
Editor
Simon Parsons
Editor
Gabriella Pasi
Editor
Abstract
A coarse-grained Distributed Constraint Satisfaction Problem (DisCSP) is a constraint problem where several agents, each responsible for solving one part (a complex local problem), cooperate to determine an overall solution. Thus, agents solve the overall problem by finding a solution to their complex local problem which is compatible with the solutions proposed by other agents for their own local problems. Several approaches to solving DisCSPs have been devised and can be classified as systematic search and local search techniques. We present Multi-Hyb, a two-phase hybrid algorithm for solving coarse-grained DisCSPs which uses both systematic and local search during problem solving. Phase 1 generates key partial solutions to the global problem using systematic search. Concurrently, a penalty-based local search algorithm attempts to find a global solution to the problem using these partial solutions. If a global solution is not found in phase 1, the information learnt from phase 1 is used to inform the search carried out during the next phase. Phase two runs a systematic search algorithm on complex variables guided by the following knowledge obtained in phase 1: (i) partial solutions and; (ii) complex local problems which appear more difficult to satisfy. Experimental evaluation demonstrates that Multi-Hyb is competitive in several problem classes in terms of: (i) the communication cost and (ii) the computational effort needed.
Citation
LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y. 2009. Multi-Hyb: a hybrid algorithm for solving DisCSPs with complex local problems. In Baeza-Yates, R., Lang, J., Mitra, S., Parsons, S. and Pasi, G. (eds.) Proceedings of the 2009 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2009), co-located with the 2009 IEEE/WIC/ACM international conference on web intelligence (WI 2009), and the joint conference workshops (WI-IAT Workshops 2009), 15-18 September 2009, Milan, Italy. Los Alamitos: IEEE Computer Society [online], volume 2, article number 5284811, pages 379-382. Available from: https://doi.org/10.1109/WI-IAT.2009.181
Conference Name | 2009 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2009) |
---|---|
Conference Location | Milan, Italy |
Start Date | Sep 15, 2009 |
End Date | Sep 18, 2009 |
Acceptance Date | Sep 30, 2009 |
Online Publication Date | Sep 30, 2009 |
Publication Date | Dec 31, 2009 |
Deposit Date | Jul 6, 2010 |
Publicly Available Date | Jul 6, 2010 |
Publisher | IEEE Computer Society |
Volume | 2 |
Article Number | 5284811 |
Pages | 379-382 |
DOI | https://doi.org/10.1109/WI-IAT.2009.181 |
Keywords | Agent cooperation; Artificial intelligence; Constraint satisfaction; Distributed constraint satisfaction; Distributed problem solving |
Public URL | http://hdl.handle.net/10059/499 |
Files
LEE 2009 Multi-hyb a hybrid algorithm
(148 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