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

Part III. Advanced Topics

Chapter 11. Knowledge Engineering for Configuration Systems

Gerhard Friedrich^a, Dietmar Jannach^b, Markus Stumptner^c and Markus Zanker^a, ^aAlpen-Adria Universität Klagenfurt, Klagenfurt, Austria, ^bDortmund University of Technology, Dortmund, Germany, ^cUniversity of South Australia, Adelaide, SA, Australia

Abstract

Developing a product configuration system is a nontrivial and challenging task for various reasons. First, the domain knowledge that has to be encoded into the system is often spread over several departments or functions within a company. Besides that, in many cases data from existing information systems have to be integrated into the configurator. Finally, the business rules or technical constraints that define the space of possible configurations can be relatively complex and also subject to frequent changes. This makes acquiring and encoding domain knowledge as well as testing and debugging particularly demanding tasks.

In this chapter, we give an overview of the challenges when developing a knowledge-based configuration system. We will particularly focus on questions related to the knowledge acquisition process and will additionally show how model-based debugging techniques can be applied to support the knowledge engineer in the testing and debugging process.

Keywords

Knowledge-based Configuration; Development Life Cycle of Configurators; Debugging of Configuration Knowledge Bases; Organizational Challenges

11.1 Introduction

Product configurators are knowledge-intense and complex software systems whose design, development, and implementation within a company is a challenging and demanding undertaking throughout the whole software life cycle. Even if an off-the-shelf and generic configuration problem-solving framework or a constraint engine such as the one described by Mailharro (1998) is used as a basis for the configurator application, there are still several aspects that contribute to the complexity of the overall development process.

Since we are only interested in nontrivial configuration systems, we will start from the premise that a knowledge-based approach is chosen. Thus, the configuration knowledge has to be represented by some form of logic, declarative rules, or constraints. In contrast to standard software development processes, a “knowledge engineering” phase (as an introduction to this topic, see Studer et al., 1998) has to be part of the life cycle. In this phase, the desired configuration logic has to be modeled using the given knowledge representation mechanism of the configurator framework. The elicitation and error-free formalization of the knowledge however requires the tight cooperation between the domain expert and a knowledge engineer, where the latter needs to establish a link between the business and technologists. One of the problems in that context is that there might be several departments in a company that have an influence on the set of configurations that can be offered to a customer. Beside technical restrictions due to, for instance, component incompatibilities or logistics, also sales and marketing considerations might determine the range of allowed configurations. Overall, a large number of stakeholders and knowledge sources have to be involved in the process. Another issue in the knowledge acquisition process is the question of the choice of appropriate tools and representations mechanisms. In modern software engineering processes, conceptual modeling approaches such as OMG’s Unified Modeling Language¹ or Domain-Specific Languages (DSLs; Fowler, 2010) are common in industry today. These graphical (domain) models are not only used in the software design phase, but should also serve as a basis for the communication between the requirements of engineer or system analyst and the domain experts. In Section 11.2, we will focus on these issues in knowledge acquisition and present a recent approach based on conceptual modeling in more detail.

Besides the noted differences in the knowledge acquisition and design phase, the declarative nature of the knowledge-based development approach also influences the required test and maintenance processes. Standard debugging approaches based on breakpoints, variable inspection, or stepping through execution traces cannot be applied to most reasoning engines, which, for example, implement automatic backtracking search, rule inferencing, or constraint propagation. Even though some commercial configuration tools such as the constraint-based one described in Junker (2001) provided an explanation facility that goes beyond simple propagation traces, the debugging and (regression) testing support is mostly very limited in today’s configuration systems. Note that this situation is particularly problematic because in many domains, the configuration knowledge bases are subject to frequent changes, such as, for instance, the telecommunication domain (e.g., Fleischanderl et al., 1998 or Felfernig et al., 2002). In Section11.3, we will discuss a recent and generic method for debugging declarative knowledge bases based on model-based diagnosis techniques. It is particular about this method that it is not limited to one single type of configuration reasoning and that it relies on partial and complete test cases in the error location process. This makes the method also naturally applicable for regression testing.

The final aspect is related to the development process of configuration systems and deals with embedding the knowledge engineering effort into the whole process of implementing a mass customization strategy. As already noted, configuration knowledge-bases are usually not defined from scratch by a single domain expert in collaboration with a knowledge engineer but a variety of organizational and business issues are related to this effort. The integration of the configuration process into the companies’ business processes, for instance, sharing of existing components and assemblies within product family architectures as well as cost, schedule, and volume targets will involve a number of different stakeholders and experts from within an organization. Furthermore, lifetime aspects of a configuration application such as evolution of product architectures and maintenance of the configuration knowledge request attention to documentation systems and knowledge management. Consequently, we will briefly discuss these organizational aspects in Section 11.4 and point to related work for further study.

11.2 The Configurator Development Life Cycle

One of the first steps when developing a configurator application is to collect and organize the required domain knowledge. When following a knowledge-based approach, the knowledge has to be formalized based on the knowledge representation mechanism of the configuration problem solver, a phase which does not exist in standard software engineering processes.

