Knowledge-based Configuration: From Research to Business Cases, FIRST EDITION (2014)

Part V. Configuration Environments

Chapter 22. S’UPREME

Alois Haselböck and Gottfried Schenner, Siemens AG, Vienna, Austria

Abstract

S’UPREME is an in-house configuration system of Siemens AG for the configuration of complex large-scale technical systems, for instance railway safety systems or industrial production systems (see also Chapter 16). This chapter gives a brief overview of the technological background and modeling expressiveness of S’UPREME.

Keywords

Knowledge-based Configuration; Generative Constraint Satisfaction; Configuration Framework; Interactive Configuration

22.1 Introduction

This chapter describes S’UPREME, an in-house configuration framework of Siemens. The technological basis of S’UPREME is an object-oriented extension of a constraint programming system, known as Generative Constraint Satisfaction (see also Hotz et al., 2014¹). It is now in productive use since around 2002, mainly in the fields of large-scale industrial production, telecommunication, and railroad equipment and safety systems.

The remainder of this chapter is organized as follows: Section 22.2 gives an overview of the architecture of the framework. Section 22.3 describes the typical steps required to define a new S’UPREME based configurator. Finally Section 22.4 provides some closing remarks.

22.2 System Architecture and Technological Background

S’UPREME is a domain-independent configuration framework providing general configuration capabilities. Figure 22.1 sketches the main components of S’UPREME’s architecture. The core of S’UPREME consists of a knowledge base meta-structure (for specifying components, properties, and constraints of a concrete configuration domain) and a solving engine.

FIGURE 22.1 System architecture of S’UPREME.

Several built-in solvers are provided: Consistency algorithms can check configurations, propagate user inputs and filter configuration options; a repair-based heuristic search algorithm and a backtracking algorithm can complete partial configurations.

Apart from these built-in solvers, the design of S’UPREME allows integration of external solvers like MILP (mixed integer linear programming) or SAT solvers (satisfiability of propositional formulas; see Falkner et al., 2010).

For a concrete configuration domain, a configurator architect designs the engineering process and models the knowledge base structure. The knowledge base consists of component types, organized in a type and aggregation hierarchy, their attributes and constraints (constraints represent propositions on which configurations are valid and complete, and which are not). The tool S’UPREME Studio helps the knowledge engineer to define the knowledge base. The resulting application is coded in Java, a big part of the code being generated by S’UPREME Studio.

S’UPREME provides a standard frame-based GUI, but usually an application-specific GUI is designed and programmed for each new configurator. Customer-specific input and output interfaces usually must be implemented as well. For persisting configurations, S’UPREME has connectors to SQL databases, object-oriented databases, and XML files.

The main and outstanding technological concept of S’UPREME is Generative Constraint Satisfaction (GCSP). GCSP is an extension of classical CSP designed to cope with dynamic aspects arising in many technical application domains, like configuration, design, or planning. Classical CSP represents a problem by a fixed set of variables, their domains, and constraints. A solution is a variable assignment where no constraint is violated. But this static set of variables is usually not appropriate if the number of components in a solution is not known at modeling time.

The most prominent extensions of the classical CSP schema toward a more dynamic view are Conditional CSP (Gottlob et al., 2007; Mittal and Falkenhainer, 1990), Dynamic CSP (Dechter and Dechter, 1998), and as used in S’UPREME, Generative CSP (Felfernig et al., 2003; Fleischanderl et al., 1998).

GCSP was designed for representing and solving large-scale complex configuration problems and is therefore a powerful and highly expressive framework. Besides constraint satisfaction, the main background of GCSP is the object-oriented paradigm with its clean separation of the problem model and the problem instance. This allows for a natural and maintainable formulation of the problem structure, a declarative formulation of the problem logics, and a clean handling of the dynamicity inherent in many configuration problems.

22.3 Modeling of the Working Example

