Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2021

Abstract

Distributed constraint optimization problems (DCOPs) are a powerful model for multi-agent coordination and optimization, where information and controls are distributed among multiple agents by nature. Sampling-based algorithms are important incomplete techniques for solving medium-scale DCOPs. However, they use tables to exactly store all the information (e.g., costs, confidence bounds) to facilitate sampling, which limits their scalability. This paper tackles the limitation by incorporating deep neural networks in solving DCOPs for the first time and presents a neural-based sampling scheme built upon regret-matching. In the algorithm, each agent trains a neural network to approximate the regret related to its local problem and performs sampling according to the estimated regret. Furthermore, to ensure exploration we propose a regret rounding scheme that rounds small regret values to positive numbers. We theoretically show the regret bound of our algorithm and extensive evaluations indicate that our algorithm can scale up to large-scale DCOPs and significantly outperform the state-of-the-art methods.

Keywords

Agent-based and Multi-agent Systems, Coordination and Cooperation, Constraints and SAT: Constraint OptimizationConstraints and SAT, Distributed Constraints

Discipline

Artificial Intelligence and Robotics | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21): Montreal, August 19-26

First Page

146

Last Page

153

ISBN

9780999241196

Identifier

10.24963/ijcai.2021/21

Publisher

IJCAI

City or Country

Montreal

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.24963/ijcai.2021/21

Download

Share

COinS