PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Constraint Optimization Problems and Applications: A Survey

Ferdinando Fioretto, Enrico Pontelli, William Yeoh

arXiv:1602.06347v4cs.AIcs.MA

TL;DR

DCOP frameworks have evolved for dynamic and uncertain multi-agent settings, but their relationships and applicability to realistic domains remain underexamined. This survey classifies DCOP extensions and reviews algorithms and applications, reporting that optimal classical, asymmetric, multi-objective, and dynamic DCOPs are NP-hard, while probabilistic and quantified DCOPs are PSPACE-hard.

  • Problem

    Despite DCOP advances, frameworks have not been related across MAS settings, while applicability to realistic domains lags behind theory and solving strategies.

    Source: §1 · p. 3, §10 · p. 65

  • Method

    The survey categorizes DCOPs by agent characteristics, environment properties, and teamwork, reviewing algorithms and naturally mapped application domains within each framework.

    Source: §10 · p. 65

  • Results

    Classical, asymmetric, multi-objective, and dynamic DCOPs are NP-hard, while probabilistic and quantified DCOPs are PSPACE-hard when solved optimally.

    Source: §9.1 · p. 60

  • Takeaways & Limitations

    The survey identifies agent coordination, algorithm scalability, modeling languages, and evaluation criteria as potential future-work directions.

    Source: §10 · p. 65

    Scalability remains a critical challenge for DCOPs.

    Source: §1 · p. 3

Abstract

from arXiv · show

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.

1. Introduction

The survey organizes DCOP models and extensions within multi-agent systems, connecting their resolution methods and applications while identifying open challenges and future directions.

1. Introduction

  • MAS agents act autonomously and may interact directly or through a shared environment, cooperate toward common goals, or compete to serve their own interests.Agents are also described as reactive to environmental changes and proactive in pursuing goals.Source: §1 · pp. 1–2
  • Dec-POMDPs capture complex multi-agent coordination under action and observation uncertainty, but are NEXP-complete even for two agents, making scalability a critical challenge (Bernstein et al., 2002; Amato, Chowdhary, Geramifard, Ure, & Kochenderfer, 2013).The framework is presented as one of the most general multi-agent approaches, focused on team coordination under uncertainty (Bernstein, Givan, Immerman, & Zilberstein, 2002).Source: §1 · pp. 2–3
  • DCOPs coordinate agents’ decentralized value assignments to optimize global objectives, linking problem-solving and communication strategies to the agents’ interaction graph.The model can exploit graph structure to generate efficient solutions (Modi, Shen, Tambe, & Yokoo, 2005; Petcu & Faltings, 2005b; Gershman, Meisels, & Zivan, 2009; Yeoh & Yokoo, 2012).Source: §1 · p. 3
  • The survey categorizes DCOP frameworks, reviews their resolution methods and applications, and identifies open challenges and future research directions.It examines how frameworks relate within the broader MAS context, including which methods may be borrowed from other paradigms and which applications fit each framework.Source: §1 · pp. 3–4
  • The original DCOP model lacks support for dynamic problems and uncertainty, motivating extensions for changing environments and uncertain agent behavior.The survey asks how the frameworks relate to broader MAS research, including which resolution methods and applications suit each.Source: §1 · p. 3
  • The survey proceeds from constraint models and DCOP representations to classical and extended variants, applications, a critical review, future directions, and conclusions.Variants covered include asymmetric costs, multi-objective optimization, changing environments, uncertainty or partial knowledge, and non-cooperative agents.Source: §1 · p. 4

2. Overview of (Distributed) Constraint Satisfaction and Optimization

The section traces DCOPs from constraint models: CSPs seek assignments satisfying every constraint, weighted models optimize preferences, and distributed models assign variables to agents.

2.1 Constraint Satisfaction Problems

  • CSPs comprise finite variables, domains, and constraints, and seek a complete assignment satisfying every constraint.The paper notes applications including resource allocation, vehicle routing, circuit diagnosis, scheduling, and bioinformatics.Source: §2.1 · p. 5

2.2 Weighted Constraint Satisfaction Problems

  • WCSPs treat constraints as preferences, assigning costs or ⊥ to value combinations and seeking a minimum-cost valid complete assignment; WCSP and COP are used interchangeably.A CSP is a special case using only costs 0 and ⊥.Source: §2.2 · pp. 5–6

2.3 Distributed Constraint Satisfaction Problems

  • DisCSPs distribute CSP variables among autonomous agents, each controlling assigned variables, and seek a complete assignment satisfying all constraints (Yokoo, Durfee, Ishida, & Kuwabara, 1998; Yokoo, 2001).The assignment from variables to agents is surjective.Source: §2.3 · p. 6

2.4 Distributed Constraint Optimization Problems

  • DCOPs extend DisCSPs by replacing Boolean satisfaction with preferences over constraint violations, as agents coordinate their variables and constraints to optimize a global objective.The survey formally introduces the DCOP framework in the next section.Source: §2.4 · p. 7

3. DCOP Classification

The section classifies DCOP models by agent and environment characteristics, situates classical and extended models across neighboring fields, and identifies assumptions and gaps in the survey’s chosen categorization.