When creating a S’UPREME configurator application the first task for the knowledge engineer is to come up with an object-oriented model of the system to configure. The object-oriented meta-model of S’UPREME is compatible with the object-oriented UML standard. In order to model the working example of this book we can therefore directly use the UML diagram of Figure 6.7 in Hotz et al. (2014).²

The knowledge engineer specifies the knowledge base with S’UPREME Studio. In this editor the knowledge engineer edits the classes and their attributes and associations. For attributes, their domains, initial values, and computation functions can be provided. For associations, the roles of the association and their cardinalities must be defined.

The screenshot in Figure 22.2 shows a part of the knowledge base of the working example in Hotz et al. (2014). In the treeview on the left, one can see the classes and the inheritance hierarchy that correspond one-to-one to the UML diagram. The editor window on the right shows an example of an association, here from the motherboard to its CPUs. The cardinality entries ensure that each CPU has an assigned motherboard and a motherboard has one or two CPUs.

FIGURE 22.2 The modeling framework S’UPREME Studio.

After the model is complete, S’UPREME studio can generate a Java-based S’UPREME configurator application for the knowledge base. For each class in the knowledge base a corresponding Java class is generated. The inheritance hierarchy is taken directly from the UML diagram; for example, the classes OSAlpha and OSBeta are subclasses of the class OS.

These generated Java classes with type-safe getter/setter methods can be treated by application programmers like normal Java classes; they can write additional methods in these classes for their purposes (output generation, GUI, testing, etc.).

Attributes are defined by statements like

In this example, the attribute usage is defined at the class PC. Associations are defined in a similar way; for example, the following statement defines the bidirectional link between a motherboard (MB) and its CPUs:

A configuration is an instantiation of the knowledge base. The S’UPREME configurator maintains one configuration at a time. Using the Standard GUI, a user can manipulate the current configuration by adding, deleting, and connecting components and by setting their attributes. From the GCSP point of view, attributes and associations are seen as constraint variables, which are checked and manipulated by GCSP reasoning.

A constraint is a condition on constraint variables (i.e., attributes and associations of component classes) that a valid configuration must satisfy. Like attributes and association, constraints are inherited along the type hierarchy. After each change in the current configuration the affected (possibly inherited) constraints are checked and their status (violated/valid) is updated. When the constraint is violated an explanation is provided by the GUI by showing the dependencies of the constraint.

Constraints can also be used for filtering out inconsistent values. For example, when setting the efficiency for a PC to B the value C is no longer allowed for the efficiency of the screen and will no longer be shown on the GUI as a possible value. A similar filtering occurs for the PC if the efficiency for the screen is set first. A constraint like the following for the class Screen achieves this behavior for both cases:

Many constraints—the so-called built-in constraints—are directly generated from the UML diagram. They are created for domains of attributes and cardinalities of associations. For instance, the fact that each CPU must have a motherboard is checked by a built-in constraint. Another example is that the clock rate of the CPU must be from {slow, medium, fast}.

Domain-specific constraints must be written in Java using the S’UPREME constraint API. As an example let us consider the constraint gc3 from Hotz et al. (2014)³: Each OS of type OSAlpha requires a CPU of type CPUD. This can be implemented as a constraint for the class OSAlpha:

The variable cpuVar represents the role of the association between the motherboard and its CPUs. By posting the constraint expression

it is ensured that in a configuration with an OSAlpha operating system a motherboard must contain one or two CPUs of type CPUD.

When a constraint is violated, the user can ask the configurator to suggest a repair action for the constraint violation. The screenshot of the S’UPREME configurator in Figure 22.3 shows a situation where the aforementioned constraint gc3 is violated. As a repair action for the constraint violation the configurator suggests to add a new CPUD to the motherboard. The user can choose a single repair action or alternatively, he/she can choose to solve all constraint violations at once by calling the repair-based built-in solver of S’UPREME.

