Asynchronous Inter-Level Forward-Checking for DisCSPs

Redouane Ezzahir 1 Christian Bessière 2 Mohamed Wahbi 3 Imade Benelallam 1 El Houssine Bouyakhf 1
1 LIMIARF - Laboratoire d'Informatique, Mathématiques appliquées, Intelligence Artificielle et Reconnaissance de Formes
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We propose two new asynchronous algorithms for solving Distributed Constraint Satisfaction Problems (DisCSPs). The first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). The second algorithm, Asynchronous Inter-Level Forward-Checking (AILFC), is based on the AFC-ng algorithm and is performed on a pseudo-tree ordering of the constraint graph. AFC-ng and AILFC only need polynomial space. We compare the performance of these algorithms with other DisCSP algorithms on random DisC-SPs in two kinds of communication environments: Fast communication and slow communication. Our experiments show that AFC-ng improves on AFC and that AILFC outperforms all compared algorithms in communication load.
Type de document :
Communication dans un congrès
CP: Constraint Programming, 2009, Lisbon, Portugal. Springer, 15th International Conference on Principles and Practice of Constraint Programming, LNCS (5732), pp.304-318, 2009, 〈10.1007/978-3-642-04244-7_25〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00545541
Contributeur : Martine Peridier <>
Soumis le : mardi 9 octobre 2018 - 22:21:03
Dernière modification le : mercredi 10 octobre 2018 - 20:25:29

Fichier

cp09-discsps.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

COCONUT | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

Redouane Ezzahir, Christian Bessière, Mohamed Wahbi, Imade Benelallam, El Houssine Bouyakhf. Asynchronous Inter-Level Forward-Checking for DisCSPs. CP: Constraint Programming, 2009, Lisbon, Portugal. Springer, 15th International Conference on Principles and Practice of Constraint Programming, LNCS (5732), pp.304-318, 2009, 〈10.1007/978-3-642-04244-7_25〉. 〈lirmm-00545541〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

103

Téléchargements de fichiers

1

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD