Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity

The project deals with configuration problems. Flexibility and efficiency in the customization of products and services - rather than series production - has become a key factor of competitiveness in the post-industrial economy. Configuration development is an excellent application area for artificial intelligence methods and for constraint satisfaction, in particular.

Developing a product configuration system is a challenging task in many ways. Product configuration tools should be designed to encode the complex knowledge from domain experts, such as the characteristics of the different components involved in the ustomization and the restriction on how these components can be combined with each other. However, this might be very difficult in general, because customization is a generative process, where both the number of the involved components and the types of components themselves may be unknown at the beginning.

The second challenge in building automatic configurators concerns the efficiency of the algorithms supporting the customization. In fact, product configuration in real scenarios is likely to involve several components and hundreds of associated variables, whose alues have to be dynamically determined based on the customer's needs. For instance, telephone switching systems often consisting of several hundreds of racks, thousands of frames, and dozens of thousands modules. Given the huge size of the problems to be reated, a major requirement is to integrate efficient algorithms to both building the configuration that best matches with the customer's desires and checking whether a given configuration satisfies the technological requirements from the industry.

In order to achieve significant progress, we will first study existing approaches and compare them formally and request feedback from the industrial advisory board. We propose to investigate a formalism suited to the cope with the above mentioned challenges, called the extensible constraint satisfaction problem (ECSP). We ill study the expressive power and the complexity of decision and computational problems related to this formalism. We also propose to investigate the complexity issues in the presence of value-generating constraints, which is a well-known type of onstraints used in database theory, but has not been investigated in the context of CSPs so far. Once the framework for extensible CSPs has been layed out, our plan is to investigate decomposition techniques, to find tractable subclasses of ECSPs. Finally, we will implement and test a configurator system, based on our framework, nd using our decomposition algorithms.

The project is organised into four main work packages. WP1 systematically studies the relevant problems to configuration, both by formally comparing existing approaches in the literature and by receiving feedback from the industrial advisory board. WP2 focuses n the extensible constraint satisfaction problems (ECSPs). Particular focus will be given to complexity analysis of the relevant decision and computational problems. WP3 consists of a comprehensive study of decomposition methods suitable to ECSPs to dentify tractable subclasses. In WP4, we will implement and test a proof-of-concept prototype of configuration system, based on ECSP and on the decomposition methods developed in WP3.

The scientific project staff will consist of one post-doc, and one doctoral student. The student is expected to intensively co-operate with the post-doc. We plan to publish the results in top artificial intelligence journals and at leading international conferences.