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

DCOPs have evolved to address dynamic and uncertain multi-agent environments, but their relationships within the broader MAS context and their applicability to realistic domains remain insufficiently explored. This survey classifies DCOP extensions, reviews algorithms and applications, and identifies complexity patterns, challenges, and future directions.

  • Problem

    Existing DCOPs lacked a framework for dynamic problems and uncertainty, while relationships among extensions and links to realistic applications remained insufficiently explored.

  • Method

    The survey categorizes DCOP advances by agent characteristics, environment properties, and teamwork, then reviews algorithms and application domains for each framework.

  • Results

    Classical, Asymmetric, Multi-Objective, and Dynamic DCOPs are NP-hard, whereas Probabilistic and Quantified DCOPs are PSPACE-hard.

  • Takeaways & Limitations

    The classification identifies future work in agent coordination, algorithm scalability, modeling languages, and evaluation criteria for DCOP models and algorithms.

  • Takeaways & Limitations

    Scalability remains a critical challenge, and some incomplete classical DCOP algorithms cannot effectively solve Asymmetric DCOPs even after PEAV reformulation.

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

Multi-agent systems coordinate autonomous agents pursuing individual or shared goals in decentralized, dynamic, and uncertain settings. The survey examines DCOP extensions, their relationships, resolution methods, applications, and open challenges.

  • Multi-Agent Systems: Agents act autonomously and interact directly through communication or indirectly through a shared environment.They may cooperate toward common goals or compete to advance their own interests.
  • Multi-Agent Systems: MAS architectures support autonomous behavior in real-world, dynamic, and uncertain environments using decision theory, game theory, and constraint programming.These architectures are established within the AAMAS community.
  • Related Frameworks: Dec-POMDPs represent complex action and observation uncertainty but are NEXP-complete even for two agents, creating a critical scalability challenge.Their generality comes with high complexity for generating optimal solutions.
  • DCOP Motivation: DCOPs lack an original framework for dynamic problems and uncertainty, motivating extensions that target diverse agent behaviors and environmental conditions.The survey addresses the unresolved relationships among these frameworks within the broader MAS context.
  • Survey Scope: The survey organizes DCOP foundations, representations, coordination models, classifications, extensions, algorithms, applications, and future directions.Its organization moves from constraint satisfaction models to classical DCOPs and notable extensions.

2. Overview of (Distributed) Constraint Satisfaction and Optimization

Constraint models progress from centralized satisfaction and optimization to distributed settings in which autonomous agents coordinate variable assignments. DCOPs extend this progression by optimizing preference-based costs across agents.

  • Constraint Satisfaction Problems: CSPs assign values to variables subject to constraints, supporting applications including resource allocation, routing, diagnosis, scheduling, and bioinformatics.A CSP comprises variables, finite domains, and constraints over variable subsets.
  • Constraint Satisfaction Problems: A complete CSP assignment must satisfy every constraint, whereas partial assignments cover only a proper subset of variables.Constraint scopes identify the variables on which each constraint is defined.
  • Weighted Constraint Satisfaction Problems: WCSPs replace Boolean satisfaction with weighted preferences that quantify the extent of constraint satisfaction or violation.Forbidden assignments receive a special value, while allowed assignments incur nonnegative costs.
  • Weighted Constraint Satisfaction Problems: A WCSP generalizes a CSP, with ordinary CSP constraints representable using only costs 0 and ⊥.WCSP and Constraint Optimization Problem are used interchangeably in the literature.
  • Distributed Models: DisCSPs distribute CSP variables, domains, and constraints among autonomous agents that communicate to satisfy all constraints.The mapping from variables to agents is part of the distributed model.
  • Distributed Models: DCOPs generalize DisCSPs by assigning preference degrees to constraint violations and extend COPs to multiple agents controlling variables and constraints.Figure 2 presents these relationships among constraint models.

3. DCOP Classification

