Research Repository

See what's under the surface

A hybrid approach to distributed constraint satisfaction.

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

Authors

David Lee

Inés Arana

Hatem Ahriz

Kit-Ying Hui



Contributors

Daniel Dochev
Editor

Marco Pistore
Editor

Paolo Traverso
Editor

Abstract

We present a hybrid approach to Distributed Constraint Satisfaction which combines incomplete, fast, penalty-based local search with complete, slower systematic search. Thus, we propose the hybrid algorithm PenDHyb where the distributed local search algorithm DisPeL is run for a very small amount of time in order to learn about the difficult areas of the problem from the penalty counts imposed during its problem-solving. This knowledge is then used to guide the systematic search algorithm SynCBJ. Extensive empirical results in several problem classes indicate that PenDHyb is effective for large problems.

Start Date Sep 4, 2008
Publication Date Dec 31, 2008
Publisher Springer (part of Springer Nature)
Pages 375-379
Series Title Lecture notes in computer science
Series Number 5253
ISBN 9783540857754
Institution Citation LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y. 2008. A hybrid approach to distributed constraint satisfaction. In Dochev, D., Pistore, M. and Traverso, P. (eds.) Proceedings of the 13th International conference on artificial intelligence: methodology, systems and applications (AIMSA 2008), 4-6 September 2008, Varna, Bulgaria. Lecture notes in computer science, 5253. Berlin: Springer [online], pages 375-379. Available from: https://doi.org/10.1007/978-3-540-85776-1_33
DOI https://doi.org/10.1007/978-3-540-85776-1_33
Keywords Constraint satisfaction; Distributed AI; Hybrid systems

Files




Downloadable Citations