In the knowledge acquisition process, a knowledge engineer or system analyst has to identify the different stakeholders and sources of information. Many pieces of information may already exist in some other software system however. Information about different aspects of a component for example may be available in the company’s ERP system; calculations for the pricing process may be found in spreadsheet applications. This issue of embedding the configurator development into the organization’s processes will be further addressed in Section 11.4. Regarding the planning process for the development cycle, note that in some domains, it might be necessary that the configurator application has to be developed in parallel with the configurable product in order to support integration testing (Fleischanderl et al., 1998). In these situations, the knowledge to be acquired may still be unstable and continuously changing. Consequently, the choice of the right knowledge acquisition techniques is crucial. In this section, therefore we will focus on aspects of how to acquire the configuration model in a correct and efficient way.

11.2.1 Experiences from Early Expert Systems

One of the earliest knowledge-based, large-scale configurator applications was DEC’s R1 (XCON) rule-based “configurer” for VAX-11/780 computer systems (McDermott, 1982). Besides the fact that this was also one of the first expert systems successfully implemented in industry, it is also one of the few applications where an experience report regarding engineering and implementation issues has been published after 10 years of practical use. In their report, Barker et al. (1989) identify various challenges when developing a large-scale configurator, many of which still apply today after more than 20 years of configuration system development in industry.

From the business and strategic perspective, one main problem then and still today is to establish an appropriate link between the business and the “technologists” (the configurator developers). This aspect is particularly important since offering configurable products on the market is a strategic decision and requires the coordination of several business functions. At DEC at that time, it was also important to have a strong commitment from management to build systems with then-innovative but immature expert systems technology, which additionally required long learning and training phases for newly-hired developers. Today, declarative technology and in particular constraint-based approaches have reached some level of maturity but are still far from being “standard” tools in industrial software development practices. Even though some approaches such as the one by Agarwal and Tanniru (1992) toward a structured development process for the case of rule-based systems have been made, the question of the proper integration of knowledge-based system development phases into standard software engineering processes (think, e.g., of testing of such systems) is still largely open today.

From the perspective of the application domain, Barker et al. (1989) identify the problems of volatility, scope expansion, and complexity. In their domain, about 40% of the rules changed per year. Scope expansion means that the system has become more and more integrated with other tools and was used by different business groups, so that various other systems had to be connected with the configurator and additional functionality was continuously required. Regarding the complexity aspect, Barker et al. report that the rule base comprised more than 10,000 rules after 10 years and that the component database contained more than 30,000 different parts.

11.2.2 Knowledge Representation Issues

The question of how configuration knowledge is represented has a strong influence on the knowledge acquisition and maintenance process. In the R1 system, the configuration logic was encoded by (IF-THEN-style) production rules. Today, such rule-based systems are no longer recognized as state-of-the-art in configuration systems or in knowledge-based systems development in general. Despite some approaches toward increasing the maintainability of rule-based systems, for example, through modularity (Davis, 1990), the maintenance of such systems is considered problematic in particular due to the possible side-effects of individual rules and that the rule application strategy determines their semantic interpretation. Another problem related to the maintenance of rule-based systems is the typical mixture of different types of knowledge in one rule-base (Studer et al., 1998), where domain knowledge (“component A is incompatible with component B”) is intermingled with knowledge that governs the solution search process (“try components of type A first”). In that context, note that due to the usually very large space of possible configurations, problem-solving heuristics still play an important role also in more recent approaches to building configurator applications. Such heuristics can include rules such as “fill a frame from left to right” in the telecommunication switch configuration problem (Fleischanderl et al., 1998) but also variable ordering or value selection strategies in constraint-based approaches. However, in constraint-based or preference-based approaches such as Mailharro (1998) or Junker and Mailharro (2003), this knowledge would be encoded differently than the compatibility constraints and does not have an impact on the set of possible configurations.

From the particular perspective of the configuration domain, another problem of rule-based systems is the limited correspondence between the structure of the knowledge base and the rule base. This missing correspondence is also one of the problematic aspects of systems that work with simple compatibility tables such as some small-scale commercial configurator solutions. Modern approaches to building configurator applications therefore commonly rely on the “component-port” model (Mittal and Frayman, 1989) in one or the other way. In that approach, a configurable system is always considered to be assembled from (configurable) components that can be connected to each other by pre-defined connection points called ports (see Hotz et al., 2014).² This general model is the basis for both constraint-based approaches such as Mailharro (1998) or Fleischanderl et al. (1998) or logic-based ones like McGuinness and Wright (1998), and conceptual-modeling based approaches (see, e.g., Felfernig et al., 2000a). The main advantage of the component-port model is that the modeled artifacts are often directly related to physical components, thus structuring the knowledge base and making it easier to comprehend and maintain for knowledge engineers.

11.2.3 The Importance of Frameworks and Tool Support

In the context of this chapter, we limit ourselves to knowledge-based approaches and at the same time assume that a preexisting configuration framework or reasoning engine (or “expert system shell” in former years) is used. Only in rare cases such as reported inFleischanderl et al. (1998), will companies be able to afford the development of a proprietary reasoning engine that is tailored to the specific requirements of the domain. In light of the many problems that can arise during knowledge engineering and maintenance, one should therefore not only pay attention to the efficiency or performance of the underlying reasoning engine but also to the availability of tools for knowledge acquisition when deciding on the technological basis for a configuration application.

