4.1. Preferred diagnoses

Users typically prefer to keep the important requirements and to change or delete (if needed) the less important ones (Junker, Reference Junker2004). The major goal of (model-based) diagnosis tasks is to identify the preferred (leading) diagnoses, which are not necessarily minimal cardinality ones (DeKleer, Reference DeKleer1990). For the characterization of a preferred diagnosis we will rely on the definition of a total ordering of the given set of constraints in C (respectively C _R). Such a total ordering can be achieved, for example, by directly asking the customer regarding the preferences, by applying multiattribute utility theory (Winterfeldt & Edwards, Reference Winterfeldt and Edwards1986; Ardissono et al., Reference Ardissono, Felfernig, Friedrich, Jannach, Petrone, Schaefer and Zanker2003) where the determined interest dimensions correspond with the attributes of C _R or by applying the rankings determined by conjoint analysis (Belanger, Reference Belanger2005). The following definition of a lexicographical ordering (Definition 6) is based on total orderings for constraints that has been applied in (Junker, Reference Junker2004) for the determination of preferred conflict sets.

Definition 6 (total lexicographical ordering)

Given a total order < on C, we enumerate the constraints in C in increasing < order c ₁..c_n, starting with the least important constraints (i.e., c_i < c_j ⇒ i < j). We compare two subsets X and Y of C lexicographically:

Based on this definition of a lexicographical ordering, we can now introduce the definition of a preferred diagnosis.■

In our working example we assumed the lexicographical ordering (c ₅ < c ₆ < c ₇), that is, the most important customer requirement is c ₇ (the 4-wheel functionality). If we assume that X = {c ₅, c ₇} and Y = {c ₆, c ₇} then Y − X = {c ₆} and X ∩ {c ₇} = Y ∩ {c ₇}. Intuitively, {c ₅, c ₇} is a preferred diagnosis compared to {c ₆, c ₇} because both diagnoses include c ₇ but c ₅ is less important than c ₆. If we change the ordering to (c ₇ < c ₆ < c ₅), FastDiag would then determine {c ₆, c ₇} as the preferred minimal diagnosis.

4.2. FastDiag approach

For the following discussions we introduce the set AC, which is initially set to C _KB ∪ C _R [the union of customer requirements (C _R) and the configuration knowledge base (C _KB)] and subsequently changed when the algorithm runs. The basic idea of the FastDiag algorithm (Algorithm 1) is the following.Footnote ² In our example, the set of customer requirements C _R = {c ₅, c ₆, c ₇} includes at least one minimal diagnosis because C _KB is consistent and C _KB ∪ C _R is inconsistent. In the extreme case C _R itself represents the minimal diagnosis, which then means that all constraints in C _R are part of the diagnosis, that is, each c_i ∈ C _R represents a singleton conflict. In our case C _R obviously does not represent a minimal diagnosis—the set of diagnoses in our working example is {Δ₁ = {c ₅, c ₆}, Δ₂ = {c ₅, c ₇}, Δ₃ = {c ₆, c ₇}} (see Section 3). The next step in Algorithm 1 is to divide the set of customer requirements C _R = {c ₅, c ₆, c ₇} into the two sets C₁ = {c ₅} and C₂ = {c ₆, c ₇} and to check whether AC − C₁ is already consistent. If this is the case, we can omit the set C₂ because at least one minimal diagnosis can already be identified in C₁. In our case, AC − {c ₅} is inconsistent, which means that we have to consider further elements from C₂. Therefore, C₂ = {c ₆, c ₇} is divided into the sets {c ₆} and {c ₇}. In the next step we can check whether AC – (C₁ ∪ {c ₆}) is consistent—this is the case that means that we do not have to further take into account {c ₇} for determining the diagnosis. Because {c ₅} does not include a diagnosis but {c ₅} ∪ {c₆} includes a diagnosis, we can deduce that {c ₆} must be part of the diagnosis. The final step is to check whether AC – {c ₆} leads to a diagnosis without including {c ₅}. We see that AC – {c ₆} is inconsistent, that is, Δ = {c ₅, c ₆} is a minimal diagnosis for the CR diagnosis problem (C _R = {c ₅, c ₆, c ₇}, C _KB = {c ₁, … , c ₄}). An execution trace of the FastDiag algorithm in the context of our working example is shown in Figure 2.

