Distributed Constraint Optimization Problems and Applications: A Survey

Ferdinando Fioretto, Enrico Pontelli, William Yeoh

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. Within a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent agent architectures 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 enabled them to support MAS in complex, real-time, and uncertain environments. This survey aims at providing an overview of the DCOP model, giving 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.

Introduction

In a multi-agent system (MAS), independent entities (agents) must coordinate their actions to achieve a global goal or satisfy local preferences. Distributed Constraint Optimization Problems (DCOPs) provide the mathematical language for this coordination. However, the "classical" DCOP model assumes a perfect world: the environment never changes, agents know everything about their local state, and everyone is perfectly cooperative.

Real-world applications—like managing a smart power grid or coordinating disaster relief—don't work this way. This paper addresses the gap between theoretical models and practical reality by classifying the "zoo" of DCOP extensions and algorithms developed over the last decade to handle noise, change, and competition.

The conceptual evolution from centralized Constraint Satisfaction Problems (CSP) to Distributed Constraint Optimization Problems (DCOP).

A Taxonomy for Multi-Agent Coordination

The primary contribution of this survey is a rigorous taxonomy for DCOPs based on five critical dimensions:

  1. Agent Behavior: Whether the effects of actions are deterministic or stochastic.
  2. Agent Knowledge: Whether the agent has total or partial knowledge of its state.
  3. Agent Teamwork: Whether agents are purely cooperative or competitive.
  4. Environment Behavior: Whether the environment's response to actions is predictable or random.
  5. Environment Evolution: Whether the problem is static or dynamic (changing over time).
Classification of DCOP models by environment behavior and evolution, alongside their interdisciplinary roots in Decision Theory and Game Theory.

As shown in the environment matrix above, the authors identify an "Empty Corner": DCOP models that are simultaneously dynamic and stochastic (indicated by the dash in the table) have not yet been fully explored, representing a significant frontier for future research.

Algorithmic Families

The authors categorize resolution algorithms into three primary algorithmic families:

  • Search-based: These use techniques like depth-first search (e.g., ADOPT, SyncBB) to explore the solution space.
  • Inference-based: These leverage dynamic programming or belief propagation (e.g., DPOP, Max-Sum) and are often more efficient for specific graph structures.
  • Sampling-based: These use statistical inference to approximate solutions in large or complex spaces (e.g., DUCT, D-Gibbs).

Key Insights and Trade-offs

  • Complexity Escalation: While solving classical DCOPs is NP-hard, moving to Probabilistic or Quantified DCOPs (which include adversarial agents) pushes the complexity to PSPACE-hard.
  • Privacy vs. Efficiency: The paper highlights "Partial Centralization" (e.g., OptAPO). By allowing a local leader to solve a sub-problem, systems gain efficiency but sacrifice agent privacy—a critical factor in many real-world MAS applications.
  • Algorithm-Problem Matching: No single algorithm is universally superior. For instance, DPOP excels in problems with small "induced width" (tree-like structures), whereas Max-Sum is better for large-scale cyclic graphs where approximate solutions are acceptable.

Applications and Future Directions

The survey maps DCOPs to over 20 real-world problem areas, including Smart Grids (economic dispatch), Sensor Networks (target tracking), and Supply Chain Management. Despite this breadth, several bottlenecks remain:

  • Unified Modeling: Unlike the centralized constraint world which uses MiniZinc, DCOP lacks a general modeling language, hindering experimental comparison.
  • Any-Communication Algorithms: Most current research focuses on "anytime" (quality over time) or "any-space" (memory limits). The authors argue for "any-communication" procedures to handle congested networks like the Internet of Things (IoT).
  • Interdisciplinary Integration: There is a pressing need to better integrate DCOP with machine learning for learning cost functions and game theory for modeling partially cooperative agents.

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. Within a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent agent architectures 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 enabled them to support MAS in complex, real-time, and uncertain environments. This survey aims at providing an overview of the DCOP model, giving 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