A modern configuration framework should provide mechanisms that abstract from the underlying technical representation as far as possible in the modeling phase. Typical elements that can be found in such tools may for example include mechanisms such as compatibility tables that are understandable even by non-IT people, user-oriented rule languages including appropriate editing support, or graphical representations of bill-of-material structures. A framework for such mechanisms and the tool support that can be provided will be presented in Section 11.2.4. In addition, appropriate support for testing, debugging, and tracing should be included in the framework in order to facilitate its practical use. We describe such a framework in Section 11.3.

11.2.4 A UML-Based Approach

Having discussed the various issues in knowledge acquisition for configurator applications, we will describe the method from Felfernig et al. (2000a) for configurator development based on the Unified Modeling Language (UML) in this subsection. Figure 11.1 gives the general overview of the proposed development process.

FIGURE 11.1 Configurator development process adapted from Felfernig et al. (2000a).

The boxes in the figure show the different steps of the development process from product modeling to productive use. The support with appropriate mechanisms and tools for the development phases (1) to (4) is at the core of Felfernig et al.’s (2000a) proposal.

In phase (1), the knowledge engineer together with the domain expert uses the Unified Modeling Language to develop a model of the configuration problem.³ However, instead of using some proprietary configuration-specific representation format, the idea is to rely on UML as a graphical notation, which is a widely known and standardized language for conceptual modeling in standard software engineering processes. Since UML is a general language not tied to a specific application domain, Felfernig et al. (2000a)propose to provide the modeler with a predefined set of configuration-specific modeling concepts. The definition of these domain-specific extensions is based on profiles and stereotypes, UML’s built-in mechanism to create a domain-specific language.

In Section 11.2.2 we discussed the importance of appropriate problem-solving heuristics when reasoning about large-scale configuration problem instances. In many cases, this sort of fine-tuning the search process takes place at the final stages of the development process and at a low technical level based on the first experiences of running the system in production. If knowledge about effective search strategies is already available in the earlier development stages however, one could try to incorporate this knowledge also into the conceptual model. Being oriented toward the domain expert and knowledge engineer, the UML-based approach of Felfernig et al. (2000a) does not comprise modeling concepts for such heuristics. While there have been some proposals in the 1990s within the fields of Knowledge Acquisition and Knowledge-Based Systems that aimed at supporting the domain expert in formulating problem-solving knowledge at a more abstract or conceptual level, we see this problem as still largely open in the configuration domain.

For each domain-specific concept, such as, for instance, the concept component-type, a set of so-called well-formedness rules in the form of OCL (Object Constraint Language) constraints are provided, which describe how the modeling concept can be properly used. Since the proposed extensions and the OCL constraints are developed using the standard mechanisms of UML, off-the-shelf UML tools can be applied to check the syntactic validity of the configuration models in phase (2).

Subsequently, in phase (3), the conceptual models should be automatically translated into an “executable” representation, which can be interpreted by a configuration problem solver. This corresponds to the ideas of model-driven software development and automatic code generation in standard software development processes. In analogy to the Model-Driven Architecture (MDA),⁴ the conceptual models can be seen as “platform independent models.” The translation of the models into executable code however means that precise semantics for the given UML modeling concepts are required. In Felfernig (2007) and Felfernig et al. (2000a, 2000b) this definition of the semantics is made by describing for each modeling construct how it translates into a general logic-based formalization of the configuration problem. In order to demonstrate the applicability of the approach also for specific realizations of the component-port approach to configuration, a mapping of the conceptual models to the constraint-based representation of the commercial ILOG Configurator framework (Mailharro, 1998) has been implemented.

In phase (4), the resulting knowledge base should be validated based on test cases and expert knowledge, before it is set into productive use in phase (5). In order to support the knowledge engineer in this phase, a debugging approach for declarative configuration knowledge bases is proposed in Felfernig et al. (2004). The proposed method relies on model-based diagnosis techniques that were originally developed for the analysis of hardware components and electronic circuits. With the help of this method, the knowledge engineer is pointed to potentially erroneous statements within the knowledge base. Since there is a close correspondence between the knowledge base contents and the conceptual models through the automatic generation process however, the engineer can use these pointers to potential errors to fix the problems at the conceptual level and then repeat the process of knowledge base generation. We will discuss more details of the employed model-based diagnosis technique in the next section.

In summary, one of the key goals of the proposed approach, which is based on model-based development, declarative knowledge representation, and AI-based reasoning, is to decrease the required development, debugging, and maintenance efforts. An exact scientific quantification of potential cost savings when using different software engineering techniques or a model-based approach is hard in general. An anecdotal example is given in Fleischanderl et al. (1998), where the authors report that in their experience up to 20% of the product development cost in their domain usually goes into the development of the configurator software. Furthermore, they estimate that using a declarative, constraint-based approach helped them to reduce the costs for configurator development by up to 60%. A further indicator that the proposed concepts are valuable in practice is that some of them were implemented in commercial tools: The ILOG JConfigurator product of the mid-2000s, for example, included both a graphical modeling component similar to the UML-based structure diagrams from Felfernig et al. (2000b) as well as an algorithm for conflict detection and explanation, which are only possible in a declarative approach.

11.3 Debugging Configuration Knowledge Bases