Fig. 2.

FastDiag execution trace for the C _R diagnosis problem (C _R = {c ₅, c ₆, c ₇}, C _KB = {c ₁, c ₂, c ₃, c ₄}). Enumerations 1–6 show the order in which the different incarnations of the FD function are activated.

4.3. Calculating n > 1 diagnoses

In order to be able to calculate n > 1 diagnosesFootnote ³ with FastDiag we have to adopt the HSDAG construction introduced in Reiter (Reference Reiter1987) by substituting the resolution of conflicts (see Fig. 1) with the deletion of elements c_i from C _R (C) (see Fig. 3). In this case, a path in the HSDAG is closed if no further diagnoses can be identified for this path or the elements of the current path are a superset of an already closed path (containment check). Conform to the HSDAG approach presented in Reiter (Reference Reiter1987), we expand the search tree in a breadth-first manner. In our working example, we can delete {c ₅} (one element of the first diagnosis Δ₁ = {c ₅, c ₆}) from the set C _R of diagnosable elements and restart the algorithm for finding another minimal diagnosis for the CR diagnosis problem ({c ₆, c ₇}, C _KB). Because AC − {c ₅} is inconsistent, we can conclude that C _R = {c ₆, c ₇} includes another minimal diagnosis (Δ₂ = {c ₆, c ₇}), which is determined by FastDiag for the CR diagnosis problem (C _R − {c ₅}, C _KB). Finally, we have to check whether the CR diagnosis problem ({c ₅, c ₇}, C _KB) leads to another minimal diagnosis. This is the case, that is, we have identified the last minimal diagnosis that is Δ₃ = {c ₅, c ₇}. The calculation of all diagnoses in our working example on the basis of FastDiag is depicted in Figure 3.

Fig. 3.

FastDiag: calculating the complete set of minimal diagnoses. Enumerations 1–6 show the order in which the different incarnations of the FastDiag algorithm are activated.

Note that for a given set of constraints (C) FastDiag always calculates the preferred diagnosis in terms of Definition 7. If Δ₁ is the diagnosis returned by FastDiag and we delete one element from Δ₁ (e.g., c ₅), then FastDiag returns the preferred diagnosis for the CR diagnosis problem ({c ₅, c ₆, c ₇} − {c ₅}, {c ₁, … , c ₇}), which is Δ₂ in our example case, that is, Δ₁ >_lex Δ₂. Consequently, diagnoses part of one path in the search tree (such as Δ₁ and Δ₂ in Fig. 3) are in a strict preference ordering. However, there is only a partial order between individual diagnoses in the search tree in the sense that a diagnosis at level k is not necessarily preferable to a diagnosis at level k + 1.

4.4. FastDiag properties