The survey classifies DCOPs according to agent and environment characteristics, organizing extensions by assumptions about behavior, knowledge, teamwork, and environmental response or evolution.

  • Classification Framework: The classification reflects DCOPs’ evolution toward diverse agent behaviors and environmental conditions.It is presented from a multi-agent-systems perspective.
  • Agent Characteristics: Agent behavior captures whether action effects are deterministic or stochastic, while agent knowledge may be total or partial.These dimensions distinguish assumptions about action outcomes and information available to agents.
  • Agent Characteristics: Agent teamwork distinguishes cooperative from competitive approaches to solving distributed problems.The parameter characterizes the approach taken by teams of agents.
  • Classification Framework: The survey focuses on DCOPs at the intersection of constraint programming, game theory, and decision theory.The classical model is inherited from constraint programming and assumes a static, deterministic, fully known, cooperative setting.
  • Classification Framework: The categorization primarily varies agent knowledge, environment behavior, and environment evolution while commonly assuming deterministic behavior, full knowledge, and full cooperation.The associated models are summarized in Table 3.

4. Classical DCOP

The classical DCOP model represents fully cooperative agents with deterministic behavior and total knowledge operating in a static, deterministic environment. The section reviews its formalization, algorithms, and selected variants.

  • Model Definition: Classical DCOPs assume fully cooperative agents with deterministic behavior and total knowledge.These assumptions define the agent-side characteristics of the model.
  • Model Definition: The classical DCOP environment is both static and deterministic.The section presents formal definitions under these environmental assumptions.
  • Section Scope: The section reviews classical DCOP definitions, relevant solving algorithms, and selected variants of particular interest.Its treatment focuses on the classical model before later extensions.

4.1 Definition

A classical DCOP assigns variables to agents and seeks a complete, constraint-satisfying assignment that minimizes the total cost of its functions.

  • A classical DCOP consists of agents, variables, finite domains, cost functions, and an assignment mapping variables to agents.
  • Each cost function contributes a factor to the global objective, and functions may also be called constraints, utility functions, or reward functions.
  • A complete assignment is a solution only when it assigns every variable and satisfies all cost functions.
  • The objective is to find a solution minimizing total problem cost over the state space of possible solutions.
  • Hard cost functions return only 0 or ⊥, whereas soft functions may assign other costs.
  • DCOP optimization is NP-hard, and utility- or reward-based formulations can instead use maximization.

4.2 DCOP: Representation and Coordination

DCOP representations encode local interactions and coordination structure for agents and algorithms. Constraint graphs, pseudo-trees, and factor graphs differ in how they organize variables, factors, and higher-order constraints.

  • Coordination assumptions: DCOP representation is central to both agent coordination and algorithm design under assumptions of local knowledge and communication.Agents know their variables, domains, relevant cost functions, and neighboring agents, but not other agents’ cost functions.
  • Constraint graph: A constraint graph connects variables that share a cost function, making the locality of interactions explicit.The example includes a three-variable clique for f123 and an edge between x2 and x4 for f24.
  • Ordering and induced width: An induced graph formed from a variable ordering connects each node to higher-priority neighbors, with induced width equal to the maximum such width.
  • Representations: Figure 4’s example depicts a constraint graph, a pseudo-tree, and a factor graph for the same four-agent DCOP.In the factor graph, a3 controls f123 and a4 controls f24.
  • Pseudo-tree: A pseudo-tree is a rooted spanning tree of the constraint graph augmented with backedges linking nodes to pseudo-parents and pseudo-children.Separators contain connected ancestors of an agent or its descendants.
  • Pseudo-tree: Pseudo-tree representations address k-ary cost functions by introducing a virtual variable that monitors scoped assignments and generates costs.
  • Factor graph: Factor graphs are bipartite graphs with variable and factor nodes, and algorithms over them directly handle k-ary cost functions.Factor-node control is delegated to an agent controlling a variable in the factor’s scope.

4.3 Algorithms