In order to introduce the diagnosis of configuration knowledge bases, we employ a small part of the example introduced and illustrated in Hotz et al. (2014).⁵ All necessary axioms are presented to make the example self-contained. We illustrate our approach by introducing a typical error and subsequently demonstrate the application of model-based diagnosis methods to locate the faulty description. Based on this example we describe the basic concepts of model-based diagnosis and finally show their application to our introductory example.

11.3.1 Motivating Example

Let us assume that besides the components that were mentioned in the introductory example, there is also a universal motherboard that can be part of valid PC configurations. This motherboard allows a CPUD and a CPUS to be combined on one motherboard. Consequently, the configuration knowledge base ⁶ has to be extended by axioms⁷ that reflect these new configuration options. In particular, a class hierarchy formed by is-a relations between various types of motherboards can be modeled as follows. Every specialized motherboard is a motherboard (Axioms 1 to 3). The specialization is exclusive (Axioms 4 to 6). Finally, Axiom 7 expresses that every motherboard must be of one specific motherboard subtype. However, in Axiom 7 the knowledge engineer forgot to extend the consequent of the formula by MBUniversal. We denote the faulty knowledge base by .

(1) MBSilver(X) MB(X).

(2) MBDiamond(X) MB(X).

(3) MBUniversal(X) MB(X).

(4) MBSilver(X) MBDiamond(X) false.

(5) MBSilver(X) MBUniversal(X) false.

(6) MBDiamond(X) MBUniversal(X) false.

(7) MB(X) MBSilver(X) MBDiamond(X).

The correct Axiom 7 should read:

MB(X) MBSilver(X) MBDiamond(X) MBUniversal(X).

Furthermore, we declare that CPUD and MBSilver as well as CPUS and MBDiamond are incompatible, which is expressed by:

(8) CPUD(C) cpu-of-mb(C,M) MBSilver(M) false.

(9) CPUS(C) cpu-of-mb(C,M) MBDiamond(M) false.

After specifying the knowledge base the knowledge engineer will usually try to validate it with the help of test cases. When debugging configuration knowledge bases, we can distinguish between positive and negative cases. Positive cases are configurations that must be consistent with whereas negative cases have to be inconsistent. Stating it differently in logical terms, the negation of a negative case must follow from . In general, test cases can be either complete or incomplete. A complete test case comprises all relevant parts (such as components and connections) of a configuration whereas an incomplete test case specifies only parts of a configuration, which in case of a positive test case must be expandable to a complete configuration. Conversely, a partial negative test case declares a partial configuration that cannot be expanded to a complete configuration. Configurations as defined in Hotz et al. (2014)⁸ are complete. A test case is a logical sentence.

Let us consider the following example of a positive incomplete test case , which specifies that there must exist a configuration where a CPUD and a CPUS are on the same motherboard.

MB(m1) CPUD(c1) CPUS(c2) cpu-of-mb(c1,m1) cpu-of-mb(c2,m1).

A negative test case on the other hand specifies that a CPUD and a CPUS must not be mixed on silver and diamond motherboards.

CPUD(c1) CPUS(c2) (MBSilver(m1) MBDiamond(m1))

cpu-of-mb(c1,m1) cpu-of-mb(c2,m1).

Testing the given knowledge base with these two test cases results in an undesired contradiction— is inconsistent. In particular, Axioms 7, 8 and 9 are unsatisfiable when combined with . Consequently, one of these axioms must be changed when assuming that the test cases are correct. Note that apart from the faulty Axiom 7 also the correct Axioms 8 and 9 are involved in the contradiction. Therefore, at first sight one of these axioms might also be faulty. However, it will turn out that if we assume either Axiom 8 or 9 to be faulty, there must be an additional faulty axiom.

Let us first assume that Axiom 8 is faulty and all other axioms are correct. Axioms 7 and 9 combined with imply that motherboard is of type silver. Consequently, Axioms 7 and 9 and case imply . Remember, however, that must be inconsistent with the knowledge base. In other words, the knowledge base has to imply . Consequently, if we consider Axiom 8 as faulty and all other axioms of as correct, there is no way to extend this set of axioms to an acceptable configuration knowledge base given the test cases. Any change of where only Axiom 8 is deleted or replaced cannot be consistent with the positive case and inconsistent with the negative case. Similar arguments hold for Axiom 9.

It follows that only Axiom 7 is a single fault diagnosis of in the sense that changing Axiom 7 will allow the formulation of a knowledge base such that the positive case is consistent and the negative case is inconsistent. If either Axiom 8 or 9 is subject to a revision, additional axioms must be altered.

11.3.2 Defining Configuration and Diagnosis

The task of debugging a configuration knowledge base is to discover those axioms of have to be changed. In particular, some of the axioms of a faulty knowledge base must be removed and possibly some axioms must be added. This extension is denoted by . We call such a revised knowledge base the target knowledge base. This target knowledge base has to be consistent with all positive test cases and must be inconsistent with all negative test cases. We start with the definition of the instances of a configuration knowledge base diagnosis problem (CKB-diagnosis problem).

Definition

Instances of a CKB-diagnosis problem

A problem instance of a configuration knowledge base diagnosis problem is defined by a set of logical sentences representing the configuration knowledge base, a set of positive test cases , and a set of negative test cases . The elements of are logical sentences representing test cases.

Based on the instances of a CKB-diagnosis problem we define a diagnosis as a subset of the configuration knowledge base:

Definition

Diagnosis

A set is a diagnosis for a CKB-diagnosis problem instance iff there exists a set of logical sentences extending such that

• consistent and

• inconsistent

A diagnosis defines those sentences of that must be deleted such that all positive examples are configurations or can be extended to configurations.⁹ However, by deleting axioms the logical theory becomes weaker such that possibly some negative test cases are not inconsistent with . Consequently, on one hand axioms are deleted from such that all positive test cases are consistent but on the other hand axioms must be added such that all negative test cases are inconsistent with the resulting knowledge base . If for a diagnosis such an extension does not exist, the diagnosis must be rejected. However, how can we verify that such an extension does not exist?

Since the negation of the negative test cases has to follow from , we can replace by the conjunction of the negated negative test cases. Note that we can exploit the usual formulation of constraints in logic-programming by employing the special symbol false to deal with negation. For example we can negate and generalize the negative test case of our example by:

CPUD(X) CPUS(Y) (MBSilver(Z) MBDiamond(Z))

cpu-of-mb(X,Z) cpu-of-mb(Y,Z) false.

If the negative test case is not considered in our example, Axiom 8 would have been a diagnosis. However, if the negative test case is taken into account, Axiom 8 cannot be a diagnosis since there is no way to extend such that is consistent and is inconsistent with the resulting knowledge base. The same argument holds for Axiom 9.

Proposition

The set for a CKB-diagnosis problem instance is a diagnosis iff is consistent.

It follows that a diagnosis will always exist under the (reasonable) assumption that positive and negative test cases do not interfere with each other.

Proposition

A diagnosis for a CKB-diagnosis problem instance exists iff is consistent.

Usually, when debugging knowledge bases, the knowledge engineer is interested in minimal changes. This can be achieved by providing minimal diagnoses. A minimal diagnosis for the CKB-diagnosis problem instance is a diagnosis where no proper subset of is a diagnosis. In general, it is possible for multiple minimal diagnoses to exist, though additional criteria can be brought to bear to rank them in computation, as discussed next.

11.3.3 Computing Diagnoses

The previous definitions allow us to employ the standard algorithms for consistency-based diagnosis with appropriate extensions for the domain. In particular, Reiter’s Hitting Set algorithm (Reiter, 1987) can be applied, which is based on the concept of conflict sets. Conflict sets provide an effective mechanism for focusing the search for diagnoses. The basic idea is to compute minimal sets of inconsistent logical sentences, termed conflict sets. In order to resolve the inconsistency at least one sentence in each conflict set has to be changed. We assume to be nonempty.

Definition

Conflict set

A conflict set for is a subset of such that is inconsistent.

A conflict set is minimal if it does not contain a proper subset that is a conflict set. The relation between diagnoses and conflict sets can be expressed by the concept of hitting sets. Given a set of sets , a set is a hitting set of iff for all and . A hitting set is minimal if it does not contain a proper subset that is a hitting set. In our domain the set corresponds to the set of conflict sets and a hitting set represents a diagnosis.

Proposition

The set of logical sentences is a minimal diagnosis for the CKB-diagnosis problem instance iff is a minimal hitting set for the set of all minimal conflict sets of .

In Felfernig et al. (2004) a method for diagnosing configuration knowledge bases is proposed, based on a combination of Reiter’s HS-DAG algorithm (Greiner et al., 1989; Reiter, 1987) and a divide-and-conquer approach to compute minimal conflict sets (Junker, 2004). The method is generally applicable to all knowledge-representation paradigms, which are based on monotonic semantics such as predicate logic, description logic, and constraints. The approach requires a complete and correct consistency-checker, which is employed to compute minimal conflict sets. Reiter’s algorithm generates minimal diagnoses in a breadth-first manner; that is, diagnoses with smaller cardinalities are constructed first. This is helpful to control computation costs since, in practice, it is sufficient for the knowledge engineer to compute some of the most probable diagnoses. These diagnoses are then used to generate additional tests and it is therefore not necessary to compute all minimal diagnoses (Shchekotykhin et al., 2012). In case it is more probable that logical sentences in a knowledge base are correct than faulty, the set of minimal cardinality diagnoses (i.e., those diagnoses where the number of elements is minimal) serves as an approximation for a set of the most probable diagnoses. Furthermore, if we limit the search for diagnoses to minimal cardinality diagnoses then the depth of the search space corresponds exactly to the number of elements in a minimal cardinality diagnosis. Since in practice the number of faulty axioms in a knowledge base is low, the application of a breadth-first strategy is feasible. In Felfernig et al. (2014b)¹⁰ techniques and algorithms for computing conflicts and diagnoses are presented.

Let us now reconsider our example knowledge base. In case only is provided there is one minimal conflict set comprising a minimal set of axioms that is inconsistent with . Consequently, the minimal diagnoses are the axioms , and , which are the minimal hitting sets of the minimal conflict set. Note that there is only one minimal conflict set in this case. If we consider the negative test case (i.e., add to the knowledge base) then there is again only one minimal conflict set . Consequently, there is exactly one minimal single-fault diagnosis .

Alternatively, let us consider a different case and assume that Axiom 7 is wrongly defined as follows:

(7) MB(X) MBSilver(X) MBDiamond(X) MBUniversal(X).

