Skip to Main content Skip to Navigation
Conference papers

Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search

Mohamed Wahbi 1, * Redouane Ezzahir 2 Christian Bessière 3 El Houssine Bouyakhf 4
* Corresponding author
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
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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748195
Contributor : Joël Quinqueton <>
Submitted on : Monday, November 5, 2012 - 9:57:21 AM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Long-term archiving on: : Saturday, December 17, 2016 - 7:34:11 AM

File

ictai12.pdf
Files produced by the author(s)

Identifiers

Citation

Mohamed Wahbi, Redouane Ezzahir, Christian Bessière, El Houssine Bouyakhf. Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search. ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2012, Athens, Greece. pp.33-40, ⟨10.1109/ICTAI.2012.14⟩. ⟨lirmm-00748195⟩

Share

Metrics

Record views

662

Files downloads

870