F L E X D I AG : AnyTime Diagnosis for Reconfiguration

Abstract

Anytime diagnosis is able to determine solutions within predefined time limits. This is especially useful in realtime scenarios such as production scheduling, robot control, and communication networks management where diagnosis and corresponding reconfiguration capabilities play a major role. Anytime diagnosis in many cases comes along with a tradeoff between diagnosis quality and the efficiency of diagnostic reasoning. In this paper we introduce and analyze FLEXDIAG which is an anytime variant of existing direct diagnosis approaches. We evaluate the algorithm with regard to performance and diagnosis quality using a configuration benchmark.

Keywords

• Anytime Diagnosis
• Reconfiguration

-

Knowledge-based configuration is one of the most successful applications of Artificial Intelligence [ 7, 24 ]. There are many different applications of configuration technologies ranging from telecommunication infrastructures [ 11 ], railway interlocking systems [ 5 ], the automotive domain [ 22, 26, 28 ] to the configuration of services [ 27 ]. Configuration technologies must be able to deal with inconsistencies which can occur in different contexts. First, a configuration knowledge base can be inconsistent, i.e., no solution can be determined. In this context, the task of knowledge engineers is to figure out which constraints are responsible for the unintended behavior of the knowledge base. Bakker et al. [ 1 ] show the application of model-based diagnosis [ 19 ] to determine minimal sets of constraints in a knowledge base that are responsible for a given inconsistency. A variant thereof is documented in Felfernig et al. [ 6 ] where an approach to the automated debugging of knowledge bases with test cases is introduced. Felfernig et al. [ 6 ] also show how to diagnose customer requirements that are inconsistent with a configuration knowledge base. The underlying assumption is that the configuration knowledge base itself is consistent but combined with a set of requirements is inconsistent.

All diagnosis approaches mentioned so far are based on conflictdirected hitting set determination [ 15, 19 ]. These approaches typically determine diagnoses in a breadth-first search manner which allows the identification of minimal cardinality diagnoses. The major disadvantage of applying these approaches is the need of predetermining minimal conflicts which is inefficient especially in cases where only the leading diagnoses (the most relevant ones) are sought.

Anytime diagnosis algorithms are useful in scenarios where diagnoses have to be provided in real-time, i.e., within given time limits. If diagnosis is applied in interactive configuration, for example, to determine repairs for inconsistent customer requirements, response times should be below one second [ 2 ]. Efficient diagnosis and reconfiguration of communication networks is crucial to retain the quality of service [ 18, 25 ]. In today’s production scenarios which are characterized by small batch sizes and high product variability, it is increasingly important to develop algorithms that support the efficient reconfiguration of schedules. Such functionalities support the paradigm of smart production, i.e., the flexible and efficient production of highly variant products. Further applications are the diagnosis and repair of robot control software [ 23 ], the reconfiguration of cars [ 29 ], and the reconfiguration of buildings [ 12 ].

Algorithmic approaches to provide efficient solutions for diagnosis problems are manyfold. Some approaches focus on improvements of Reiter’s original hitting set directed acyclic graph (HSDAG) [ 19 ] in terms of a personalized computation of leading diagnoses [ 3 ] or other extensions that make the basic approach [ 19 ] more efficient [ 31 ]. Wang et al. [ 30 ] introduce an approach to derive binary decision diagrams (BDDs) on the basis of a pre-determined set of conflicts – diagnoses can then be determined by solving the BDD. A pre-defined set of conflicts can also be compiled into a corresponding linear optimization problem [ 10 ]; diagnoses can then be determined by solving the given problem. In knowledge-based recommendation scenarios, diagnoses for user requirements can be pre-compiled in such a way that for a given set of customer requirements, the diagnosis search task can be reduced to querying a relational table (see, for example, [ 14, 20 ]). All of the mentioned approaches either extend the approach of Reiter [ 19 ] or improve efficiency by exploiting pre-generated information about conflicts or diagnoses.