3. DCOP Classification

  • The MAS classification distinguishes agent behavior, knowledge, and teamwork from environment behavior and evolution, capturing stochasticity, partial knowledge, competition, and change.Agent behavior and environment response can each be deterministic or stochastic; agent knowledge can be total or partial, teamwork cooperative or competitive, and the environment static or dynamic.Source: §3 · p. 7
  • Classical DCOPs extend WCSPs to distributed settings, while game theory informs Asymmetric and Multi-Objective DCOPs and decision theory informs Probabilistic and Dynamic DCOPs.The survey also notes models drawing on constraint programming, game theory, and decision theory.Source: §3 · p. 8, Figure 3 · p. 8
  • The survey’s categorization assumes deterministic agent behavior, full cooperation, and total knowledge, while leaving dynamic uncertain environments unexplored and noting limited teamwork modeling.It focuses on agent knowledge, environment behavior, and environment evolution; the survey identifies mixed cooperative and competitive agents as a formalism discussed later.Source: §3 · p. 8, Table 3 · p. 8

4. Classical DCOP

Classical DCOPs model fully cooperative agents with deterministic behavior and total knowledge in a static, deterministic environment. This section reviews their formal definitions, solving algorithms, and selected variants.

4. Classical DCOP

  • Classical DCOPs assume fully cooperative agents with deterministic behavior and total knowledge, in a static, deterministic environment.The section also reviews formal definitions, solving algorithms, and selected variants of the model.Source: §4 · p. 9

4.1 Definition

A classical DCOP assigns finite-domain variables to agents and defines cost functions over variable scopes. It seeks a complete assignment satisfying every cost function while minimizing total cost.

4.1 Definition

  • A classical DCOP is a tuple of finite agent, variable, domain, and cost-function sets, with each variable assigned to one agent and each cost function scoped over relevant variables.The global objective is the sum of the cost functions; each function maps scoped variable assignments to a nonnegative cost or ⊥.Source: §4.1 · p. 9
  • A solution is a complete assignment satisfying all cost functions, and the DCOP goal is to minimize their total cost.A cost function is satisfied when its value on the assignment is not ⊥.Source: §4.1 · p. 9
  • A cost function is hard when it returns only 0 or ⊥ for every solution; otherwise, it is soft.Source: §4.1 · p. 9
  • A DCOP can instead be formulated as a maximization problem, typically when its objective functions are utilities or rewards rather than costs.Source: §4.1 · p. 9
  • Finding an optimal solution for a classical DCOP is NP-hard.Source: §4.1 · p. 10

4.2 DCOP: Representation and Coordination

DCOP representations shape both agent coordination and algorithm design. The section’s baseline assumptions limit knowledge of variables, costs, and communication to local agents and their neighbors.

4.2 DCOP: Representation and Coordination

  • Each variable and domain are known only to its agent and neighbors; agents know costs involving their variables and communicate only with neighbors.No other agent knows those costs.Source: §4.2 · p. 10

4.2.1 CONSTRAINT GRAPH

  • The constraint graph connects variables sharing a cost function, showing interaction locality; induced width counts higher-priority neighbors under an ordering and takes their maximum.A k-ary cost function is represented by a clique among its variables.Source: §4.2.1 · p. 10

4.2.2 PSEUDO-TREE

  • A pseudo-tree is a rooted spanning tree in which variables sharing a cost function lie on the same branch; tree edges link parent and child, while backedges link pseudo-relatives.For k-ary costs, virtual variables can monitor assignments and generate costs (Bowring, Tambe, & Yokoo, 2006), or control can be delegated to a participating variable (Pecora, Modi, & Scerri, 2006; Matsui, Matsuo, Silaghi, Hirayama, & Yokoo, 2008).Source: §4.2.2 · pp. 10–11

4.2.3 FACTOR GRAPH

  • Factor graphs represent function factorization with variable and factor nodes; unlike pseudo-tree algorithms, their algorithms directly handle k-ary costs by assigning factor-node control to an agent in scope (Kschischang, Frey, & Loeliger, 2001).Source: §4.2.3 · p. 11

4.3 Algorithms

This section surveys DCOP algorithms by classifying classical methods according to their properties and comparing representative complete and incomplete methods by runtime, memory, and communication. It also describes D-Gibbs, a decentralized incomplete synchronous sampling approach in which agents sample along a pseudo-tree and can return solutions with quality guarantees.

4.3 Algorithms

  • DCOP algorithms are classified as complete or incomplete and by runtime, memory, and communication; anytime methods can return valid solutions before termination and seek to improve them over time.The surveyed algorithms assume one variable per agent; their properties may differ under multi-variable generalizations.Source: §4.3 · p. 12

4.3.1 PARTIAL CENTRALIZATION

  • Partial centralization delegates group decisions to an agent, often improving local coordination efficiency at the cost of information privacy; fully decentralized methods preserve more privacy but require more communication.A centralizing agent must access other agents’ local subproblems.Source: §4.3.1 · pp. 12–13

4.3.2 SYNCHRONICITY

  • Synchronous algorithms impose an update order and maintain consistent local views, whereas asynchronous algorithms update independently and reduce idle time but risk inconsistent views that can impair performance.Peri and Meisels (2013) found that introducing some synchronization may benefit some algorithms.Source: §4.3.2 · p. 13

