Maintien asynchrone de la consistance d'arc dans la recherche distribuée synchrone

Mohamed Wahbi 1 Redouane Ezzahir 2 Christian Bessière 3 El Houssine Bouyakhf 4
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
3 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Nous avons proposé récemment Nogood-Based Asynchronous Forward Checking (AFC-ng), un algo-rithme efficace et robuste pour résoudre des Problèmes de Satisfaction de Contraintes Distribués (DisCSPs). AFC-ng exécute de manière asynchrone une phase de vérification en avant pendant la recherche synchrone. Dans ce papier, nous proposons deux nouveaux algorithmes basés sur le même mécanisme qu'AFC-ng. Cependant, au lieu d'utiliser le forward checking comme propriété de filtrage, nous proposons de maintenir d'une manière asynchrone la consistance d'arc (MACA). Le premier algorithme que nous proposons, MACA-del, maintient la consistance d'arc grâce à un type de messages supplé-mentaire, des messages de suppression. Le deuxième algorithme, MACA-not, réalise la consistance d'arc sans aucun nouveau type de message. Nous fournissons une analyse théorique et uneévaluation expérimentale de l'approche proposée. Nos expérimentations montrent la bonne performance des algorithmes MACA et plus particulièrement ceux de MACA-not.
Document type :
Conference papers
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00830408
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 10, 2019 - 2:17:11 PM
Last modification on : Friday, October 11, 2019 - 9:26:16 AM

File

papier_18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00830408, version 1

Citation

Mohamed Wahbi, Redouane Ezzahir, Christian Bessière, El Houssine Bouyakhf. Maintien asynchrone de la consistance d'arc dans la recherche distribuée synchrone. JFPC: Journées Francophones de Programmation par Contraintes, Jun 2013, Aix-en-Provence, France. ⟨lirmm-00830408⟩

Share

Metrics

Record views

324

Files downloads

14