Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00691197
Contributor : Mohamed Wahbi <>
Submitted on : Wednesday, April 25, 2012 - 3:29:20 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Long-term archiving on: : Monday, November 26, 2012 - 3:45:53 PM

File

RR-12013.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00691197, version 1

Collections

Citation

Mohamed Wahbi, Redouane Ezzahir, Christian Bessière, El Houssine Bouyakhf. Nogood-Based Asynchronous Forward-Checking Algorithms. [Research Report] RR-12013, Lirmm. 2012, pp.29. ⟨lirmm-00691197⟩

Share

Metrics

Record views

378

Files downloads

751