4.3.3 EXPLORATION PROCESS

  • Classical DCOP algorithms use search, inference, or sampling: they respectively explore assignments, aggregate costs using graph structure, or sample the search space to approximate a function.The survey presents a taxonomy and representative complete and incomplete algorithms rather than exhaustive algorithm descriptions.Source: §4.3.3 · p. 14, Figure 5 · p. 14

4.3.4 COMPLETE ALGORITHMS

  • Complete algorithms include search-based SyncBB, AFB, ADOPT, ConcFB, and OptAPO, plus inference-based DPOP, using bounds, concurrent search, mediation, or pseudo-tree cost aggregation to find optimal solutions.SyncBB and ADOPT require O(dn) operations, while DPOP requires O(dw∗); ADOPT communicates only with neighbors, whereas SyncBB may communicate beyond them. ADOPT has extensions that trade optimality, runtime, memory, or privacy, and NCBB is an anytime variant; DPOP also has extensions trading runtime, memory, privacy, or optimality. ConcFB runs concurrent AFB searches and shares its runtime, memory, and communication characteristics; the original OptAPO was incomplete, with a later complete variant addressing mediator race conditions.Source: §4.3.4 · pp. 15–18

4.3.5 INCOMPLETE ALGORITHMS

  • Incomplete methods trade optimality guarantees for alternative search behavior: Max-Sum uses belief propagation, region-optimal methods solve bounded regions, MGM and DSA perform local search, and DUCT samples assignments.Max-Sum is guaranteed to converge to an optimal solution on acyclic graphs but not necessarily cyclic ones. Region-optimal methods provide error bounds tied to region size or distance and can return improving solutions until region-optimal; MGM has no quality guarantee, while DSA uses stochastic choices to escape local minima. DUCT provides quality guarantees that improve with iterations and is anytime.Source: §4.3.5 · pp. 18–21
  • D-Gibbs maps DCOPs to maximum a-posteriori estimation and decentralizes Gibbs sampling as an incomplete, synchronous, sampling-based algorithm.Gibbs sampling is a centralized Markov Chain Monte-Carlo method for approximating joint probability distributions.Source: §4.3.5 · p. 21
  • Agents sample sequentially from the pseudo-tree root to the leaves using context-conditioned value probabilities, and propagate cost information upward until a fixed iteration limit or convergence.After choosing a value, each agent informs lower-priority neighbors; children then sample. D-Gibbs can provide quality guarantees on the returned solution.Source: §4.3.5 · p. 21
  • D-Gibbs has the same runtime characteristics as DUCT, requires O(l) memory per agent, and sends O(ℓnl) messages per iteration, each of constant size O(1), only to neighbors.Each agent stores current values of its neighbors; messages carry either an agent's current value or partial solution cost.Source: §4.3.5 · pp. 21–22
  • A GPU-based version accelerates agents’ sampling process (Fioretto, Yeoh, & Pontelli, 2016a).Source: §4.3.5 · p. 22

4.4 Tradeoffs Between the Various DCOP Algorithms

DCOP algorithm suitability depends on matching algorithm characteristics to application needs. The recommendations distinguish complete algorithms from incomplete ones based on optimality, memory, communication, quality guarantees, and problem structure.

4.4.1 COMPLETE ALGORITHMS

  • For applications requiring optimality, choose complete algorithms according to memory, communication, and network constraints.Inference-based methods such as DPOP suit agents with ample memory and few-large-message communication; search-based methods suit memory-limited agents, except when induced width is small. OptAPO is preferred when partial centralization is allowed; otherwise ConcFB is recommended over AFB, which outperforms ADOPT and SyncBB. If agents cannot communicate beyond neighbors, ADOPT or variants such as BnB-ADOPT and NCBB are alternatives; those variants can outperform ADOPT while maintaining its resource requirements (Chechetka & Sycara, 2006; Yeoh et al., 2010).Source: §4.4.1 · p. 22

4.4.2 INCOMPLETE ALGORITHMS

  • When incomplete solutions need quality guarantees, choose among algorithms according to the desired bound and how it is parameterized.Bounded Max-Sum ties its error bound to edge subsets removed to make the graph acyclic; region-optimal methods use region size k or hop count t; DUCT and D-Gibbs use sampling iterations and probabilistic bounds. Weighted (BnB-)ADOPT and A-DPOP also parameterize error bounds and speedup.Source: §4.4.2 · p. 23
  • Without a required quality guarantee, Max-Sum, MGM, and DSA trade off differently with domain size and induced width.MGM and DSA often outperform Max-Sum on large-domain problems because Max-Sum’s memory and computational costs grow exponentially with domain size; Max-Sum is efficient at small induced widths and optimal when induced width is 1. It generally finds good-quality solutions, particularly with recent improvements (Zivan, Parash, Cohen, Peled, & Okamoto, 2017).Source: §4.4.2 · p. 23
  • Hard constraints rule out DUCT and D-Gibbs, while MGM and DSA serve as robust benchmarks when problem characteristics are unknown.The sampling algorithms require smooth cost functions and cannot handle prohibited value combinations; search- or inference-based algorithms are then appropriate. MGM and DSA tend to find reasonably high-quality solutions in practice, though known problem characteristics may let other algorithms do better.Source: §4.4.2 · p. 23

