DisBO-wd: a distributed constraint satisfaction algorithm for coarse-grained distributed problems.

Basharu, Muhammed; Arana, In�s; Ahriz, Hatem

Abstract

We present a distributed iterative improvement algorithm for solving coarse-grained distributed constraint satisfaction problems (DisCSPs). Our algorithm is inspired by the Distributed Breakout for coarse-grained DisCSPs where we introduce a constraint weight decay and a constraint weight learning mechanism in order to escape local optima. We also introduce some randomisation in order to give the search a better chance of finding the right path to a solution. We show that these mechanisms improve the performance of the algorithm considerably and make it competitive with respect to other algorithms.

Citation

BASHARU, M., ARANA, I. and AHRIZ, H. 2008. DisBO-wd: a distributed constraint satisfaction algorithm for coarse-grained distributed problems. In Bramer, M., Coenen, F. and Petridis, M. (eds.) Research and development in intelligent systems XXIV: technical proceedings of the 27th Annual international conference of the British Computer Society's Specialist Group on Artificial Intelligence (SGAI) (AI-2007): innovative techniques and applications of artificial intelligence, 10-12 December 2007, Cambridge, UK. London: Springer [online], pages 23-36. Available from: https://doi.org/10.1007/978-1-84800-094-0_3

• Conference Name: 27th Annual international conference of the British Computer Society's Specialist Group on Artificial Intelligence (SGAI) (AI-2007)
• Conference Location: Cambridge, UK
• Start Date: Dec 10, 2007
• End Date: Dec 12, 2007
• Acceptance Date: Dec 31, 2007
• Online Publication Date: Dec 31, 2007
• Publication Date: Dec 31, 2007
• Deposit Date: Dec 23, 2008
• Publicly Available Date: Dec 23, 2008
• Publisher: Springer
• Pages: 23-36
• ISBN: 9781848000933
• DOI: https://doi.org/10.1007/978-1-84800-094-0_3
• Keywords: Distributed iterative improvement algorithm; Distributed constraint satisfaction problems; DisCSPs
• Public URL: http://hdl.handle.net/10059/280