Dynamic Constraint Satisfaction in Configuration

Contents

Configuration tasks exhibit dynamic aspects which require extending the basic constraint satisfaction framework. In this paper we give a new, well-founded and relatively simple definition of such dynamic constraint satisfaction problems (DCSP). On the basis of the definition, we show that the decision problem for DCSP is NP-complete. We also show that although the complexity of DCSP is the same as for CSP, DCSP is strictly more expressive in a knowledge representation sense. However, DCSP has its limitations in representing configuration knowledge. We generalise the activity constraints of DCSP with disjunctions and default negation, and show that the decision problem remains NP-complete with this generalization. We finally describe two approaches to implementing DCSP and provide test results for both.