4.5 Notable Variant: Asymmetric DCOPs

Asymmetric DCOPs model problems in which agents can incur different costs from the same constraint, unlike classical DCOPs, and require methods that coordinate those individual costs. The survey describes their definition, limitations of classical reformulations, and specialized algorithms.

4.5.1 DEFINITION

  • Asymmetric DCOPs let agents participating in a cost function incur different costs for the same assignment, unlike classical DCOPs, which require equal costs.They remain NP-hard, but can be reduced to equivalent classical DCOPs using a polynomial number of variables and constraints.Source: §4.5 · p. 23, §4.5.1 · pp. 23–24

4.5.2 RELATION TO CLASSICAL DCOPS

  • The PEAV reformulation adds mirror variables and equality constraints, but can scale poorly; existing incomplete classical algorithms may also converge to a hard-constraint-satisfying local optimum.Those algorithms can fail to distinguish among solutions satisfying all hard constraints, motivating specialized methods.Source: §4.5.2 · p. 24

4.5.3 ALGORITHMS

  • Asymmetric DCOP algorithms aggregate agents’ individual costs using either a two-phase strategy or single-phase back checking, performed synchronously or asynchronously.The two-phase approach evaluates one side of each constraint before completing an assignment, then aggregates the remaining sides; single-phase methods check each side during assignment.Source: §4.5.3 · p. 24
  • SyncABB-2ph and SyncABB-1ph are complete synchronous search methods that extend SyncBB, respectively aggregating remaining costs after a complete assignment or using back checking during search.Both have the same worst-case runtime, memory, and communication requirements as SyncBB.Source: §4.5.3 · p. 25
  • ATWB is a complete asynchronous search method extending AFB with forward and backward bounding, sending CPA copies backward so assigned agents can return cost estimates.Its worst-case runtime, memory, and communication requirements match AFB.Source: §4.5.3 · p. 25
  • ACLS is an incomplete synchronous search method extending DSA, where agents evaluate neighbor proposals and probabilistically commit to changes to escape local minima.Its worst-case runtime, memory, and communication requirements match DSA.Source: §4.5.3 · p. 25
  • MCS-MGM is an incomplete synchronous search method extending MGM, with agents sharing their side-specific costs to calculate total constraint costs and coordinate the largest-gain change.Its worst-case runtime, memory, and communication requirements match MGM.Source: §4.5.3 · pp. 25–26

4.6 Notable Variant: Multi-Objective DCOPs

Multi-Objective DCOPs extend DCOPs to problems with potentially conflicting objectives. Their solutions are characterized by Pareto optimality, and the survey reviews complete and incomplete algorithms for finding such solutions.

4.6.1 DEFINITION

  • An MO-DCOP assigns each complete assignment a vector of costs across multiple objective-function sets, compared pointwise across objectives.The model extends DCOPs to optimize more than one objective simultaneously, including potentially conflicting objectives.Source: §4.6.1 · p. 26, §4.6 · p. 26
  • A solution is Pareto optimal when no other solution improves at least one objective without worsening another; the Pareto front collects their cost vectors.Solving an MO-DCOP is equivalent to finding the Pareto front, which may be exponential in the number of variables even for tree-structured problems.Source: §4.6.1 · p. 27

4.6.2 ALGORITHMS

  • Complete algorithms include MO-SBB, which broadcasts non-dominated solutions as global bounds, and a pseudo-tree extension of ADOPT using vector boundaries.MO-SBB returns the Pareto-optimal solutions after dominance filtering; the ADOPT-based method assumes aligned cost-function scopes and can require exponentially many cost-vector combinations.Source: §4.6.2 · p. 28
  • B-MOMS approximates bounds for MO-DCOPs through bounding, multi-objective Max-Sum, and value-propagation phases, using utopia points to compute bounds.Its worst-case runtime matches Max-Sum, while message size and per-agent memory are O(pdn).Source: §4.6.2 · pp. 28–29
  • DP-AOF scalarizes objectives with weights after computing the utopia point, while MO-DPOPLp seeks a solution nearest that point under an Lp-norm.MO-DPOPLp is guaranteed to find a Pareto-optimal solution only with the L1-norm; DP-AOF runs DPOP h times to compute the utopia point.Source: §4.6.2 · p. 29
  • DIPLS iteratively applies Pareto local search from random assignments, with a controller filtering and broadcasting non-dominated solutions.Its worst-case runtime is O(ℓkp), and the controller's message size is O(np).Source: §4.6.2 · pp. 29–30

5. Dynamic DCOPs

Dynamic DCOPs model changing environments as sequences of classical DCOPs, requiring agents to solve the current problem while adapting to changes they cannot predict. Their algorithms aim to stabilize solutions after changes, while variants add commitment deadlines or learned transition dynamics.

