Distributed Constraint Optimization Problems(DCOPs)(Fioretto et al., 2018; Modi et al., 2004; Petcu & Faltings, 2005) can be thought as a variant of Constraint Satisfaction Problems(CSPs). In real-world problems(like sensor networks), it’s impossible to get an assignment to all variables that satisfy all the constraints. One way is we model the problem as Max Constraint Satisfaction Problems(MAX-CSPs). In other words, we figure out an assignment to all variables that satisfy a maximum number of constraints. Constraint Optimization Problems(COPs) are another way to draw up the problem. It relaxes hard constraints to soft constraints and its objective is to minimize costs. The Distributed Constraint Satisfaction(DisCSP) paradigm (Yokoo, 2012) has been proposed as a way to model and reason about the interactions between agents’ local decisions. Likewise, DCOP is a distributed version of COP meaning the problem is modeled and resolved in a decentralized manner. In DCOP variables are monitored by agents, thus a communication model is needed and it follows agents’ local knowledge. Distributed models are faster(parallelism) and robust(no single point of failure, no single network bottleneck) by their distribution nature. They also naturally map to multi-agent systems and maintain more confidential information.
In a multi-agent system(MAS), an agent is described as an entity that behaves autonomously in the pursuit of goals. An agent is autonomous, interactive, reactive, and proactive.
DCOP algorithms are a class of distributed cooperative multi-agent algorithms in which several autonomous agents coordinate their decisions to achieve a shared goal while accounting for personal preferences.
Mathematically, a DCOP is composed by the following entities:
- \(\mathcal{A}=\{a_1,...,a_p\}\): The set of autonomous agents participating in the problem
- \(\mathcal{X}=\{x_1,...,x_n\}\): The set of variables in the problem.
- \(\mathcal{D}=\{D_1,...,D_n\}\): The domains for the variables in X, where \(D_i\) represents the set of possible values that the variable \(x_i\) may be assigned
- \(\mathcal{C}=\{c_1,...,c_e\}\): The set of problem constraints. Each constraint \(c_i\) is a function that involves (multiple) variable(s) from X and associates a cost for each combination of their value assignments.
- \(\alpha:\mathcal{X}\rightarrowtail \mathcal{A}\): A mapping that associates variables to agents, expressing which agent controls which variables
DCOP has wide applications in the real world. (Fioretto et al., 2017) describes a DCOP model with MGM(Maheswaran et al., 2004) algorithm to solve Demand-side management(DSM) smart device schuduling problem.
In genral, DCOP can be represented as constraint graph where each vertices are variables and edges are constarints.
DCOP algorithms can be classified as being either complete or incomplete, based on whether they can guarantee the optimal solution or they trade optimality for shorter execution times, producing near-optimal solutions. We evaluate DCOP algorithms by following metrics: agent complexity, network loads, message size, anytime( An algorithm is said anytime if it can return a valid solution even if the DCOP agents are interrupted at any time before the algorithm terminates), quality guarantees and execution time vs. solution quality.
A synchronous algorithm requires a systematic process divided into steps and each agent waits for particular messages before acting. As a result, it gets a consistent view of the search process and more idle time. On the other side, the asynchronous algorithm makes decisions based on agents’ local state and agents’ actions are not dependent on the sequence of received messages. It minimizes idle time but has no guarantees on the validity of local views.
The computational complexity of DCOP as defined above is NP-hard(3-colorability of a graph is know to be NP-complete(Papadimitriou, 1994)).
(Petcu & Faltings, 2005) proposes a complete method for dcop called DPOP(distributed pseudo-tree optimization procedure) algorithm based on dynmaic programming and pseudotree.
A pseudo-tree arrangement of a graph G is a rooted tree with the same vertices as G and the property that adjacent vertices from the original graph fall in the same branch of the tree. An alternative pseudo-tree definition: A spanning tree of the constraint graph such that no two nodes in sibling subtrees share a constraint in the constraint graph.
The main idea with their use in search, is that due to the relative independence of nodes lying in different branches of the pseudotree, it is possible to perform search in parallel on these independent branches. A DFS(depth-first search) tree is also a pseudotree(although the inverse does not always hold). A pseudotree consists of tree edges, shown as solid lines, and back edges, shown as dashed lines, that are not part of the spanning tree. We call a path in the graph that is entirely made of tree edges, a tree-path. A tree-path associated with a back-edge is the tree-path connecting the two nodes involved in the back-edge. For each back-edge, the higher node involved in that back-edge is called the back-edge handler. DPOP runs three phases.
- It builds a depth-first search(DFS) tree that overlays the constraint network. This pseudotree, made of parent links and pseudo-parent links (when loops appear in the constraint graph) is used by agents owning variables to interact during the next phases.
- Once the DFS tree is build, cost messages are sent by the leafs and propagate from children to parent up to the root. A cost message, assessed by joining all the messages received from children, is a relation associating a cost to every possible assignment of the variables in the agent’s separator.
- Once the root has received the cost messages from its children, it assesses the aggregated costs of the whole problem and then it decides the best assignment for its variables.
Finally, it broadcasts this assignment in a value message to its children, who assess their best assignments and send them down the tree.
(Hirayama & Yokoo, 1997) introduces a Synchronous Branch and Bound(SBB) algorithm for for solving Distributed Maximal Constraint Satisfaction Problems (DM-CSPs), which belong to an important class of Distributed Partial Constraint Satisfaction Problem(DPCSP)(Yokoo et al., 1992).
(Farinelli et al., 2008) shows a novel representation of the dcop as a cyclic bipartite factor graph composed of variable and function nodes and use an extension of the max-sum algorithm to generate approximate solutions to this global optimisation problem through decentralised local message passing between interacting agents.
A factor graph is an undirected bipartite graph in which vertices represent variables and constraints (called factors), and an edge exists between a variable and a constraint if the variable is in the scope of the constraint.
Messages will flow from factors to variables, and vice versa and are only associating costs to values of the recipient. A factor \(f_m\) assesses the message \(R_{m\rightarrow n}\) to variable \(x_n\) by adding its own cost \(c_m\) to the costs received from all the variables connected to it, except \(x_n\), and choosing the best cost for a value of \(x_n\) when several alternatives exists for obtaining this value. In return, a variable \(x_n\) assesses a message \(Q_{n\rightarrow m}\) to factor \(f_m\) by only adding messages received from connected factors except the factor \(f_m\). When a factor or a variable computes twice the same message for the same recipient, it stops propagation. The process ends at convergence or when a time limit is reached.
A forum for discussion on DCOP algorithms and applications has been held at the Optimization in Multi-Agent Systems (OptMAS) workshop since 2010 at the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
References
-
Distributed Constraint Optimization Problems and Applications: A Survey
Fioretto, Ferdinando, Pontelli, Enrico, and Yeoh, William
Journal of Artificial Intelligence Research Mar 2018
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.
-
ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees
Modi, Pragnesh Jay, Shen, Wei-Min, Tambe, Milind, and Yokoo, Makoto
Artificial Intelligence Mar 2004
The Distributed Constraint Optimization Problem (DCOP) is able to model a wide variety of distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while allowing agents to operate asynchronously. We show how this failure can be remedied by allowing agents to make local decisions based on conservative cost estimates rather than relying on global certainty as previous approaches have done. This novel approach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed to find the globally optimal solution while allowing agents to execute asynchronously and in parallel. Detailed experimental results show that on benchmark problems Adopt obtains speedups of several orders of magnitude over other approaches. Adopt can also perform bounded-error approximation – it has the ability to quickly find approximate solutions and, unlike heuristic search methods, still maintain a theoretical guarantee on solution quality.
-
A scalable method for multiagent constraint optimization
Petcu, Adrian, and Faltings, Boi
In In: International Joint Conference on Artificial In℡ligence. Volume Mar 2005
We present in this paper a new complete method for distributed constraint optimization. This is a utility-propagation method, inspired by the sum-product algorithm [Kschischang et al., 2001]. The original algorithm requires fixed message sizes, linear memory and linear time in the size of the problem. However, it is correct only for tree-shaped constraint networks. In this paper, we show how to extend that algorithm to arbitrary topologies using a pseudotree arrangement of the problem graph. We compare our algorithm with standard backtracking algorithms, and present experimental results. For some problem types we report orders of magnitude less messages, and even the ability to deal with arbitrary large problems. Our algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well.
-
Distributed constraint satisfaction: foundations of cooperation in multi-agent systems
Yokoo, Makoto
In In: International Joint Conference on Artificial In℡ligence. Volume Mar 2012
-
A multiagent system approach to scheduling devices in smart homes: 31st AAAI Conference on Artificial Intelligence, AAAI 2017
Fioretto, Ferdinando, Yeoh, William, and Pontelli, Enrico
WS-17-01 Mar 2017
Demand-side management (DSM) in the smart grid allows customers to make autonomous decisions on their energy consumption, helping energy providers to reduce the peaks in load demand. The automated scheduling of smart devices in residential and commercial buildings plays a key role in DSM. Due to data privacy and user autonomy, such an approach is best implemented through distributed multi-agent systems. This paper makes the following contributions: (i) It introduces the Smart Home Device Scheduling (SHDS) problem, which formalizes the device scheduling and coordination problem across multiple smart homes as a multi- agent system; (ii) It describes a mapping of this problem to a distributed constraint optimization problem; (ill) It proposes a distributed algorithm for the SHDS problem; and (iv) It presents empirical results from a physically distributed system of Raspberry Pis, each capable of controlling smart devices through hardware interfaces.
-
Distributed Algorithms for DCOP: A Graphical-Game-Based Approach
Maheswaran, Rajiv T., Pearce, Jonathan P., and Tambe, Milind
In In PDCS Mar 2004
This paper addresses the application of distributed constraint optimization problems (DCOPs) to large-scale dynamic environments. We introduce a decomposition of DCOP into a graphical game and investigate the evolution of various stochastic and deterministic algorithms. We also develop techniques that allow for coordinated negotiation while maintaining distributed control of variables. We prove monotonicity properties of certain approaches and detail arguments about equilibrium sets that offer insight into the tradeoffs involved in leveraging efficiency and solution quality. The algorithms and ideas were tested and illustrated on several graph coloring domains.
-
Computational Complexity
Papadimitriou, Christos H
In In PDCS Mar 1994
-
DPOP: A Scalable Method for Multiagent Constraint Optimization
Petcu, Adrian, and Faltings, Boi
In Jan 2005
We present in this paper a new, complete method for distributed constraint optimization, based on dynamic programming. It is a utility propagation method, inspired by the sum-product algorithm, which is correct only for tree-shaped constraint net- works. In this paper, we show how to extend that algorithm to arbitrary topologies using a pseudotree arrangement of the problem graph. Our algorithm requires a linear number of messages, whose max- imal size depends on the induced width along the particular pseudotree chosen. We compare our algorithm with backtracking algo- rithms, and present experimental results. For some problem types we report orders of magnitude fewer messages, and the ability to deal with arbitrarily large problems. Our algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well.
-
Distributed partial constraint satisfaction problem
Hirayama, Katsutoshi, and Yokoo, Makoto
In Principles and Practice of Constraint Programming Jan 1997
Abstract. Many problems in multi-agent systems can be described as distributed Constraint Satisfaction Problems (distributed CSPs), where the goal is to nd a set of assignments to variables that satis es all constraints among agents. However, when real problems are formalized as distributed CSPs, they are often over-constrained and have no solution that satis es all constraints. This paper provides the Distributed Partial Constraint Satisfaction Problem (DPCSP) as a new framework for dealing with over-constrained situations. We also present new algorithms for solving Distributed Maximal Constraint Satisfaction Problems (DM-CSPs), which belong to an important class of DPCSP. The algorithms are called the Synchronous Branch and Bound (SBB) and the Iterative Distributed Breakout (IDB). Both algorithms were tested on hard classes of over-constrained random binary distributed CSPs. The results can be summarized as SBB is preferable when we are mainly concerned with the optimality ofasolution, while IDB is preferable when we want to get a nearly optimal solution quickly. 1
-
Distributed constraint satisfaction for formalizing distributed problem solving
Yokoo, M., Ishida, T., Durfee, E.H., and Kuwabara, K.
In [1992] Proceedings of the 12th International Conference on Distributed Computing Systems Jun 1992
Viewing cooperative distributed problem solving (CDPS) as distributed constraint satisfaction provides a useful formalism for characterizing CDPS techniques. This formalism and algorithms for solving distributed constraint satisfaction problems (DCSPs) are compared. A technique called asynchronous backtracking that allows agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques used in constraint satisfaction problems, is presented. Experimental results show that solving DCSPs in a distributed fashion is worthwhile when the problems solved by individual agents are loosely coupled.\textless\textgreater
-
Decentralised coordination of low-power embedded devices using the max-sum algorithm
Farinelli, A., Rogers, A., Petcu, A., and Jennings, N. R.
In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 Jun 1992
This paper considers the problem of performing decentralised co-ordination of low-power embedded devices (as is required within many environmental sensing and surveillance applications). Specifically, we address the generic problem of maximising social welfare within a group of interacting agents. We propose a novel representation of the problem, as a cyclic bipartite factor graph, composed of variable and function nodes (representing the agents’ states and utilities respectively). We show that such representation allows us to use an extension of the max-sum algorithm to generate approximate solutions to this global optimisation problem through local decentralised message passing. We empirically evaluate this approach on a canonical coordination problem (graph colouring), and benchmark it against state of the art approximate and complete algorithms (DSA and DPOP). We show that our approach is robust to lossy communication, that it generates solutions closer to those of DPOP than DSA is able to, and that it does so with a communication cost (in terms of total messages size) that scales very well with the number of agents in the system (compared to the exponential increase of DPOP). Finally, we describe a hardware implementation of our algorithm operating on low-power Chipcon CC2431 System-on-Chip sensor nodes.