FIGURE 22.3 Repair action in the PC configurator with S’UPREME.

The main solving method used in S’UPREME is heuristic repair (Tsang, 1993, Chapter 8.2.2), which has several advantages:

• It is fast and can handle large-scale problem instances. A typical S’UPREME configurator has to deal with the following orders of magnitudes: number of knowledge base classes, ; number of constraint definitions in the knowledge base, ; number of components (instances) in a configuration, ; number of instantiated constraints, .

• It can deal with inconsistent intermediate states (e.g., in situations where the user of the configurator reaches an inconsistent scenario by his/her inputs. For instance, he/she selected expensive components that exceed his/her price limits. A standard CSP or SAT solver would give up immediately, because the input facts alone are inconsistent. Heuristic repair will start solving no matter if the current situation is incomplete or inconsistent.

• Systems must be maintained, modernized, and updated to changed environmental or strategic situations. Changes in existing systems may lead to conflicts that must be repaired. Of course, the adapted system shall keep as many components and structures of the old system as possible. Also not all reconfiguration actions are equally costly. For instance, changing the RAM is usually less costly than changing the motherboard. Heuristic repair can deal with such reconfiguration tasks in a natural way by defining different costs for different repair actions.

• It is easy to adapt the heuristics used by the solver by providing an explicit ordering of the constraint variables.

The disadvantage of local search methods like heuristic repair is their incompleteness. If completeness is required then a complete backtracking solver can be used, although in practice without the right heuristic, complete methods can only be used for moderate problem sizes (e.g., up to a few hundred component instances).

22.4 Conclusion

A configuration system must always be integrated into the ordering, pricing, configuration, and manufacturing process of a business unit. This integration is well-supported by S’UPREME due to its open architecture, its standard object-oriented model, and its Java API.

S’UPREME was and is successfully used in domains like mobility (train control systems, interlocking systems), telecommunication, and industrial production within Siemens (see Falkner and Schreiner, 2014⁴). Including country-specific variants there exist more than 30 different configurator applications based on S’UPREME.

Technical systems are often configured in an interactive process. The user specifies his/her requirements and selects components, then the configurator checks the inputs, shows inconsistencies, rules out options that have became invalid, and derives additional knowledge (e.g., additionally needed components). Then, in turn, the user proceeds with his/her inputs, and so on. The process stops when the user has specified all of his/her requirements and the configuration is complete and consistent. A generative constraint system like S’UPREME supports this interactive process in a very natural way, guiding the user through a sequence of configuration steps.

References

1. Dechter R, Dechter A. Belief maintenance in dynamic constraint networks. In: AAAI 1998, Madison, WI. 1998;37–42.

2. Falkner A, Schreiner H. SIEMENS: configuration and reconfiguration in industry. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014:199–210. (Chapter 16).

3. Falkner A, Haselböck A, Schenner G, Schreiner H. Modeling and solving technical product configuration problems. Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM). 2010;25(2):115–129.

4. Felfernig A, Friedrich G, Jannach D, Stumptner M, Zanker M. Configuration knowledge representations for semantic web applications. Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM). 2003;17(1):31–50.

5. Fleischanderl G, Friedrich GE, Haselböck A, Schreiner H, Stumptner M. Configuring large systems using generative constraint satisfaction. IEEE Intelligent Systems. 1998;13(4):59–68.

6. Gottlob G, Greco G, Mancini T. Conditional constraint satisfaction: Logical foundations and complexity. In: 20th International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, India. 2007:88–93.

7. Hotz L, Felfernig A, Stumptner M, Ryabokon A, Bagley C, Wolter K. Configuration knowledge representation & reasoning. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014:41–72. (Chapter 6).

8. Mittal S, Falkenhainer B. Dynamic constraint satisfaction problems. In: Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, MA. 1990:25–32.

9. Tsang E. Foundations of Constraint Satisfaction. London, San Diego, New York: Academic Press; 1993.