Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search

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.
Fichier principal
Vignette du fichier
ictai12.pdf (308.07 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00748195 , version 1 (05-11-2012)

Identifiers

Cite

Mohamed Wahbi, Redouane Ezzahir, Christian Bessiere, 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⟩
412 View
563 Download

Altmetric

Share

Gmail Facebook X LinkedIn More