Distributed constraint optimization: Difference between revisions

Revision as of 00:31, 3 March 2006

Revision as of 13:50, 27 April 2007

Line 1:

'''Distributed constraint optimization''' (DCOP) is the [[Distributed computing|distributed]] analogue to [[Constraint optimization|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.

==DefinitionDefinitions==

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

Line 7 ⟶ 8:

*<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>f</math> is function <ref>"<math>f : \mathcal{P}(\mathcal{DV})</math>" \rightarrowdenotes \mathbb{N}the \cup[[power set]] of <math>V</math></ref><ref>"<math>\inftytimes</math>" (whereand "<math>\mathcal{P}(\mathcal{D})prod</math>" denotesdenote the [[powerCartesian setproduct]] of .</ref><center><math>f : \bigcup_{S \in \mathcal{DP}(V)}\prod_{v_i \in S} \left( \{v_i\} \times D_i \right) \rightarrow \mathbb{N} \cup \{\infty\}</math>) </center>that maps every possible grouping of variable assignmentsassignment to a cost. This function can also be thought of as defining 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 an [[operator]] <math>\sigma : f \rightarrow \mathbb{N} \cup \infty</math> that aggregates all of the individual <math>f</math> costs for all possible variable assignments. This is usually accomplished through summation: of<math>\sigma(f) the\mapsto costs\sum_{s \in \bigcup_{S \in \mathcal{P}(V)}\prod_{v_i \in S} \left( \{v_i\} \times D_i \right)} f(s)</math>.

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(f)</math> for a given assignment of the variables.

Line 29 ⟶ 30:

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

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

==Notes==

<references/>