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
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 : 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 metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 10, 2019 - 2:01:43 PM
Last modification on : Monday, January 11, 2021 - 5:24:09 PM


Files produced by the author(s)



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⟩



Record views


Files downloads