Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search

Mohamed Wahbi 1, * Redouane Ezzahir 2 Christian Bessière 3 El Houssine Bouyakhf 4
* Auteur correspondant
1 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
3 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We recently proposed Nogood-Based Asynchronous Forward Checking (AFC-ng), an efficient and robust algorithm for solving Distributed Constraint Satisfaction Problems (DisCSPs). AFC-ng performs an asynchronous forward checking phase during synchronous search. In this paper, we propose two new algorithms based on the same mechanism as AFC-ng. However, instead of using forward checking as a filtering property, we pro- pose to maintain arc consistency asynchronously (MACA). The first algorithm we propose, MACA-del, enforces arc consistency thanks to an additional type of messages, deletion messages. The second algorithm, MACA-not, achieves arc consistency without any new type of message. We provide a theoretical analysis and an experimental evaluation of the proposed approach. Our experiments show the good performance of MACA algorithms, particularly those of MACA-not.
Type de document :
Communication dans un congrès
ICTAI'12: International Conference on Tools with Artificial Intelligence, Nov 2012, Athens, Greece. pp.8, 2012, 〈http://ictai12.unipi.gr/〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748195
Contributeur : Joël Quinqueton <>
Soumis le : lundi 5 novembre 2012 - 09:57:21
Dernière modification le : mardi 16 janvier 2018 - 14:37:45
Document(s) archivé(s) le : samedi 17 décembre 2016 - 07:34:11

Fichier

ictai12.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00748195, version 1

Citation

Mohamed Wahbi, Redouane Ezzahir, Christian Bessière, El Houssine Bouyakhf. Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search. ICTAI'12: International Conference on Tools with Artificial Intelligence, Nov 2012, Athens, Greece. pp.8, 2012, 〈http://ictai12.unipi.gr/〉. 〈lirmm-00748195〉

Partager

Métriques

Consultations de la notice

321

Téléchargements de fichiers

357