This paper focuses on configuration as a process that iteratively applies commonly known reasoning techniques and creates an incrementally growing configuration description. This approach emphasizes the synthesis aspect of configuration, which continuously acquires requirements and computes their effects on a configuration in a cyclic way. We provide the definitions of needed ingredients as there are partial configuration, configuration decision, and reasoning for computing entailments of made configuration decisions. These ingredients are the basis for implementations of configuration systems that follow these approach.
Configuration is the task of composing a valid system description from known component definitions ( configuration model) and customer requirements. Typical configuration approaches map this task to reasoning techniques such as constraint solving [Sabin and Freuder, 1996; John, 2002], Description Logics [McGuinness, 2003], or Answer Set Programming [Soininen et al., 2001]. Through this mapping, appropriate reasoners solve the configuration task by computing a solution of their respective logical reasoning problems.
These approaches make a fundamental assumption, i.e. that the requirements of the configuration task can be initially given, e.g., through a a set of requirements – see also [Sabin and Weigel, 1998] which call this approach batch configuration . But for many, not simple, configuration tasks this does not hold [Neumann, 1988; Stumptner et al., 1998; Fleischanderl et al., 1998]. This is due to the fact, that only during the configuration experience, when the configured product grows in front of the user’s eye, the user realizes their own desires and needs [Simonson, 2003]. For example, during a sales conversation, if a requirement causes the need of a subsystem, previously not recognized, additional requirements come into account that are related to the subsystem. Thus, the requirements are not completely clear in the beginning but change during the configuration undertaking. Simple examples are web-based configurators for consumer products such as cars or electronic items that lead the user through a sequence of web-pages for successively acquiring requirements. Other examples are industrial configurators which firstly acquire features of a system and than configure system specific components, like it is described in [Haag, 1998; Ranze et al., 2002; Hotz et al., 2006] – see also [Sabin and Weigel, 1998] which call this approach incremental configuration.
These considerations lead to a configuration approach that combines reasoning techniques with the characteristic of a configuration process . Process-related subtasks are identification of next steps in the configuration process or managing partial configurations. Especially the retraction of decisions previously made by a user is a characteristic of configuration processes [Gu¨nter and Cunis, 1992; Hotz and Wolter, 2013].
Configuration approaches that take only a certain reasoning technology into account, such as configuration based on Description Logics [McGuinness, 2003] or pure constraint processing [Tsang, 1993], have to build an external architecture (or even user interface) around the reasoning kernel, which handles configuration process tasks. Such approaches consider a configuration process as a sequence of changing but fully defined configuration tasks. However, they leave the process-related subtasks to the external architecture and do not integrate them in a configuration system. These approaches lead to domain dependent non-declarative implemented configuration processes.
If a configuration system integrates reasoning facilities and process or procedural aspects, such as e.g. [Gu¨nter and Cunis, 1992; Stumptner et al., 1998; Fleischanderl et al., 1998; Gu¨nter and Hotz, 1999], the inherent dynamic aspects of configuration tasks can be solved in a general, domain independent way, based on the configuration model. This view is also supported by the early definitions or thoughts about configuration as a syntheses task, in opposite to an analysis task like diagnosis [Brown and Chandrasekaran, 1989; Cunis et al., 1989; Gu¨nter and Cunis, 1992; Brown, 1996; Gu¨nter and Ku¨hn, 1999].
Other approaches that focus on such aspect of
configuration are generative constraints. In [Stumptner et al., 1998] the
incrementing configuration is modeled through specific
variables that are activated if certain parts of a configured system
come into play. This approach is similar to the one defined
in the following, however, we do not map the generative
notion to a certain reasoning technology
Thus, in this position paper, we elaborate on basic characteristics of the configuration process which lead to a complex mapping of the configuration task to reasoning techniques. Newly introduced operators allow a definition of the dynamics of the configuration process. These include definitions for components and restrictions as well as requirements as usual. Additionally, they provide notions for partial configurations and requirement variables. Furthermore, operators for computing requirement variables, acquiring requirements, and for the actual reasoning will lead to a comprehensive definition of the configuration problem.
Thus, we focus on the iterative characteristic of configuration, i.e. incrementing configuration with intermediate partial configurations (see Section 2). By taking this view, the paper furthermore tries to clarify the relationship of configuration to other reasoning techniques (see Section 3).
We follow ideas published in [Cunis et al., 1989; Gu¨nter, 1995]. However, by introducing process related definitions and operators, a summary of the needed ingredients is established that shall give the basis for process-based configuration technologies. 2
In the following, through definitions that build on each other, we develop a definition of a complex configuration problem that take the iterative character of the configuration process into account. We develop a general definition of the complex configuration task that is independent of a certain knowledge representation, such as logic or constraint-based approaches.
First, we provide the definition of a configuration model. This model defines all possible configurations in a generic way. The model represents entities to be configured (such as hardware components, software modules, or services) and relations between them.
We here discuss a combination of entities (e.g., represented with component types or classes) and relations (e.g., represented with constraints). However, the operators defined in the following are independent of the representation. For example, if a pure constraint-based representation is initially used, appropriate operators should have to be developed for supporting the here considered complex configuration tasks.
The definitions are illustrated with an example of composing a menu with antipasti, main course, and dessert. While antipasti will always be selected if a hearty menu is desired, the selection of a dessert cannot be computed from constraints. A hearty menu is part of initial requirements, while the dessert is only selected after the main course, demonstrating a dynamic requirements acquisition.
Definition 1 (Configuration Model) . A configuration model CM is a generic description of entities of an application domain. CM is a tuple hΓ, Ψ, Φi, where • Γ is a set of attributed entity models E M ∈ Γ (e.g. classes or concepts) each representing a set of concrete entities to be configured. An entity model consists of named properties. Each property P is a binary relation that maps from E M to a property domain PDP . • Ψ is a set of property domains PDP ∈ Ψ of properties P. A PDP might be a structural property domain (and P is called structural property) with a set of structural property values, i.e. an entity model optionally combined with a cardinality. Or it might be a primitive datatype, such as a number, symbol, or string or a probably infinite set (e.g. for number ranges) of those, than P is called data-type property. • Φ is a set of n-ary relations E R ∈ Φ between properties of entity models.
Example 1. An entity model with one data-type property, one structural property, and a n-ary relation representing the fact that a menu should consist in any case of a main course and might optionally has an antipasti and a dessert. Depending on the kind of taste, an antipasti is selected if hearty taste is desired: (Entity-Model name: Menu super-type: Aggregate data-properties: ((kindOfTaste {hearty light})) hasCourses: ((AntiPasti :min 0 :max 1) (MainCourse :min 1 :max 1) (Dessert :min 0 :max 1))) (Entity-Model name: AntiPasti
super-type: Part) (Entity-Model name: MainCourse
super-type: Part) (Entity-Model name: Dessert
super-type: Part) (Constraint name: HeartyEqualsToAntiPasti
Menu.kindOfTaste == hearty <=>
Menu.hasCourses HAS (AntiPasti :min 1 :max 1))
For representing concrete components of an application domain, entity instances are used. First, we define a simple entity instance, later on we enhance this definition. Definition 2 (Simple Entity Instance). A SE IEM represents one concrete entity of the application domain. SE IEM belongs to an entity model E M and has all or some properties of E M. The property values are constant values that belong to the respective property values of E M.
For representing customer requirements about the desired configuration, configuration requirements are defined as follows.
Definition 3 (Simple Configuration Requirememts) . Simple configuration requirements SR are a set of simple entity instances with some properties filled with constant values. Example 2. Two simple entity instances representing the requirement “Hearty menu with a main course”: (Entity-Instance name: menu-1 entity-model: Menu kindOfTaste: {hearty} hasCourses: {mainCourse-1}) (Entity-Instance name: mainCourse-1
entity-model: MainCourse) Typically, a configuration task is defined as follows: Definition 4 (Simple Configuration Task) . A configuration task is defined through an entity model E M and configuration requirements SR.
Definition 5 (Simple Configuration) . A configuration is defined through a set of completely filled configuration instances CI.
A knowledge representation technique allows it to represent an configuration model and configuration requirements. Furthermore, it provides reasoning techniques that allow to solve the simple configuration problem.
Definition 6 (Simple Configuration Problem) . CM = hΓ, Ψ, Φi be a configuration model. A simple configuration problem in CM is a tuple hCM, SRi, where SR is a set of initial simple entity instances. A solution (a configuration ) of the problem hCM, SRi is a set of simple entity instances that is consistent with CM and fulfills the configuration requirements SR.
How consistency is concretely defined depends on the knowledge representation. However, in general for structural properties, consistency means that entity instances belong to S according to the cardinality descriptions of the structural property. Thus, structural relations emphasize a configuration being a collection of related entity instances, while n-ary relations related properties of those instances.
Example 3. A resulting configuration, the constraint infers the need of an entity instance representing antipasti: (Entity-Instance name: menu-1 entity-model: Menu kindOfTaste: {hearty} hasCourses: {mainCourse-1 antiPasti-1}) (Entity-Instance name: mainCourse-1
entity-model: MainCourse) (Entity-Instance name: antiPasti-1
entity-model: AntiPasti)
These definition provide the basis for configuration tasks: a configuration model, the customer requirements, and a knowledge representation that allows for creating a configuration that fulfills the customer requirements. This definition makes a basic assumption, i.e. that SR, the set of particular customer requirements, are given. In simple, one step configuration problems, such as parameterization of technical systems, this is a reasonable assumption. In more complex applications, the requirements evolve during the configuration process. This observation leads to further definitions.
First, we enhance the definition of a simple entity instance by allowing not only constant values for properties but also subsets.
Definition 7 (Partial Property Domain). Let P be a property of an entity instance E I of entity model E M. And let PDP be the property value of P as defined in CM. A partial property domain PPDP of P is a subset of PDP , i.e. PPDP ⊆ PDP .
Please note that a specific partial property domain is a property domain with one value representing a constant value, e.g. a number of a data-type property or a single instance of a structural property.
Example 4. Example for a partial property domain of a structural property with one entity instance and two open cardinality definitions: hasCourses: {mainCourse-1 (AntiPasti :min 0 :max 1) (Dessert :min 0 :max 1)} Definition 8 (Terminal Property Domain). A terminal property domain T PDP of property P is a partial property domain that is marked with terminal. A constant value is automatically marked as terminal. Structural property values or sets may be marked through the heuristic operator (see below).
Example 5. Example for a partial property domains of a data-type property indicated as terminal:
kindOfTaste: {hearty [terminal]} Definition 9 (Entity Instance). An E IEM represents one concrete entity of the application domain. E IEM belongs to an entity model E M and has the same properties as E M. The property values might be the same as defined for E M or subsets of those, they might be partial or terminal property domains. These partially filled entity instances represent uncertain knowledge about the concrete entity. A completely filled entity instance has a terminal property domain for each property.
Example 6. One partially filled entity instance: (Entity-Instance name: menu-1 entity-model: Menu kindOfTaste: hearty hasCourses: {mainCourse-1 (AntiPasti :min 0 :max 1) (Dessert :min 0 :max 1)}) Example 7. One completely filled entity instance: (Entity-Instance name: menu-1 entity-model: Menu kindOfTaste: {hearty [terminal]} hasCourses: {mainCourse-1 antiPasti-1 [terminal]}) Definition 10 (Partial Configuration) . A partial configuration PO is a set of partially or completely filled entity instances. Definition 11 (Configuration Requirememts) . Configuration requirements R are a set of instances with some property values set to terminal property domains.
Thus, configuration requirements are a specific kind of partial configuration namely one with instances whose properties do not have a terminal property domain for each property. We also call this partial configuration initial partial configuration.
Definition 12 (Final Configuration) . A final configuration F C is a set of completely filled entity instances. Furthermore, for each structural property of an instance in F C, a related instances exists in F C according to the structural property value (i.e. the defined entity model and the cardinality).
Now, probably the main step in our definitions follows, i.e. the introduction of the definition of a variable. Typically, properties of components are considered as variables and the configuration task is to provide a value for these variables, i.e. for the properties of the components. In our definition, a variable stands for a decision that has to be made for gaining a final configuration. Thereby, each variable stands for one property of an entity instance that has to be determined. However, during the configuration process there might be several variables for one property, e.g. if a property value is reduced by the user in several steps. Definition 13 (Variable). A variable V represents one decision of setting the value of one certain property. One or more decisions have to be made for each property of every entity instance. The variable represents possible outcomes of the decision through its variable domain Vd. A variable domain is a property value.
Example 8. Variable representing the decision that antipasti and dessert shall be selected as courses of a menu: (Variable entity-instance: menu-1 property: hasCourses property-value: {mainCourse-1 (AntiPasti :min 0 :max 1) (Dessert :min 0 :max 1)}) Definition 14 (Reduced Variable). A reduced variable RV of a variable V with a domain Vd is a variable with a domain RVd with RVd ⊂ Vd. The reduced domain might also be a terminal property domain. For a structural property with a structural property value, the subset is a set of instances that are conform with the cardinality descriptions of the structural property value.
The reduced variable represents the result of a made decision.
Definition 15 (Heuristic Operator). A heuristic operator HO is an operator that takes a variable V and computes a reduced variable RV (probably with a terminal property domain) by some heuristic method, thus: HO: V → RV .
The heuristic operator represents the method for gaining a reduced variable, e.g. the selection of a default value, the computation of a function computing a reduced domain for the variable, or the acquisition of a value for that variable from the user. Thus, the heuristic operator acquires subsequent requirements that come up during the configuration process. Furthermore, by reducing a structural property the heuristic operator incrementally expands the configuration, because new entity instances are created when reducing the structural property (see above). A new entity instance has the same properties and property values as its entity model. Example 9. Reduced variable created by a heuristic operator that asks the user, if a dessert is needed, answer was “yes”: (Variable entity-instance: menu-1 property: hasCourses property-value: {mainCourse-1 (AntiPasti :min 0 :max 1) dessert-1)})
Example 9 represents the answer to the typically raised question after a meal “Would you like a dessert?”, which is a simplistic example for a dynamic requirement acquisition. Definition 16 (Entailment Operator). An entailment operator E O is an operator that takes the configuration model CM (especially the denfied n-ary relations), a partial configuration PCi, and one reduced variable RV and computes a new partial configuration PCi+1 which contains the value of the reduced variable and all entailments of this reduction, computed by some reasoning method, thus: E O: CM, PCi, RV → PCi+1.
In the initial case, RV might be empty, i.e. E O: CM, PC0, → PC1 computing the entailments of the values in PC0, i.e. the initial partial configuration.
The entailment operator represents the integration of one made decision into a partial configuration and the computation of the influences of this decision to the partial configuration. The influences are computed on the basis of the configuration model, especially the n-ary relations, which relate properties of entity models. An influence or entailment is a reduction of domains of some variables in PCi. Typical examples for an entailment operator are the solution of a constraint problem or applying Description Logic services. Example 10. Reduced variable created by an entailment operator that uses the constraint for deciding that an antipasti is needed if a hearty menu was selected: (Variable entity-instance: menu-1 property: hasCourses property-value: {mainCourse-1 antiPasti-1 (Dessert :min 0 :max 1)}) Definition 17 (Open Issue Operator). An open issue operator OIO is an operator that takes the configuration model CM and a partial configuration PC and computes new variables Vi that have no terminal property domains and are collected in the set A, thus: OIO: CM, PC → A, with Vi ∈ A.
From Example 6 the OIO computes the variable shown in Example 8 because of the partial property domain for property hasCourses.
Definition 18 (Select Operator). A select operator SO is an operator that select one variable V out of the set A by some selection method, thus: SO: A → V.
Now, we define the actual configuration process and identify its main part, i.e. the configuration cycle . A configuration process starts with an initial partial configuration given through the requirements of a customer. By successively applying the above operators the final configuration will be created. This process is defined as follows:
Starting from the initial partial configuration IP, E O computes the first entailments and, thus, PC1. Hereafter, the open issue operator OIO can be applied to PC1 for computing next variables with non-terminal property domains and builds A1. The operator SO selects a next variable to be decided V1. From here the heuristic operator HO reduces the variable’s domain to RV1. The entailment operator uses the previous partial configuration ( E O(PC1)) for computing the next partial configuration PC2. This way the operators are successively applied until the final configuration PCn is created and no more open issues can be identified (i.e. OIO computes an empty set). In total, we have: IP, −E−O→ PC1 −O−I−O→ A1 −S−O→ V1 −−→ RV 1 HO EO(PC1) HO −−−−−−→ PC2 −O−I−O→ A2 −S−O→ V2 −−→ RV 2 EO(PC2) HO −−−−−−→ PC3 −O−I−O→ A3 −S−O→ V3 −−→ RV 3 . . .
EO(PCn−2) HO −−−−−−−→ PCn−1 −O−I−O→ An−1 −S−O→ Vn−1 −−→ RV n−1 EO(PCn−1) OIO −−−−−−−→ PCn −−−→ ∅
Thus, the general configuration cycle is defined as follows: Definition 19 (Configuration Cycle) . A configuration cycle COC is a sequence of operators OIO, SO, HO, E O as follows: EO(PCi)
PCi −O−I−O→ Ai −S−O→ Vi −H−O→ RV i −−−−−−→ PCi+1 Definition 20 (Complex Configuration Problem) . CM = hΓ, Ψ, Φi be a configuration model. A complex configuration problem in CM is a tuple hCM, R, HO, E O, SO, OIOi, where R is a set of initial entity instances and HO, E O, SO, OIO the previously introduced operators. A solution of the problem hCM, R, HO, E O, SO, OIOi is a final configuration that was computed by applying the configuration cycle, that is consistent with CM, and that fulfills the configuration requirements R.
Like in the simple configuration problem definition, how consistency is concretely defined depends on the knowledge representation. Furthermore, the knowledge representation defines the entailment operator. 3
The commonly used view on configuration is to specify a configuration model and customer requirements as a reasoning task of a reasoning system, such as a constraint system, and than solve the reasoning task and present the resulting configuration. This paper provides a view on configuration that basically iterates these two steps of defining requirements and reason about them, i.e.: 1. Start from an initial configuration including the requirements, 2. compute entailment of the requirements on the configuration (operator E O), 3. create an agenda with not yet made decisions (operator
OIO), 4. select one decision (operator SO),
7. goto Step 3.
The computation of the entailments (Step 2 and Step 6) correspond to the solution of the reasoning task, e.g. by constraint processing. The construction of a reasoning task is included in the configuration process in the steps 3, 4, and 5.
Thus, the overall schema for configuration as seen in our approach provides an iterative application of commonly applied reasoning techniques for configuration. For solving a complex configuration problem, a configuration system or a technological approach should realize the operators defined above.
Of course, there exist variations of the here presented basic framework. For example, the proposed approach to represent requirements with instances might be enhanced to complex requirements that need further reasoning to compute them [Tha¨ringen, 1995; Kopisch and Gu¨nter, 1992]. Or the selection of a decision may be enhanced to selecting multiple decisions or to let the user select next decisions from the agenda. Another extension is to include techniques for conflict resolution [Gu¨nter and Hotz, 1995; Felfernig and Schubert, 2010; Hotz and Wolter, 2013]. However, this paper provides the basic ingredients for solving a configuration task incrementally. Configuration tools which follow our approach are KONWERK [Gu¨nter and Hotz, 1999], engcon [Hollmann et al., 2000], or Plakon [Cunis et al., 1989]. 4
This paper defines the necessary ingredients for a configuration process that iteratively generates a configuration. Besides the typically used reasoning techniques, the process additionally supplies steps for creating requirements on the fly and include them and their entailments in a growing configuration. Enhancements in future work will be the inclusion of operators for resolving conflicts that might occur during the configuration process. [Stumptner et al., 1998] M. Stumptner, G. Friedrich, and A. Haselbo¨ck. Generative Constraint-based Configuration of Large Technical Systems. AI EDAM, 12(04):307–320, 1998. [Tsang, 1993] Edward Tsang. Foundations of Constraint Satisfaction. Academic Press, London, San Diego, New York, 1993.