Distributed Gibbs: A memory-bounded sampling-based DCOP algorithm

• Main Authors: NGUYEN, Duc Thien, YEOH, William, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2013
• Subjects: DCOP; Sampling; Gibbs; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/1656; https://ink.library.smu.edu.sg/context/sis_research/article/2655/viewcontent/aamas13_dgibbs.pdf
• Institution: Singapore Management University

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.