Applying interchangeability techniques to the distributed breakout algorithmReportar como inadecuado

Applying interchangeability techniques to the distributed breakout algorithm - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: Petcu, Adrian; Faltings, Boi


Documentos relacionados