Constructive problem solving : a model construction approach towards configuration

Abstract

In this paper we give a formalisation of configuration as the task to construct for a given specification, which is understood as a finite set of logical formulas, a model that satisfies the specification. In this approach, a specification consists of two parts. One part describes the domain, the possible components, and their interdependencies. The other part specifies the particular object that is to be configured. The language that is used to represent knowledge about configuration problems integrates three sublanguages that allow one to express constraints, to build up taxonomies, and to define rules. We give a sound calculus by which one can compute solutions to configuration problems if they exist and that allows one to recognize that a specification is inconsistent. In particular, the calculus can be used in order to check whether a given configuration satisfies the specification.