Distributed Gibbs: A linear-space sampling-based DCOP algorithm

• Main Authors: NGUYEN, Duc Thien, YEOH, William, LAU, Hoong Chuin, ZIVAN, Roie
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Constrained optimization; Ducts; Multi agent systems; Confidence bounds; Distributed constraint optimizations; Large problems; Memory requirements; Multi-agent coordinations; Resource allocation problem; Sampling-based; Sampling-based algorithms; Problem solving; Artificial Intelligence and Robotics; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4348; https://ink.library.smu.edu.sg/context/sis_research/article/5351/viewcontent/Distributed_Gibbs_A_linearspace_samplingbased_DCOP_algorithm2019Journal_of_Artificial_Intelligence_ResearchOpen_Access__1_.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 article, we introduce two new sampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs (PD-Gibbs). Both algorithms have memory requirements per agent that is linear in the number of agents in the problem. Our empirical results show that our algorithms can find solutions that are better than DUCT, run faster than DUCT, and solve some large problems that DUCT failed to solve due to memory limitations. © 2019 AI Access Foundation. All rights reserved.