An alternative to conflict-directed diagnosis [ 19 ] are direct diagnosis algorithms that determine minimal diagnoses without the need of pre-determing minimal conflict sets [ 9, 17, 21 ]. The FASTDIAG algorithm [ 9 ] is a divide-and-conquer based algorithm that supports the determination of diagnoses without a preceding conflict detection. In this paper we show how this algorithm can be converted into an anytime diagnosis algorithm (FLEXDIAG) that is able to improve performance by disregarding the aspect of minimality, i.e., the algorithm allows for tradeoffs between diagnosis quality (e.g., minimality) and performance of diagnostic search. In this paper we focus on reconfiguration scenarios, i.e., we show how FLEXDIAG can be applied in situations where a given configuration (solution) has to be adapted conform to a changed set of customer requirements.

Our contributions in this paper are the following. First, we show how to solve reconfiguration tasks with direct diagnosis. Second, we make direct diagnosis anytime-aware by including a parametrization that helps to systematically reduce the number of consistency checks. Finally, we report the results of a FLEXDIAG-related evaluation conducted on the basis of a configuration benchmark.

The remainder of this paper is organized as follows. In Section 2 we introduce an example configuration knowledge base from the domain of resource allocation. This knowledge base will serve as a working example throughout the paper. Thereafter (Section 3) we introduce a definition of a reconfiguration task. In Section 4 we discuss basic principles of direct diagnosis on the basis of FLEXDIAG and show how this algorithm can be applied in reconfiguration scenarios. In Section 5 we present the results of a performance analysis. A simple example of the application of FLEXDIAG in production environments is given in Section 6. In Section 7 we discuss major issues for future work. With Section 8 we conclude the paper. 2

Example Configuration Knowledge Base

A configuration system determines configurations (solutions) on the basis of a given set of customer requirements [ 13 ]. In many cases, constraint satisfaction problem (CSP) representations [ 16 ] are used for the definition of a configuration task. A configuration task and a corresponding configuration (solution) can be defined as follows.

