Distributed constraint optimization: Difference between revisions

Revision as of 13:50, 27 April 2007

Revision as of 13:57, 27 April 2007

Line 3:

==Definitions==

===DCOP===

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

Line 10 ⟶ 12:

*<math>f</math> is function<ref>"<math>\mathcal{P}(\mathcal{V})</math>" denotes the [[power set]] of <math>V</math></ref><ref>"<math>\times</math>" and "<math>\prod</math>" denote the [[Cartesian product]].</ref><center><math>f : \bigcup_{S \in \mathcal{P}(V)}\prod_{v_i \in S} \left( \{v_i\} \times D_i \right) \rightarrow \mathbb{N} \cup \{\infty\}</math></center>that maps every possible variable assignment 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]] that aggregates all of the individual <math>f</math> costs for all possible variable assignments. This is usually accomplished through summation: <center><math>\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)</math>.</center>

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.

===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.

==Example==