Solving DisCSPs with penalty-driven search.

Abstract

We introduce the Distributed, Penalty-driven Local search algorithm (DisPeL) for solving Distributed Constraint Satisfaction Problems. DisPeL is a novel distributed iterative improvement algorithm which escapes local optima by the use of both temporary and incremental penalties and a tabu-like no-good store. We justify the use of these features and provide empirical results which demonstrate the competitiveness of the algorithm.

Citation

BASHARU,M., ARANA, I. and AHRIZ, H. 2005. Solving DisCSPs with penalty-driven search. In Proceedings of the 20th American Association for Artificial Intelligence national conference on artificial intelligence (AAAI-05), co-located with the 17th Annual conference on innovative applications of artificial intelligence (IAAI-05), 9-13 July 2005, Pittsburgh, USA. Palo Alto: AAAI Press, pages 47-52.

• Conference Name: 20th American Association for Artificial Intelligence national conference on artificial intelligence (AAAI-05)
• Conference Location: Pittsburgh, USA
• Start Date: Jul 9, 2005
• End Date: Jul 13, 2005
• Acceptance Date: Apr 29, 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: 47-52
• ISBN: 9781577352365
• Keywords: Distributed constraint satisfaction problems; DisPeL; DisCSP; Distributed penalty driven local search algorithm
• Public URL: http://hdl.handle.net/10059/288