Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm

Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, Roie Zivan

Abstract

Distributed Constraint Optimization Problems (DCOPs) are a fundamental framework for multi-agent coordination, yet they face significant scalability challenges due to the exponential memory requirements of traditional algorithms. This paper introduces SD-Gibbs and PD-Gibbs, two sampling-based algorithms that map DCOPs to Maximum A Posteriori (MAP) estimation in Markov Random Fields. By utilizing Gibbs sampling, these algorithms achieve linear memory complexity per agent. Experimental results on graph coloring, sensor networks, and radar coordination benchmarks demonstrate that the proposed methods significantly outperform state-of-the-art algorithms like DUCT in terms of scalability and solution quality.

Introduction

In multi-agent systems, coordination is essential for optimizing global goals, ranging from drone swarm navigation to smart grid management. These challenges are often modeled as Distributed Constraint Optimization Problems (DCOPs). However, as the number of agents increases, traditional DCOP solvers frequently encounter a "memory wall." Inference-based algorithms like DPOP require exponential memory relative to the problem's induced width, while search-based methods like Distributed UCT (DUCT) suffer from exponential memory growth to store statistics for every possible agent context.

Methodology: Distributed Gibbs Sampling

To address these scalability issues, Nguyen et al. propose a novel approach by bridging the gap between statistical physics and multi-agent systems. By mapping DCOPs to MAP estimation in Markov Random Fields, the authors adapt Gibbs Sampling, a Markov Chain Monte Carlo (MCMC) technique, for distributed environments.

Representation of a DCOP: (a) constraint graph, (b) pseudo-tree structure, and (c) reward function table.

The paper introduces two primary variants:

  1. Sequential Distributed Gibbs (SD-Gibbs): Agents sample new values sequentially based on the current states of their neighbors. This process utilizes a pseudo-tree structure to coordinate information flow.
  2. Parallel Distributed Gibbs (PD-Gibbs): To enhance computational efficiency, multiple agents sample simultaneously. A local priority system ensures that neighboring agents do not sample at the same time, preserving the mathematical integrity of the sampling process.

A key optimization included in both variants is a "best-response" mechanism. Instead of purely random sampling, agents track the single best value observed given their neighbors' current states, improving the convergence toward optimal solutions.

Experimental Evaluation

The algorithms were evaluated against standard DCOP benchmarks, including Graph Coloring Problems, Sensor Network Coordination, and Radar Coordination. These tests compared the proposed Gibbs variants against state-of-the-art solvers like DPOP and DUCT.

Key Results

  • Scalability: While DPOP and DUCT failed due to memory exhaustion at approximately 20 agents in graph coloring tasks, SD-Gibbs and PD-Gibbs successfully scaled to 29 agents and beyond. The memory requirement per agent is reduced from $O(Domain^{Ancestors})$ to $O(Agents)$, representing a significant leap in scalability.
  • Solution Quality: In sensor network scenarios, the Gibbs-based algorithms found near-optimal solutions that consistently outperformed DUCT within identical time constraints.
  • Performance: PD-Gibbs demonstrated superior speed compared to SD-Gibbs, validating the effectiveness of the parallel priority-based sampling approach.

Conclusion

The introduction of SD-Gibbs and PD-Gibbs provides a robust solution to the memory bottleneck in DCOP solving. By achieving linear memory complexity, these algorithms enable the coordination of much larger agent populations than previously possible. Future work may explore the adaptation of these sampling techniques to dynamic environments with changing constraints and unreliable communication channels.

Summary updated

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 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.
BibTeX
@article{nguyen2019distributed,
  author = {Duc Thien Nguyen and William Yeoh and Hoong Chuin Lau and Roie Zivan},
  title = {{Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm}},
  journal = {J. Artif. Intell. Res.},
  year = {2019},
  doi = {10.1613/jair.1.11400},
}
Figure