Classical DCOP algorithms differ in solution guarantees, synchronization, centralization, exploration process, and resource requirements. The survey organizes representative algorithms by these dimensions and summarizes their quality, runtime, memory, and communication characteristics.

  • Algorithm classes: Classical DCOP algorithms are classified as complete or incomplete according to whether they guarantee optimality or trade it for shorter execution times.They are also characterized by runtime, memory, and communication requirements.
  • Coordination model: Partial centralization can improve coordination performance, but it reduces privacy because a centralizing agent accesses other agents’ local subproblems.Fully decentralized algorithms preserve more privacy at the cost of larger communication effort.
  • Update model: Synchronous algorithms preserve consistency among agents’ local views, whereas asynchronous algorithms reduce idle time but provide no such consistency guarantee.Asynchronous agents can react quickly to processed messages, while synchronous execution may delay some actions.
  • Exploration process: Search-based algorithms explore possible assignments, while inference-based algorithms aggregate costs by exploiting constraint-graph structure.The taxonomy also distinguishes classical algorithms according to their resolution process.
  • Complete algorithms: SyncBB is complete and synchronous, performs O(d^n) operations, and may communicate with non-neighboring agents under its complete agent ordering.Its largest message has size O(n), and each agent requires O(n) memory.
  • Complete algorithms: ADOPT is complete and asynchronous, performs O(d^n) operations in a degenerate pseudo-tree, uses O(n + ld) memory per agent, and communicates only with neighbors.It maintains lower and upper subtree-cost bounds to guide best-first exploration and prune provably sub-optimal partial assignments.
  • Complete algorithms: ConcFB runs multiple parallel AFB searches concurrently, using forward bounding and dynamic splitting to identify and prune promising or unpromising subspaces.Its runtime, memory, and communication characteristics are identical to AFB because it runs parallel AFB versions concurrently.
  • Complete algorithms: DPOP is complete, synchronous, and inference-based, using UTIL and VALUE propagation over a DFS pseudo-tree; each agent performs O(dw*) operations.It sends O(n) messages and requires O(dw*) memory per agent.

4.4 Tradeoffs Between the Various DCOP Algorithms

DCOP algorithm choice depends on the application's optimality, memory, communication, and privacy requirements. The survey therefore recommends different complete or incomplete algorithms according to these characteristics.

  • Application suitability depends on matching an algorithm's characteristics to the application's requirements.The survey frames algorithm selection around the properties that matter in each application.
  • COMPLETE ALGORITHMS: Complete algorithms are required when the application demands optimality.The recommendation framework first separates algorithms according to whether optimality is mandatory.
  • COMPLETE ALGORITHMS: With ample memory and a preference for few large messages, inference-based algorithms are preferred because search-based methods generally perform redundant communication.Examples include DPOP and its extensions versus SyncBB, AFB, ADOPT, ConcFB, and OptAPO.
  • COMPLETE ALGORITHMS: With limited memory, search-based algorithms are preferred, except when the problem has small induced width, such as an acyclic constraint graph.The survey identifies small memory requirements as the main reason to choose search-based methods in this setting.
  • INCOMPLETE ALGORITHMS: When a solution-quality guarantee is required from an incomplete algorithm, Bounded Max-Sum, region-optimal algorithms, DUCT, or D-Gibbs can be selected.Their guarantees can be parameterized through graph edge removal, region size or hops, or sampling iterations, depending on the desired bound.

4.5 Notable Variant: Asymmetric DCOPs

Asymmetric DCOPs model problems in which agents incur different costs for the same constraint assignment. The survey describes classical-DCOP reformulations and specialized algorithms for coordinating these agent-specific costs.

  • Asymmetric DCOPs represent problems where agents participating in one cost function may incur different costs for the same assignment.Classical DCOPs require all agents controlling variables in that cost function to incur the same cost.
  • An Asymmetric DCOP extends the DCOP tuple with agent-specific cost functions, allowing each participating agent's incurred cost to differ.The function definition maps assignments together with the relevant agent to a nonnegative cost or the disallowed marker ⊥.
  • The objective of an Asymmetric DCOP differs from the classical objective because each participating agent evaluates its own cost from a complete assignment.The paper defines each agent's incurred cost for a cost function before specifying the asymmetric solution objective.
  • RELATION TO CLASSICAL DCOPS: PEAV can encode asymmetric costs through neighboring agents' mirror variables and equality constraints, but this may substantially increase the number of DCOP variables.The reformulation also does not make most existing incomplete classical algorithms effective on these problems.
  • RELATION TO CLASSICAL DCOPS: Existing incomplete classical algorithms may converge to a locally optimal hard-constraint-satisfying solution because they cannot distinguish among different feasible solutions after PEAV reformulation.This motivates designing algorithms specialized for Asymmetric DCOPs.
  • Specialized Asymmetric DCOP algorithms adapt classical search or local-search methods while coordinating the aggregation of agents' individual costs.The survey identifies one-phase and two-phase aggregation strategies and describes complete and incomplete adaptations including SyncABB, ATWB, ACLS, and MCS-MGM.
  • MCS-MGM has agents exchange current values and then send each side's cost to neighboring participants so total constraint costs can be calculated.Each agent adds the two sides of a cost function before calculating its local improvement information.

4.6 Notable Variant: Multi-Objective DCOPs

