Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

5-2013

Abstract

Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on confidence bounds via their Distributed UCT (DUCT) sampling-based algorithm. Unfortunately, its memory requirement per agent is exponential in the number of agents in the problem, which prohibits it from scaling up to large problems. Thus, in this paper, we introduce a new sampling-based DCOP algorithm called Distributed Gibbs, whose memory requirements per agent is linear in the number of agents in the problem. Additionally, we show empirically that our algorithm is able to find solutions that are better than DUCT; and computationally, our algorithm runs faster than DUCT as well as solve some large problems that DUCT failed to solve due to memory limitations.

Keywords

DCOP, Sampling, Gibbs

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

AAMAS '13: Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems, May, 6-10, 2013, Saint Paul, Minnesota

First Page

167

Last Page

176

ISBN

9781450319935

Publisher

IFAAMAS

City or Country

Richland, SC

Copyright Owner and License

Authors/LARC

Additional URL

http://www.ifaamas.org/Proceedings/aamas2013/docs/p167.pdf

Download

Share

COinS