5.1 Definition

  • A D-DCOP is a sequence of classical DCOPs, each of which agents must solve optimally despite knowing only the current problem, not future changes.The model allows costs, agents, or other parts of the problem to change over time.Source: §5.1 · p. 30, §5 · p. 30
  • Self-stabilization requires finite-step convergence to a stable assignment and closure while the environment remains unchanged; solving D-DCOPs is NP-hard because each time-step problem must be solved independently.Stability seeks to minimize the steps needed to converge after a change.Source: §5.1 · pp. 30–31

5.2 Algorithms

  • D-DCOP algorithms are designed to respond efficiently to environmental changes, often seek self-stabilization, and are classified as complete or incomplete by whether they find each time-step optimum.These requirements motivate adaptations beyond simply applying a classical DCOP solver at every step.Source: §5.1 · p. 30, §5.2 · p. 31

5.2.1 COMPLETE ALGORITHMS

  • S-DPOP stabilizes after at most τ UTIL messages and k VALUE messages following a change, with per-step worst-case runtime, memory, and communication matching DPOP.Its self-stabilizing phases maintain the DFS pseudo-tree and perform UTIL and VALUE propagation.Source: §5.2.1 · p. 31
  • I-ADOPT and I-BnB-ADOPT (Yeoh, Varakantham, Sun, & Koenig, 2011) reuse bounds from prior problems, recomputing them for affected agents; they match ADOPT’s per-step worst-case runtime and communication.Their any-space property lets them use additional memory to speed up solving when it is available.Source: §5.2.1 · pp. 31–32

5.2.2 INCOMPLETE ALGORITHMS

  • SBDO (Billiau, Chang, & Ghose, 2012a) exchanges is-good and no-good messages to update assignments and handle constraint violations, with per-change worst-case requirements matching SyncBB.FMS (Ramchurn, Farinelli, Macarthur, & Jennings, 2010) recomputes changed factors and propagates messages only through regions affected by topological changes; its per-step worst-case requirements match Max-Sum.Source: §5.2.2 · p. 32

5.3 Notable Variants: D-DCOPs with Commitment Deadlines or Markovian Properties

  • RS-DPOP models hard or soft commitment deadlines and stability penalties for changing soft-committed variables, with the same order complexity as S-DPOP.Its UTIL and VALUE propagation phases account for commitment deadlines, with per-step worst-case runtime, memory, and communication matching S-DPOP.Source: §5.3 · p. 33
  • Distributed Q-learning and R-learning (Nguyen, Yeoh, Lau, Zilberstein, & Zhang, 2014) learn unknown transitions in MD-DCOPs, while PD-DCOP transitions are known and depend on current random variables rather than the agents’ current solution.Both learning algorithms match DPOP’s per-step worst-case requirements, but Distributed Q-learning sends O(m^2) messages rather than DPOP’s O(m).Source: §5.3 · pp. 33–34

6. Probabilistic DCOPs

This section surveys probabilistic DCOPs, which represent uncertainty in cost functions while agents remain cooperative and deterministic, and covers algorithms for different variants. It also discusses a finite-horizon extension for agents that learn costs through exploration and ICG-Max-Sum’s approach to robust solutions for uncertain P-DCOPs.

6.1 Definition

  • P-DCOPs represent uncertainty through stochastic cost outcomes or uncontrollable random variables, with decision makers evaluating distributions using an evaluator and utility function.Their cost functions return probability distributions for decision-variable assignments; random variables model exogenous events such as weather or device malfunctions.Source: §6 · p. 34, §6.1 · p. 35

6.2 Algorithms

  • P-DCOP algorithms address different uncertainty variants and are often not directly comparable; solving general P-DCOPs is PSPACE-hard, and their complexity classes remain largely unexplored.The survey classifies algorithms as complete or incomplete according to whether they guarantee optimal solutions for a given evaluator and utility function.Source: §6.2 · p. 37, §6.1 · p. 37

6.2.1 COMPLETE ALGORITHMS

  • E[DPOP] extends DPOP with collaborative sampling and is complete for linear evaluators; SD-DPOP is complete and selects values using second-order stochastic dominance.Global-E[DPOP] has message size O(dw*s^q); SD-DPOP's message size depends on its Pareto-set representation of continuous or discretized cost functions.Source: §6.2.1 · pp. 38–39

6.2.2 INCOMPLETE ALGORITHMS

  • DNEA reduces cost-function uncertainty using an evaluator and neighbor exchange, while U-GDL propagates distributions through convolution and uses stochastic dominance to filter solutions.Both are incomplete; U-GDL may use sampling when PDFs are not closed under convolution.Source: §6.2.2 · pp. 39–40

6.3 Notable Variant: P-DCOPs with Partial Agent Knowledge

  • For partial-knowledge P-DCOPs, agents must coordinate exploration of unknown costs with exploitation of known costs to minimize total online cost within a limited time.This model was originally called Distributed Coordination of Exploration and Exploitation (DCEE) (Taylor, Jain, Jin, Yokoo, & Tambe, 2010).Source: §6.3 · p. 40

6.3.1 DEFINITION

  • The partial-knowledge model adds a finite horizon T and seeks a sequence of complete assignments that minimizes cumulative cost as agents gain environmental knowledge.Agents have at most T steps to change decision-variable values, thereby solving successive P-DCOP problems.Source: §6.3.1 · pp. 40–41