A detailed listing of the basic operations of FastDiag is shown in Algorithm 1. First, the algorithm checks whether the constraints in C contain a diagnosis, that is, whether AC − C is consistent—the function assumes that it is activated in the case that AC is inconsistent. If AC − C is inconsistent or C = ∅, FastDiag returns the empty set as result (no solution can be found, line 2 of the algorithm). If at least one diagnosis is contained in the set of constraints C, FastDiag activates the FastDiag function that is in charge of retrieving a preferred diagnosis (line 3 of the algorithm). FastDiag follows a divide and conquer strategy where the recursive function FastDiag divides the set of constraints (in our case the elements of C _R) into two different subsets (C₁ and C₂; line 8 of the algorithm) and tries to figure out whether C₁ already contains a diagnosis (line 5 of the algorithm). If this is the case, FastDiag does not further take into account the constraints in C₂. If only one element is remaining in the current set of constraints C and the current set of constraints in AC is still inconsistent, then the element in C is part of a minimal diagnosis (line 6 of the algorithm). FastDiag is complete in the sense that if C contains exactly one minimal diagnosis then FD will find it. If there are multiple minimal diagnoses then one of them (the preferred one, see Definition 7) is returned. The recursive function FD is triggered if AC − C is consistent and C consists of at least one constraint. In such a situation a corresponding minimal diagnosis can be identified. If we assume the existence of a minimal diagnosis Δ that cannot be identified by FastDiag, this would mean that there exists at least one constraint c_a in C that is part of the diagnosis but not returned by FD. The only way in which elements can be deleted from C (i.e., not included in a diagnosis) is by the return ∅ statement in FD and ∅ is only returned in the case that AC is consistent, which means that the elements of C₂ (C₁) from the previous FD incarnation are not part of the preferred diagnosis. Consequently, it is not possible to delete elements from C, which are part of the diagnosis. FastDiag computes only minimal diagnoses in the sense of Definition 5. If we assume the existence of a nonminimal diagnosis Δ calculated by FastDiag, this would mean that there exists at least one constraint c_a with Δ − {c_a} is still a diagnosis. The only situation in which elements of C are added to a diagnosis Δ is if C itself contains exactly one element. If C contains only one element (let us assume c_a) and AC is inconsistent (in the function FastDiag) then c_a is the only element that can be deleted from AC, that is, c_a must be part of the diagnosis.

5.1. Performance of FastDiag

In this section we will compare the performance of FastDiag with the performance of the hitting set algorithm (Reiter, Reference Reiter1987) in combination with the QuickXplain conflict detection algorithm introduced in (Junker, Reference Junker2004).

The worst case complexity of FastDiag in terms of the number of consistency checks needed for calculating one minimal diagnosis is 2d × log₂(n/d) + 2d, where d is the minimal diagnoses set size and n is the number of constraints (in C). The best case complexity is log₂(n/d) + 2d. In the worst case each element of the diagnosis is contained in a different path of the search tree: log₂(n/d) is the depth of the path, 2d represents the branching factor and the number of leaf-node consistency checks. In the best case all elements of the diagnosis are contained in one path of the search tree.

The worst case complexity of QuickXplain in terms of consistency checks needed for calculating one minimal conflict set is 2k ⋅ log₂(n/k ) + 2k where k is the minimal conflicts set size and n is again the number of constraints (in C; Junker, Reference Junker2004). The best case complexity of QuickXplain in terms of the number of consistency checks needed is log₂(n/k ) + 2k (Junker, Reference Junker2004). Consequently, the number of consistency checks per conflict set (QuickXplain) and the number of consistency checks per diagnosis (FastDiag) fall into a logarithmic complexity class.

Let n _cs be the number of minimal conflict sets in a constraint set and n _diag be the number of minimal diagnoses, then we need n _diag FastDiag calls (see Algorithm 1) plus n _cs additional consistency checks and n _cs activations of QuickXplain with n _diag additional consistency checks for determining all diagnoses. The results of a performance evaluation of FastDiag are depicted in the Figure 4, Figure 5, Figure 6, and Figure 7. The basis for these evaluations was the bicycle configuration knowledge base taken from the CLib⁴ (www.itu.dk/research/cla/externals/clib/) configuration benchmarks library (34 variables and about 65 constraints). For this example knowledge base we randomly generated different sets of requirements (of cardinality 5, 7, 10, and 15 requirements) and measured the performance of calculating corresponding diagnosis sets (the first diagnosis, first 5 diagnoses, first 10 diagnoses, and all diagnoses). The run time performance of the different diagnosis algorithms and the needed amount of TP calls is shown in the Figures 4–7. As solver we used the CLib-based decision diagram representation that allows for backtracking-free solution search. The tests have been executed on a standard desktop computer (Intel Core 2 Quad CPU QD9400 2.66-GHz CPU with 2 GB of RAM). Note that we have evaluated the performance of FastDiag with different other benchmark configuration knowledge bases on the CLib Web page with basically the same result. FastDiag shows to be a valuable alternative for determining diagnoses in interactive settings especially for calculating the preferred first-n solutions.

Fig. 4.