In this case the universal motherboard was not forgotten but the knowledge engineer mixed up and . Furthermore, let us assume that only the positive example is given. In this case the set of minimal conflict sets is , and . Consequently, the minimal diagnoses (or hitting sets of the conflict sets) are and .

To summarize, we presented a generic debugging approach for a declarative representation of configuration knowledge that employs model-based diagnosis techniques. In analogy to regression testing procedures in software engineering, positive and negative examples for configured product instances are used to locate faults in a configurator application. The presented approach supports knowledge engineers by pointing them to minimal subsets of the knowledge base that are most probably faulty in case the configurator does not accept all the positive examples or does not reject all the negative examples.

Overall, the test cases (examples) thus play a central role in the approach and the availability of a sufficient amount of test cases can help to strongly reduce the number of diagnosis candidates. A typical point in time when errors are introduced into knowledge bases is when the rules are updated or extended, which happens quite frequently in many application domains. In that case, all past configurations that have been calculated before the maintenance operation and that should be still valid, can thus serve as positive test cases and can therefore be used in regression tests. Furthermore, remember that the presented approach also supports the use of partial test cases, which means that the knowledge engineer can specify valid configuration fragments and is not required to manually check a complete and possibly complex configuration for correctness before defining it as a test case. Still, more support in the area of test case management is possible, for example, through the automatic generation of representative test cases. We see this aspect as a relevant research direction not only in the configuration domain, but also for knowledge-based systems in general.

11.4 Organizational Challenges

The challenge of developing a configurator application has the setup and maintenance of a configuration knowledge base at its heart. However, besides the technical issues of knowledge encoding, acquisition of configuration knowledge from domain experts as well as its validation and maintenance that we discussed up to now (i.e., the content side), a variety of further organizational, business, and process facets is related to configuration knowledge base development. The knowledge base defines the variability of the configurable product offer in question. Initially, a company that is in the situation of configuration knowledge base development can either progress from, for instance, Mass Production (see Felfernig et al., 2014a¹¹) or rework an already existing product configuration approach. While in the latter case organizational experience with mass customization (see Piller and Blazek, 2014¹²) and configurable product offerings is already in place, in the first case, knowledge base development will be accompanied by a variety of organizational and managerial issues. Usually, the product offering itself and the degree of variability that is offered for customization needs to be designed from scratch as the implementation of a mass customization strategy requires a fundamental rethinking of the product architecture itself. Mikkola (2009), for instance, explores the relationship between product architecture design and mass customization. She discusses a modularity measure for product architectures and the associated opportunities for mass customization strategies. Based on Mikkola’s recommendations, different variants of configuration models can be (partially) assessed with respect to their aptness for successful mass customization strategies.

The process of product development itself typically consists of the specification of multiple views, in particular the functional, technical, and physical view (Arana et al., 2007; Jiao and Tseng, 1999). Another example of structuring configuration models along different views comes from Malmgren et al. (2011) for the construction industry. Due to the two-phase construction of prefabricated buildings (production and assembly at the customer site) the physical view in Jiao and Tseng (1999) is divided into separate production and assembly views. This modularization of configuration models is particularly necessary in case of a graphical representation of the configuration model in order to reduce diagrammatic complexity and to avoid conceptual overload of the involved stakeholders (Moody, 2009). The functional view models the functionality and typically depends on the analysis of customer requirements in target market niches. In contrast, the technical view describes the product design by its modules and modular structure and ensures technological feasibility by enforcing design parameters and structuring mechanisms. In the third step—the physical view—the product design has to be mapped to physical components and assemblies. There, the manufacturability of the configured products as well as costs, volumes, and schedules are in the focus and can lead to feedback loops to functional and technical views. Obviously, these process steps can therefore only be executed in an iterative and interleaved manner where different organizational units like marketing and sales, design, and manufacturing and logistics collaborate tightly. In Jiao and Tseng (1999) a methodology for developing a product family architecture for mass customization based on these three process steps is proposed and empirical results from a case study are provided for further reading. In addition, Nellore et al. (1999) focus on the initial specification process in new product development and propose a model to manage the interaction of the different stakeholders in this early and vital phase.

While the presented UML-based approach is very helpful in easing communication between the different stakeholders in a configurator development project, further means of external documentation of configuration knowledge have been explored. Haug (2010)generalizes the idea of configurator documentation systems and proposes a product model management software that constitutes a knowledge management and learning platform for the stakeholders involved in a product configuration development and maintenance project. The documentation software supports representation concepts such as class information cards and product variant master (PVM) that are adequately comprehensible to domain experts. Haug informedly argues that cutting cost on documentation in configurator development projects is short-sighted and leads to reduced or no maintainability of the developed configurator applications. Finally, the book of Hvam et al. (2008) discusses several case studies on the implementation of mass customization strategies with the help of product configuration systems from a practical point of view and can therefore also serve as a helpful guide.

11.5 Conclusion

