Solving DisCSPs with penalty-driven search.

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

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.

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th American Association for Artificial Intelligence national conference on artificial intelligence (AAAI-05)
• 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
• Peer Reviewed: Peer Reviewed
• 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
• Contract Date: Jan 8, 2009