Calculating the first minimal diagnosis with FastDiag versus hitting set-based diagnosis on the basis of QuickXplain for 5, 7, 10, and 15 user requirements (req): performance in milliseconds on the top and number of needed TP calls on the bottom. [A color version of this figure can be viewed online at journals.cambridge.org/aie]

Fig. 5.

Calculating the topmost-5 minimal diagnoses with FastDiag versus hitting set-based diagnosis on the basis of QuickXplain for 5, 7, 10, and 15 user requirements (req): performance in milliseconds on the top and number of needed TP calls on the bottom. [A color version of this figure can be viewed online at journals.cambridge.org/aie]

Fig. 6.

Calculating the topmost-10 minimal diagnoses with FastDiag versus hitting set-based diagnosis on the basis of QuickXplain for 5, 7, 10, and 15 user requirements (req): performance in milliseconds on the top and number of needed TP calls on the bottom. [A color version of this figure can be viewed online at journals.cambridge.org/aie]

Fig. 7.

Calculating all minimal diagnoses with FastDiag versus hitting set-based diagnosis on the basis of QuickXplain for 5, 7, 10, and 15 user requirements (req): performance in milliseconds on the top and number of needed TP calls on the bottom. [A color version of this figure can be viewed online at journals.cambridge.org/aie]

Figure 4 shows a comparison between the hitting set based diagnosis approach (denoted as HSDAG) and the FastDiag algorithm (denoted as FastDiag) in the case that only one diagnosis is calculated. FastDiag clearly outperforms the HSDAG approach independent of the way in which diagnoses are calculated (breadth-first or best-first). Figure 5 shows the performance evaluation for calculating the topmost-5 minimal diagnoses. The result is similar to the one for calculating the first diagnosis, that is, FastDiag outperforms the two HSDAG versions. Our evaluations show that FastDiag is very efficient in calculating preferred minimal diagnoses.

5.2. Empirical evaluation

Based on a computer configuration dataset of the Graz University of Technology (N = 415 configurations) we evaluated the three presented approaches with respect to their capability of predicting diagnoses that are acceptable for the user (diagnoses leading to selected configurations). Each entry of the dataset consists of a set of initial user requirements C _R inconsistent with the configuration knowledge base C _KB and the configuration that had been finally selected by the user. Because the original requirements stored in the dataset are inconsistent with the configuration knowledge base, we could determine those diagnoses that indicated which minimal sets of requirements have to be deleted in order to be able to find a solution.

We evaluated the prediction accuracy of the three diagnosis approaches (breadth-first HSDAG, FastDiag, and best-first HSDAG). We first measured the distance between the predicted position of a diagnosis leading to a selected configuration and the expected position of the diagnosis (which is 1). This distance was measured in terms of the root mean square deviation (RMSD; see Formula 1). The results of this first analysis are the following: an important result is that FastDiag has the lowest RMSD value (0.95), best-first HSDAG has a similar prediction quality (RMSD = 0.97), and breadth-first HSDAG has the worst prediction quality (RMSD = 1.64).

(1)

RMSD is an often used quality estimate but it provides only a limited view on the precision of a (diagnosis) prediction. Therefore, we wanted to analyze the precision of the diagnosis selection strategies discussed in this paper—a measure for the precision of a diagnosis algorithm is depicted in Formula 2. The idea behind this measure is to describe how often a diagnosis that leads to a selected configuration (selected by the user) is among the topmost-n ranked diagnoses. As shown in Table 1, FastDiag and best-first HSDAG have highest prediction accuracy in terms of precision, whereas the breadth-first HSDAG approach shows the worst precision.

(2)

Table 1.

Precision of FastDiag versus HSDAG based approaches

Note: HSDAG, hitting set directed acyclic graph.

We applied a Mann–Whitney U test in order to statistically analyze differences between the three diagnosis approaches in terms of ranking behavior. We conducted a pairwise comparison between the diagnosis approaches on the basis of the mentioned Mann–Whitney U test. We could identify a significant difference between the rankings of best-first HSDAG and breadth-first HSDAG based diagnosis (p = 6.625e ⁻⁵) and also between FastDiag and breadth-first HSDAG based diagnosis (p < 2.441e ⁻⁷). There was no significant difference between best-first HSDAG and FastDiag in terms of ranking behavior (p = 0.12).

