Distributed constraint optimization: Difference between revisions

Revision as of 13:57, 27 April 2007

Revision as of 14:08, 27 April 2007

Line 6:

===DCOP===

A '''DCOP''' can be defined as a [[Tuple|tuple]] <math>\langle A, V, \mathcal{D}, f, \alpha, \sigma \rangle</math>, where:

*<math>A</math> is a [[set]] of [[Intelligent agent|agents]];

*<math>V</math> is a set of variables, <math>\{v_1,v_2,\ldots,v_{|V|}\}</math>;

Line 18:

===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:<center><math>t : V \rightarrow (D \in \mathcal{D}) \cup \{\emptyset\}.</math></center> Note that a context is essentially a partial solution and need not contain values for <em>every</em> variable in the problem; therefore, <math>t(v_i) \mapsto \emptyset</math> implies that the agent <math>\alpha(v_i)</math> has not yet assigned a value to variable <math>v_i</math>. Given this representation, the "[[Domain_(mathematics)|___domain]]" (<i>i.e.</i>, the set of input values) of the function <code>f</code> 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>i.e.</i>, the <math>t</math> function) as an input to the <math>f</math> function.

==ExampleExamples==

===Graph Coloring===

Consider [[Graph coloring|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 [[Image:6n-graf.png|100px]], the following would be its representation as a DCOP for solving the 3-coloring problem:

The [[Graph coloring|graph coloring]] problem is as follows: given a [[Graph_(mathematics)|graph]] <math>G = \langle N, E \rangle</math> and a set of colors <math>C</math>, assign each [[Vertex_(graph_theory)|vertex]], <math>n\in N</math>, a color, <math>c\in C</math>, such that the number of adjacent vertices with the same color is minimized.

*<math>A=\{a_1, a_2, \ldots, a_6\}</math>

*<math>V=\{v_1, v_2, \ldots, v_6\}</math>

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]] <math>|C|</math> (there is one ___domain value for each possible color). For each vertex <math>n_i \in N</math>, create a variable in the DCOP <math>v_i \in V</math> with ___domain $D_i = C$. For each pair of adjacent vertices <math>\langle n_i, n_j \rangle \in E</math>, create a constraint of cost 1 if both of the associated variables are assigned the same color: <center><math>(\forall c \in C : f(\langle v_i, c \rangle, \langle v_j, c \rangle ) \mapsto 1).</math></center>The objective, then, is to minimize <math>\sigma(f)</math>.

*<math>\mathcal{D} = \{D_1, D_2, \ldots, D_6\}</math>, where each <math>D \in \mathcal{D} = \{\mbox{Red}, \mbox{Green}, \mbox{Blue}\}</math>

*<math>f</math> returns 0 in all but the following cases:

**<math>f(D_1 = D_2) = \infty</math> (<em>i.e.</em> whenever <math>D_1</math> equals the value of <math>D_2</math>, the cost is infinite)

**<math>f(D_1 = D_5) = \infty</math>

**<math>f(D_5 = D_2) = \infty</math>

**<math>f(D_2 = D_3) = \infty</math>

**<math>f(D_3 = D_4) = \infty</math>

**<math>f(D_4 = D_5) = \infty</math>

**<math>f(D_4 = D_6) = \infty</math>

*<math>\sigma = \sum_{\mathcal{P}(\mathcal{D})}f</math>

The objective, then, is to minimize <math>\sigma(f)</math>.

==Notes==