Order-of-magnitude preferences (OMPs)

Although an aDCSP can capture the hard constraints over decisions in a given problem as well as their dynamically changing solution space (as described by the activity constraints), the representation scheme it employs does not take into account any preferences users may have over possible alternative value assignments. Therefore, this work is extended to allow preference information to be attached to attribute-value assignments. The way in which this can be achieved depends on the representation and reasoning mechanisms underlying the preference calculus. In general, a preference calculus can be defined as a tuple $\langle \mathds{P},\oplus,\preccurlyeq\rangle$ where:

• $\mathds{P}$ is the set of preferences,
• $\oplus$ is a commutative, associative operator that is closed in $\mathds{P}$, and
• $\preccurlyeq$ forms a partial order, that is, reflexive, anti-symmetric and transitive relation defined over $\mathds{P}\times\mathds{P}$.

Because $\preccurlyeq$ is reflexive, antisymmetric and transitive, comparing preferences with the $\preccurlyeq$ relation yields one of four possible results:

• Two preferences $P_1,P_2\in\mathds{P}$ are equal to one another (denoted $P_1=P_2$) iff $P_1\preccurlyeq P_2$ and $P_2\preccurlyeq P_1$.
• A preference $P_1\in\mathds{P}$ is strictly greater than a preference $P_2\in\mathds{P}$ (denoted $P_1\succ P_2$) iff $P_1\not\preccurlyeq P_2$ and $P_2\preccurlyeq P_1$.
• A preference $P_1\in\mathds{P}$ is strictly smaller than a preference $P_2\in\mathds{P}$ (denoted $P_1\prec P_2$) iff $P_1\preccurlyeq P_2$ and $P_2\not\preccurlyeq P_1$.
• Two preferences $P_1,P_2\in\mathds{P}$ are incomparable with one another (denoted $P_1?P_2$) iff $P_1\not\preccurlyeq P_2$ and $P_2\not\preccurlyeq P_1$.

Thus, an activity-based dynamic preference constraint satisfaction problem (aDPCSP) is a tuple $\langle\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A},\langle\mathds{P},\oplus,\preccurlyeq\rangle,P\rangle$ where

• $\langle\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A}\rangle$ is an aDCSP,
• $\langle \mathds{P},\oplus,\preccurlyeq\rangle$ is a preference calculus, and
• $P$ is a mapping $D_{x_1}\cup\ldots\cup D_{x_n}\mapsto\mathds{P}$ from the individual attribute-value assignments to the preferences.

The preferences attached to attribute-value assignments express the relative desirability of these assignments. The aim of the aDPCSP is to find a solution with the highest combined preference. That is, given an aDPCSP $\langle\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A},\langle\mathds{P},\oplus,\preccurlyeq\rangle,P\rangle$, any solution $\langle x_i:d_{x_i},\ldots,x_j:d_{x_j}\rangle$ of the aDCSP $\langle\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A}\rangle$ such that no other solution $\langle x_k:d_{x_k},\ldots,x_l:d_{x_l}\rangle$ of $\langle\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A}\rangle$ exists with $P(x_i:d_{x_i})\oplus\ldots \oplus P(x_j:d_{x_j})\prec P(x_k:d_{x_k})\oplus\ldots\oplus P(x_l:d_{x_l})$ is a solution to the aDPCSP.

In this section, a preference calculus is introduced to extend an aDCSP into an aDPCSP. The calculus will be illustrated with examples from the compositional modelling domain.