DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimisation Problems *

Abstract : We propose a distributed upper confidence bound approach, DUCT, for solving distributed constraint optimisation problems. We compare four variants of this approach with a baseline random sampling algorithm, as well as other complete and incomplete algorithms for DCOPs. Under general assumptions, we theoretically show that the solution found by DUCT after T steps is approximately T −1-close to the optimal. Experimentally, we show that DUCT matches the optimal solution found by the well-known DPOP and O-DPOP algorithms on moderate-size problems, while always requiring less agent communication. For larger problems, where DPOP fails, we show that DUCT produces significantly better solutions than local, incomplete algorithms. Overall we believe that DUCT is a practical, scalable algorithm for complex DCOPs.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01593215
Contributor : Christos Dimitrakakis <>
Submitted on : Wednesday, December 12, 2018 - 6:00:37 PM
Last modification on : Friday, March 22, 2019 - 1:37:14 AM
Long-term archiving on : Wednesday, March 13, 2019 - 12:19:24 PM

File

DUCT-hal.pdf
Files produced by the author(s)

Identifiers

Citation

Brammert Ottens, Christos Dimitrakakis, Boi Faltings. DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimisation Problems *. ACM Transactions on Intelligent Systems and Technology, ACM, In press, 8 (5), pp.1 - 27. ⟨10.1145/3066156⟩. ⟨hal-01593215⟩

Share

Metrics

Record views

62

Files downloads

55