User:SyntaxPC/Distributed constraint optimization

From Wikipedia, the free encyclopedia

Distributed constraint optimization (DCOP) is the distributed analogue to constraint optimization.

[edit] Definition

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

$A$ is a set of agents;
$V$ is a set of variables, $\{v_1,v_2,\ldots,v_{|V|}\}$ ;
$\mathcal{D}$ is a set of domains, $\{D_1, D_2, \ldots, D_{|V|}\}$ , where each $D \in \mathcal{D}$ is a finite set containing the values to which its associated variable my be assigned;
$f$ is function $f : \mathcal{P}(\mathcal{D}) \rightarrow \mathbb{N} \cup \infty$ (where " $\mathcal{P}(\mathcal{D})$ " denotes the power set of $\mathcal{D}$ ) that maps every possible grouping of variable assignments to a cost. This function can also be thought of as defining constraints between variables;
$α$ is a function $\alpha : V \rightarrow A$ mapping variables to their associated agent. $\alpha(v_i) \mapsto a_j$ implies that it is agent $a j$ 's responsibility to assign the value of variable $v i$ . Note that it is not necessarily true that $α$ is either an injection or surjection; and
$σ$ is an operator $\sigma : f \rightarrow \mathbb{N} \cup \infty$ that aggregates all of the individual costs for all possible variable assignments. This is usually accomplished through summation of the costs.

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

[edit] 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:

$A=\{a_1, a_2, \ldots, a_6\}$
$V=\{v_1, v_2, \ldots, v_6\}$
$\mathcal{D} = \{D_1, D_2, \ldots, D_6\}$ , where each $D \in \mathcal{D} = \{\mbox{Red}, \mbox{Green}, \mbox{Blue}\}$
f returns 0 in all but the following cases:
- $f(D_1 = D_2) = \infty$ (i.e. whenever $D 1$ equals the value of $D 2$ , the cost is infinite)
- $f(D_1 = D_5) = \infty$
- $f(D_5 = D_2) = \infty$
- $f(D_2 = D_3) = \infty$
- $f(D_3 = D_4) = \infty$
- $f(D_4 = D_5) = \infty$
- $f(D_4 = D_6) = \infty$
$\sigma = \sum_{\mathcal{P}(\mathcal{D})}f$