Multi-Objective DCOPs extend DCOPs to optimize multiple potentially conflicting objectives, typically through Pareto-based solution concepts. The survey classifies their algorithms as complete or incomplete and describes representative methods and complexity trade-offs.

  • Definition: Multi-Objective DCOPs combine DCOPs with multi-objective optimization, where decisions must accommodate potentially conflicting objectives.
  • Definition: A solution is Pareto optimal when no other solution improves at least one objective without worsening another.
  • Definition: The Pareto front contains the cost vectors of all Pareto-optimal solutions, and solving a MO-DCOP is equivalent to finding this set.
  • Definition: Because Pareto fronts can be exponentially large, algorithms may return weakly Pareto-optimal or otherwise practical compromise solutions instead of the complete front.A utopia point independently minimizes each objective, but it is generally unattainable.
  • Algorithms: MO-DCOP algorithms are classified as complete or incomplete according to whether they find all Pareto-optimal solutions or only a subset.B-MOMS uses bounding, multi-objective Max-Sum, and value propagation; its worst-case runtime matches Max-Sum, with O(pdn) message size and memory.
  • Algorithms: Complete methods include MO-SBB and a pseudo-tree-based extension of ADOPT, while incomplete methods include B-MOMS, DP-AOF, and DIPLS.The pseudo-tree-based algorithm has ADOPT-equivalent worst-case runtime and communication, but vector combinations can grow exponentially.

5. Dynamic DCOPs

Dynamic DCOPs model changing multi-agent problems as sequences of DCOPs and require agents to adapt efficiently as environments evolve. The survey emphasizes self-stabilization, incremental recomputation, and variants handling commitments and changing factors.

  • Definition: A Dynamic DCOP is a sequence of classical DCOPs, with agents solving the current DCOP optimally while remaining unaware of future changes.
  • Definition: Dynamic environments motivate stability and self-stabilization, requiring convergence after changes and closure while the environment remains unchanged.Convergence starts from the prior assignment and closure prevents further assignment changes absent environmental changes.
  • Complexity: 75. Solving D-DCOPs is NP-hard because each DCOP in the sequence must be solved independently.
  • Complete Algorithms: S-DPOP extends DPOP with self-stabilizing pseudo-tree, UTIL, and VALUE propagation phases for dynamic environments.
  • Complete Algorithms: S-DPOP retains DPOP’s worst-case runtime, memory, and communication requirements and stabilizes after at most τ UTIL messages and k VALUE messages.
  • Complete Algorithms: Incremental any-space ADOPT variants recompute bounds only for affected agents and can use additional memory to accelerate solving.Their worst-case runtime and communication per time step match ADOPT.
  • Notable Variants: Other variants address changing factors or commitments: FMS recomputes only changed factors, while RS-DPOP models hard and soft deadlines with stability penalties.RS-DPOP has the same order complexity as S-DPOP.

6. Probabilistic DCOPs

Probabilistic DCOPs extend DCOPs to stochastic environments by representing uncertain outcomes with random variables and evaluating aggregated costs through probability-based criteria. The survey describes their formulation, uncertainty-handling mechanisms, solution algorithms, and computational challenges.

  • P-DCOPs address stochastic environments where exogenous events can influence agents’ action outcomes, such as weather or malfunctioning devices.
  • A P-DCOP uses cost functions over decision and random variables, with each decision assignment producing a probability distribution.Random variables are not controlled by agents, and their possible events have associated probability distributions.
  • Evaluation functions summarize uncertain aggregated costs, while utility functions rank outcomes according to application-specific preferences.Expectation is one possible evaluation function, and utility is generally non-decreasing when lower cost corresponds to higher utility.
  • In a P-DCOP, each local function returns a random variable, while the global aggregate is formed from the individual distributions, commonly through convolution.The aggregated random variable represents the uncertain sum of local costs, paralleling utility summation in classical DCOPs.
  • First-order stochastic dominance ranks lotteries when one distribution is preferred regardless of the decision maker’s weakly increasing utility function.The survey also notes minimax regret for settings where outcome probabilities are unknown or difficult to estimate.
  • Algorithms: BE-Rebid-2 coordinates pairs of agents, but increasing the number of agents executing a joint action can decrease solution quality through the team uncertainty penalty.Its worst-case runtime and communication requirements match those of MGM.
  • Algorithms: Heist models each uncertain cost function as a multi-armed bandit and selects joint actions using estimated Upper Confidence Bounds over a finite horizon.Its worst-case runtime is O(ℓTdl), memory is O(dl), and message count is O(ℓTl), with message size O(Td).
  • Algorithms: ICG-Max-Sum has worst-case runtime O(ℓ|I|dl), dominated by a master problem exponential in cost-function scope variables for each belief and iteration.

