Nogood-Based Asynchronous Forward Checking Algorithms

Mohamed Wahbi (1) , Redouane Ezzahir (2) , Christian Bessiere (3) , El Houssine Bouyakhf (4)

1 TASC - Theory, Algorithms and Systems for Constraints
2 ENSA - Ecole Nationale des Sciences Appliquées [Agadir]
3 COCONUT - Agents, Apprentissage, Contraintes
4 LIMIARF - Laboratoire d'Informatique, Mathématiques appliquées, Intelligence Artificielle et Reconnaissance de Formes

We propose two new 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.

Mots clés: Distributed solving; Constraint programming

Domaines: Intelligence artificielle [cs.AI]

Mohamed Wahbi, Redouane Ezzahir, Christian Bessiere, El Houssine Bouyakhf. Nogood-Based Asynchronous Forward Checking Algorithms. Constraints, 2013, 18 (3), pp.404-433. ⟨10.1007/s10601-013-9144-4⟩. ⟨hal-00816928⟩