6.3.2 ALGORITHMS

  • BE-Rebid evaluates exploration and backtracking actions, while Heist uses bandit-based UCB and distributed belief propagation; BE-Rebid-2 found that greater coordination can lower solution quality.Taylor et al. (2011) call this effect the team uncertainty penalty; Heist balances exploration and exploitation and derives optimal asymptotic regret bounds.Source: §6.3.2 · pp. 41–42
  • ICG-Max-Sum iteratively solves master and subproblems with Max-Sum, adding witness points until convergence to minimize maximum regret over uncertain problem distributions.It does not learn cost-function outcomes and assumes horizon T = 1.Source: §6.3.2 · p. 42
  • Runtime is O(ℓ|I|dl) and memory is O(|I|dl); messages match Max-Sum in count, but each has size O(|I|d).The master problem dominates runtime and memory; two parallel Max-Sum iterations run per ICG-Max-Sum iteration.Source: §6.3.2 · pp. 42–43
  • Le, Fioretto, Yeoh, Son, and Pontelli (2016) introduced a variation that minimizes expected regret instead of maximum regret.Source: §6.3.2 · p. 43

7. Quantified DCOPs

Quantified DCOPs extend DCOPs to partially cooperative settings by distinguishing cooperative and adversarial agents with quantifiers. Their ordered variables require specialized complete algorithms that reason over lower and upper bounds.

7.1 Definition

  • QDCOPs use existential and universal quantifiers to distinguish cooperative from adversarial agents, adapting QCSP and QDCSP models to DCOPs.Existential variables take one value, while universal variables are unassigned and the result must hold for every value in their domains.Source: §7.1 · p. 43, §7 · p. 43
  • QDCOP solutions bound the objective: existential choices define the lower bound and worst-case universal choices define the upper bound; solving QDCOPs is P-SPACE-hard (Benedetti et al., 2008; Lallouet, Lee, Mak, & Yip, 2015).Unlike a DCOP solution, which gives a single value and cost, a QDCOP solution has lower and upper bounds.Source: §7.1 · p. 43

7.2 Algorithms

  • QDCOPs impose a rigid quantifier order, so classical DCOP algorithms do not directly apply; complete approaches extend pseudo-tree algorithms, using null edges when needed to preserve ordering.The algorithms treat universal variables as adversarial virtual agents seeking to minimize the objective.Source: §7.2 · p. 44
  • Min-max ADOPT computes lower bounds from existential variables and upper bounds from universal variables, stopping when the root finds them equal.It is an asynchronous search algorithm using VALUE and COST messages, with no major pruning strategy.Source: §7.2 · p. 44
  • Alpha-beta ADOPT extends Min-max ADOPT with alpha/beta thresholds that prune assignments unable to improve on an evaluated solution; Bi-threshold ADOPT uses two backtracking thresholds instead of one.Alpha is the lower bound controlled by universal variables, and beta the upper bound controlled by existential variables.Source: §7.2 · p. 44

8. DCOP Applications … 8.4 Scheduling Problems

The section surveys how DCOPs map to diverse multi-agent applications, from emergency response and radio-frequency allocation to recommendations and scheduling. It outlines the corresponding models and objectives, illustrating how distributed decision-making fits each domain.

8.1 Disaster Management and Coordination Problems

  • Evacuation DCOPs assign evacuee groups to shelters to minimize overflow and travel while meeting capacity and service needs (Carpenter, Dugan, Kopena, Lass, Naik, Nguyen, Sultanik, Modi, & Regli, 2007; Kopena, Sultanik, Lass, Nguyen, Dugan, Modi, & Regli, 2008; Lass, Kopena, Sultanik, Nguyen, Dugan, Modi, & Regli, 2008a; Lass, Regli, Kaplan, Mitkus, & Sim, 2008b; Kinoshita, Iizuka, & Iizuka, 2013).Each group is a DCOP agent with a shelter-allocation variable; costs encode group size, capacity, medical needs, and distance.Source: §8.1 · p. 46
  • CFST models coordinate task sequences, deadlines, travel, and coalitions to maximize completed tasks; LEP adds dynamically revealed tasks and interruption penalties (Ramchurn et al., 2010; Amador, Okamoto, and Zivan, 2014).In the CFST model, agents choose tasks and coalition utility represents task-completion success.Source: §8.1 · pp. 46–47

8.2 Radio Frequency Allocation Problems

  • Cooperative WLAN channel-assignment DCOPs model access points as agents and minimize total interference; dynamic spectrum approaches address time-varying interference sources (Monteiro et al., 2012a, 2012b; Xie, Howitt, and Raja, 2007; Mir, Merghem-Boulahia, and Ga¨ıti, 2010).The cooperative model uses signal-to-interference-and-noise ratio costs for same-channel and partially overlapping adjacent-channel transmissions.Source: §8.2 · p. 47

8.3 Recommendation Systems

  • A group travel-recommendation DCOP combines users’ service preferences with supplier recommendations to optimize the package for the group (Lorenzi, dos Santos, Ferreira Jr, and Bazzan, 2008).User agents represent travel choices, while recommender agents represent suppliers; constraints enforce compatibility between them.Source: §8.3 · pp. 47–48

