RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inferences

Ziyu Chen, Wenxin Zhang, Yanchen Deng, Dingding Chen, Qing Li

Abstract

Distributed Constraint Optimization Problems (DCOPs) are a vital framework for multi-agent coordination. While the Distributed Pseudotree Optimization Procedure (DPOP) is efficient in message count, its exponential memory requirements limit scalability. Memory-Bounded DPOP (MB-DPOP) addresses this through cycle-cutting but introduces significant computational redundancy. This paper introduces RMB-DPOP, which optimizes MB-DPOP by replacing centralized iteration with a distributed, asynchronous enumeration mechanism, improved variable selection, and result caching. Experimental results demonstrate that RMB-DPOP significantly outperforms state-of-the-art solvers in communication overhead, runtime, and scalability.

Introduction

Distributed Constraint Optimization Problems (DCOPs) are essential for coordinating agents in applications such as sensor networks and smart grids. The DPOP algorithm is a benchmark for efficiency in message count but suffers from memory explosion in complex problems. MB-DPOP was developed to mitigate this by limiting memory usage to a constant $k$ through the iteration of "cut-nodes." However, MB-DPOP's centralized iteration at cluster roots leads to redundant calculations and synchronization bottlenecks, preventing it from scaling effectively.

Problem Statement: Redundancy in MB-DPOP

The primary flaw in MB-DPOP is its failure to exploit problem independence. In a pseudo-tree structure, different branches may be independent of many variables being iterated. MB-DPOP forces a central root to iterate through all combinations of cut-nodes, even those irrelevant to specific sub-trees. This creates a massive bottleneck where agents wait on unnecessary computations.

A pseudo-tree representation of a DCOP, illustrating the hierarchical structure and back-edges (dashed) that define agent dependencies.

Methodology

RMB-DPOP introduces three primary refinements to transform MB-DPOP into a more efficient, asynchronous solver:

  1. Distributed Enumeration Mechanism (DEM): DEM factorizes the iteration process. Instead of a single root managing all combinations, each branch only processes assignments for variables in its separator set (the variables that actually affect it). This enables asynchronous processing across independent branches and reduces the total combinations each agent must process.
  2. Iterative Selection Mechanism (ISM): ISM optimizes the choice of cut-nodes. Rather than using simple heuristics, ISM iteratively selects nodes that cover the maximum number of high-width clusters. It also favors nodes deeper in the tree to keep computations local.
  3. Caching Mechanism: Since the algorithm is iterative, agents often encounter the same sub-problems. RMB-DPOP stores previous inference results; if a new set of variable assignments matches a cached entry, the agent skips the expensive computation and passes the stored result up the tree.

Theoretical analysis confirms that RMB-DPOP is a strict optimization: it will never send more messages than the original MB-DPOP for the same set of cut-nodes.

Experimental Evaluation

The authors evaluated RMB-DPOP against DPOP, MB-DPOP, and PT-FB using random DCOPs (densities 0.1 to 0.5) and scale-free networks.

Performance comparison of RMB-DPOP against baselines across (a) Number of Messages, (b) Network Load, and (c) Runtime as a function of agent count.

Key Results

  • Scalability: In tests with 30 agents, MB-DPOP (with $k=3$) failed to complete, while RMB-DPOP handled up to 34 agents with ease.
  • Efficiency: RMB-DPOP consistently reduced network load and runtime by orders of magnitude. Notably, RMB-DPOP with a memory limit of $k=6$ often outperformed MB-DPOP with a more relaxed limit of $k=9$.
  • Robustness: On dense graphs (0.5 density), RMB-DPOP ($k=9$) solved over 90% of problems within 15 minutes, compared to less than 80% for the original MB-DPOP.

Conclusion

RMB-DPOP represents a significant advancement in complete DCOP solvers. By unlocking the inherent parallelism of the pseudo-tree and eliminating redundant inferences, it provides a strictly better optimization over MB-DPOP. The authors suggest that these mechanisms are algorithm-agnostic and could be integrated into other DCOP frameworks to further improve performance.

Summary updated

BibTeX
@inproceedings{chen2020rmb,
  author = {Ziyu Chen and Wenxin Zhang and Yanchen Deng and Dingding Chen and Qing Li},
  title = {{RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inferences}},
  booktitle = {AAMAS},
  year = {2020},
  url = {https://openreview.net/forum?id=gcPD8SQMQQ},
}
Figure