CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

DUCT: An upper confidence bound approach to distributed constraint optimization problems

Brammert Ottens ; Christos Dimitrakakis (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; Boi Faltings
ACM Transactions on Intelligent Systems and Technology (2157-6904). Vol. 8 (2017), 5,
[Artikel, refereegranskad vetenskaplig]

We propose a distributed upper confidence bound approach, DUCT, for solving distributed constraint optimization 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.

Nyckelord: Coordination; Distributed constraint optimization; Multiagent systems; Tree search

Denna post skapades 2017-10-04. Senast ändrad 2017-11-24.
CPL Pubid: 252338


Läs direkt!

Länk till annan sajt (kan kräva inloggning)