Distributed constraint optimization: Difference between revisions

Revision as of 23:49, 2 March 2006

Revision as of 00:31, 3 March 2006

Line 3:

==Definition==

A DCOP can be defined as a [[Tuple|tuple]] <math>\langle A, V, \mathcal{D}, Ff, \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>;

*<math>\mathcal{D}</math> is a set of domains, <math>\{D_1, D_2, \ldots, D_{|V|}\}</math>, where each <math>D \in \mathcal{D}</math> is a [[Finite set|finite set]] containing the values to which its associated variable my be assigned.;

*<math>Ff</math> is a set offunction <math>|V|^2</math>f cost: functions, one for each pair of the variables, such that <math>f_\mathcal{ijP} : D_i (\times D_jmathcal{D}) \rightarrow \mathbb{N} \cup \infty</math>. (where In"<math>\mathcal{P}(\mathcal{D})</math>" otherdenotes words,the for[[power all pairsset]] of variables there exists a cost function<math>\mathcal{D}</math>) that maps every possible value assignmentgrouping of thevariable variablesassignments to a cost. TheseThis functionsfunction can also be thought of as binarydefining constraints between variables.;

*<math>\alpha</math> is a function <math>\alpha : V \rightarrow A</math> mapping variables to their associated agent. <math>\alpha(v_i) \mapsto a_j</math> implies that it is agent <math>a_j</math>'s responsibility to assign the value of variable <math>v_i</math>. Note that it is not necessarily true that <math>\alpha</math> is either an [[Injective function|injection]] or [[surjection]].; and

*<math>\sigma</math> is aan function[[operator]] <math>\sigma : Ff \rightarrow \mathbb{N} \cup \infty</math> 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 <math>\sigma(Ff)</math> for a given assignment of the variables.

==Example==

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:

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

*<math>V=\{v_1, v_2, \ldots, v_6\}</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>.