Configuration as Composite Constraint Satisfaction

Daniel Sabin, Eugene C. Freuder

Selecting and arranging parts is the core of a configuration task. The validity of a configuration is defined in terms of constraints. Highly declarative, domain independent and simple to use, the constraint satisfaction problem (CSP) paradigm offers an adequate framework for this task. However, the basic paradigm is not powerful enough to capture or to take advantage of essential as-pects of configuration, such as the unknown a priori number of constituent parts of a system or the inherent internal structure of these parts. Although notable effort has been spent on extending the basic paradigm to accommodate these issues, we still lack a comprehensive formalism for configuration. This paper presents the main ideas behind a general constraint-based model of configuration tasks represented as a new class of nonstandard constraint satisfaction problems, called composite CSP. Composite CSP unifies several CSP extensions, providing a more comprehensive and efficient basis for formulating and solving configuration problems.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.