Definition 1 (Configuration Task and Configuration). A configuration task can be defined as a CSP (V; D; C) where V = fv1; v2; :::; vng is a set of variables, D = [dom(vi) represents domain definitions, and C = fc1; c2; :::; cmg is a set of constraints. Additionally, user requirements are represented by a set of constraints R = fr1; r2; :::; rkg. A configuration (solution) for a configuration task is a set of assignments (constraints) S = fs1 : v1 = a1; s2 : v2 = a2; :::; sn : vn = an)g where ai 2 dom(vi) which is consistent with C [ R.

An example of a configuration task represented as a constraint satisfaction problem is the following.

Example (Configuration Task). In this resource allocation problem example, items (a barrel of fuel, a stack of paper, a pallet of fireworks, a pallet of personal computers, a pallet of computer games, a barrel of oil, a palette of roof tiles, and a palette of rain pipes) have to be assigned to three different containers. There are a couple of constraints (ci) to be taken into account, for example, fireworks must not be combined with fuel (c1). Furthermore, there is one requirement (r1) which indicates that the palette of fireworks has to be assigned to container 1. On the basis of this configuration task definition, a configurator can determine a configuration S.

V = ff uel; paper; f ireworks; pc; games; oil; roof; pipesg dom(f uel) = dom(paper) = dom(f ireworks) = dom(pc) = dom(games) = dom(oil) = dom(roof ) = dom(pipes) = f1; 2; 3g C = fc1 : f ireworks 6= f uel; c2 : f ireworks 6= paper; c3 : f ireworks 6= oil; c4 : pipes = roof; c5 : paper 6= f uelg R = fr1 : f ireworks = 1g S = fs1 : pc = 3; s2 : games = 1; s3 : paper = 2; s4 : f uel = 3; s5 : f ireworks = 1; s6 : oil = 2; s7 : roof = 1; s8 : pipes = 1g

On the basis of the given definition of a configuration task, we now introduce the concept of reconfiguration (see also [ 12, 18, 25, 28 ]). 3

Reconfiguration Task

It can be the case that an existing configuration S has to be adapted due to a change or extension of the given set of customer requirements. Examples thereof are changing requirements that have to be taken into account in production schedules, failing components or overloaded network infrastructures in a mobile phone network, and changes in the internal model of the environment of a robot. In the following we assume that the palette of paper should be reassigned to container 3 and the personal computer and games palettes should be assigned to the same container. Formally, the set of new requirements is represented by R : fr10 : pc = games; r20 : paper = 3g. In order to determine reconfigurations, we have to calculate a corresponding diagnosis (see Definition 2).

Definition 2 (Diagnosis). A diagnosis (correction subset) is a subset of S = fs1 : v1 = a1; s2 : v2 = a2; :::; sn : vn = ang such that S [ C [ R is consistent. is minimal if there does not exist a diagnosis 0 with 0 .

On the basis of the definition of a minimal diagnosis, we can introduce a formal definition of a reconfiguration task.

Definition 3 (Reconfiguration Task and Reconfiguration). A reconfiguration task can be defined as a CSP (V; D; C; S; R ) where V is a set of variables, D represents variable domain definitions, C is a set of constraints, S represents an existing configuration, and R = fr10; r20; :::; rk0g (R consistent with C) represents a set of reconfiguration requirements. A reconfiguration is a variable assignment S = fs1 : v1 = a01; s2 : v2 = a02; :::; sl : vl = a0lg where si 2 , a0i 6= ai, and S [ S [ C [ R is consistent.

If R is inconsistent with C, the new requirements have to be analyzed and changed before a corresponding reconfiguration task can be triggered [ 4, 8 ]. An example of a reconfiguration task in the context of our configuration knowledge base is the following.

Example (Reconfiguration Task). In the resource allocation problem, the original customer requirements R are substituted by the requirements R = fr10 : pc = games; r20 : paper = 3g. The resulting reconfiguration task instance is the following.

V = ff uel; paper; f ireworks; pc; games; oil; roof; pipesg dom(f uel) = dom(paper) = dom(f ireworks) = dom(pc) = dom(games) = dom(oil) = dom(roof ) = dom(pipes) = f1; 2; 3g C = fc1 : f ireworks 6= f uel; c2 : f ireworks 6= paper; c3 : f ireworks 6= oil; c4 : pipes = roof; c5 : paper 6= f uelg S = fs1 : pc = 3; s2 : games = 1; s3 : paper = 2; s4 : f uel = 3; s5 : f ireworks = 1; s6 : oil = 2; s7 : roof = 1; s8 : pipes = 1g R = fr10 : pc = games; r20 : paper = 3g

To solve a reconfiguration task (see Definition 3), conflict-directed diagnosis approaches [ 19 ] would determine a set of minimal conflicts and then determine a hitting set that resolves each of the identified conflicts. In this context, a minimal conflict set CS S is a minimal set of variable assignments that trigger an inconsistency with C [ R , i.e., CS [ C [ R is inconsistent and there does not exist a conflict set CS0 with CS0 CS. In our working example, the minimal conflict sets are CS1 : fs1 : pc = 3; s2 : games = 1g, CS2 : fs3 : paper = 2g, and CS3 : fs4 : f uel = 3g. The corresponding minimal diagnoses are 1 : fs1; s3; s4g and 2 : fs2; s3; s4g. The elements in a diagnosis indicate which variable assignments have to be adapted such that a reconfiguration can be determined that takes into account the new requirements in R . If we choose 1, the reconfigurations (reassignments) for the variable assignments in 1 can be determined by a CSP solver call C [ R [ (S 1). The resulting configuration S0 can be fs1 : pc = 1; s2 : games = 1; s3 : paper = 3; s4 : f uel = 2; s5 : f ireworks = 1; s6 : oil = 2; s7 : roof = 1; s8 : pipes = 1g. For a detailed discussion of conflict-based diagnosis we refer to Reiter [ 19 ]. In the following we introduce an approach to the determination of minimal reconfigurations which is based on a direct diagnosis algorithm, i.e., diagnoses are determined without the need of determining related minimal conflict sets. 4

Reconfiguration with FLEXDIAG

In the following discussions, the set AC = C [ R [ S represents the union of all constraints that restrict the set of possible solutions for a given reconfiguration task. Furthermore, S represents a set of constraints that are considered as candidates for being included in a diagnosis . The idea of FLEXDIAG (Algorithm 1) is to systematically filter out the constraints that become part of a minimal diagnosis using a divide-and-conquer based approach.

Algorithm 1

FLEXDIAG. 1 func FLEXDIAG(S; AC = C [ R [ S) : 2 if isEmpty(S) or inconsistent(AC S) return ; 3 else return FLEXD(;; S; AC);

In our example reconfiguration task, the original configuration S = fs1; s2; s3; s4; s5; s6; s7; s8g and the new set of customer requirements is R = fr10; r20g. Since S [ R [ C is inconsistent, we are in the need of a minimal diagnosis and a reconfiguration S such that S [ S [ R [ C is consistent. In the following we will show how the FLEXDIAG (Algorithm 1) can be applied to determine a minimal diagnosis .

The FLEXDIAG algorithm is assumed to be activated under the assumption that AC is inconsistent, i.e., the consistency of AC is not checked by the algorithm. If AC is inconsistent but AC S is also inconsistent, FLEXDIAG will not be able to identify a diagnosis in S; therefore ; is returned. Otherwise, a recursive function FLEXD is activated which is in charge of determining one minimal diagnosis . In each recursive step, the constraints in S are divided into two different subsets (S1 and S2) in order to figure out if already one of these subsets includes a diagnosis. If this is the case, the second set must not be inspected for diagnosis elements anymore.

FLEXDIAG is based on the concepts of FASTDIAG [ 9 ], i.e., it returns one diagnosis ( ) at a time and is complete in the sense that if a diagnosis is contained in S, then the algorithm will find it. A corresponding reconfiguration can be determined by a solver call C [ R [ (S ). The determination of multiple diagnoses at a time can be realized on the basis of the construction of a HSDAG [ 19 ]. If m = 1 (see Algorithm 1), the number of consistency checks needed for determining one minimal diagnosis is 2 log2( n ) + 2 in the worst case [ 9 ]. In this context, represents the set size of the minimal diagnosis and n represents the number of constraints in solution S.

If m > 1, the number of needed consistency checks can be systematically reduced if we accept the tradeoff of possibly loosing the property of diagnosis minimality (see Definition 2). If we allow settings with m > 1, we can reduce the upper bound of the number of consistency checks to 2 log2( 2nm ) in the worst case. These upper bounds regarding the number of needed consistency checks allow to estimate the worst case runtime performance of the diagnosis algorithm which is extremely important for realtime scenarios. Consequently, if we are able to estimate the upper limit of the runtime needed for completing one consistency check (e.g., on the basis of simulations with an underlying constraint solver), we are also able to figure out lower bounds for m that must be chosen in order to guarantee a FLEXDIAG runtime within predefined time limits.

Table 1 depicts an overview of consistency checks needed depending on the setting of the parameter m and the diagnosis size for jSj = 16. For example, if m = 2 and the size of a minimal diagnosis is = 4, then the upper bound for the number of needed consistency checks is 16. If the size of increases further, the number of corresponding consistency checks does not increase anymore. Figures 1 and 2 depict FLEXDIAG search trees depending on the setting of granularity parameter m.

FLEXDIAG determines one diagnosis at a time which indicates variable assignments of the original configuration that have to be changed such that a reconfiguration conform to the new requirements (R ) is possible. The algorithm supports the determination of leading diagnoses, i.e., diagnoses that are preferred with regard to given user preferences [ 9 ]. FLEXDIAG is based on a strict lexicographical ordering of the constraints in S: the lower the importance of a constraint si 2 S the lower the index of the constraint in S. For example, s1 : pc = 3 has the lowest ranking. The lower the ranking, the higher the probability that the constraint will be part of a reconfiguration S . Since s1 has the lowest priority and it is part of a conflict, it is element of the diagnosis returned by FLEXDIAG. For a discussion of the properties of lexicographical orderings we refer to [ 9, 15 ]. 5

Evaluation

In order to evaluate FLEXDIAG, we analyzed the two major aspects of (1) algorithm performance and (2) diagnosis quality in terms of minimality and accuracy. We analyzed both aspects by varying the value of parameter m. Our hypothesis in this context was that the higher the value of m, the lower the number of needed consistency checks (the higher the efficiency of diagnosis search) and the lower diagnosis quality in terms of the share of diagnosis-relevant constraints returned by FLEXDIAG. Diagnosis quality can, for example, be measured by the degree of minimality of the constraints contained in a diagnosis returned by FLEXDIAG (see Formula 1). id

m=1 1.0(1.0) 1.0(1.0) 1.0(1.0) 1.0(1.0)

If m > 1, there is no guarantee that the diagnosis determined for S is a superset of the diagnosis min determined for S in the case m = 1. Besides minimality, we introduce accuracy as an additional quality indicator (see Formula 2). The higher the share of elements of min in , the higher the corresponding accuracy (the algorithm is able to reproduce the elements of the minimal diagnosis for m = 1). accuracy( ) = j \ minj j minj

In order to evaluate FLEXDIAG with regard to both aspects we applied the algorithm to the configuration benchmark from www.splotresearch.org - the configuration models are feature models which include requirement constraints, compatibility constraints, and different types of structural constraints such as mandatory relationships and alternatives. The feature models were represented as CSP on the basis of the Java-based Choco library.3 For each setting (see Table 2) in the benchmark, we randomly generated jR j new requirements that were inconsistent with an already determined configuration (10 iterations per setting). The average cardinality of a minimal diagnosis for m = 1 is j minj. Related average runtimes (in milliseconds)4 and degrees of minimality and accuracy (see Formula 1) are depicted in Table 2. As can be seen in Table 2, increasing the value of m leads to an improved runtime performance in our example cases. Minimality and accuracy depend on the configuration domain and are not necessarily monotonous. For example, since a diagnosis determined by FLEXDIAG is not necessarily a superset of a diagnosis determined with m = 1, it can be the case that the minimality of a diagnosis determined with m > 1 is greater than 1 (if FLEXDIAG determines a diagnosis with lower cardinality than the minimal diagnosis determined with m = 1).

Note that in this paper we did not compare FLEXDIAG with more traditional diagnosis approaches – for related evaluations we refer the reader to [ 9 ] were detailed related analyses can be found. The outcome of these analyses is that direct diagnosis approaches such as FLEXDIAG clearly outperform standard diagnosis approaches based on the resolution of minimal conflicts [ 19 ]. 6

Reconfiguration in Production

The following simplified reconfiguration task is related to scheduling in production where it is often the case that, for example, schedules and corresponding production equipment has to be reconfigured. In 3 choco-solver.org. 4 Test platform: Windows 7 Professional 64 Bit, Intel(R) Core(TM) i5-2320 3.00 GHz CPU with 8.00 GB of memory. (1) (2) this example setting we do not take into account configurable production equipment (configurable machines) and limit the reconfiguration to the assignment of orders to corresponding machines. The assignment of an order oi to a certain machine mj is represented by the corresponding variable oimj . The domain of each such variable represents the different possible slots in which an order can be processed, for example, o1m1 = 1 denotes the fact that the processing of order o1 on machine m1 is performed during and finished after time slot 1.

Further constraints restrict the way in which orders are allowed to be assigned to machines, for example, o1m1 < o1m2 denotes the fact that order o1 must be completed on machine m1 before a further processing is started on machine m2. Furthermore, no two orders must be assigned to the same machine during the same time slot, for example, o1m1 6= o2m1 denotes the fact that order o1 and o2 must not be processed on the same machine in the same time slot (slots 1..3). Finally, the definition of our reconfiguration task is completed with an already determined schedule S and a corresponding reconfiguration request represented by the reconfiguration requirement R = fr10 : o3m3 < 5g, i.e., order o3 should be completed within less than 5 time units.

V = fo1m1; o1m2; o1m3; o2m1; o2m2; o2m3; o3m1; o3m2; o3m3g dom(o1m1) = dom(o2m1) = dom(o3m1) = f1; 2; 3g: dom(o1m2) = dom(o2m2) = dom(o3m2) = f2; 3; 4g: dom(o1m3) = dom(o2m3) = dom(o3m3) = f3; 4; 5g: C = fc1 : o1m1 < o1m2; c2 : o1m2 < o1m3; c3 : o2m1 < o2m2; c4 : o2m2 < o2m3; c5 : o3m1 < o3m2; c6 : o3m2 < o3m3; c7 : o1m1 6= o2m1; c8 : o1m1 6= o3m1; c9 : o2m1 6= o3m1; c10 : o1m2 6= o2m2; c11 : o1m2 6= o3m2; c12 : o2m2 6= o3m2; c13 : o1m3 6= o2m3; c14 : o1m3 6= o3m3; c15 : o2m3 6= o3m3g S = fs1 : o1m1 = 1; s2 : o1m2 = 2; s3 : o1m3 = 3; s4 : o2m1 = 2; s5 : o2m2 = 3; s6 : o2m3 = 4; s7 : o3m1 = 3; s8 : o3m2 = 4; s9 : o3m3 = 5g R = fr10 : o3m3 < 5g

This reconfiguration task can be solved using FLEXDIAG. If we keep the ordering of the constraints as defined in S, FLEXDIAG (with m = 1) returns the diagnosis : fs4; s5; s6; s7; s8g which can be used to determine the new solution S = fs1 : o1m1 = 1; s2 : o1m2 = 2; s3 : o1m3 = 3; s4 : o2m1 = 3; s5 : o2m2 = 4; s6 : o2m3 = 5; s7 : o3m1 = 2; s8 : o3m2 = 3; s9 : o3m3 = 4g. Possible ordering criteria for constraints in such rescheduling scenarios can be, for example, customer value (changes related to orders of important customers should occur with a lower probability) and the importance of individual orders. If some orders in a schedule should not be changed, this can be achieved by simply defining such requests as requirements (R ), i.e., change requests as well as stability requests can be included as constraints ri0 in R . 7

Ongoing And Future Work

We are currently evaluating FLEXDIAG with a more complex (industrial) benchmark from three different German car manufacturers on the level of type series. In this context we include further evaluation metrics that help to better estimate the quality of diagnoses (reconfigurations) – for example, the currently applied accuracy metric does not take into account the importance of the different constraints contained in a diagnosis. Furthermore, we will extend the FLEXDIAG algorithm in order to make it applicable in scenarios where knowledge bases are tested [ 6 ]. Our goal in this context is to improve the performance of existing automated debugging approaches and to investigate to which extent diagnoses resulting from m > 1 are considered as relevant by knowledge engineers. Finally, we will compare FLEXDIAG with local search approaches such as genetic algorithms. 8

Conclusions

Efficient reconfiguration functionalities are needed in various scenarios such as the reconfiguration of production schedules, the reconfiguration of the settings in mobile phone networks, and the reconfiguration of robot context information. We analyzed the FLEXDIAG algorithm with regard to potentials of improving existing direct diagnosis algorithms. When using FLEXDIAG, there is a clear tradeoff between performance of diagnosis calculation and diagnosis quality (measured, for example, in terms of minimality and accuracy). 110

References

[1] R. Bakker , F. Dikker , F. Tempelman , and P. Wogmim , ' Diagnosing and solving over-determined constraint satisfaction problems' , in 13th International Joint Conference on Artificial Intelligence , pp. 276 - 281 , Chambery, France, ( 1993 ).

[2] S.K. Card , G.G. Robertson , and J.D. Mackinlay , ' The information visualizer, an information workspace' , in CHI '91 Proceedings of the SIGCHI Conference on Human Factors in Computing Systems , pp. 181 - 188 , New Orleans, Louisiana, USA, ( 1991 ). ACM.

[3] J. DeKleer , ' Using crude probability estimates to guide diagnosis' , AI Journal , 45 ( 3 ), 381 - 391 , ( 1990 ).

[4] A. Falkner , A. Felfernig , and A. Haag , ' Recommendation Technologies for Configurable Products' , AI Magazine , 32 ( 3 ), 99 - 108 , ( 2011 ).

[5] A. Falkner and H. Schreiner , 'SIEMENS: Configuration and Reconfiguration in Industry', in Knowledge-based Configuration - From Research to Business Cases, eds., A. Felfernig , L. Hotz , C. Bagley , and J. Tiihonen , chapter 16 , 251 - 264 , Morgan Kaufmann Publishers, ( 2013 ).

[6] A. Felfernig , G. Friedrich , D. Jannach , and M. Stumptner , ' Consistency-based diagnosis of configuration knowledge bases' , Artificial Intelligence , 152 ( 2 ), 213 - 234 , ( 2004 ).

[7] A. Felfernig , L. Hotz , C. Bagley , and J. Tiihonen , Knowledge-based Configuration: From Research to Business Cases , Elsevier/Morgan Kaufmann Publishers, 1st edn., 2014 .

[8] A. Felfernig , M. Schubert , G. Friedrich, M. Mandl , M. Mairitsch , and E. Teppan, ' Plausible repairs for inconsistent requirements' , in 21st International Joint Conference on Artificial Intelligence (IJCAI'09) , pp. 791 - 796 , Pasadena, CA, USA, ( 2009 ).

[9] A. Felfernig , M. Schubert , and C. Zehentner , ' An efficient diagnosis algorithm for inconsistent constraint sets' , Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM) , 26 ( 1 ), 53 - 62 , ( 2012 ).

[10] A. Fijany and F. Vatan , ' New approaches for efficient solution of hitting set problem' , in Winter International Symposium on Information and Communication Technologies , pp. 1 - 6 , Cancun, Mexico, ( 2004 ). Trinity College Dublin.

[11] Gerhard Fleischanderl , Gerhard E. Friedrich, Alois Haselbo¨ck, Herwig Schreiner, and Markus Stumptner, ' Configuring large systems using generative constraint satisfaction' , IEEE Intelligent Systems , 13 ( 4 ), 59 - 68 , ( 1998 ).

[12] G. Friedrich , A. Ryabokon , A. Falkner , A . Haselbo¨ck, G. Schenner, and H. Schreiner , ' (Re)configuration using Answer Set Programming' , in IJCAI 2011 Workshop on Configuration , pp. 17 - 24 , ( 2011 ).

[13] L. Hotz , A. Felfernig , M. Stumptner , A. Ryabokon , C. Bagley , and K. Wolter , ' Configuration Knowledge Representation & Reasoning', in Knowledge-based Configuration - From Research to Business Cases, eds., A. Felfernig , L. Hotz , C. Bagley , and J. Tiihonen , chapter 6 , 59 - 96 , Morgan Kaufmann Publishers, ( 2013 ).

[14] D. Jannach , ' Finding preferred query relaxations in content-based recommenders' , in 3rd Intl. IEEE Conference on Intelligent Systems , pp. 355 - 360 , London, UK , ( 2006 ).

[15] Ulrich Junker , ' QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems' , in 19th Intl. Conference on Artifical Intelligence (AAAI'04) , eds., Deborah L. McGuinness and George Ferguson , pp. 167 - 172 . AAAI Press, ( 2004 ).

[16] A. Mackworth , ' Consistency in Networks of Relations' , Artificial Intelligence , 8 ( 1 ), 99 - 118 , ( 1977 ).

[17] J. Marques-Silva , F. Heras , M. Janota , A. Previti , and A. Belov , ' On computing minimal correction subsets' , in IJCAI 2013 , pp. 615 - 622 , Peking, China, ( 2013 ).

[18] I. Nica , F. Wotawa , R. Ochenbauer , C. Schober , H. Hofbauer , and S. Boltek , 'Kapsch: Reconfiguration of Mobile Phone Networks', in Knowledge-based Configuration - From Research to Business Cases, eds., A. Felfernig , L. Hotz , C. Bagley , and J. Tiihonen , chapter 19 , 287 - 300 , Morgan Kaufmann Publishers, ( 2013 ).

[19] R. Reiter , ' A theory of diagnosis from first principles' , Artificial Intelligence , 32 ( 1 ), 57 - 95 , ( 1987 ).

[20] M. Schubert and A. Felfernig , 'BFX: Diagnosing Conflicting Requirements in Constraint-based Recommendation' , International Journal on Artificial Intelligence Tools , 20 ( 2 ), 297 - 312 , ( 2011 ).

[21] I. Shah , ' Direct algorithms for finding minimal unsatisfiable subsets in over-constrained csps' , International Journal on Artificial Intelligence Tools , 20 ( 1 ), 53 - 91 , ( 2011 ).

[22] Carsten Sinz , Andreas Kaiser, and Wolfgang Ku¨chlin, ' Formal methods for the validation of automotive product configuration data' , Artificial Intelligence for Engineering Design, Analysis and Manufacturing , 17 ( 1 ), 75 - 97 , ( 2003 ).

[23] G. Steinbauer , M. Mo¨rth, and F. Wotawa , ' Real-Time Diagnosis and Repair of Faults of Robot Control Software' , in RoboCup 2005 , LNAI, pp. 13 - 23 . Springer, ( 2005 ).

[24] M. Stumptner , ' An Overview of Knowledge-based Configuration' , AI Communications , 10 ( 2 ), 111 - 126 , ( 1997 ).

[25] M. Stumptner and F. Wotawa , ' Reconfiguration using model-based diagnosis' , in 10th International Workshop on Principles of Diagnosis (DX-99) , pp. 266 - 271 , ( 1999 ).

[26] J. Tiihonen and A. Anderson , ' VariSales', in Knowledge-based Configuration - From Research to Business Cases, eds., A. Felfernig , L. Hotz , C. Bagley , and J. Tiihonen , chapter 26 , 377 - 388 , Morgan Kaufmann Publishers, ( 2013 ).

[27] J. Tiihonen , W. Mayer , M. Stumptner , and M. Heiskala , ' Configuring Services and Processes', in Knowledge-based Configuration - From Research to Business Cases, eds., A. Felfernig , L. Hotz , C. Bagley , and J. Tiihonen , chapter 21 , 313 - 324 , Morgan Kaufmann Publishers, ( 2013 ).

[28] R. Walter and W. Ku¨chlin, ' ReMax - A MaxSAT aided Product (Re-) Configurator ', in Workshop on Configuration 2014 , pp. 55 - 66 , ( 2014 ).

[29] R. Walter , C. Zengler , and W. Ku¨chlin, ' Applications of maxsat in automotive configuration' , in Workshop on Configuration 2013 , pp. 21 - 28 , ( 2013 ).

[30] K. Wang , Z. Li , Y. Ai , and Y. Zhang , ' Computing Minimal Diagnosis with Binary Decision Diagrams Algorithm' , in 6th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD'2009) , pp. 145 - 149 , ( 2009 ).

[31] F. Wotawa , ' A variant of reiter's hitting-set algorithm' , Information Processing Letters , 79 ( 1 ), 45 - 51 , ( 2001 ).