Distributed Constraint Optimization Problems and Applications: A Survey

Ferdinando Fioretto, Enrico Pontelli, William Yeoh

Introduction

In Multi-Agent Systems (MAS), autonomous agents must coordinate to achieve global goals, such as sensors tracking targets or smart grids balancing power loads. Centralized decision-making is often impractical due to privacy concerns, communication bottlenecks, or the sheer scale of the system.

The Distributed Constraint Optimization Problem (DCOP) framework addresses this by enabling agents to optimize a global objective through local interactions. As shown in the conceptual lineage below, DCOPs extend classical Constraint Satisfaction Problems (CSP) and Constraint Optimization Problems (COP) into distributed environments.

Conceptual evolution from centralized CSPs to Distributed Constraint Optimization Problems (DCOPs).

Taxonomy of DCOP Extensions

While "classical" DCOPs assume static, deterministic environments with perfectly cooperative agents, real-world applications are rarely so idealized. This survey provides a rigorous classification of DCOP extensions based on three primary dimensions: Agent Knowledge (total vs. partial), Environment Behavior (deterministic vs. stochastic), and Environment Evolution (static vs. dynamic).

Classification of DCOPs based on environment behavior and evolution, alongside their interdisciplinary intersections with Decision Theory and Game Theory.

DCOPs represent a unique "sweet spot" where Constraint Programming (inference/search), Game Theory (self-interest/equilibria), and Decision Theory (uncertainty/Markov processes) overlap. This convergence has led to specialized models such as Asymmetric DCOPs, which allow agents to coordinate without revealing internal cost structures, and Multi-Objective DCOPs, which balance conflicting goals via Pareto optimality.

Algorithmic Landscape

Resolution algorithms for DCOPs are generally categorized into three main families:

  1. Search-based (e.g., ADOPT, SyncBB): These explore the space of possible solutions. They are typically memory-efficient but can suffer from high communication overhead.
  2. Inference-based (e.g., DPOP, Max-Sum): Derived from dynamic programming and belief propagation, these exploit the problem's graph structure to aggregate costs. While efficient, they may require exponentially large messages.
  3. Sampling-based (e.g., DUCT, D-Gibbs): These incomplete approaches use statistical inference to approximate solutions, offering a vital trade-off between solution quality and runtime.

Key Insights and Complexity

  • Communication vs. Computation Trade-off: The choice of a DCOP algorithm is often dictated by the scarcest resource. If bandwidth is low but memory is available, search-based methods are preferred; if bandwidth is high but agents are low-power, inference-based methods are more suitable.
  • The Team Uncertainty Penalty: In probabilistic settings, researchers have found that increasing coordination can sometimes paradoxically decrease solution quality due to the extreme complexity of managing joint uncertainty.
  • Complexity Mapping: The survey notes that while Classical, Asymmetric, and Dynamic DCOPs are NP-hard, Probabilistic and Quantified DCOPs (which involve adversarial agents or stochastic environments) jump in complexity to PSPACE-hard.

Benchmarks and Future Horizons

The field relies on standard benchmarks like graph coloring and sensor network coordination, supported by simulators such as DisChoco, Frodo, AgentZero, and JADE. Despite significant progress, several challenges remain:

  • Modeling Language Gap: The lack of a "universal" language (similar to MiniZinc for centralized problems) makes it difficult to compare algorithms across different studies.
  • Any-Communication Frontier: There is a growing need for "any-communication" procedures—algorithms that can adapt to fluctuating network loads and restricted bandwidth in real-time.
  • Hybrid Environments: Most current research focuses on either dynamic or uncertain environments. The combination of both (Dynamic + Stochastic) remains a wide-open and highly realistic area for future research.

Summary updated

Abstract

The field of multi-agent system (MAS) is an active area of research within artificial intelligence, with an increasingly important impact in industrial and other real-world applications. In a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as a prominent agent model to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have been proposed to enable support of MAS in complex, real-time, and uncertain environments. This survey provides an overview of the DCOP model, offering a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.
BibTeX
@article{fioretto2018distributed,
  author = {Ferdinando Fioretto and Enrico Pontelli and William Yeoh},
  title = {{Distributed Constraint Optimization Problems and Applications: A Survey}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  doi = {10.1613/jair.5565},
}
Figure