Skip to Main content Skip to Navigation

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 metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Mohamed Wahbi Connect in order to contact the contributor
Submitted on : Wednesday, April 25, 2012 - 3:29:20 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Monday, November 26, 2012 - 3:45:53 PM


Files produced by the author(s)


  • HAL Id : lirmm-00691197, version 1



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⟩



Record views


Files downloads