Distributed guided local search for solving binary DisCSPs.

Abstract

We introduce the Distributed Guided Local Search (Dist- GLS) algorithm for solving Distributed Constraint Satisfaction Problems. Our algorithm is based on the centralised Guided Local Search algorithm, which is extended with additional heuristics in order to enhance its efficiency in distributed scenarios. We discuss the strategies we use for dealing with local optima in the search for solutions and compare performance of Dist-GLS with that of Distributed Breakout (DBA). In addition, we provide the results of our experiments with distributed versions of random binary constraint satisfaction and graph colouring problems.

Citation

BASHARU, M., ARANA, I. and AHRIZ, H. 2005. Distributed guided local search for solving binary DisCSPs. In Russell, I. and Markov, Z. (eds.) Proceedings of the 18th International conference of the Florida Artificial Intelligence Research Society (FLAIRS 2005), 16-18 May 2005, Clearwater, USA. Palo Alto: AAAI Press [online], pages 660-665. Available from: http://www.aaai.org/Papers/FLAIRS/2005/Flairs05-108.pdf

• Conference Name: 18th International conference of the Florida Artificial Intelligence Research Society (FLAIRS 2005)
• Conference Location: Clearwater, USA
• Start Date: May 16, 2005
• End Date: May 18, 2005
• Acceptance Date: May 16, 2005
• Online Publication Date: Dec 31, 2005
• Publication Date: Dec 31, 2005
• Deposit Date: Jan 8, 2009
• Publicly Available Date: Jan 8, 2009
• Publisher: Association for the Advancement of Artificial Intelligence
• Pages: 660-665
• ISBN: 9781577352341
• Keywords: Distributed guided local search algorithm; DistGLS; Distributed constraint satisfaction problems
• Public URL: http://hdl.handle.net/10059/289
• Publisher URL: http://www.aaai.org/Papers/FLAIRS/2005/Flairs05-108.pdf