Asynchronous Inter-Level Forward-Checking for DisCSPs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2009

Asynchronous Inter-Level Forward-Checking for DisCSPs

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

Dates and versions

lirmm-00545541 , version 1 (09-10-2018)

Identifiers

Cite

Redouane Ezzahir, Christian Bessiere, Mohamed Wahbi, Imade Benelallam, El Houssine Bouyakhf. Asynchronous Inter-Level Forward-Checking for DisCSPs. CP: Principles and Practice of Constraint Programming, Sep 2009, Lisbon, Portugal. pp.304-318, ⟨10.1007/978-3-642-04244-7_25⟩. ⟨lirmm-00545541⟩
102 View
147 Download

Altmetric

Share

More