Distributed Constraint Optimization Problems and Applications: A Survey

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.

References in corpus (4)

• Asynchronous Forward Bounding for Distributed COPs
• Asymmetric Distributed Constraint Optimization Problems
• Completeness and Performance Of The APO Algorithm
• Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation

Cited by in corpus (8)

• A Graph-Based Modeling Abstraction for Optimization: Concepts and Implementation in Plasmo.jl
• Resilient robot teams: a review integrating decentralised control, change-detection, and learning
• Auction-based and Distributed Optimization Approaches for Scheduling Observations in Satellite Constellations with Exclusive Orbit Portions
• HS-CAI: A Hybrid DCOP Algorithm via Combining Search with Context-based Inference
• AsymDPOP: Complete Inference for Asymmetric Distributed Constraint Optimization Problems
• Recycled ADMM: Improve Privacy and Accuracy with Less Computation in Distributed Algorithms
• Differentially Private Multi-Agent Planning for Logistic-like Problems
• A Privacy-Preserving and Trustable Multi-agent Learning Framework