7. Quantified DCOPs

Quantified DCOPs extend DCOPs with existentially and universally quantified variables, requiring solutions to remain valid across universally quantified assignments. Their rigid quantifier ordering motivates specialized pseudo-tree-based algorithms rather than direct use of classical DCOP methods.

  • QDCOPs adapt quantified constraint models to DCOPs, associating each variable with either an existential or universal quantifier.
  • Universally quantified variables are not coordinated or assigned, because the solution must hold for every value in their domains; existential variables receive one domain value.
  • QDCOPs impose a rigid variable order reflecting quantifier evaluation, so classical DCOP algorithms cannot be applied directly.Specialized algorithms use DFS pseudo-trees, which may be reshaped with null edges to preserve quantifier order.
  • Resolution methods: Complete QDCOP algorithms treat universally quantified variables as adversarial virtual agents minimizing the overall objective.
  • Resolution methods: Min-max ADOPT extends ADOPT with asynchronous search and VALUE/COST message propagation for QDCOP assignments and costs.
  • Resolution methods: Alpha-beta ADOPT extends Min-max ADOPT by using alpha-beta pruning, with alpha and beta representing lower and upper cost bounds.
  • Resolution methods: Bi-threshold ADOPT extends ADOPT by maintaining two backtracking thresholds instead of one, analogous to alpha and beta bounds.

8. DCOP Applications

DCOPs map naturally to decentralized multi-agent applications because agents can coordinate distributed decisions while optimizing shared objectives. The survey covers emergency response, networking, recommendation, scheduling, and resource-management applications.

  • DCOP applications span many MAS domains because the model captures core multi-agent characteristics and supports domain-independent algorithms.The survey organizes applications according to its DCOP classification.
  • Disaster management: Disaster-management applications use decentralized DCOP coordination on low-powered mobile devices with limited bandwidth.
  • Disaster management: Disaster evacuation models coordinate evacuee groups toward available shelters while accounting for shelter-capacity constraints.
  • Disaster management: CFST models ambulance and fire-brigade coalitions through task-location variables, reachability constraints, deadlines, and shared assignments.
  • Disaster management: The law-enforcement variant adds dynamically revealed tasks and allows agents to interrupt current tasks at penalties proportional to interrupted-task importance.
  • Networking: Cooperative channel-assignment DCOPs configure neighboring access points to reduce interference across simultaneous wireless transmissions.Dynamic spectrum-allocation variants address time-varying interference sources that are periodically sampled and measured.
  • Recommendation systems: Group-recommendation DCOPs combine individual user preferences with recommender-agent constraints to find compatible travel packages for groups.
  • Scheduling: Distributed meeting scheduling represents events, required resources, durations, and time-dependent resource costs while avoiding scheduling conflicts.One formulation treats events as decision variables assigned to feasible time slots.

8.5 Sensor Network Problems

Sensor-network and service-oriented applications use DCOPs to coordinate constrained devices, mobile sensing, wireless connectivity, and distributed resource placement. The formulations encode movement, scheduling, coverage, interference, energy, and deployment constraints.

  • Sensor networks: Sensor networks combine many autonomous nodes with limited communication range and battery life across environmental, military, and tracking applications.
  • Sensor networks: Target-tracking DCOPs model sensors detecting moving targets, including weighted graph-coloring formulations that minimize violated constraints and energy loss.Shared-region weights represent the importance of overlap between sensor coverage areas.
  • Sensor networks: Hierarchical DCOPs scale target-tracking problems by solving local regions separately and combining shared variables and constraints at higher levels.
  • Sensor networks: Robotic network formulations let robot agents choose valid movements that optimize wireless-link power loss or gain without changing network topology.
  • Sensor networks: Mobile Sensor Team formulations model positions over discrete time and minimize remaining target-coverage requirements based on agents’ joint credibility.
  • Sensor networks: DCOP-based sensor-sleep scheduling enforces neighbor exclusion and prevents consecutive activation while minimizing network delay.Energy-harvesting variants maximize event-detection probability while maintaining energy-neutral, indefinite operation.
  • Service-oriented computing: Service-oriented server-allocation problems address distributed providers, clients, and quality-of-service requirements across networked middleware.
  • Service-oriented computing: Application Component Placement assigns application components to servers under processing, communication, storage, bandwidth, and single-server constraints.The objective is to maximize server-component utilities.

