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.
Type de document :
Rapport
[Research Report] RR-12013, Lirmm. 2012, pp.29
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00691197
Contributeur : Mohamed Wahbi <>
Soumis le : mercredi 25 avril 2012 - 15:29:20
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : lundi 26 novembre 2012 - 15:45:53

Fichier

RR-12013.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

391