Nogood-Based Asynchronous Forward-Checking Algorithms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports (Research Report) Year : 2012

Nogood-Based Asynchronous Forward-Checking Algorithms

Abstract

We propose two asynchronous algorithms for solving Distributed Constraint Satisfaction Problems (DisCSPs). The first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). Besides its use of nogoods as justification of value removals, AFC-ng allows simultaneous backtracks going from different agents to different destinations. The second algorithm, Asynchronous Forward-Checking Tree (AFC-tree), is based on the AFC-ng algorithm and is performed on a pseudo-tree ordering of the constraint graph. AFC-tree runs simultaneous search processes in disjoint problem subtrees and exploits the parallelism inherent in the problem. We prove that AFC-ng and AFC-tree only need polynomial space. We compare the performance of these algorithms with other DisCSP algorithms on random DisCSPs and instances from real benchmarks: sensor networks and distributed meeting scheduling. Our experiments show that AFC-ng improves on AFC and that AFC-tree outperforms all compared algorithms, particularly on sparse problems.
Fichier principal
Vignette du fichier
RR-12013.pdf (286.91 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00691197 , version 1 (25-04-2012)

Identifiers

  • HAL Id : lirmm-00691197 , version 1

Cite

Mohamed Wahbi, Redouane Ezzahir, Christian Bessiere, El Houssine Bouyakhf. Nogood-Based Asynchronous Forward-Checking Algorithms. [Research Report] RR-12013, Lirmm. 2012, pp.29. ⟨lirmm-00691197⟩
228 View
514 Download

Share

More