Most modern and nontrivial product configuration systems rely on a knowledge base that restricts the solution space of potentially configured products to those instances that are actually valid according to technical or business-related restrictions and constraints. The goal of this chapter was to elaborate on the process from acquiring these “technical and economic restrictions and constraints” from their sources as well as encode, maintain, and validate it during the operational lifetime of the configuration system. Initially, we gave a rough overview on the development from the first rule-based knowledge representation mechanisms to a logic-based encoding that follows the component-port paradigm. In addition, we presented a UML-based representation mechanism for configuration knowledge acquisition. Such visual models abstract from the concrete declarative representation mechanism and allow domain experts a more intuitive access to knowledge base development in an analogy to model-driven approaches in software engineering. However, in this chapter we only focused on planar representations of configuration models and did not address the concept of views as a structuring mechanism. An extension to the presented UML-based approach (Felfernig et al., 2000a) that included a functional view for specifying abstract user requirements as opposed to a unified technical and physical view was proposed in Felfernig and Zanker (2000). Other extensions include representation of personalization knowledge in order to ease self-service configuration scenarios in e-commerce (Ardissono et al., 2003; Tiihonen and Felfernig, 2010) or to facilitate personalized optimization functions for computing configured instances (Zanker et al., 2010). Another aspect of knowledge engineering for configurator development addresses the integration with partners in supply networks. In cases where there are organizational requirements to keep detailed configuration knowledge hidden from other participants in a supply chain, a distributed solving mechanism needs to be applied (Felfernig et al., 2001). In Jannach and Zanker (2013) modeling approaches for such a distributed configuration problem based on a CSP-based formalism are discussed and distributed solving mechanisms comparatively assessed. A more abstract discussion on the perspectives of mass customization in dynamic value networks can be found in Dietrich et al. (2006). Based on a case study of custom-made shoe production, opportunities for adaptable business models are explored.

The validation of configuration knowledge bases by employing model-based diagnosis techniques is another key aspect of this chapter. With the presented approach minimal sets of potentially faulty statements in a declarative knowledge can be identified when sets of positive and negative examples of configured product instances are given. As has been pointed out, the maintenance and evolution of configuration knowledge bases is greatly facilitated by enabling such a form of regression testing. We refer to Felfernig et al. (2004) for technical details of this debugging approach. Another opportunity for the employment of model-based diagnosis techniques is the reconfiguration problem (see Nica et al., 2014¹³). As opposed to computing a configured product instance from scratch, in a reconfiguration task an already configured instance has to be modified in order to fulfill new or changed customer requirements or to be consistent with a modified version of a configuration knowledge base. Efficient support for such an after-sales service is still an open challenge. See Jannach et al. (2007) for a comprehensive survey on these research issues in knowledge-based configuration.

Finally, some of the organizational challenges in the configuration domain have also been addressed in this chapter. The implementation of a mass customization strategy goes well beyond the engineering effort of a configurator application itself. For instance,Heiskala et al. (2007) provide a comprehensive literature survey on the implementation processes of mass customization strategies and their associated configurator development. The construction of configuration knowledge bases is closely related to new product development and product design in general (Otto and Wood, 2001) and to the creation of a product architecture for mass customization in particular (Mikkola, 2009). Therefore, the knowledge engineering effort for configurator development needs to be closely integrated into these processes, and there must be a clear understanding of the interactions between the stakeholders that also serve as sources for configuration knowledge (Jiao and Tseng, 1999; Nellore et al., 1999).

References

1. Agarwal R, Tanniru M. A structured methodology for developing production systems. Decision Support Systems. 1992;8(6):483–499.

2. Arana J, Elejoste M, Lakunza JA, Uribetxebarria J, Zangitu M. Product Modeling and Configuration Experiences. Idea Group 2007; pp. 33–58, (Chapter 2).

3. Ardissono L, Felfernig A, Friedrich G, et al. A framework for the development of personalized, distributed web-based configuration systems. AI Magazine. 2003;24(3):93–108.

4. Barker V, O’Connor D, Bachant J, Soloway E. Expert systems for configuration at Digital: XCON and beyond. Communications of the ACM. 1989;32(3):298–318.

5. Davis J. Effect of modularity on maintainability of rule-based systems. International Journal of Man-Machine Studies. 1990;32(4):439–447.

6. Dietrich AJ, Kirn S, Timm IJ. Implications of mass customization on business information systems. International Journal on Mass Customization. 2006;1(2–3):218–236.

7. Felfernig A. Standardized configuration knowledge representations as technological foundation for mass customization. IEEE Transactions on Engineering Management. 2007;54(1):41–56.

8. Felfernig A, Zanker M. Diagrammatic acquisition of functional knowledge for product configuration systems with the unified modeling language. In: Proceedings of the First International Conference on Theory and Application of Diagrams (Diagrams ’00). London, UK: Springer Verlag; 2000:361–375. Lecture Notes in Computer Science vol. 1889.

9. Felfernig A, Friedrich G, Jannach D. Generating product configuration knowledge bases from precise domain extended UML models. In: 12th International Conference on Software Engineering and Knowledge Engineering (SEKE’2000) Chicago, Illinois. 2000a:284–293.

10. Felfernig A, Jannach D, Zanker M. Contextual diagrams as structuring mechanisms for designing configuration knowledge bases in UML. In: 3rd International Conference on the Unified Modeling Language (UML2000). York, UK: Springer; 2000b:240–254. Lecture Notes in Computer Science vol. 1939.

11. Felfernig A, Friedrich G, Jannach D, Zanker M. Towards distributed configuration. In: 24th German Conference on Artificial Intelligence (KI). Vienna: Springer; 2001:198–212. Lecture Notes in Computer Science vol. 2174.

