Official Project-Website
|
|
(IST project IST-FET-2001-37004) Official Project-Website |
The Smodels system is an implementation of Answer-Set Programming implementation for cardinality and weight constraint logic programs.
Modern software products are large and may consist of thousands of components where each component provides some specific functionality. In the configuration management problem we are given a description of the components, a set of user requirements and we have to find a valid configuration of components that satisfies the requirements.
The difficulties arise from the fact that the components interoperate in various ways: a component may need the functionality provided by other components, a functionality may be provided by several different components, some components may conflict with each other so it is not possible have both of them in the same product, and so on.
The ASP systems are used to create the valid configurations. The ASP program is divided into three parts:
a configuration model that is a set of non-ground rules that defines how the relationships between components work;
a component description that is a set of ground facts that defines what components are available and what relationships they have with other components.
a user requirements description that is a set of ground facts that tells what properties the user wants the product to have.
The configuration model is created only once, when the product is first designed. The component description is updated whenever a new component or a new version of an existing component is added to the system. These two are stored in the configurator tool.
The third part, user requirements description, is generated separately whenever we want to use the configurator.
Additionally, we can use ASP for debugging purposes. In this approach we have also a diagnostic model that explains why it is not possible to satisfy a given set of user requirements.
Using Answer Set Programming allows us to have a concise declarative representation for the configuration model. The main concepts of configuration management have an intuitive translation into ASP rules and we can separate the rules that define the configuration model from the rules that define the components so we can make modular configurators.
The actual configuration model is quite small in most cases so they are easy to understand and maintain once one has became acquainted with the ASP paradigm. For example, the configuration model for the iPKG system has only 30 non-ground rules.
In Debian GNU/Linux System the components are different versions of software packages. The basic relationships between the packages are:
A depends on B if the package A does not work if the package B is not present in the configuration.
A conflicts with B if the package A cannot be installed at the same time as package B is.
A recommends B if most users of A will expect that B is also present in the system.
A may also provide a generic functionality.
Below we have a simple example that illustrates the simple relations
between packages:
We have two different software packages (mail_reader_1 and mail_reader_2) that both provide an email reader. Both of them require that mail_transport_agent is installed and in this example we assert that it is not possible to have both of them installed at one time. Additionally, there is an extension package that provides new functionality for mail_reader_1 and does not work without it.
The simplified Debian configuration problem can be solved with the following three ASP and one Perl programs:
the configuration model;
the diagnostic model;
sample package data file; and
the Perl driver script.
Next we go through several possible ways to compute the configurations.
Another example case is the iPKG system is an offshoot of the Debian package management system that is aimed for hand-held devices. The following ASP programs define the configuration model for a snapshot of the package list:
the configuration model; and
the package data file.
Juha Tiihonen, Timo Soininen, Ilkka Niemelä, and Reijo Sulonen. A practical tool for mass-customising configurable products. In Proceedings of the 14th International Conference on Engineering Design, pages 1290-1299, 2003.
Juha Tiihonen, Timo Soininen, Ilkka Niemelä, and Reijo Sulonen. Empirical testing of a weight constraint rule based configurator. In ECAI 2002 Configuration Workshop, pages 17-22, 2002.
Timo Soininen, Ilkka Niemelä, Juha Tiihonen, and Reijo Sulonen. Representing configuration knowledge with weight constraint rules. In Proceedings of the AAAI Spring 2001 Symposium on Answer Set Programming, pages 195-201, Stanford, USA, March 2001. AAAI Press. [ps.gz]
Tommi Syrjänen: Including Diagnostic Information in Configuration Models. In Proceedings of the First International Conference on Computational Logic, London, UK, July 2000, Volume 1861 of Lecture Notes in Artificial Intelligence, Springer, Berlin. [ps.gz]
Tommi Syrjänen: Optimizing Configurations. In Proceedings of the ECAI Workshop W02 on Configuration, August, 2000, Berlin, Germany. [ps.gz]
Timo Soininen, Ilkka Niemelä, Juha Tiihonen, and Reijo Sulonen. Unified configuration knowledge representation using weight constraint rules. In Workshop Notes of the ECAI'2000 Configuration Workshop, pages 79-84, Berlin, Germany, August 2000. [ps.gz]
Tommi Syrjänen: A Rule-Based Formal Model for Software Configuration. Research Report A55, Helsinki University of Technology, Laboratory for Theoretical Computer Science, 1999. [link]