Distributed constraint optimization

Distributed constraint optimization (DCOP) is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is either minimized or maximized.

Definitions

DCOP

A DCOP can be defined as a tuple ${\displaystyle \langle A,V,{\mathcal {D}},f,\alpha ,\sigma \rangle }$ , where:

• ${\displaystyle A}$  is a set of agents;
• ${\displaystyle V}$  is a set of variables, ${\displaystyle \{v_{1},v_{2},\ldots ,v_{|V|}\}}$ ;
• ${\displaystyle {\mathcal {D}}}$  is a set of domains, ${\displaystyle \{D_{1},D_{2},\ldots ,D_{|V|}\}}$ , where each ${\displaystyle D\in {\mathcal {D}}}$  is a finite set containing the values to which its associated variable my be assigned;
• ${\displaystyle f}$  is function^[1][2]${\displaystyle f:\bigcup _{S\in {\mathcal {P}}(V)}\prod _{v_{i}\in S}\left(\{v_{i}\}\times D_{i}\right)\rightarrow \mathbb {N} \cup \{\infty \}}$ that maps every possible variable assignment to a cost. This function can also be thought of as defining constraints between variables;
• ${\displaystyle \alpha }$  is a function ${\displaystyle \alpha :V\rightarrow A}$  mapping variables to their associated agent. ${\displaystyle \alpha (v_{i})\mapsto a_{j}}$  implies that it is agent ${\displaystyle a_{j}}$ 's responsibility to assign the value of variable ${\displaystyle v_{i}}$ . Note that it is not necessarily true that ${\displaystyle \alpha }$  is either an injection or surjection; and
• ${\displaystyle \sigma }$  is an operator that aggregates all of the individual ${\displaystyle f}$  costs for all possible variable assignments. This is usually accomplished through summation:${\displaystyle \sigma (f)\mapsto \sum _{s\in \bigcup _{S\in {\mathcal {P}}(V)}\prod _{v_{i}\in S}\left(\{v_{i}\}\times D_{i}\right)}f(s)}$ .

The objective of a DCOP is to have each agent assign values to its associated variables in order to either minimize or maximize ${\displaystyle \sigma (f)}$  for a given assignment of the variables.

Context

A Context is a variable assignment for a DCOP. This can be thought of as a function mapping variables in the DCOP to their current values:

${\displaystyle t:V\rightarrow (D\in {\mathcal {D}})\cup \{\emptyset \}.}$ 

Note that a context is essentially a partial solution and need not contain values for every variable in the problem; therefore, ${\displaystyle t(v_{i})\mapsto \emptyset }$  implies that the agent ${\displaystyle \alpha (v_{i})}$  has not yet assigned a value to variable ${\displaystyle v_{i}}$ . Given this representation, the "___domain" (i.e., the set of input values) of the function f can be thought of as the set of all possible contexts for the DCOP. Therefore, in the remainder of this article we may use the notion of a context (i.e., the ${\displaystyle t}$  function) as an input to the ${\displaystyle f}$  function.

Example problems

Distributed Graph Coloring

The graph coloring problem is as follows: given a graph ${\displaystyle G=\langle N,E\rangle }$  and a set of colors ${\displaystyle C}$ , assign each vertex, ${\displaystyle n\in N}$ , a color, ${\displaystyle c\in C}$ , such that the number of adjacent vertices with the same color is minimized.

As a DCOP, there is one agent per vertex that is assigned to decide the associated color. Each agent has a single variable whose associated ___domain is of cardinality ${\displaystyle |C|}$  (there is one ___domain value for each possible color). For each vertex ${\displaystyle n_{i}\in N}$ , create a variable in the DCOP ${\displaystyle v_{i}\in V}$  with ___domain ${\displaystyle D_{i}=C}$ . For each pair of adjacent vertices ${\displaystyle \langle n_{i},n_{j}\rangle \in E}$ , create a constraint of cost 1 if both of the associated variables are assigned the same color:

${\displaystyle (\forall c\in C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}$ 

The objective, then, is to minimize ${\displaystyle \sigma (f)}$ .

Distributed Multiple Knapsack Problem

The Distributed Multiple- variant of the Knapsack problem is as follows: given a set of items of varying volume and a set of knapsacks of varying capacity, assign each item to a knapsack such that the amount of overflow is minimized. Let ${\displaystyle I}$  be the set of items, ${\displaystyle K}$  be the set of knapsacks, ${\displaystyle s:I\rightarrow \mathbb {N} }$  be a function mapping items to their volume, and ${\displaystyle c:K\rightarrow \mathbb {N} }$  be a function mapping knapsacks to their capacities.

To encode this problem as a DCOP, for each ${\displaystyle i\in I}$  create one variable ${\displaystyle v_{i}\in V}$  with associated ___domain ${\displaystyle D_{i}=K}$ . Then for all possible context ${\displaystyle t}$ :

${\displaystyle f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}}$ 

where ${\displaystyle r(t,k)}$  is a function such that

${\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}$ 

Algorithms

Algorithm Name	Year Introduced	Complexity	Correctness/ Completeness	Implementations
NCBB No-Commitment Branch and Bound[3]	2006	Memory: Polynomial (or any-space)	Proven	Reference Implementation: not publicly released DCOPolis ( GNU LGPL)
DPOP Distributed Pseudotree Optimization Procedure[4]	2004	Memory: Exponential	Proven	Reference Implementation: FRODO (free but proprietary) DCOPolis ( GNU LGPL)
OptAPO Asynchronous Partial Overlay[5]	2004		Proven, but proof of completeness has been called into question[6]	Reference Implementation: OptAPO DCOPolis ( GNU LGPL; In Development)
Adopt Asynchronous Backtracking[7]	2003	Memory: Polynomial	Proven	Reference Implementation: Adopt DCOPolis ( GNU LGPL)

Notes and references

1. "${\displaystyle {\mathcal {P}}({\mathcal {V}})}$ " denotes the power set of ${\displaystyle V}$ 
2. "${\displaystyle \times }$ " and "${\displaystyle \prod }$ " denote the Cartesian product.
3. Chechetka, Anton; Sycara, Katia (May), "No-Commitment Branch and Bound Search for Distributed Constraint Optimization" (PDF), Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1427–1429 {{citation}}: Check date values in: |date= and |year= / |date= mismatch (help)
4. Petcu, Adrian; Faltings, Boi (September), "A Distributed, Complete Method for Multi-Agent Constraint Optimization" (PDF), Proceedings of the Fifth International Workshop on Distributed Constraint Reasoning {{citation}}: Check date values in: |date= and |year= / |date= mismatch (help)
5. Mailler, Rober; Lesser, Victor (2004), "Solving Distributed Constraint Optimization Problems Using Cooperative Mediation" (PDF), Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, IEEE_Computer_Society, pp. 438–445
6. Grinshpoun, Tal; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007), "Termination Problem of the APO Algorithm" (PDF), Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning, pp. 117–124
7. Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), "An asynchronous complete method for distributed constraint optimization" (PDF), Proceedings of the second international joint conference on autonomous agents and multiagent systems, ACM Press, pp. 161–168