6.1. Knowledge base analysis

The authors of Felfernig et al. (Reference Felfernig, Friedrich, Jannach and Stumptner2004) introduce an algorithm for the automated debugging of configuration knowledge bases. The idea is to combine a conflict detection algorithm such as QuickXplain (Junker, Reference Junker2004) with the hitting set algorithm used in model-based diagnosis (MBD; Reiter, Reference Reiter1987) for the calculation of minimal diagnoses. In this context, conflicts are induced by test cases (examples) that, for example, stem from previous configuration sessions, have been automatically generated, or have been explicitly defined by domain experts. Further applications of MBD in constraint set debugging are introduced in Felfernig et al. (Reference Felfernig, Friedrich, Isak, Shchekotykhin, Teppan and Jannach2007) where diagnosis concepts are used to identify minimal sets of faulty transition conditions in state charts and in Felfernig et al. (Reference Felfernig, Friedrich, Teppan and Isak2008) where MBD is applied for the identification of faulty utility constraint sets in the context of knowledge-based recommendation. In contrast to Felfernig et al. (Reference Felfernig, Friedrich, Jannach and Stumptner2004, Reference Felfernig, Friedrich, Isak, Shchekotykhin, Teppan and Jannach2007, Reference Felfernig, Friedrich, Teppan and Isak2008), our work provides an algorithm that allows to directly determine diagnoses without the need to determine corresponding conflict sets. FastDiag can be applied in knowledge engineering scenarios for calculating preferred diagnoses for faulty knowledge bases given that we are able to determine reasonable ordering for the given set of constraints; this could be achieved, for example, by the application of corresponding complexity metrics (Chen & Suen, Reference Chen and Suen2003).

6.2. Conflict detection

In contrast to the algorithm presented in this paper, calculating diagnoses for inconsistent requirements typically relies on the existence of (minimal) conflict sets. A well-known algorithm with a logarithmic number of consistency checks, depending on the number of constraints in the knowledge base and the cardinality of the minimal conflicts, is QuickXplain (Junker, Reference Junker2004). It has made a major contribution to more efficient interactive constraint-based applications. QuickXplain is based on a divide and conquer strategy. FastDiag relies on the same principle of divide and conquer but with a different focus, namely, the determination of minimal diagnoses. QuickXplain calculates minimal conflict sets based on the assumption of a linear preference ordering among the constraints. Similarly, if we assume a linear preference ordering of the constraints in C, FastDiag calculates preferred diagnoses.

6.3. Interactive settings

Note that in the interactive configuration scenario discussed in this paper our goal was to support open configuration that lets the user explore the configuration space where the system proactively points out inconsistent requirements, such a functionality is often provided by commercial configuration environments. O'Sullivan et al. (Reference O'Sullivan, Papdopoulos, Faltings and Pu2007) focus on interactive settings where users of constraint-based applications are confronted with situations where no solution can be found. In this context, O'Sullivan et al. (Reference O'Sullivan, Papdopoulos, Faltings and Pu2007) introduce the concept of minimal exclusion sets that correspond to the concept of minimal diagnoses as defined in Reiter (Reference Reiter1987). As mentioned, the major focus of O'Sullivan et al. (Reference O'Sullivan, Papdopoulos, Faltings and Pu2007) are settings where the proposed algorithm supports users in the identification of acceptable exclusion sets. The authors propose an algorithm (representative explanations) that helps to improve the quality of the presented exclusion set (in terms of diversity) and thus increases the probability of finding an acceptable exclusion set for the user. Our diagnosis approach calculates preferred diagnoses in terms of a predefined ordering of the constraint set. Thus, compared to the work of O'Sullivan et al. (Reference O'Sullivan, Papdopoulos, Faltings and Pu2007), we follow a different approach in terms of focusing more on preferences than on the degree of representativeness.

6.4. Diagnosis algorithms

