Next: Order-of-magnitude preferences (OMPs) Up: Dynamic Constraint Satisfaction with Previous: Dynamic Constraint Satisfaction with

## Background: Activity-based dynamic preference constraint satisfaction

A hard constraint satisfaction problem (CSP) is a tuple , where
• is a vector of n attributes,
• is a vector containing exactly one domain for each attribute in . Each domain is a set of values that may be assigned to the attribute corresponding to the domain.
• is a set of compatibility constraints. A compatibility constraint defines a relation over a subset of the domains , and hence .

A solution to a hard constraint satisfaction problem is any tuple such that

• each attribute is assigned a value from its domain: , and
• all compatibility constraints are satisfied: .

An activity-based dynamic CSP (aDCSP), originally proposed in by Mittal and Falkenhainer [31], extends conventional CSPs with the notion of activity of attributes. In an aDCSP, not all attributes are necessarily assigned in a solution, but only the active ones. As such, each attribute is either active and assigned a value or inactive:

 active

The activity of attributes in an aDCSP is governed by activity constraints that enforce under which assignments of attributes, an assignment to another attribute is relevant or possible. This information is important because it not only dictates for which attributes a value must be searched, but also the set of compatibility constraints that must be satisfied. Clearly, only the compatibility constraints for which all attributes are active must be satisfied, and a hard CSP is a sub-type of aDCSP in which all attributes are always active.

In summary, an activity-based dynamic constraint satisfaction problem (aDCSP) is a tuple , where

• is a hard CSP, and
• is a set of activity constraints. An activity constraint restricts the sets of attribute-value assignments under which an attribute is active or inactive:

 activeactive

where .

A solution to an activity-based dynamic constraint satisfaction problem is any tuple such that

• the attributes that are part of the solution are assigned a value from their domain: ,
• all activity constraints are satisfied:

and
• all compatibility constraints are satisfied:

 activeactive

Next: Order-of-magnitude preferences (OMPs) Up: Dynamic Constraint Satisfaction with Previous: Dynamic Constraint Satisfaction with
Jeroen Keppens 2004-03-01