12. Felfernig A, Friedrich G, Jannach D, Zanker M. Web-based configuration of virtual private networks with multiple suppliers. In: Gero JS, ed. Proceedings 7th International Conference on Artificial Intelligence in Design (AID-02). Cambridge, UK: Kluwer Academic Publisher; 2002:41–62.

13. Felfernig A, Friedrich G, Jannach D, Stumptner M. Consistency-based diagnosis of configuration knowledge bases. Artificial Intelligence. 2004;152(2):213–234.

14. Felfernig A, Hotz L, Bagley C, Tiihonen J. Motivation for the Book. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014a:3–7. (Chapter 1).

15. Felfernig A, Reiterer S, Reinfrank F, Ninaus G, Jeran M. Conflict Detection and Diagnosis in Configuration. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014b:73–87. (Chapter 7).

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

17. Fowler M. Domain-Specific Languages. Boston, MA: Addison-Wesley; 2010.

18. Greiner R, Smith BA, Wilkerson RW. A Correction to the algorithm in Reiter’s theory of diagnosis. Artificial Intelligence. 1989;41(1):79–88.

19. Haug A. A software system to support the development and maintenance of complex product configurators. International Journal of Advanced Manufacturing Technology. 2010;49(1–4):393–406.

20. Heiskala M, Paloheimo K-S, Tiihonen J. Mass customization with configurable products and configurators: A review of benefits and challenges. In: Mass Customization Information Systems in Business. first ed., New York, NY: IGI Global; 2007:1–32. (Chapter 1).

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

22. Hvam L, Mortensen N, Riis H. Product Customization. Berlin: Springer; 2008.

23. Jannach D, Zanker M. Modeling and solving distributed configuration problems: A CSP-based approach. IEEE Transactions on Knowledge and Data Engineering. 2013;25(3):603–618.

24. Jannach D, Felfernig A, Kreutler G, Zanker M, Friedrich G. Research issues in knowledge-based configuration. In: Mass Customization Information Systems in Business. Newyork, NY: Idea Group; 2007:221–236. (Chapter 11).

25. Jiao J, Tseng MM. A methodology of developing product family architecture for mass customization. Journal of Intelligent Manufacturing. 1999;10(1):3–20.

26. Junker U. Preference-based programming for Configuration. In: 17th International Joint Conference on Artificial Intelligence (IJCAI-2001), Configuration Workshop Seattle, WA. 2001;50–56.

27. Junker U. QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In: McGuinness DL, Ferguson G, eds. 19th Intl Conference on Artifical Intelligence (AAAI’04). San Jose, CA: AAAI Press; 2004:167–172.

28. Junker U, Mailharro D. Preference programming: Advanced problem solving for configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM). 2003;17(1):13–29.

29. Mailharro D. A Classification and Constraint-based Framework for Configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM). 1998;12(04):383–397.

30. Malmgren L, Jensen P, Olofsson T. Product modeling of configurable building systems – a case study. Journal of Information Technology in Construction (ITcon). 2011;16:697–712.

31. McDermott J. R1: a rule-based configurer of computer systems. Artificial Intelligence. 1982;19(1):39–88.

32. McGuinness D, Wright J. An industrial-strength description logic-based configurator platform. Intelligent Systems and their Applications, IEEE. 1998;13(4):69–77.

33. Mikkola JH. Management of product architecture modularity for mass customization: modeling and theoretical considerations. IEEE Transactions on Engineering Management. 2009;54(1):57–69.

34. Mittal S, Frayman F. Towards a generic model of configuration tasks. In: 1989:1395–1401. 11th International Joint Conference on Artificial Intelligence (IJCAI-89), Detroit, Michigan. vol. 2.

35. Moody DL. The physics of notations: toward a scientific basis for constructing visual notations in software engineering. IEEE Transactions on Software Engineering. 2009;35(6):756–779.

36. Nellore R, Söderquist K, Eriksson K-A. A specification model for product development. European Management Journal. 1999;17(1):50–63.

37. Nica I, Wotawa F, Ochenbauer R, Schober C, Hofbauer H, Boltek S. Kapsch: reconfiguration of mobile phone networks. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014:229–240. (Chapter 19).

38. Otto KN, Wood KL. Product Design. Upper Saddle River, NY: Prentice Hall; 2001.

39. Piller FT, Blazek P. Core capabilities of sustainable mass customization. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014:107–120. (Chapter 9).

40. Reiter R. A theory of diagnosis from first principles. Artificial Intelligence. 1987;32(1):57–95.

41. Shchekotykhin KM, Friedrich G, Fleiss P, Rodler P. Interactive ontology debugging: two query strategies for efficient fault localization. Web Semantics: Science, Services and Agents on the World Wide Web. 2012;12–13:88–103.

42. Studer R, Benjamins VR, Fensel D. Knowledge engineering: principles and methods. Data and Knowledge Engineering. 1998;25(1–2):161–197.

43. Tiihonen J, Felfernig A. Towards recommending configurable offerings. International Journal of Mass Customization. 2010;3(4):389–406.

44. Zanker M, Aschinger M, Jessenitschnig M. Constraint-based personalized configuring of product and service bundles. International Journal on Mass Customization. 2010;3(4):407–425.