8.7 Smart Grid and Smart Homes Problems

DCOPs model decentralized coordination problems across smart grids, buildings, homes, supply chains, and power networks. These formulations represent device, generator, network, prosumer, or market decisions while retaining domain constraints.

  • Power Systems: Smart-grid DCOP applications address generation, consumption, network restoration, islanding, and direct energy trading under distributed control.Applications include economic dispatch, power-supply restoration, microgrid islanding, and prosumer energy trading.
  • Power Systems: Economic dispatch coordinates generator settings to meet loads at minimum cost while satisfying physical power-network constraints.A planning-horizon extension also captures transmission-line, load, and generator restrictions across sequences of set-points over time.
  • Power Systems: Restoration and islanding formulations assign network-node variables and constraints to agents, representing power flows, conservation, and feasible generator-load clusters.Restoration models use load and direction variables, with acyclicity and Kirchhoff flow-conservation constraints.
  • Smart Buildings and Homes: Smart-building and smart-home formulations coordinate devices or households without centralized authority, targeting desired environments, lower energy peaks, and reduced bills.The Smart Environment Configuration Problem represents each device with an agent controlling a variable for its possible actions.
  • Supply Chains: Supply-chain DCOPs determine participants, exchanges, partners, and terms using Task Dependency Networks, including dynamic entry, departure, and changing market conditions.Dynamic models accommodate changes in goods prices, production capacity, and consumer requirements.

9. Analyses and Perspectives on DCOPs

The survey compares DCOP variants by agent and environment characteristics, cooperation, and computational complexity. It identifies unresolved challenges in realistic coordination, algorithms, languages, and simulation.

  • DCOP Model Variants: Classical DCOPs support cooperative teams pursuing one goal in static, deterministic, fully observable environments, whereas extensions address privacy, multiple objectives, dynamics, uncertainty, or adversaries.Algorithm selection depends on the structural properties of the application and the problem designer’s requirements.
  • DCOP Model Variants: Asymmetric DCOPs represent different agent costs for joint actions, while Multi-Objective DCOPs optimize multiple objectives that cannot be expressed by one function.These variants are useful for privacy-sensitive resource allocation and applications such as disaster management.
  • DCOP Model Variants: Probabilistic DCOPs handle exogenous uncertain events, and Quantified DCOPs model adversarial choices or planning under uncertainty.Sampling and minimax, maximin, or regret-based methods are discussed for uncertain costs.
  • Open Challenges: Combined uncertain and dynamic environments remain underexplored, and no coordination strategy has yet been studied for rapidly evolving situations requiring different approaches.The survey also calls for incomplete, anytime, and any-space methods to handle large DCOPs under resource limits.
  • Complexity: NP-hard optimal solving applies to classical, Asymmetric, Multi-Objective, and Dynamic DCOPs, while Probabilistic and Quantified DCOPs are PSPACE-hard.The survey summarizes these model complexities in Table 6.
  • Open Challenges: Most nonclassical formalisms lack mature algorithmic and theoretical foundations, while a general DCOP modeling language and high-fidelity dynamic or probabilistic simulators remain needed.The survey proposes interdisciplinary links to game theory and decision theory as one route for advancing the field.

10. Conclusions

DCOPs have expanded from a popular formalism for distributed reasoning into extensions supporting complex, real-time, and uncertain environments. The survey categorizes these advances, connects them to applications, and identifies directions for improving coordination, scalability, modeling, and evaluation.

  • Conclusions: DCOP extensions address limitations involving complex, real-time, dynamic, and uncertain environments, as well as differing levels of agent cooperation.The classical model does not capture all such environmental characteristics.
  • Conclusions: The survey categorizes DCOP advances by agent characteristics, environment properties, and teamwork, linking each framework with algorithms and naturally modeled application domains.It also analyzes recent AAMAS research within the DCOP framework.
  • Conclusions: Future work concerns agent coordination, algorithm scalability, modeling languages, and evaluation criteria for DCOP models and algorithms.These directions are identified as part of the survey’s concluding synthesis.
Loading 1602.06347v4…