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

Consider 3-coloring a graph; 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 3 (there is one ___domain value for each possible color). Given the graph  , the following would be its representation as a DCOP for solving the 3-coloring problem:

• ${\displaystyle A=\{a_{1},a_{2},\ldots ,a_{6}\}}$ 
• ${\displaystyle V=\{v_{1},v_{2},\ldots ,v_{6}\}}$ 
• ${\displaystyle {\mathcal {D}}=\{D_{1},D_{2},\ldots ,D_{6}\}}$ , where each ${\displaystyle D\in {\mathcal {D}}=\{{\mbox{Red}},{\mbox{Green}},{\mbox{Blue}}\}}$ 
• ${\displaystyle f}$  returns 0 in all but the following cases:
  • ${\displaystyle f(D_{1}=D_{2})=\infty }$  (i.e. whenever ${\displaystyle D_{1}}$  equals the value of ${\displaystyle D_{2}}$ , the cost is infinite)
  • ${\displaystyle f(D_{1}=D_{5})=\infty }$ 
  • ${\displaystyle f(D_{5}=D_{2})=\infty }$ 
  • ${\displaystyle f(D_{2}=D_{3})=\infty }$ 
  • ${\displaystyle f(D_{3}=D_{4})=\infty }$ 
  • ${\displaystyle f(D_{4}=D_{5})=\infty }$ 
  • ${\displaystyle f(D_{4}=D_{6})=\infty }$ 
• ${\displaystyle \sigma =\sum _{{\mathcal {P}}({\mathcal {D}})}f}$ 

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

Notes

1. "${\displaystyle {\mathcal {P}}({\mathcal {V}})}$ " denotes the power set of ${\displaystyle V}$ 
2. "${\displaystyle \times }$ " and "${\displaystyle \prod }$ " denote the Cartesian product.