Alexander Felfernig, Cipriano Forza, and Albert Haag, Editors Proceedings of the 16th International Configuration Workshop
Martin Stettinger, Graz University of Technology, Austria Nikola Suzic, University of Novi Sad, Serbia and University of Padova, Italy Configuration problems have always been subject of interest for the application and the development of advanced Artificial Intelligence techniques. The selection of papers of this year's workshop demonstrates the wide range of applicable AI techniques including contributions on configuration knowledge representation, algorithms, theoretical approaches, and real-world configuration problems & applications.
The workshop is of interest for both, researchers working in the various fields of Artificial Intelligence as well as for industry representatives interested in the relationship between configuration technology and the business problem behind configuration and mass customization. It provides a forum for the exchange of ideas, evaluations, and experiences especially related to the use of Artificial Intelligence techniques in the configuration context.
As such, this year's Configuration Workshop again aims at providing a stimulating environment for knowledge-exchange among academia and industry and thus building a solid basis for further developments in the field.
Using Answer Set Programming for Feature Model Representation and Configuration Varvana Myllärniemi , Juha Tiihonen, Mikko Raatikainen, and Alexander Felfernig Integrating Distributed Configurations with RDFS and SPARQL Gottfried Schenner, Stefan Bischof, Axel Polleres, and Simon Steyskal
Martin Stettinger, Alexander Felfernig, Michael Jeran, Gerald Ninaus,
Optimization based framework for transforming automotive configurations for production planning
Andres F. Barco, Elise Vareilles, Michel Aldanondo, and Paul Gaborit Towards More Flexible Configuration Systems: Enabling Product Managers to Implement
Linda L. Zhang, Xiaoyu Chen, Andreas Falkner, and Chengbin Chu Towards an understanding of how the capabilities deployed by a Web-based sales configurator can increase the benefits of possessing a mass-customized product
Alexander Felfernig, Martin Stettinger, Gerald Ninaus, Michael Jeran, Stefan Reiterer, Andreas
Copyright © 2014 for the individual papers by the papers' authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. 1 9 17 23 31 39 47 55 59 67 75 81 89
Using Answer Set Programming for
Feature Model Representation and Configuration Varvana Mylla¨ rniemi 1 and
Juha Tiihonen1 and
Mikko Raatikainen 1 and
Alexander Felfernig2 Abstract. Feature models are a wide-spread approach used for expressing variability in software product lines. Answer set programming (ASP) is nowadays an increasingly popular approach to configuration knowledge representation. In this paper, we study the similarities between feature modeling and configuration knowledge representation with ASP. We define the feature configuration problem utilizing ASP, and show two different ways using an example of translating the basic feature modeling concepts embodied in the graphical feature models into ASP programs. This way we want to emphasize the role of ASP as a means to tackle the feature configuration problem. 1
Introduction
Features and feature models [
Software product line variability, and consequently, feature
models, can grow large and complex. Due to the combinatorial explosion,
analyzing feature models and finding a valid feature configuration is
infeasible to do manually with large-scale feature models [
In the field of mechanical and physical products, configuration has
a long and successful history as a basis for mass-customization, see,
e.g., [
As a supporting tooling, Answer Set Programming (ASP) is an
increasingly important formalism for the representation of
configuration models. Configuration is one of the first applications of ASP
solving; the requirements of configuration problems were taken into
account already in the development of the early ASP tool Smodels
[
The two disciplines of software product lines and configurable
products have similar goals and challenges in the variability
management [
RQ1: How can the feature configuration problem be stated through ASP? RQ2: What are the different ways to represent a feature model diagram as an ASP program? RQ3: What are the synergies in the variability management between feature modeling and product configuration?
Figure 1 illustrates the strategy that this paper utilizes to answer the research problem and questions. In particular, it shows how the graphical feature diagrams are represented with textual languages, and these textual languages are then automatically translated to ASP programs. Since the same graphical feature model can be represented both with the textual feature modeling language (Kumbang) as well as with the product configuration language (PCML), it is possible to compare and identify conceptual similarities and differences between software variability management and product configuration.
Moreover, the figure illustrates the strategy of utilizing intermediate level languages: this omits the need to manually write ASP programs directly, and consequently, any inherent cognitive difficulties.
The contributions of this paper are the following. Firstly, we adapt
the existing work [
The remainder of this paper is organized as follows. Section 2 lays
out the background as a previous work. Section 3 defines the
feature configuration task and problem with ASP. Section 4 shows how
graphical feature models can be represented as ASP programs by
translating them through a textual feature modeling language called
Kumbang (cf. Figure 1). Section 5 demonstrates that the same
graphical feature model can be represented by Product Configuration
Modeling Language (PCML) and its translation to ASP. Section 6
discusses the similarities of the software variability and traditional
product configuration. Section 7 concludes.
2
2.1
A feature in a feature model can be seen as a characteristic of a
system that is visible to the end-user [
Given a set of features, a feature model represents the variability
and relations of those features. A feature model is represented as a
hierarchically arranged set of features that consists of relations between
a parent (or compound) feature and its child features (or subfeatures)
and cross-hierarchy constraints [
At least four basic relations between parent and child features can
be identified [
Secondly, a child feature can be optional in relation to its parent feature, for example, feature GPS can either be selected or left out for all mobile phones. Thirdly, a set of child features can be alternative in relation to their parent feature, which means that exactly one of the child features must be selected when the parent feature is in the product. As an example, exactly one of features Basic, Colour, and High resolution must be present in the product that has feature Screen. Fourthly, a set of child features can be in or relation to their parent feature, which means that one or more of them are present in the product that has the parent feature; this is exemplified by features Camera and MP3 in Figure 2.
Additionally, there can be cross-hierarchy constraints. For example, features GPS and Basic are mutually exclusive, which means they cannot be in the same product, whereas feature High resolution must always be included in a product that contains feature Camera. These constraints are presented as annotations in Figure 2.
Various feature models and extensions to basic feature models
have been proposed, as discussed in [
Firstly, there can be feature models with attributes [
Secondly, there can be feature models with cardinality [
The usage of feature models varies from an informal
documentation or visualization to more rigorous usages enabling even
automated analysis. Respectively, the research has matured from the early
notations [
Answer Set Programming
As summarized in [
ASP makes it possible to express the problem as a theory
consisting of logic program rules with clear declarative semantics, and the
stable models, i.e., the answer sets of the theory correspond to the
solutions to the problem [
Programs that follow the Answer Set Programming paradigm are
a generalization of normal logic programs. A generalized and
unified syntax of ASP programs called ASP-Core-2 has been defined
[
Optimality criteria, variables and built-in functions can be defined.
The syntax of ASP programs is close to Prolog, but the computation
method via model generation is different [
There are a number of ASP solvers available, see [
The competition tasks included 3 problems in complexity class P , 15
problems in N P , 3 problems Beyond-NP (P2P ), and 5 optimization
problems; the domains of the tasks include combinatorial, database,
diagnosis, graph, planning and scheduling problems. An example of
current, well performing set of tools is Potassco, the Potsdam Answer
Set Solving Collection[
The authors of this paper have applied weight constraint rule
language (WCRL) that is almost a genuine subset of ASP-Core-2. The
languages ASP-Core-2 and WCRL are compatible enough so that the
concrete WCRL logic programs generated by our tools are valid
input to systems based on ASP-Core-2. This was verified with Clingo
version 4.3, available from [
In the following, we describe the basic concepts of weight constraint rules focusing on the concepts needed in the rest of the paper.
Instead of explaining the concepts utilizing a running example, these
concepts are exemplified for Kumbang in Section 4 and for PCML in
Section 5. For further details and examples, please see [
Cardinality constraints are used as the primary basic building blocks of the product configuration rules. Cardinality constraints are of the form
lfa1; : : : ; an; not b1; : : : ; not bmgu where l and u are the lower and upper bounds of the constraint.
Basic atoms are the smallest lexical units, for example a, or b. A literal is an atom b or a not-atom not b. A cardinality constraint is satisfied by a set of atoms S if the number of those literals in fa1; : : : ; an; not b1; : : : ; bmg that are satisfied by S is between the bounds l and u.
A constraint rule is an expression of the form
C0 :- C1; : : : ; Cn where the body of the rule consists of a number of cardinality constraints Ci, and the head C0 cannot contain negated atoms. A program P is then a set of constraint rules.
For product configuration, the following rules are often useful.
Firstly, in choice rules the number of satisfied atoms in the head must be between l and u:
lfa1; : : : ; angu :- C1; : : : ; Cn Secondly, a rule with an empty head yields an integrity constraint :- C1; : : : ; Cn, that is, an unsatisfiable constraint that allows specifying inconsistent situations where finding the answer is not possible.
Finally, a rule with an empty body is called a fact. For example, a fact C0 states that C0 is always true.
Given a set of atoms S, a rule C0 :- C1; : : : ; Cn is satisfied iff S satisfies C0 whenever S satisfies each of C1; : : : ; Cn. A program P is satisfied by S if each rule in P is satisfied by S. A stable model or answer set of a weight constraint rule program is defined as a set of atoms that 1) satisfies the program (is a classical model of the program) and 2) every atom in a stable model is justified (grounded) by the rules in the program. For example, consider the logical formula b ^ (b ^ :c ! a) that has three (classical) models fb; cg, fa; bg and fa; b; cg. The answer set program
b: a :- b; not c:
has one stable model fa; bg. For the formalization of this definition,
refer to [
Variable-free ground weight constraint rules discussed up to now become more practical by allowing the use of variables, function symbols, and predicates. A rule with variables is treated as a short hand for all its ground instantiations with respect to the Herbrand universe of the program. Decidability is retained by allowing only domain-restricted rules. Ignoring the details, each variable in a rule must appear in a domain predicate which occurs positively in the body of the rule. For example, p(X) :- q(X) over constants fa; b; cg is an abbreviation of
p(a) :- q(a); p(b) :- q(b); p(c) :- q(c)
Given predicates and domains, rules with the so called conditional literals are frequently applied in product configuration. For example, a fact with predicate chair and domain predicate member states that every board must have exactly one chair that must also be a member:
1 fchair(X) : member(X)g 1: 3
Feature Configuration Problem Utilizing ASP
Research question RQ1 identified the need to address the feature
configuration problem with ASP. In order to utilize ASP and existing
solvers (see Section 2.2), one needs to define the basic concepts of the
feature configuration problem. Figure 4 defines the feature
configuration problem. Here, we adapt the definition of [
Definition of the feature configuration task. Given CM a feature configuration model CM translated to a set
of rules, GF a set of ground facts representing the types in CM and
unique identifiers for the instances of types, and R a set of rules R representing requirements, is there a feature configuration C, that is, a stable model of CM [ S, such that C satisfies R?
Firstly, a feature configuration model CM in Figure 4 specifies the entities, such as features; their properties, such as feature attributes; and composition structure, i.e. the feature tree structure; and the rules how the entities and their properties can be combined in a proper manner for a valid product. More informally, a feature configuration model represents the variability in the product line. For example, the feature model in Figure 2 is represented as one configuration model CM .
Within the definition in Figure 4, a distinction is made between types in a configuration model and instances in a configuration.
Types in a configuration model define the properties of their individuals that can appear in a configuration. For example, in Figure 2, feature type storage defines the different attributes and their values, whereas feature instance storage in the actual product has a specific value for the size, for example 16 GB.
Ground facts GF in Figure 4 describe the possible feature instances and the attribute values of instances that can exist in a feature configuration. For example, for the feature Storage in Figure 2, a ground fact featStorage(i). indicates that feature instance with a unique identifier i is of feature type Storage. Additionally, a ground fact hasattr(i,attrsizeGB,16). tells that this instance has a specific attribute value assignment to indicate 16GB storage.
The set of rules R define requirements thus having a different status from the rules in the configuration model: these requirements represent the requirements that a specific product instance must satisfy.
In a valid product configuration, the requirements must be satisfied by a configuration but cannot justify any elements in it. For a feature configuration problem, the requirements are stated as features that must be present in the configuration, or as attribute values that these features have. For example, for Figure 2, one requirement could be stated as hasattr(i,attrsizeGB,16)., meaning that there must be 16 GB storage in the product.
A feature configuration C consists of a set of positive and negative atoms. Positive atoms represent the feature instances and attribute values that are in the configuration. Due to the characteristics of ASP and stable models discussed in Section 2.2, the feature instances and attribute values in the configuration C, that is, the positive atoms in C, both satisfy the configuration model and its requirements, and are justified by them. For example, among the atoms that would be in the feature configuration for Figure 2, an atom in(i) indicates the inclusion of feature Storage. Further, if the storage is set to 16GB, an atom hasattr(i,attrsizeGB,16) is true, while atoms representing other attribute values, such as hasattr(i,attrsizeGB,32), are false.
Consequently, the feature configuration C in the definition above is both consistent and complete. Informally, a consistent feature configuration is such that no rules of the configuration model are violated. A complete feature configuration is such that all the necessary selections have been made.
An ASP solver can be used to find consistent and complete configurations that meet a set of given requirements, given that such configurations exist. Therefore, the configuration problem definition above and its ASP solution can be used to support both domain and application engineering activities. At the domain engineering level, it can be checked whether the given feature configuration model CM doesn’t have any consistent and complete configurations, which implies a self-contradictory model. At the application engineering level, the configuration task can support the finding of consistent and complete configurations, potentially even specifying the requirements R in an iterative manner.
For supporting the user in the configuration task, deducing the consequences of requirements is based on computing an approximation of the set of configurations satisfying the requirements that are valid but not necessarily all consequences are found. Intuitively, the consequences contain a set of facts that must hold for the configurations satisfying the requirements, a set of facts that cannot be true for the given requirements, and a set of unknown facts.
From the practical point of view, a product line engineer needs to capture the product line features and their commonality and variability into a configuration model CM . There are two options for this representation. The first option is to represent the informal feature model, for example, the visual notation in Figure 2, directly as an ASP program. However, this kind of a modeling task requires skills in logic programming, which may not be the case with an average product line engineer. The second option is to capture the feature model with a machine-processable, but human-readable textual language that utilizes directly the concepts known to a product line engineer, and then automatically translate the resulting middle-level model to an ASP program. This translation to ASP also gives the semantics to the middle-level representation language, as well as enables the use of existing ASP solvers for the configuration task. As is illustrated in Figure 1, this paper takes the latter approach.
In the following, we discuss how feature models can be represented as ASP programs, and consequently, how to represent the configuration model CM . 4
Representing Feature Models as ASP Programs
through Textual Feature modeling Language
Section 3 presented the feature configuration problem utilizing ASP
programs and identified the need to represent a given feature model
as an ASP program. In the following, we show how the graphical
feature model in Figure 2 and the basic feature modeling concepts
can be represented as ASP programs. This is done in two phases,
as illustrated in Figure 1: firstly, Section 4.1 shows how the feature
model is represented as a textual model in Kumbang, and thereafter
Section 4.2 shows how the textual model in Kumbang is translated to
WCRL automatically with the Kumbang tool set [
Representing the Feature Model in Kumbang
In order to enable the feature configuration with ASP, the feature
model in Figure 2 needs to be represented in a form that is both
understandable to a product line engineer, and can be unambiguously
translated to an ASP program. For this purpose, we utilize
Kumbang language [
Figure 5 illustrates how the feature model in Figure 2 is represented with Kumbang language. In the following, we discuss the main characteristics and differences to the notation used in Figure 2.
Firstly, to adhere to the definition of the feature configuration task
in Figure 4, Kumbang differentiates between a configuration model
and a configuration. Variability in features is modelled explicitly in a
configuration model (illustrated in Figure 5), whereas in a
configuration, all variability has been resolved. The elements in a configuration
model are referred to as types (for example, feature type Storage in
Figure 5), while the elements in a configuration are referred to as
instances. In contrast, traditional feature modeling notations do not
usually make the conceptual distinction between feature types and
instances. However, this may cause some difficulties in situations in
which the definition of the features needs to be distinct from the
feature compositional hierarchy. For example, if features need to be
referred to in several places in the hierarchy (c.f., [
Secondly, traditional feature modeling uses a number of
compositional relations between features, such as mandatory, optional, and
alternative. As illustrated in Figure 3, the multitude of these
relations can be expressed with one relation: cardinality. In order to
define such relations in the configuration model, the cardinality needs
a placeholder in the textual notation: such a placeholder in Kumbang
is called a part definition. For example, the part definition Media
media[
Representing the Kumbang Model in WCRL
Figure 6 illustrates how the feature model in Figure 5 is translated to
WCRL. The translation has been performed automatically with the
Kumbang tool set [
Firstly, each feature type in the configuration model must be defined: for example, fact featureType(featMobilePhone). states that object constant featMobilePhone represents a feature type.
Similarly, the attribute value types are defined, for example, fact attrSize(8). states that attribute value type named Size has 8 as one possible value.
Secondly, the root of the model must be defined. Rule 1fin(F ) : f root(F )g1: tions can be more complex: For example, part definition apps in states that if feature type F is the root, a valid configuration must type feature Media has two possible types of which one or two need have exactly one feature instance selected (in(F)) that is instantiated to be in a configuration, and if two are selected, they need to be diffrom the root type, defined using predicate froot. nfhaspart(X1; X2; P ) : ppart(X1; X2; P; I)gm :- F (X1); in(X1): where F and P are replaced with feature and part names, and n; m replaced with the lower and upper bounds of the cardinality. Predicate haspart is used to indicate that a feature instance is instantiated as a part in the configuration, whereas predicate ppart is merely stating the possible parts. Together, these predicates justify the inclusion of a feature instance through composition:
in(X2) :- haspart(X1; X2; N ); ppart(X1; X2; N; I): Fourthly, attribute definitions are captured with the following rule:
1fhasattr(X; Ad; V ) : Av(V )g1 :- in(X); F (X): where Ad is replaced with the name of the attribute definition, Av with the name of the attribute value type, and F with the name of the defining feature type.
Finally, the configuration model must also define the identifiers for each feature instance. This enables, for example, to state requirements R about the features that must be present in the configuration (see Figure 4). In Figure 6, the feature instances are given identifiers by enumerating all possible instances in the configuration, for example, fact featMobilePhone(i0). gives identifier i0 to feature MobilePhone. Additionally, the identifiers are used to state the possible compositional relations between the instances with the predicate ppart. Using these identifiers, it is possible to state the requirements about the feature instances that must be in the configuration, for example, in(i8). requires that feature Camera must be present in the configuration. 5 Representing Feature Models as ASP Programs through Product Configuration modeling
Language In this Section, the example feature model of Figure 2 is represented with a configuration modeling language designed to model the variability of physical products. We also exemplify the corresponding ASP presentation. 5.1
Representing the Feature Model in PCML
For illustrating the application of a configuration modeling language,
we apply PCML, Product Configuration Modeling Language [
PCML is used by the WeCoTin configurator [
The main concepts of PCML are feature types, their compositional structure, attributes, and constraints. Feature types define the subfeatures (parts) and attributes of their individuals that can appear in a configuration. In a configuration, subfeatures (parts) of a feature individual are realized with feature individuals. The realizing feature individual(s) “fill the role” created by the subfeature definition. If the cardinality includes 0, an empty realization is possible. A configuration is a non-empty tree of feature individuals and individuals representing attribute values. In addition, the compositional structure is explicitly presented.
The main modeling mechanism of this example is the compositional structure. Feature type Mobile Phone t in 7 serves as the root configuration model MyProduct feature Mobile_Phone_t subfeature Screen_p allowed features
Basic_t, Colour_t, High_resolution_t cardinality 1 subfeature Calls_p
allowed features Calls_t cardinality 1 subfeature GPS_p
allowed features GPS_t cardinality 0 to 1 subfeature Media_p
allowed features Media_t cardinality 0 to 1 subfeature Storage_p
allowed features Storage_t cardinality 1 constraint GPS_excludes_Basic not ((present(
GPS_p)) and (Screen_p individual of Basic_t)) feature Basic_t feature Colour_t feature High_resolution_t feature Media_t subfeature Camera
allowed features Camera_t cardinality 0 to 1 subfeature MP3
allowed features MP3_t cardinality 0 to 1 constraint Camera_requires_High_resolution
(present(Camera)) implies ($config.Screen_p individual of High_resolution_t) constraint Media_requires_Camera_or_MP3
(present(Camera)) or ( present ( MP3 ) ) constraint Camera_and_Mp3_require_min_32GB ((present(Camera)) and (present(MP3))) implies ($config.Storage_p.Size_GB >= 32) feature Camera_t feature MP3_t feature GPS_t feature Calls_t feature Storage_t attribute Size_GB value type integer
constrained by $ in list(8,16,32,64) configuration feature Mobile_Phone_t of the compositional structure ’configuration type’, see Figure 7. An individual of the type serves as the root of the configuration.
Feature type Mobile Phone t defines it’s compositional structure through a set of subfeature definitions. A subfeature definition specifies a subfeature name, a non-empty set of possible subfeature types (allowed types for brevity) and a cardinality indicating the valid number of subfeatures. Note that the example of Figure 7 applies a naming convention where the names of feature types end with t and names of subfeatures (parts) with p.
A mandatory subfeature is represented by specifying cardinality 1 and by specifying exactly one allowed type. An example is the mandatory feature Calls p. An optional subfeature is modeled with a subfeature definition whose cardinality is 0 to 1, e.g. the feature GPS p. Alternative features are modeled with cardinality 1 and more than one allowed type. E.g., feature Screen p. Or-subfeatures are not directly supported by PCML, because with large cardinalities individuals of the same type would be allowed. Therefore for modeling Media t, further subfeatures were defined and a constraint added that enforces the presence of at least one subfeature.
The only attribute of the example is Storage t defining an enumerated integer attribute Size GB.
Representing the PCML Model in WCRL Figure 8 shows a partial WCRL/ASP representation of the example feature model. When studying the WCRL/ASP presentation of Figure 8, it is visible that early versions of PCML and WeCoTin applied terminology where feature types were called component types and subfeatures were called parts.
Figure 8 shows the corresponding WCRL presentation (partial).
The comments explain the predicates. For a more complete
explanation, see [
Figure 9 shows one of the 52 answer sets. It represents a feature configuration with Colour, Calls, Storage, Storage size=16 GB. % if an individual C2 is as part of C1 -> in(C2) in(C2) :- pa(C1,T,C2,Pn), ppa(T,C1,C2,Pn). % exclusive parthood: same individual cannot % be a part of several whole individuals :- 2{pa(C1,T,C2,Pn):ppa(T,C1,C2,Pn)}, compT_Feature(C2). %transitivity of is-a hierachy isa(X,Z):- isa(X,Y), isa (Y,Z),
compTDom(X), compTDom(Y), compTDom(Z). % reflexivity of is-a isa(X,X):- compTDom(X). %Example types % Screen_t is a component type and a subtype of ’Feature’ compTDom(compT_Feature). %Screen types are direct subtypes of ’Feature’ compTDom(compT_Basic_t). compT_Feature(C) :- compT_Basic_t(C). isa(compT_Basic_t,compT_Feature). compTDom(compT_Colour_t). compT_Feature(C) :- compT_Colour_t(C). isa(compT_Colour_t,compT_Feature). compTDom(compT_High_resolution_t). compT_Feature(C) :- compT_High_resolution_t(C). isa(compT_High_resolution_t,compT_Feature). % Storage_t compTDom(compT_StoraStorage_t). compT_Feature(C) :- compT_Storage_t(C). isa(compT_Storage_t,compT_Feature). % attribute Size_GB of Storage_t 1{prop_Storage_t_Size_GB(X,compT_Storage_t,Y):prSpec(Y)}1
:- in(X),compT_Storage_t(X). prSpec(8). prSpec(16). prSpec(32). prSpec(64). %part name Screen_p pan(part_Screen_p). %cardinality 1 1{pa(C1,compT_Mobile_Phone_t,C2,part_Screen_p): ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p)}1 :
in(C1),compT_Mobile_Phone_t(C1).
% assignment of possible part individuals of allowed
% types for part screen_p with helper predicate for.
% The automated translation makes such an allocation
% for symmetry breaking, which this example
% does not need
ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p)
:compT_Mobile_Phone_t(C1),compT_Basic_t(C2),
for(compT_Mobile_Phone_t,C1,C2,part_Screen_p).
ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p)
:compT_Mobile_Phone_t(C1),compT_Colour_t(C2),
for(compT_Mobile_Phone_t,C1,C2,part_Screen_p).
ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p)
:compT_Mobile_Phone_t(C1),compT_High_resolution_t(C2),
for(compT_Mobile_Phone_t,C1,C2,part_Screen_p).
% Constraint compilation omitted for brevity.
% it is performed by subexpression.
6 Discussion
In this paper, we showed two ways to represent feature models as
ASP programs by utilizing existing textual modeling languages
designed for feature modeling and product configuration modeling. The
use of an intermediate, textual language between the graphical
feature models and logic programs is not that common: it seems
typical that graphical feature diagrams are directly translated, e.g., to
propositional logic [
The benefit of using such intermediate languages and models is that they may be more approachable to product line engineers: they utilize modeling concepts that more or less directly correspond to the concepts used to represent software variability. Such intermediate languages can serve a multitude of purposes: they can be represented graphically and modelled with the aid of graphical tools; they can be created or edited directly if need arises; and they can be automatically translated to ASP programs.
Another option would have been to directly represent or encode the entities and relations in feature models as ASP programs. The benefit of writing directly ASP programs is that the resulting ASP programs most probably are more compact and directly humanreadable. The drawback is that logic programming even in the form of ASP programs might be challenging for a product line engineer not trained in computational logic programming.
For simplicity, our representation in this paper covered some basic concepts of feature models. Nevertheless, the languages discussed in Sections 4 and 5 cover much richer sets of modeling constructs.
For example, the capability to represent feature inheritance was not utilized in the examples. Similarly, the literature contains numerous proposed extensions of feature models. Some of them are included in our conceptualizations and corresponding tools (e.g. attributes, cardinalities) while some are not. In any case, a detailed discussion about the needed modeling concepts is a future work item.
By mapping the feature modeling notation to both Kumbang and PCML, we demonstrated that both approaches, one tailored for feature modeling and one for product configuration, can be utilized for modeling software variability. A specific addition to the traditional feature modeling concepts done in this paper is to differentiate between feature instances and feature types. This dichotomy, however, parallels with domain and application engineering in software product families and is, therefore, quite natural for software variability although it has not been applied explicitly in feature modeling.
The product configuration community has applied configuration modeling and configuration techniques in full scale production use for decades. It may be that some modeling constructs and approaches related to managing variability could be carried over to describe and analyze feature models. In such a case, existing analyses and respective tools could be readily utilized.
However, the derivation of product lines is not just about configuration: feature models are applicable to a wide range of settings, not just to configurable software product lines. Because of this, the tools intended for product configuration do not necessarily support all the relevant activities in the application engineering phase of software product lines.
In general, due to the availability of a variety of different
efficient ASP solvers, it seems beneficial to represent feature models
as ASP programs. Despite the fact that the theoretical computational
complexity inherent in the feature configuration problem is NP-hard,
the current ASP solvers are efficient in calculating the stable models
even for programs that represent real-life feature models. We believe
that it is more important to find and utilize real problems in testing
scalability instead of generated random problems. Consequently, we
have configured real problems interactively, without no noticeable
delay: see the configuration model with slightly less than 500
variation points [
This is one concrete step towards better unification between these two similar disciplines of research.
Acknowledgment We acknowledge the financial support of TEKES as part of the Need 4 Speed (N4S) program of DIGILE and the Austrian Research Promotion Agency (Casa Vecchia, 825889).
Integrating Distributed Configurations
with RDFS and SPARQL Gottfried Schenner1 and
Stefan Bischof1 and
Axel Polleres2 and
Simon Steyskal1;2 Abstract. Large interconnected technical systems (e.g. railway networks, power grid, computer networks) are typically configured with the help of multiple configurators, which store their configurations in separate databases based on heterogeneous domain models (ontologies). In practice users often want to ask queries over several distributed configurations. In order to reason over these distributed configurations in a uniform manner a mechanism for ontology alignment and data integration is required. In this paper we describe our experience with using standard Semantic Web technologies (RDFS and SPARQL) for data integration and reasoning. 1
INTRODUCTION
Product configuration [
For large interconnected systems (e.g. railway networks, power grid) the configuration of the overall system may be stored across separate databases, each database containing only the information for a sub-system.
The domain models and databases of these configurators are a valuable source of information about the deployed system. But there must be a way to access the information in an uniform and integrated manner in order to exploit this.
Figure 1 shows a typical scenario from the railway domain. The individual stations of a network are built by different vendors (A, B, C). Vendors A and B use proprietary configurators (A, B) and store the configurations of these stations in separate projects. Vendor C does not use a configurator, therefore there is no (digital) data available to integrate.
In the railway scenario the railway company owning the railway network wants to obtain information about the whole network in a vendor-independent way. To achieve this, some form of ontology and data integration is necessary. We can identify three steps: (i) create a vendor-independent ontology, (ii) map or align the vendor-specific ontologies or schemas to the vendor-independent ontology, and (iii) provide the vendor-specific data in terms of the vendor-independent ontology.
This paper investigates, how to use standard Semantic Web technologies (RDFS, SPARQL and OWL) for data integration. Our approach uses SPARQL CONSTRUCT queries to generate a linked system view of the distributed configurations as depicted in Figure 2.
This system view can then (i) be queried in a uniform manner, (ii) be checked for contraint violations taking all relevant configurations into account and (iii) be used for reasoning and general consistency checks (cf. Figure 3). 1 Siemens AG Österreich, Siemensstrasse 90, 1210 Vienna, Austria
{gottfried.schenner|bischof.stefan}@siemens.com 2 Vienna University of Economics & Business, 1020 Vienna, Austria {axel.polleres|simon.steyskal}@wu.ac.at
The remainder of this paper is structured as follows: Chapter 2 discusses the preliminaries of this paper, especially the used Semantic Web technologies. Chapter 3 introduces the working example of this paper, Chapter 4 shows how to derive an integrated view of the system from the individual configurator specific databases, in Chapter 5 we discuss, how to reason about the overall system with SPARQL queries and we discuss related work in Chapter 6. Finally, we conclude our paper in Chapter 7. 2
PRELIMINARIES The proposed approach builds heavily on Semantic Web standards and technologies. Instance data is represented as RDF triples, domain models are mapped to domain dependent ontologies/vocabularies and queries are formulated in SPARQL. 2.1
Data representation with RDF
The Resource Description Framework (RDF) [
In RDF every resource is identified by its URI and represented as subject - predicate - object triples, where subjects and predicates are URIs and objects can either be literals (strings, integers, . . . ) or URIs as shown in Figure 4. Additionally, subjects or objects can be defined as blank nodes, these blank nodes do not have a corresponding URI and are mainly used to describe special types of resources without explicitly naming them. For example the concept mother could be represented as a female person having at least one child. 2.2
Querying with SPARQL
SPARQL Protocol And RDF Query Language (SPARQL) [
Besides basic query operations such as union of queries, filtering,
sorting and ordering of results as well as optional query parts,
version 1.1 extended SPARQL’s portfolio by aggregate functions (SUM,
AVG, MIN, MAX, COUNT,. . . ), the possibility to use subqueries,
perform update actions via SPARQL Update and several other heavily
requested missing features [
Furthermore, it is possible to create entirely new RDF graphs based on the variable bindings constituted in graph patterns which are matched against one or more input graphs, using SPARQL CONSTRUCT queries. Using such CONSTRUCT queries offers the possibility to easily define transformations between two or more RDF graphs/ontologies, which serves as a basic building block for the present paper. 2.3
Semantic heterogeneity
In order to be able to integrate two or more ontologies into one
integrated knowledge base, it is mandatory to define correspondences
between the elements of those ontologies to reduce semantic
heterogeneity among the integrated ontologies [
The problem of semantic heterogeneity can be caused by several
facts, e.g. that different ontologies model the same domain in
different levels of precision or use different terms for the same
concepts [
Nevertheless, based on the absence of ontology matching tools which are capable of detecting such complex correspondences, we assume the presence of already known correspondences between entities of the ontologies for our integration scenario. 3
WORKING EXAMPLE As working example4 a fictitious computer network is used and represented as UML class diagrams. Figure 5 shows the customer view (system view) of the network.
The following additional constraints hold for the system view: In the computer network every computer has a unique address A computer can be part of 1-2 subnets
A computer is part of exactly one project 3 All listings within this paper are serialized in Turtle syntax. 4 The example ontologies and queries are available upon request from the first
author. A project is some arbitrary subdivision of the whole network (e.g. building)
A subnet can be part of multiple projects In the example there are 2 vendors (A and B), each providing their own configurator. A project can be configured either with configurator A or configurator B. In both cases there is one configurator database for every project. None of the domain models contains the concept of a subnet as found in the system view.
Figure 6a shows the domain model of configurator A. In the domain model of configurator A computers are called devices. Internal devices are the devices configured in the current project. External devices are devices of other projects that are directly connected to a internal device. These are needed to configure the network cards of the internal device.
Figure 7a shows the domain model of configurator B. Vendor B realizes the computer network with switches. Computers can have 1 or 2 ports, which must be connected to a port of an switch. The attribute external is set to ’true’ for elements that are external to the current project. 3.1
Converting object-oriented models to
ontologies
Although using Description Logics for configuration has a long
history [
This conversion captures the bare minimum that is required for our
data integration approach. See [
Listing 1 shows a fragment of the class model of Figure 6a and the instance data of Figure 6b in RDF & OWL5.
Listing 1: Ontology A with instance data # object model ontoA : Device rdf : type owl : Class . ontoA : InternalDevice rdf : type owl : Class ;
rdfs : subClassOf ontoA : Device . ontoA : Device_address rdf : type 5 For the sake of simplicity, we omitted owl:DatatypeProperty and respective project definitions. UML class C C1 extends C attribute A assoc A(C1,C2) object O of class C attributevalue A for every tuple(O1,O2) in assoc A
RDF/OWL URI(C) rdf:type owl:Class .
URI(C1) rdfs:subClassOf URI(C) .
URI(A) rdf:type owl:DatatypeProperty , owl:FunctionalProperty ; rdfs:domain URI(C); rdfs:range TYPE(A) .
URI(A) rdf:type owl:ObjectProperty; rdfs:range URI(C1); rdfs:domain URI(C2) .
URI(O) rdf:type URI(C) .
URI(O) URI(A) VALUE(A) .
URI(O1) URI(A) URI(O2). owl : DatatypeProperty , owl : FunctionalProperty ; rdfs : domain ontoA : Device ; rdfs : range xsd : unsignedInt . ontoA : Device_slot1Connected rdf : type owl : ObjectProperty ; rdfs : range ontoA : Device ; rdfs : domain ontoA : Device . # instance data ontoA : A1 rdf : type ontoA : InternalDevice ; ontoA : Device_address "1" ^^ xsd : unsignedInt ; ontoA : Device_slot1Connected
ontoA : A2 , ontoA : A3 ; ontoA : Device_slot2Connected
ontoA : B3 , ontoA : B4 . ontoA : A3 rdf : type ontoA : InternalDevice ; ontoA : Device_address "3" ^^ xsd : unsignedInt ; ontoA : Device_slot1Connected
ontoA : A1 , ontoA : A2 . ontoA : B1 rdf : type ontoA : ExternalDevice ; ontoA : Device_address "4" ^^ xsd : unsignedInt ; ontoA : Device_slot1Connected
ontoA : B2 , ontoA : A1 . ontoA : B2 rdf : type ontoA : ExternalDevice ; ontoA : Device_address "5" ^^ xsd : unsignedInt ; ontoA : Device_slot1Connected
ontoA : B1 , ontoA : A1 . 3.2
Unique Name Assumption and Closed World
Assumption When converting the instance data of a configurator to RDF an identifier (URI) for every object must be generated. Most product configurators impose the Unique Name Assumption, i.e. objects with different object-ID refer to different objects of the domain. In the example above we therefore know that ontoA:A1 and ontoA:A2 refer to different Devices.
RDF/OWL does not impose the Unique Name Assumption. This is a desirable feature when reasoning about linked data. If one wants to integrate instance data from different sources using heterogeneous ontologies, these ontologies will often refer to the same entity under different URIs. The same can happen, when we integrate multiple interconnected configurations into one configuration.
Figures 6b and 7b show the configurations of two projects (A and B). Although every computer/device is only represented once in each configuration, some computers/device are known in both projects (a) Ontology A
(b) Instance data of Project A i.e. the ExternalDevice ontoA:B1 and the Computer ontoB:B1 are referring to the same real world object under different URIs.
As a pragmatic solution for the Unique Name Assumption for this paper all URIs are treated as different, unless explicitly stated by owl:sameAs.
Similar considerations apply to the Closed World Assumption. In a configurator database one assumes that all components relevant to the current context are known. For instance in our example all the computers in the current project are known and one can use the Closed World Assumption to conclude that there are no other internal computers. The same applies to external computers that are directly connected to a internal computer. But we cannot apply the Closed World Assumption to the whole computer network, since we have no information about how many projects and computers there are in total. 4
DATA INTEGRATION WITH SPARQL
We followed an approach proposed in [
Creation of the system view As a first step in our data integration approach a system view of the configurator specific instance data is created. This system view reflects the view of the owner of the configured system and is completely self contained i.e. does not contain any URIs of the domain specific ontologies. To derive the system view from the proprietary configurator data we use SPARQL CONSTRUCT queries. Figure 6b shows a configuration of configurator A, Figure 7b shows a configuration of configurator B. The projects of the two configurations are connected via the subnet containing A1(C1), B1(C4) and B2(C5). 4.1.1
Creating instances To map an instance of the source ontology to a new instance of the target ontology we can either generate a new URI in the namespace of the target ontology or use blank nodes.
The following example (cf. Listing 2) creates a computer in the system ontology for every device of the source ontology A by creating a new unique URI using a unique identifier of the target object (in this case the attribute address).
One advantage of using that approach is that for every instance only one URI will be created in the instance data and the order of Open Configuration: a New Approach to Product
Customization
Linda L. Zhang1 and Xiaoyu Chen*1, 2 and Andreas Falkner3 and Chengbin Chu2 Abstract.1 State-of-the-art product configuration enables companies to deliver customized products by selecting and assembling predefined configuration elements based on known relationships. This paper introduces an innovative concept, open configuration, in order to assist companies in configuring products that correspond exactly to what customers want. Superior to product configuration, open configuration involves both predefined configuration elements and new ones in configuring customized products. As a first step, this study explains the concept of open configuration and the basic principles. It also discusses in detail the challenges involved in open configuration, such as conceptual model development, open configuration optimization, and open configuration knowledge representation. 1
INTRODUCTION
With the advancement of design and manufacturing technologies,
customers are no longer satisfied with standardized products. They
increasingly demand products that could satisfy their individual
needs. As a result, companies need to timely offer customized
products at affordable costs to survive [
Product configuration has received much attention from
industrial and academia alike. Researchers have approached
product configuration from different perspectives and have
developed diverse methods, methodologies, approaches, and
algorithms to solve different configuration issues and problems. In
spite of the diversities among these solution tools, they are
developed based on a common assumption: the configuration
elements, such as components, modules, attributes, functions, and
their relationships are predefined. In relation to this assumption, the
products that can be configured are known in principle even if not
explicitly listable [
This study proposes an innovative concept ‘open configuration’ in order to help companies configure such products that can meet both predefined and unforeseen customer requirements, that is, to meet customer requirements as complete as possible without making too much compromise (see Section 2). In this regard, in configuring customized products, open configuration deals with not only the addition of new configuration elements, such as functions, components, but also the modification of existing configuration elements, more specifically components. Existing component modification is to accommodate the integration of new components with the predefined ones.
In the rest of this paper, Section 2 uses a fridge configuration example to illustrate the limitation of product configuration, i.e., the product configured lie in a known range in accordance with the predefined components. Section 3 introduces the concept of open configuration, its basic principles, and its process. Section 4 sheds lights on the challenges involved in open configuration. We end the paper in Section 5 by pointing out the ongoing research that we are working on. 2
PRODUCT CONFIGURATION
As a special design activity, product configuration capitalizes on
design results, such as components, attributes and their
relationships [
Take fridge configuration as an example. Assume in this example, there are 6 component types, including Refrigerator (R), Freezer (F), Freezer drawer (Fd), Variable compartment (V), Base (B), Outer casing (O). Each component type is defined by a set of attributes (number, size, price) and each attribute can assume a number of values. Table 1 summarizes these component types, the attributes, and attribute values.
For example, NR : (1, 2) represents the number of Refrigerators in one fridge can be 1 or 2; SR : (small, medium, large, extra-large) indicates the component Refrigerator has four different sizes: small, medium, large, extra-large. Price mentioned hereinafter states the price of the configured fridge.
There are relationships among components, among attributes, and between components and attributes. For examples, {SR large, NF 1} {SF small} means if one large sized Refrigerator and one Freezer are selected, the size of the Freezer is small; NFd 0 {NR 2, SR medium} states that if the component Freezer drawer is selected then two medium Refrigerators are required. The other relationships include: {SR medium, NF 0} NR 2 ; {SF small, SR small} NV 1; {SR extra-large, NF 1} {SF extra-large} ; {SF extra-large} {SB wide, SO wide} ; {NV 1,NF 0} {NR 1, SR large,SV small} ; {SR small, NF 1} {SF large} .
There are four additional rules, including (1) (NR NV NF ) 3 , meaning the total number of Refrigerator, Variable compartment, and Freezer in one fridge should be no more than 3, (2) NR 2 NV NF 0 , indicating if two Refrigerators are selected, the number of Freezer and Variable compartment is zero, (3) NFd NF 0 representing that Freezer cannot be selected together with Freezer drawer, and (4) NFd NV 0 indicating that Freezer drawer cannot be selected together with Variable compartment.
According to the above pre-defined components and their relationships, only 17 fridge configurations are available as possible solutions. While Fig. 1 shows 8 fridge configurations due to the space issue, different positions of components in Fig. 1.c, Fig. 1.d, Fig. 1.e, Fig. 1.f, and Fig. 1.g lead to the other 9 fridge configurations. All customized fridges to be configured based on customer requirements fall into this range of configuration solutions. (Note: Fridges from the left to the right are arranged based on the increase of price.) Take fridge f in Fig. 1 as an example to explain the components and their attributes in the configuration solution. This fridge configuration is represented as FCf {R :1,small ; V :1,small ;F :1,small ;B :1,standard ; O :1,standard} .
It has one small Refrigerator on top, one small Variable compartment in the middle, one small Freezer at the bottom, one standard Base, and one standard Outer casing.
Refrigerator
Refrigerator
Freezer
Variable compartment
Freezer Refrigerator Refrigerator
Refrigerator Refrigerator
Refrigerator Variable compartment
Freezer
Freezer
Refrigerator a b c d e f g
h Refrigerator Refrigerator
Freezer drawer
Suppose the requirements from a customer include a cheaper fridge with a freezer and a large refrigerator. In accordance with these requirements, the constraints can be modeled as {R :1,large; NF 1; min P} . The configured fridge must satisfy these constraints and additional rules mentioned earlier while fulfilling the customer requirements. In this regard, the constraints {R :1, large} and {NF 1} limit the possible choices to: {FCc , FCe} , i.e., the configuration solutions shown in Figs. 1.c and 1.e. The cost constraint {min P} indicating the minimal price results in the final solution to be FCc {R :1,large ; F :1,small ; B :1,standard ;O :1, standard } .
As only predefined elements are involved, product configuration fails to provide customized products in a true sense or provides these products which can meet unforeseen customer requirements. Take the above fridge configuration as an example.
Suppose that the requirements from another customer include any of the following: a fridge consisting of only one medium refrigerator, a fridge consisting of 2 freezers, an outer casing with a special color, and a cheaper fridge to be moved easily and with at least one
freezer drawer.
In general, the first two requirements violate some predefined constraints (although the first one requires a new - lower - type of outer casing as a side-effect); the last two introduce new concepts.
In more detail, the third requirement requires a new attribute value for the component outer casing. The last one is more complex. A part of it, i.e., being cheaper and with one freezer drawer, can be fulfilled by the predefined functions and components, while the rest cannot be fulfilled by the available functions, thus calling for a new function: ‘to be movable’. This new function, in turn, needs new components, such as ‘wheels’, ‘brakes’, etc., which are necessary for delivering this function. Because of the lack of these components, product configuration can provide the customer with one of the fridges shown in Fig. 1 without satisfying all his requirements. The customer, thus, has to accept this fridge by making compromise (e.g., accept a cheapest fridge with a freezer drawer, which cannot be moved easily). 3
OPEN CONFIGURATION In order to help companies configure customized products that correspond exactly to what a customer requires, this paper puts forward the concept of open configuration. The basic principle and general process of open configuration are introduced below. Built on top of product configuration, open configuration is to configure customized products to meet customer requirements in a true sense. Similar as product configuration, it utilizes design results, selects components, and arranges the selected components according to constraints and rules. In extension to product configuration, it involves new component design, more specifically the specification of functions and the selection of the corresponding components. In addition, it deals with the modification of the predefined components, which allows the integration of new configuration elements.
Open configuration overview and process Open configuration involves two types of knowledge: predefined knowledge and dynamic knowledge. Predefined knowledge relates to predefined functions, components, and relationships; dynamic knowledge is associated with newly defined elements. In relation to these customer requirements, which can be fulfilled by the predefined functions (i.e., Type Ⅰ requirements in Fig. 2), the corresponding components are selected, while for these requirements, which cannot be fulfilled by the predefined functions (i.e., Type Ⅱ requirements in the figure), new functions and corresponding components are specified. The specification of these new configuration elements contributes to the extension of the dynamic knowledge. The relationships among the predefined elements and the newly defined elements are specified as well.
This specification contributes to the interaction between the predefined knowledge and the dynamic knowledge. By respecting the constraints embedded in both the predefined and dynamic knowledge, all necessary components are selected, modified, and arranged into a customized product.
Type Ⅰ requirements
Type Ⅱ requirements
Predefined knowledge Dynamic knowledge Customer requirements
Customized products
In more detail, suppose that given customer requirements are valid, complete and do not conflict with one another. These requirements are evaluated first to determine whether or not they can be fulfilled by the available configuration elements (i.e., functions and components). According to the evaluation results, these requirements are classified into Type Ⅰ and Type Ⅱ requirements. Fig. 3 summarizes this process. carried out. The selected components are arranged into product configuration alternatives by following the product structure described in the dynamic and predefined knowledge. These configuration alternatives are further evaluated under certain criteria. Based on the evaluation results, the optimal one or multiple are suggested to customers. 4
CHALLENGES INVOLVED IN OPEN
CONFIGURATION In accordance with the involvement of new configuration elements, open configuration changes the basic assumptions and reasoning processes of product configuration. In this regard, there are a number of potential challenges involved in open configuration.
Due to the page limitation, this paper discusses five of these challenges, including open configuration modeling, system design and development, open configuration solving, open configuration optimization, and open configuration knowledge representation.
Open configuration modeling Open configuration modeling addresses the modeling of open configuration knowledge and the reasoning mechanism for using the configuration knowledge. The modeling of open configuration knowledge is to model configuration elements, constraints, and rules. It involves two kinds of knowledge: predefined knowledge and dynamic knowledge. A product model and corresponding functional architectures should be developed for defining and further classifying the two different types of knowledge. The modeling of the reasoning mechanism is to shed light on (1) how new functions are specified, (2) how new components are determined, and (3) how components are selected and arranged into products.
In open configuration modeling, the components and functions are characterized by their attributes, while the inter-connections among the components are represented by connections and ports.
The modeling of the dynamic knowledge needs to take into account the fact that new functions and components are added based on the unforeseen customer requirements. Thus, its modeling involves newly-added concepts, constraints, and rules. The modeling of the predefined knowledge needs to consider these predefined components, modified components, and their relationships. The interaction between predefined knowledge and dynamic knowledge needs to be modeled as well.
Open configuration modeling is more sophisticated than
configuration modeling due to the involvement of the dynamic
knowledge. In this regard, it is interesting to see whether or not
these techniques which are suitable for modeling product
configuration (e.g., Unified Modeling Language (UML), Alloy,
and generative Constraint Satisfaction Problem (CSP) [
If these techniques are not feasible, new modeling formalisms and constructs are to be developed. 4.2
System design and development System design and development for open configuration refers to the design and development of the computer information system to implement open configuration, i.e., open configurators. Open Components arrangement Configured alternatives evaluation Customized products Customer requirements evaluation
Type Ⅰ requirements Yes
All required configuration elements available No Type Ⅱ requirements
New functions specification
New components specification
For Type Ⅱ requirements, new functions are specified and all possible components which can realize these functions are subsequently determined. Also specified are the relationships among functions, among components, and between functions and components. This process contributes to the extension of the dynamic knowledge. For Type Ⅰ requirements, all possible components are selected from the predefined ones. In addition, to be compatible with the newly introduced components, some predefined components are modified by respecting constrains and rules embedded in the predefined and dynamic knowledge. This process reflects the interaction between the dynamic and predefined knowledge. From the modified components, newly introduced components, and selected predefined components, suitable components are further selected for forming configuration alternatives, which can meet customer requirements. In the selection, consistency and compatibility evaluations might be configurators consist of a customer input module which deals with customer requirements evaluation, open configuration knowledge bases, reasoning and evaluation mechanisms, optimization and diagnosis mechanisms, and an output module which communicates the configuration results with users. Different from product configurators, open configurators involve two knowledge bases: a knowledge base for the predefined knowledge and the other for the dynamic knowledge. Joint reasoning mechanisms between the two knowledge bases are required, which mainly associate with interacting and integrating elements from the two knowledge bases.
For the dynamic knowledge base, new elements design modules are needed to develop and maintain this knowledge base. The new elements design modules include the module for specifying new functions with respect to the requirements, the module for selecting new components to fulfill new functions and the module for interfacing with the predefined elements. For the predefined knowledge base, different from product configurators, there need to be a modification module for modify existing components to be compatible with the new ones.
In designing and developing open configurators, the techniques should have the ability to model dynamic knowledge and the interaction between dynamic knowledge and predefined knowledge. In this regard, the available system design techniques for product configuration may need to be modified in designing and developing open configurators. 4.3
Open configuration knowledge
representation Open configuration knowledge representation entails the effective organization of open configuration knowledge, including the predefined and dynamic knowledge. It logically uniforms the open configuration knowledge and enables the utilization of the knowledge in different configuration tasks.
The representation of open configuration knowledge includes the representation of predefined components, relationships, constraints and rules; the representation of newly-added components, relationships, constraints and rules; and the representation of the constraints and relationships between predefined knowledge and newly added knowledge. From the experience of the knowledge representation for product configuration, open configuration should be considered as both a classification problem (i.e., capturing the aspects of taxonomy and topology) and a constraint satisfaction problem (i.e., capturing the aspects of constraints and resource balancing). Considering the dynamic and indeterminate feature of open configuration, it might be potentially challenging to capture different aspects of open configuration knowledge (e.g., taxonomy, topology, constraints, and resource balancing) in one model. Further studies may try to design new models (or sub models to be embedded in the available tools) separately on each aspect and joint them together to represent the knowledge. 4.4
Open configuration solving Open configuration solving relates to the development and application of algorithms or other tools to solve open configuration problems. In solving an open configuration problem, the problem needs to be modeled first with respect to customer requirements and configuration rules. To solve this model, algorithms need to be developed subsequently.
In the situation that customer requirements demand new functions, the dynamic knowledge will be specified. The modeling of open configuration problem will associate with the interaction between the customer requirements and two types of knowledge (predefined knowledge and dynamic knowledge). The main difficulties are (1) the modeling of new function specification, (2) the modeling of new components selection according to the customer requirements, (3) and the modeling of the interaction between new components and selected existing components. After modeling an open configuration problem, suitable algorithms need to be developed to solve the model. Because of the differences between product configuration and open configuration and the corresponding differences between a product configuration model and an open configuration model, these algorithms, which are suitable for product configuration solving, may not be applicable for open configuration solving. Thus, new algorithms are to be developed. 4.5
Open configuration optimization During each step of open configuration, optimal functions, components and structures need to be specified from a number of alternatives. The dynamic feature of open configuration increases the degree of difficulty in optimizing the new functions, new components, and the interaction between new components and predefined ones. In this regard, an explicit optimization mechanism needs to be developed.
In accordance with the open configuration process discussed earlier, the optimization mechanism should evaluate the configuration elements at three levels. In the first level, the mechanism should evaluate all the possible function alternatives for fulfilling Type II requirements and decide on the optimal ones.
This optimization might be based on, e.g., the performance and completeness of these function alternatives. In the second level, the mechanism should evaluate all the possible component alternatives for delivering the determined new functions and decide on the optimal ones. This optimization may take into account, e.g., the compatibility among the new components and the interaction with predefined components. In the third level, the mechanism should evaluate all the product configuration alternatives and decide on the optimal ones. This optimization may consider, e.g., product reliability. 5
CONCLUSION In response to the limitation of product configuration, this paper proposed open configuration to help design customer-driven product in a true sense. It introduced the concept and process of open configuration. It also discussed several challenges involved in open configuration. Currently, we are working on the formulation of open configuration. In the formulation, new components, relationships among new components, and relationships between new components and existing components will be defined and modeled. This formulation is to rigorously define open configuration and shed light on the reasoning behind open configuration.
Towards an understanding of how the capabilities deployed by a Web-based sales configurator can increase the benefits of possessing a mass-customized product Chiara Grosso1 and
Alessio Trentin 1 and
Cipriano Forza 1 Abstract. Manufacturers that adopt mass customization are paying a growing attention to understanding not only how product customization can be delivered efficiently, but also how this strategy can create value for their customers. As reported in literature, the customer-perceived value of a mass-customized product also depends on the uniqueness and self-expressiveness benefits that a customer may experience above and beyond the traditionally considered utility of possessing a product that fits with the customer’s functional and aesthetical needs. Increasing customer-perceived value by delivering uniqueness and selfexpressiveness benefits can therefore be one key in augmenting the customer’s willingness to pay for a mass-customized product. This paper conceptually develops and empirically tests the hypotheses that five sales-configurator capabilities previously defined in literature increase uniqueness and self-expressiveness benefits of a mass-customized product, in addition to the traditionally considered utilitarian benefit. The hypothesized relationships have been tested by analyzing self-customization experiences made by engineering students using a set of real Web-based sales configurators of different consumer goods. The analysis results show that easy comparison, flexible navigation and focused navigation capabilities have a positive impact on each of the considered benefits, while user-friendly product space description and benefit-cost communication capabilities have a positive impact on utilitarian benefit only. The findings of this study complement previous research results on what characteristics sales configurators should have to increase consumer-perceived benefits of mass customization.
1
According to Pine [42, p.48] mass customization is defined as
‘‘developing, producing, marketing and delivering affordable goods
and services with enough variety and customization that nearly
everyone finds exactly what they want’’. Nowadays,
masscustomization strategies are more and more widespread and,
therefore, mass customizers may need to identify unexploited
sources of differentiation advantage [
In such a context, increasing the customer-perceived benefits of possessing a mass-customized product can be one key in delivering value that exceeds those of competing mass customizers’ offerings.
In particular, manufacturers that adopt mass customization need to
take into account the various benefits that consumers can experience
from mass-customization and the product value implication for
customers [
Since mass customizers are increasingly adopting Web-based sales configurators, it is important to understand what characteristics sales configurators should have to increase customer-perceived benefits of a mass-customized product. Previous research, however, has focused on how sales configurators should be designed to increase the traditionally considered utilitarian benefit of owning a selfcustomized product. The present paper offers additional insights into this issue by conceptually developing and empirically testing hypotheses on how capabilities deployed by a Web-based sales configurator can increase the benefits of possessing a masscustomized product. 2 Consumer perceived benefits of a masscustomized product
According to Holbrook [
Previous mass-customization studies on mass-customized
product value [
Utilitarian benefit, according to Merle et al. [
The uniqueness benefit of possessing a mass-customized
product is defined by Merle et al [
Self-expressiveness benefit is defined by Merle et al. 38] as the
benefit that originates from the opportunity to possess a product
that is a reflection of the consumer’s image. This is in accordance
with the self-consistency motive underlying self-concept, where
the term “self-consistency” denotes the tendency for an individual
to behave consistently with his/her view of his/her self [
Sales configurators
Consistent with previous research [
The benefits and challenges of implementing and using a sales
configurator have been the focus of several researches e.g., [
Another example is Chang et al.’s [
Previous studies on sales configurators, however, have typically
regarded the mass-customized product only as a source of utilitarian
benefits related to the fulfillment of customers’ functional and
aesthetical needs. As discussed in the previous section, however, a
mass-customized product can also be a source of benefits resulting
from uniqueness and self-expressiveness. What characteristics a
sales configurator should have to increase uniqueness and
selfexpressiveness benefits is therefore a question that deserves
additional research, as previously pointed out by Schreier [
Research hypotheses
In addressing the question raised at the end of the previous
section, we draw upon the five sales-configurator capabilities
conceptualized by Trentin et al.[
In the existing literature, a number of studies make the point that,
to increase the utilitarian benefit of possessing a mass-customized
product, a sales configurator should support a company’s potential
customer in learning about the options available within the
company’s solution space, in learning about how these options are
useful in fulfilling his/her preferences and in learning about his/her
preferences themselves e.g., [
Consequently, such a learning process also augments the uniqueness benefit that a customer will enjoy from the possession of the configured product. Finally, this also applies to product fit with an individual’s need for behaving consistently with his/her view of his/her self by possessing a product that reflects his/her self concept. Accordingly, such a learning process also increases the self-expressiveness benefit that a customer will derive from the product configuration eventually purchased.
Clearly, the more effective the learning process enabled by a
sales configurator, the greater the utilitarian benefit, the
uniqueness benefit and the self-expressiveness benefit of
possessing the configured product. While Franke and Hader [25,
p.16] find that the learning effects of single self-customization
experiences lasting only a few minutes with sales configurators
“that were not even specifically designed for learning purposes are
remarkable”, we argue that such learning effects are greater if a
sales configurator deploys a higher level of each of the capabilities
conceptualized by Trentin et al. [
A sales configurator with a higher level of flexible navigation
capability allows a potential customer to go through a greater
number of complete trial-and-error cycles to evaluate the effects of
his/her prior choices and to improve upon them. This is because
this kind of sales configurator allows its users to change, at any
step of the configuration process, the choice they made at any
previous stage without having to begin the process all over again
and allows them to immediately recover a previous configuration
in case they decide to reject the newly-created one [
A sales configurator with a higher level of user-friendly product
space description capability promotes a potential customer’s
learning process by increasing the congruence between the
challenges of the configuration task and the abilities of the
configurator user. This is because a sales configurator with this
capability presents product space information to potential
customers using the most suitable format (e.g., text, image,
animation,…) depending on their skill levels and cognitive styles
and offers different types of choices (e.g., among product
functions and performance levels rather than among product
components, or vice versa) according to the users’ prior
knowledge about the product [
A sales configurator with a higher level of focused navigation
capability increases learning effects by tailoring the sales
configuration experience to each individual user’s characteristics on
the interaction level [
A sales configurator with a higher level of benefit-cost
communication capability promotes a potential customer’s learning
process by providing him/her with better pre-purchase feedback on
the effects of his/her configuration choices. Such a sales
configurator is more effective in explaining the benefits the
customer would derive from consumption of the configured
product, as well as the monetary and nonmonetary sacrifices that
the customer would bear for obtaining that product [
Finally, a sales configurator with a higher level of easy
comparison capability increases learning effects by providing better
pre-purchase feedback on the effects of the configuration choices
made by a potential customer. This is because such a sales
configurator allows its users to compare previously-saved
configurations on the same screen and to rank-order them based on
some criterion that is meaningful to the users [
As each of the sales configurator capabilities mentioned above make the learning process more effective and the effectiveness of such a learning process increases the utilitarian benefit, the uniqueness benefit and the self-expressiveness benefit of the configured product eventually purchased, we posit the following hypotheses, which are graphically summarized in Figure 1.
HXa. The higher the level of flexible navigation capability (H1a), focus navigation capability (H2a), benefit-cost communication capability (H3a), user-friendly product space description (H4a), easy comparison capability (H5a) deployed by a sales configurator, the greater the utilitarian benefit that a consumer derives from a product self-customized using that configurator.
HXb. The higher the level of flexible navigation capability (H1b), focus navigation capability (H2b), benefit-cost communication capability (H3b), user-friendly product space description (H4b), easy comparison capability (H5b) deployed by a sales configurator, the greater the uniqueness benefit that a consumer derives from a product self-customized using that configurator.
HXc. The higher the level of flexible navigation capability (H1c), focus navigation capability (H2c), benefit-cost communication capability (H3c), user-friendly product space description (H4c), easy comparison capability (H5c) deployed by a sales configurator, the greater the self-expressiveness benefit that a consumer derives from a product self-customized using that configurator. 4
Method
To test our hypotheses we conducted an empirical analysis using data collected from a sample of 675 sales-configuration experiences made by 75 students at the authors’ university (age range: 24-27; 30% females). Each participant was asked to make one masscustomization experience on each of nine pre-assigned Web-based sales configurators and, for each experience, to fill out a questionnaire covering the constructs of interest (see Appendix A), for a total of 675 mass-customization experiences. Each experience involved browsing the sales-configuration website and configuring one product from start to finish, on that website, according to one’s own preferences. The nine sales configurators assigned to each participant were chosen from a set of 30 real Web- based configurators of consumer goods. The set included ten configurators of notebooks/laptops (e.g., www.dell.com), nine configurators of sports shoes/sneakers (e.g., www.converse.com) and eleven configurators of economy cars (e.g., www.volkswagen.com). The inclusion of multiple product categories, ranging from relatively simple products with relatively few configuration steps to more complex products with more configuration steps, was motivated by the aim of increasing the variation ranges of the independent variables within our sample. To further increase the differences among the mass-customization experiences comprising our sample, we assigned sales configurators to participants according to the following rules: (i) no pairs of participants were assigned the same combination of configurators, (ii) each participant was assigned three configurators for each product category, and (iii) each of the triples assigned to each participant included at least one product configurator with a high mean score of the five capabilities within the corresponding product category and at least one configurator with a low mean score of the five capabilities within the same product category.
The data were analyzed through structural equation modeling,
using LISREL 8.80. Following Anderson and Gerbing [
Discriminant validity, which measures the extent to which the
individual items of a construct are unique and do not measure other
constructs, was tested using [
Reliability of the measurement scales was assessed using both AVE
and the Werts, Linn and Joreskog (WLJ) composite reliability (C.R.)
method [
Results
After establishing measurement scale reliability and validity for the focal constructs, we estimated the full model including the hypothesized relationships among the same constructs. Our hypotheses were that all five sales-configurator capabilities increase consumer-perceived utilitarian benefit, uniqueness benefit and selfexpressiveness benefit of a mass-customized product. Accordingly, all five capabilities were modeled as impacting both utilitarian benefit and uniqueness benefit and self-expressiveness benefit.
Table 2 reports the LISREL estimates of the path coefficients and the corresponding t values. In assessing whether a hypothesis is supported or not, we adopted a p value of 5% as a threshold. This is a conservative choice, as a cut-off value of 10% is often used in literature.
As regards utilitarian benefit, all the estimated path coefficients were positive, as hypothesized, and statistically significant at p< 0.05, indicating that all our hypotheses regarding the utilitarian benefit are supported. As regards uniqueness benefit, the estimated path coefficients were positive, as hypothesized, and statistically significant at p< 0.05 for easy comparison, flexible navigation and focused navigation capabilities, but not for benefit-cost communication and user-friendly product space description capabilities. Therefore, only three of our five hypotheses are supported. The same pattern of results was found with regard to self-expressiveness benefit. It is worthwhile noting, however, that the estimated path coefficient between benefit-cost communication capability and self-expressiveness benefit is statistically significant at p< 0.10, though not at p< 0.05. 6
Discussion of results and related work
The analysis results support the hypotheses that easy comparison, flexible navigation and focused navigation capabilities raise not only the utilitarian benefit of possessing a mass-customized product, but also its uniqueness and selfexpressiveness benefits. These findings improve our understanding of how product configurators should be designed to increase customers’ willingness to pay for a mass-customized product by triggering uniqueness and self-expressiveness benefits, in addition to utilitarian benefit.
As regards user-friendly product space description and
benefitcost communication capabilities, however, only the hypotheses
that they increase utilitarian benefit are supported, while the others
are not. Two possible explanations can be provided for these
unexpected findings. One explanation revolves around the notion
of functional fixedness. Functional fixedness is the phenomenon in
which an individual finds difficulties in attributing and
recognizing different types of relationships between objects
presented to him/her during decision-making processes or
problem-solving situations [
The present paper contributes to the debate as to what
characteristics sales configurators should have to increase
consumers’ willingness to buy as well as consumers’ willingness to
pay for a mass-customized product. This debate has typically
focused on a twofold objective: (i) alleviating the difficulty that a
consumer experiences in self-customizing a product with a sales
configurator and in making a purchase decision and (ii) increasing
the utilitarian benefit deriving from the closeness of fit between the
objective characteristics of the configured product and the
consumer’s functional and aesthetical needs. Several
recommendations have been made by prior, both conceptual and
empirical studies joining this debate, and many of these
recommendations are subsumed by the five sales-configurator
capabilities considered in this study [
Related work has been conducted in the domain of recommender
technologies. Like Web-based sales configurators, recommender
applications are intended to support online customers in making
purchase decisions [
Interestingly, Felfernig et al. [
This result is echoed by our findings that benefit-cost communication, easy comparison and user-friendly product space capabilities predict the utilitarian benefit deriving from the possession of a mass-customized product.
Limitations and further research
The present research is not without limitations, which might be addressed in future research. A primary limitation lies in the fact the empirical study was conducted with engineering students and using only three categories of consumer goods. While engineering students are undeniably potential buyers of the considered products, they constitute a biased sample of the potential customers of such goods. In addition, these products represent only a small subset of consumer goods. A wider set of products would strengthen the generalizability of the results. Consequently, future research should seek to replicate our findings in truly representative samples of potential customers and should use a wider set of consumer goods.
Another limitation of the present study is its focus on the main
effects [
Managerial implications
While having its limitations, our study not only reinforces the importance of the research on the role of sales configurators in mass-customization strategies, but also provides useful managerial implications. By considering additional benefits, besides the utilitarian one, our study increases practitioners’ awareness that sales/product configurators can be an effective tool to augment the consumer-perceived benefits of possessing a mass-customized product. Exploiting such sources of differentiation advantages as the fulfillment of consumers’ needs for uniqueness and selfexpressiveness can be one key for a company to augment the value of its mass-customization strategy. For those firms that are interested in fulfilling consumers’ needs for uniqueness and selfexpressiveness, our theoretical explanations and our empirical results highlight the importance of adopting sales configurators with higher levels of easy comparison, flexible navigation and focused navigation capabilities. This is another step in the direction of providing practitioners with prescriptive indications on how sales configurators should be designed to increase the benefits of possessing mass-customized products.
ACKNOWLEDGEMENTS We acknowledge the financial support of the University of Padova, Project ID CPDA129273.
APPENDIX A. Measurement instrument Benefit-cost communication capability(a)
BCC1 Thanks to this system, I understood how the various choice options influence the value that this product has for me.
Thanks to this system, I realized the advantages and drawbacks of each of the options I had to choose from.
This system made me exactly understand what value the product I was configuring had for me.
Easy comparison capability(a)
EC1 The system enables easy comparison of product
configurations previously created by the user.
EC2 The system lets you easily understand what previously
created configurations have in common.
EC3 The system enables side-by-side comparison of the
details of previously saved configurations.
EC4 The systems lets you easily understand the differences
between previously created configurations.
User-friendly product-space description capability(a)
UFD1 The system gives an adequate presentation of the choice options for when you are in a hurry, as well as when you have enough time to go into the details.
UFD2 The product features are adequately presented for the user who just wants to find out about them, as well as for the user who wants to go into specific details.
UFD3 The choice options are adequately presented for both
the expert and inexpert user of the product.
Flexible navigation capability(a)
FlexN1 The system enables you to change some of the choices you have previously made during the configuration process without having to start it over again.
FlexN2 With this system, it takes very little effort to modify the choices you have previously made during the configuration process.
FlexN3 Once you have completed the configuration process, this system enables you to quickly change any choice made during that process.
Focused navigation capability(a)
FocN1 The system made me immediately understand which
way to go to find what I needed.
FocN2 The system enabled me to quickly eliminate from further consideration everything that was not interesting to me at all.
FocN3 The system immediately led me to what was more
interesting to me.
FocN4 This system quickly leads the user to those solutions
that best meet his/her requirements.
Utilitarian benefit(b)
UT1 This product is exactly what I had hoped for.
UT2 I could create the product that was the most adapted to
what I was looking for.
UT3 I could create the product I really wanted to have.
Uniqueness benefit(b)
UN1 With this product, I will not look like everybody else.
UN2 With this program, I could design a product that others
will not have.
UN3 With this product, I have my small element of
differentiation compared to others. Self-expressiveness benefit(b)
SE1 I could create a product that is just like me.
SE2 This product reflects exactly who I am.
SE3 This product is in my own image.
Towards Open Configuration Alexander Felfernig1 and
Stefan Reiterer2 and
Martin Stettinger1 and Andreas Falkner3 and
Gerald Ninaus1 and Gerhard Leitner 4 and
Michael Jeran1 and
Juha Tiihonen5
Abstract. Configuration technologies are typically applied in
closed settings where one (or a small group of) knowledge
engineer(s) is in charge of knowledge base development and
maintenance. In such settings it is also assumed that only single users
configure the corresponding products and services. Nowadays, a couple
of scenarios exist that require more openness: it should be possible
to cooperatively develop knowledge bases and to jointly configure
products and services, even by adding new features or constraints in
a flexible fashion. We denote this integration of groups of users into
configuration-related tasks as open configuration. In this paper we
introduce features of open configuration environments and potential
approaches to implement these features.
1
Configuration [
Most configuration-related functionalities are assuming closed
settings where knowledge bases are developed by a single (or a small
group of) knowledge engineer(s) and the corresponding
configurators are applied by single users. Implementing configurator
applications this way entails drawbacks which become manifest in terms of
scalability problems in knowledge engineering [
Scalability Problems. The transformation of domain knowledge
into a configuration knowledge base is an effortful process
often characterized by a knowledge acquisition bottleneck [
These approaches help to improve the efficiency of knowledge
engineering but still do not solve the problem of missing scalability:
the increasing amount and complexity of configuration knowledge
bases exceeds the resources available for performing the
corresponding development and maintenance operations [
Suboptimal Decisions. A basic assumption of existing configuration systems is that products and services are typically configured by single users. However, many scenarios exist where not a single user but a group of users is in charge of configuring a product (see Section 3). Existing configuration environments do not take into account such scenarios which often leads to situations where a single user has to ”encode” the requirements and preferences of a whole group.
This can lead to suboptimal configurations (decisions) that do not
reflect the group preferences in an optimal fashion. Future
configuration technologies should take into account the fact that groups of
users can be engaged in configuration processes and provide group
decision mechanisms that help the group to jointly configure a
product in a consensual fashion. We denote this type of configuration
as group-based configuration. Especially in scenarios where
multiple stakeholders define and configure products, enhanced flexibility
is required: configurator users may request to add or refine product
features and constraints which can be seen, for example, in open
innovation [
The concepts of community-based knowledge engineering,
groupbased configuration, and flexible product enhancement can be
summed up under the notion of open configuration. In this paper we
sketch functionalities which have to be provided by open
configuration environments. In Section 2 we introduce features and potential
technological solutions to tackle the issue of scalability in knowledge
engineering scenarios. In Section 3 we discuss features of
groupbased configuration. In Section 4 we discuss aspects of product
enhancement in open configuration. With Section 5 we provide a
discussion of related work. We conclude the paper with Section 6.
In the following we will discuss aspects that become relevant if we
want to integrate a larger group of users into configuration knowledge
engineering. For the sake of simplicity and without loss of
generality we assume that a configuration knowledge base is represented in
terms of a constraint satisfaction problem (CSP) [
V = fwillingness to take risks (wr), expected return rate (rr), investment period (ip)g dom(wr)= flow, medium, highg, dom(rr)=f<6%, 6-9%,>9%g, dom(ip) = fshortterm, mediumterm, longtermg micro task topic variables questions dialog sequences constraints examples diagnoses
description definition/evaluation of variables included in V definition/evaluation of questions related to vi 2 V definition/evaluation of question sequences definition/evaluation of constraints in C definition/evaluation of test cases in T evaluation of conflict resolution alternatives for C
In cases where one or a small group of knowledge engineers is
in charge of developing and maintaining a configuration knowledge
base, attributes (component types), domains, and related constraints
are typically formalized on the basis of examples and textual
descriptions provided by domain experts [
The correctness of changes performed on a knowledge base can be
evaluated, for example, on the basis of regression tests where positive
and negative test cases are used to figure out whether the knowledge
base shows the intended behavior [
Community-based Knowledge Engineering. Intelligent testing and
debugging [
In the following we discuss issues that have to be taken into account when integrating groups into community-based knowledge engineering processes. An in-depth integration of a larger group of users allows knowledge engineers to delegate basic engineering tasks (so-called micro tasks). Table 1 provides an overview of micro task topics. For each topic a couple of different concrete micro tasks can be defined, for example, a variable can be defined but also evaluated with regard to the appropriateness of it’s domain definition.
In order to figure out variables (component types) relevant for the configuration knowledge base, users should be allowed to enter proposals for variables and component types (including the corresponding domain definitions) on their own. Variables are often associated with questions posed to the user of a configurator application – alternative formulations of such questions and also the sequences in which these questions are posed should be defined and evaluated by users. In addition to structural properties typically defined in terms of variables or component types and their relationships, constraints define additional restrictions on possible combinations of variable values (components).
Especially in community-based scenarios, where a larger number of users interacts with the knowledge engineering environment, engineering practices will change in the sense that users are providing knowledge chunks in a collaborative fashion and the knowledge engineering environment is in charge of aggregating this information.
In this context, it is necessary to have mechanisms that automatically
distribute knowledge acquisition tasks among users in a systematic
fashion (e.g., depending on the workload, knowledge level, and
preferences of users). Such tasks can be represented in a more-or-less
traditional form of todo-lists but can also be represented in terms of
so-called games with a purpose [
A simple example of such a knowledge acquisition interface is depicted in Figure 1. In this example game, the users Ann and Paul have the task to cooperatively figure out combinations of customer requirements that are incompatible, i.e., induce an inconsistency with the knowledge base. The players have successfully completed their task if they, for example, selected the same set of assignments as candidates for incompatibilities. The underlying assumption of this game is that Ann does not know the input of Paul and vice-versa.
Further examples of gamification-based interfaces for configuration knowledge acquisition are: cooperative definition of relevant variables (including their domains), the estimation of intuitive dialog sequences (which questions should be asked in which order), the derivation of further constraint types (e.g., filter constraints that match user requirements to corresponding technical product properties), and the estimation of accepted repair rankings in situations where no solution could be found. Such scenarios can be supported by input templates that represent micro-tasks (see Figure 1).
Testing and Debugging. The definition and evaluation of
(positive and negative) test cases is a crucial issue since the correctness
of a test suite directly influences the correctness of the results
determined by a configurator. In [
A negative example is assumed to be integrated in negated form into the knowledge base in the case that it has not been rejected by the knowledge base. On the basis of the following two test cases (examples) we can show how positive examples are used to find errors in the knowledge base. Both test cases are in conflict with constraints
A conflict between a test case t and a set of constraints in the
configuration knowledge base can be defined as a conflict set CS C:
CS [ t inconsistent. Such a conflict set CS is minimal if there does
not exist another conflict set CS0 with CS0 CS. To resolve a
minimal conflict, only one element has to be deleted from CS. In
our example, the test case t1 is in conflict with the constraints c2 and
c3 and test case t2 is in conflict with the constraint c5. Consequently
we have two different (and minimal) conflict sets which are CS1:
fc2; c3g and CS2: fc5g. Resolving these conflicts results in two
different diagnoses, namely D1 = fc2; c5g and D2 = fc3; c5g, i.e., a
diagnosis is a hitting set [
Typically, there are many alternative diagnoses and the question has to be answered which of these is acceptable for the users engaged in testing and debugging. Figure 2 depicts a basic approach of integrating knowledge about the users expertise in the determination of a diagnosis. For the conflict CS1 = fc2; c3g, the majority of users prefers to keep c2 as-is and to delete or change c3 to resolve the conflict. Since CS2 is a singleton, no alternatives exist for resolving the conflict, i.e., c5 must be selected. Overall, the elements in the diagnosis D2 = fc3; c5g have a lower community support and therefore will be changed or deleted by the users in order to restore the consistency with the test-suite ft1; t2g. 3
Group-based Configuration An assumption of existing configuration environments is that there is no need for additional configuration support in scenarios where groups of users are jointly configuring their preferred product or service. A major consequence of this assumption is that single users are forced to encode the preferences of a group which is often done in a suboptimal fashion.
Within the scope of an industry study with representatives of N=25 companies applying configurators we figured out that none of the existing configuration environments provides technologies that support groups of users in jointly configuring a solution. However, there is a strong agreement on the fact that such technologies have to be included in future configurators. The study participants reported different scenarios for the application of group-based (socially aware) configuration technologies. Social awareness in this context denotes the fact that specific properties of group decision processes are explicitly taken into account by the configuration environment (e.g., software release plans product line scoping and open innovation bundle configuration (e.g., hotel, flight, tour, etc.) stakeholder selection for a new software project architectural design in software development financial service configuration building configuration (e.g. smart home, office block) funding decisions components and constraints requirements, releases, dependencies, preferences (new) features, constraints between features, preferences (new) destinations, hotels, sightseeing tours, (resource) constraints, preferences (new) persons, constraints regarding competences and resources, preferences components, interfaces, technologies, constraints between components, preferences financial services, resource constraints, preferences rooms, furniture, light control equipment, constraints between components, preferences project proposals, resource constraints, preferences decision makers stakeholders in software project representatives from different departments, customers travel group (initial) team members (distributed) software project members family members family members, suppliers, company representatives evaluators, consultants, decision makers the need to achieve consensus among group members). Examples of such scenarios are depicted in Table 2.
In these scenarios a group of users is in charge of jointly
configuring a product or service, for example, when configuring a holiday
trip (bundle configuration) for a group of friends [
Taking into account requirements and preferences of group members requires decisions regarding trade-offs. In the context of holiday trips such a trade-off could be the acceptance of a lower-quality hotel which is much nearer to the sightseeing destination preferred by a specific user. When configuring software release plans, a trade-off could concern the postponement of a specific requirement to a later release while increasing the importance level of this requirement (to avoid further postponements).
The determination of trade-offs must be based on preference
aggregation mechanisms [
An example of the application of the least misery strategy in the
context of deciding about a common sightseeing trip is depicted in
Table 3. In this simplified example, each person is allowed to select
at most two destinations and the corresponding trip must include two
destinations. Since Ben and John have similar preferences, majority
voting would discriminate Kate. In contrast, least misery tries to find
a trade-off that has the potential to create group consensus. For a
detailed discussion of preference aggregation mechanisms we refer
the reader to [
A major issue for future research is the consideration of longer time periods. For example, if a group of friends jointly configures a holiday trip every year, the aggregation mechanisms used by the group-based configuration environment should take into account (as far as possible) the degree to which individuals had to accept tradeoffs in the past and use this information for the recommendation of fair trade-offs in future configuration sessions.
On the technical level the above mentioned properties require basic research in the following areas.
First, constraint-based search methods have to be extended with
mechanisms that help to predict (partial) configurations which are of
relevance for the group. This requires learning methods for search
heuristics [
Second, the determination of trade-offs for inconsistent
requirements and preferences has to be based on efficient diagnosis
methods integrated with intelligent preference aggregation mechanisms
[
Third, negotiation and argumentation mechanisms have to be developed which support individuals to express acceptable trade-offs.
In our holiday configuration scenario an example of such a statement is ”I accept to visit Greece this year if we agree to organize a trip to Italy next year”. Such arguments cannot be expressed on the basis of existing preference representations. The ability to include additional variables (component types), values (components), and constraints in a flexible fashion is important for the implementation of open configuration. destination Ben John
Kate least misery majority voting 1 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0
Product line scoping [
Open innovation [
A further example of the need for flexible enhancements are
postponement strategies [
Related and Future Work
Intelligent testing and debugging methods for configuration
knowledge bases have been introduced in [
Bessiere et al. [
Human Computation is based on the idea of passing those tasks to
humans which are easy to solve for them but are not solvable by
computers [
Preferences are not known beforehand but are constructed within
the scope of a decision process [
On the basis of the results of a first industry study we reported example application domains and discussed related research challenges.
The concepts presented in this paper can be applied in a broad range
of scenarios which go beyond open configuration. Further example
application domains are (constraint-based) scheduling [
ACKNOWLEDGEMENTS The work presented in this paper has been conducted in the research project PEOPLEVIEWS funded by the Austrian Research Promotion Agency (843492).
REFERENCES