There are a couple of algorithms that help to improve the efficiency of diagnosis determination; they are further developments of the original algorithm introduced by Reiter (Reference Reiter1987). These approaches focus on making the construction of hitting sets more efficient. Wotawa (Reference Wotawa2001) introduces an algorithm that reduces the number of subset checks compared to the original HSDAG approach (Reiter, Reference Reiter1987). Fijany and Vatan (Reference Fijany and Vatan2004) introduce an approach to represent the problem of determining minimal hitting sets as a corresponding integer programming problem. Further approaches to optimize the determination of hitting sets are discussed in Lin and Jiang (Reference Lin and Jiang2003). All the mentioned approaches rely on (minimal) conflict sets that are the basis for calculating a set of minimal diagnoses, whereas FastDiag is a complete and minimal diagnosis algorithm without the need of conflict sets. It is important to mention that especially when calculating the first n-diagnoses (for n > 1, i.e., not a single diagnosis), FastDiag can also exploit the mentioned algorithms of Lin and Jiang (Reference Lin and Jiang2003) and Wotawa (Reference Wotawa2001) for the calculation of more than one diagnosis, that is, it is not bound to the usage of the original HSDAG algorithm. Lin and Jiang (Reference Lin and Jiang2002) introduce an approach to determine hitting sets on the basis of genetic algorithms; a similar approach to the determination of diagnoses is presented in Feldman et al. (Reference Feldman, Provan and Gemund2008) who introduce a stochastic fault diagnosis algorithm, which is based on greedy stochastic search. Such approaches show to significantly improve search performance; however, there is no general guarantee of completeness and diagnosis minimality. Finally, there exist a couple of algorithms that are improving the algorithmic performance of diagnosis calculation due to additional knowledge about the structural properties of the diagnosis problem. For example, Jannach and Liegl (Reference Jannach and Liegl2006) show the determination of (minimal) diagnoses for the case of conjunctive queries on database tables (the set of diagnoses can be precompiled by executing the individual parts of the query on the given data set). Siddiqi and Huang (Reference Siddiqi and Huang2007) show one approach to exploit structural properties of system descriptions to improve the overall performance of diagnosis determination; in this case cones are areas in a gate with a certain structure and a certain probability of including a diagnosis, and the search process focuses on exactly those areas. FastDiag does not exploit specific properties of the underlying constraint set; however, taking into account such properties can further improve the performance of the algorithm. Corresponding evaluations are within the scope of future work.

6.5. Personalized diagnosis

Many of the existing diagnosis approaches do not take into account the need for personalizing the set of diagnoses to be presented to a user. Identifying diagnoses of interest in an efficient manner is a clear surplus regarding the acceptance of the underlying application, for example, users of a configurator application are not necessarily interested in minimal cardinality diagnoses (Reiter, Reference Reiter1987) but rather in those that correspond to their current preferences. A first step toward the application of personalization concepts in the context of knowledge-based recommendation is presented in Felfernig et al. (Reference Felfernig, Friedrich, Schubert, Mandl, Mairitsch and Teppan2009). The authors introduce an approach that calculates leading diagnoses on the basis of similarity measures used for determining n-nearest neighbors. A general approach to the identification of preferred diagnoses is introduced in DeKleer (Reference DeKleer1990), where probability estimates are used to determine the leading diagnoses with the overall goal to minimize the number of measurements needed for identifying a malfunctioning device. Basic principles of determining diagnoses in knowledge-based recommendation scenarios are discussed in Jannach and Liegl (Reference Jannach and Liegl2006). Furthermore, Froehlich et al. (Reference Fröhlich, Nejdl and Schroeder1994) introduce a logical characterization of preferences that are expressed as preference relations on single diagnoses and modal logical formulas on groups of diagnoses. In contrast to our work, Froehlich et al. (Reference Fröhlich, Nejdl and Schroeder1994) do not provide an algorithm to efficiently calculate preferred diagnoses. We see our work as a major contribution in this context because FastDiag helps to identify leading diagnoses more efficiently. Further empirical studies in different application contexts are within the major focus of our future work.