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.
Type de document :
Communication dans un congrès
CP: Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. 19th International Conference on Principles and Practice of Constraint Programming, pp.708-723, 2013, 〈10.1007/978-3-642-40627-0_52〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00839024
Contributeur : Joël Quinqueton <>
Soumis le : jeudi 27 juin 2013 - 08:21:25
Dernière modification le : mardi 19 juin 2018 - 01:21:08

Lien texte intégral

Identifiants

Citation

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

Partager

Métriques

Consultations de la notice

213