Asynchronous Forward Bounding Revisited - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

Asynchronous Forward Bounding Revisited

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

Dates and versions

lirmm-00839024 , version 1 (10-10-2019)

Identifiers

Cite

Mohamed Wahbi, Redouane Ezzahir, Christian Bessiere. 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⟩
222 View
116 Download

Altmetric

Share

Gmail Facebook X LinkedIn More