Solving DisCSPs with Penalty Driven Search

Muhammed Basharu, Ines Arana, Hatem Ahriz

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.

Content Area: 1. Agents/Multiagent Systems

Subjects: 15.2 Constraint Satisfaction; 7. Distributed AI

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.