Skip to Main content Skip to Navigation
Conference papers

Asynchronous Forward Bounding Revisited

Mohamed Wahbi 1 Redouane Ezzahir 2 Christian Bessière 3
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 : The Distributed Constraint Optimization Problem (DCOP) is a powerful framework for modeling and solving applications in multi-agent coordination. Asynchronous Forward Bounding (AFB_BJ) is one of the best algorithms to solve DCOPs.We propose AFB_BJ + , a revisited version of AFB_BJ in which we refine the lower bound computations. We also propose to compute lower bounds for the whole domain of the last assigned agent instead of only doing this for its current assignment. This reduces both the number of messages needed and the time future agents remain idle. In addition, these lower bounds can be used as a value ordering heuristic in AFB_BJ + . The experimental evaluation on standard benchmark problems shows the efficiency of AFB_BJ +  compared to other algorithms for DCOPs.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00839024
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 10, 2019 - 2:01:43 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM

File

cp13-afb.pdf
Files produced by the author(s)

Identifiers

Citation

Mohamed Wahbi, Redouane Ezzahir, Christian Bessière. Asynchronous Forward Bounding Revisited. CP: Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. pp.708-723, ⟨10.1007/978-3-642-40627-0_52⟩. ⟨lirmm-00839024⟩

Share

Metrics

Record views

384

Files downloads

139