Dynamic Constraint Satisfaction Problems

Constraint satisfaction (CSP) is a powerful and extensively used framework for describing search problems. A CSP is typically defined as the problem of finding consistent assignment of values to a fixed set of variables given some constraints over these variables. However, for many synthesis tasks such as configuration and model composition, the set of variables that are relevant to a solution and must be assigned values changes dynamically in response to decisions made during the course of problem solving. In this paper, we formalize this notion as a dynamic constraint satisfaction problem that uses two types of constraints. Compatibility constraints correspond to those traditionally found in CSPs, namely, constraints over the values of variables. Activity constraints describe conditions under which a variable may or may not be actively considered as a part of a final solution. We present a language for expressing four types of activity constraints in terms of variable values and variables being considered. We then describe an implemented algorithm that enables tight interaction between constraints about variable activity and constraints about variable values. The utility of this approach is demonstrated for configuration and model composition tasks.

Authors

• Sanjay Mittal Brian Falkenhainer

Keywords

No keywords are indexed for this paper.