8.4 Scheduling Problems

  • Meeting-scheduling DCOPs seek to maximize net resource utility while avoiding overlapping events that require shared resources.In the described events-as-variables formulation, each event takes an eligible time slot or zero if unscheduled (Maheswaran, Tambe, Bowring, Pearce, and Varakantham, 2004b).Source: §8.4 · p. 48
  • Water-allocation DCOPs optimize active agents’ objectives under physical constraints while maximizing normative constraints that protect passive ecological interests (Giuliani et al., 2014; Amigoni, Castelletti, & Giuliani, 2015).Agents represent water supplies, hydropower production, and ecological preservation; passive ecological agents do not make decisions.Source: §8.4 · pp. 48–49
  • The vessel-rotation planning DCOP assigns vessels’ terminal visits and arrival and departure times while representing terminal capacity, preferences, waiting penalties, and visit time windows.Vessel agents control visit and timing variables; terminal agents control auxiliary variables representing terminal capacity.Source: §8.4 · p. 49
  • Patient-scheduling DCOPs model appointment feasibility, resource use, patient preferences, and treatment priorities to support efficient care under limited resources (Hannebauer and M¨uller, 2001; Billiau, Chang, Ghose, and Miller, 2012b, 2012c).The dynamic radiotherapy model represents patient-private information and the public machine schedule, accounting for treatment duration and tumor-specific restrictions.Source: §8.4 · pp. 49–50

8.5 Sensor Network Problems · 8.6 Service-Oriented Computing Problems

The sections show how DCOPs model sensor-network tasks constrained by energy, communication, sensing, and mobility, and service-computing tasks involving distributed resources, quality requirements, and changing conditions. They describe formulations ranging from weighted graph coloring to dynamic and hierarchical DCOPs.

8.5 Sensor Network Problems

  • Target tracking seeks to detect as many targets as quickly as possible while conserving sensor energy; Zhang et al. (2005) model it as weighted graph coloring mapped to a DCOP.Sensors are nodes, shared scan regions are weighted edges, and colors represent time slots; each sensor must scan its sector at least once.Source: §8.5 · p. 50
  • Semnani and Basir (2013) partition target-tracking problems into local regions, solve them with separate DCOPs, then combine shared variables and constraints in a hierarchical DCOP.The hierarchy is intended to scale to larger problems.Source: §8.5 · p. 50
  • In robotic network optimization, Jain et al. (2009) model robot positions as variables and use a P-DCOP to balance exploration of unknown wireless-link costs with exploitation of known costs.Robots make small movements without changing network topology; link costs depend on positions, and radio interference is difficult to predict.Source: §8.5 · pp. 50–51
  • Mobile Sensor Team DCOPs minimize remaining target-coverage requirements, while agent domains, target constraints, and the constraint graph can change at each time step.A target's remaining requirement depends on its environmental requirement and the joint credibility of agents currently covering it.Source: §8.5 · p. 51
  • Sensor sleep scheduling models on/off states to conserve power: Chachra and Marefat (2006) minimize network delay under neighbor and consecutive-on constraints, while Stranders et al. (2009) maximize event detection probability with energy-neutral operation.Energy-neutral operation means each agent can have an indefinite lifetime.Source: §8.5 · p. 52

8.6 Service-Oriented Computing Problems

  • Application Component Placement assigns components to servers under hardware, communication, and privacy requirements; Jin et al. (2011) model server bids as variables and maximize utility subject to placement constraints.Hard constraints ensure each component is placed on exactly one server and that inter-server communication bandwidth requirements are met.Source: §8.6 · pp. 52–53
  • Server allocation selects service providers to maximize social welfare while meeting client QoS requirements; Choudhury et al. (2014) model entities' service decisions and changing requests or offers as a Dynamic DCOP.Variable utility combines an entity's consumer, provider, and forwarder roles, with factors including GPU cycles, battery power, memory, and bandwidth.Source: §8.6 · p. 53

8.7 Smart Grid and Smart Homes Problems · 8.8 Supply Chain Management Problems · 8.9 Traffic Flow Control Problems

Across smart-grid, supply-chain, and traffic applications, the sections describe DCOPs as encodings for coordinating distributed decisions under network, resource, and changing-condition constraints.

8.7 Smart Grid and Smart Homes Problems

  • DCOP economic dispatch coordinates generator outputs and line capacities to balance supply and demand at minimum cost, while dynamic variants constrain generator-output changes across time steps.The classic formulation can minimize generator carbon emissions; the planning-horizon version adds constraints between consecutive time steps.Source: §8.7 · p. 54
  • Power restoration DCOPs model nodes with load and direction variables, enforcing tree-shaped power flow and Kirchhoff’s law to restore the maximum number of affected sinks.The objective follows line failures and is subject to flow-conservation and transmission-capacity constraints.Source: §8.7 · pp. 54–55
  • Microgrid-islanding DCOPs represent generation, consumption, line flows, and switch states, seeking a switching configuration that minimizes unserved load subject to capacity and flow constraints.The resulting islands are clusters of generators and loads able to operate without external energy supply.Source: §8.7 · p. 55
  • Prosumer energy-trading DCOPs model bilateral trades on network edges and enforce energy balance, line capacity, and flow constraints while maximizing prosumer benefits.Each prosumer is an agent; the two directed edge variables represent units sold to or bought from a neighbor.Source: §8.7 · p. 55
  • Smart-building DCOPs assign device actions to achieve environmental goals, while smart-home scheduling coordinates device schedules to meet temporal goals and reduce energy costs and daily peaks.The models encode action costs, consumption, preferences, and temporal constraints; a dataset was released for the smart-home scheduling problem.Source: §8.7 · pp. 55–56

