Applying interchangeability techniques to the distributed breakout algorithmReport as inadecuate

Applying interchangeability techniques to the distributed breakout algorithm - Download this document for free, or read online. Document in PDF available to download.

Publication date: 2004

In this paper, we develop two methods for improving the performance of the standard Distributed Breakout Algorithm \cite{yokoo:dba} using the notion of interchangeability. We study the performance of this algorithm on the problem of distributed sensor networks. In particular, we consider how neighborhood interchangeability and neighborhood partial interchangeability \cite{freuder:interch} can be used to keep conflicts localized and avoid ``chain reactions'' where a conflict originating in one part of the problem spreads to neighboring areas. We see from the experimental results that such techniques can bring about significant improvements in terms of the number of cycles required to solve the problem (and therefore improvements in terms of communication and time requirements), especially for difficult problems. Moreover, the improved algorithms are able to solve a higher proportion of the test problems.

Keywords: constraint satisfaction ; distributed AI ; problem solving ; sensor networks Reference EPFL-REPORT-52608

Author: Petcu, Adrian; Faltings, Boi


Related documents