next up previous
Next: Representation of OMPs Up: Dynamic Constraint Satisfaction with Previous: Background: Activity-based dynamic preference


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:

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

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

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.



Subsections
next up previous
Next: Representation of OMPs Up: Dynamic Constraint Satisfaction with Previous: Background: Activity-based dynamic preference
Jeroen Keppens 2004-03-01