8.8 Supply Chain Management Problems

  • Supply-chain formation DCOPs model producers and consumers choosing trading partners, quantities, and costs over feasible exchanges, with dynamic versions allowing participants and problem properties to change.The formulations use task dependency networks to represent feasible producer-consumer exchanges and optimize a cost function.Source: §8.8 · pp. 56–57

8.9 Traffic Flow Control Problems

  • Traffic-light synchronization DCOPs coordinate adjacent signals’ directions to create green waves, representing conflicts and incoming-vehicle costs in dynamic optimization.Agents represent traffic lights, and their variables select between two coordination directions.Source: §8.9 · p. 57
  • Probabilistic DCOP traffic approaches address partial cost knowledge by letting agents learn changing traffic patterns from average travel times of the first 100 cars.Agents have limited time to explore signal-duration intervals and update their cost functions from those evaluations.Source: §8.9 · pp. 57–58

9. Analyses and Perspectives on DCOPs

DCOP extensions address different multi-agent settings, but choosing a model and algorithm suited to the problem domain is essential. The survey identifies open needs in algorithmic foundations, coordination, and evaluation infrastructure.

9.1 Comparative Overview of DCOP Models

  • Classical, asymmetric, multi-objective, and dynamic DCOPs address cooperative static settings, private unequal costs, multiple objectives, and evolving environments, respectively.Classical DCOPs suit static, deterministic, fully observable, single-goal tasks; multi-objective methods face memory demands proportional to objective count and Pareto-set size, favoring incomplete strategies.Source: §9.1 · pp. 58–59
  • Probabilistic DCOPs model uncertain events, while Quantified DCOPs model adversarial agents; combined dynamic and uncertain environments remain under-researched.Partial-knowledge probabilistic models can use sampling and decision methods such as minimax, maximin, or regret-based approaches.Source: §9.1 · pp. 59–60
  • Classical, asymmetric, multi-objective, and dynamic DCOPs are NP-hard to solve optimally, whereas probabilistic and quantified extensions are PSPACE-hard.Table 6 summarizes the complexity of the DCOP models discussed in the survey.Source: §9.1 · p. 60, Table 6 · p. 60

9.2 Algorithms and Theoretical Analysis

  • Beyond mature classical algorithms, most DCOP formalisms lack strong algorithmic and theoretical foundations, motivating research across game theory, decision theory, and machine learning.Potential directions include auction mechanisms for partially cooperative agents, inference and convex optimization for message passing, and integrating partial observability with DCOP structure.Source: §9.2 · pp. 60–61
  • Future incomplete algorithms should adapt to time, memory, and communication limits, while formal study of coordination phase transitions could guide more efficient strategies.At intermediate agent workloads, simple coordination can lose effectiveness; dynamic decomposition has produced near-optimal policies while reducing communication.Source: §9.2 · pp. 61–62

9.3 Evaluation Metrics and Benchmarks

  • Common assumptions that agents control one variable and constraints are binary can make DCOP algorithms inefficient on realistic multi-variable problems.Compilation can require exponential memory, while decomposition can add unnecessary computation and communication; centralized local solvers offer another approach, and redesigned algorithms support multiple variables.Source: §9.3 · p. 62
  • The absence of a shared DCOP language and standard runtime metric hinders algorithm comparison, motivating algebraic or logic-based modeling and benchmark repositories.Existing runtime measures include NCCCs, simulated runtime, and cycles, but researchers lack consensus on a standard metric.Source: §9.3 · pp. 62–65
  • Existing simulators support varied execution and testing features, but high-fidelity tools for Dynamic and Probabilistic DCOPs are still needed.DisChoco, Frodo, and AgentZero provide different algorithm, messaging, and debugging capabilities; JADE offers a general MAS runtime and monitoring tools.Source: §9.3 · pp. 63–64

10. Conclusions

DCOPs are a popular framework for distributed reasoning and coordination, but their applicability to realistic domains lags behind their theoretical and algorithmic development. This survey connects DCOP frameworks and solving strategies to potential applications and future research directions.

10. Conclusions

  • DCOPs are popular for distributed reasoning and coordination, while extensions address limitations in complex, real-time, and uncertain environments and varying levels of agent cooperation.Extensions also address dynamic environments.Source: §10 · p. 65
  • Despite substantial progress in DCOP theory and algorithms, their applicability to realistic domains lags behind, motivating the survey’s link between solving strategies and potential applications.Source: §10 · p. 65
  • The survey categorizes DCOP advances by agent characteristics, environment properties, and teamwork, reviews algorithms and application domains, and identifies future directions in coordination, scalability, modeling languages, and evaluation.Source: §10 · p. 65

Related papers

Loading 1602.06347v4…