=Paper=
{{Paper
|id=Vol-1453/16_FelfernigWalterReiterer_Flexdiag-AnytimeDiagnosisFor_Confws-15_p105
|storemode=property
|title=FlexDiag: anytime diagnosis for reconfiguration
|pdfUrl=https://ceur-ws.org/Vol-1453/16_FelfernigWalterReiterer_Flexdiag-AnytimeDiagnosisFor_Confws-15_p105.pdf
|volume=Vol-1453
|dblpUrl=https://dblp.org/rec/conf/confws/FelfernigWR15
}}
==FlexDiag: anytime diagnosis for reconfiguration==
https://ceur-ws.org/Vol-1453/16_FelfernigWalterReiterer_Flexdiag-AnytimeDiagnosisFor_Confws-15_p105.pdf
F LEX D IAG : AnyTime Diagnosis
for Reconfiguration
Alexander Felfernig1 and Rouven Walter2 and Stefan Reiterer1
Abstract. Anytime diagnosis is able to determine solutions within Anytime diagnosis algorithms are useful in scenarios where diag-
predefined time limits. This is especially useful in realtime scenar- noses have to be provided in real-time, i.e., within given time limits.
ios such as production scheduling, robot control, and communication If diagnosis is applied in interactive configuration, for example, to
networks management where diagnosis and corresponding reconfig- determine repairs for inconsistent customer requirements, response
uration capabilities play a major role. Anytime diagnosis in many times should be below one second [2]. Efficient diagnosis and recon-
cases comes along with a tradeoff between diagnosis quality and the figuration of communication networks is crucial to retain the qual-
efficiency of diagnostic reasoning. In this paper we introduce and ity of service [18, 25]. In today’s production scenarios which are
analyze F LEX D IAG which is an anytime variant of existing direct characterized by small batch sizes and high product variability, it is
diagnosis approaches. We evaluate the algorithm with regard to per- increasingly important to develop algorithms that support the effi-
formance and diagnosis quality using a configuration benchmark. cient reconfiguration of schedules. Such functionalities support the
paradigm of smart production, i.e., the flexible and efficient produc-
Keywords: Anytime Diagnosis, Reconfiguration. tion 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].
1 Introduction Algorithmic approaches to provide efficient solutions for diagno-
sis problems are manyfold. Some approaches focus on improvements
Knowledge-based configuration is one of the most successful appli- of Reiter’s original hitting set directed acyclic graph (HSDAG) [19]
cations of Artificial Intelligence [7, 24]. There are many different in terms of a personalized computation of leading diagnoses [3] or
applications of configuration technologies ranging from telecommu- other extensions that make the basic approach [19] more efficient
nication infrastructures [11], railway interlocking systems [5], the [31]. Wang et al. [30] introduce an approach to derive binary decision
automotive domain [22, 26, 28] to the configuration of services [27]. diagrams (BDDs) on the basis of a pre-determined set of conflicts –
Configuration technologies must be able to deal with inconsistencies diagnoses can then be determined by solving the BDD. A pre-defined
which can occur in different contexts. First, a configuration knowl- set of conflicts can also be compiled into a corresponding linear opti-
edge base can be inconsistent, i.e., no solution can be determined. In mization problem [10]; diagnoses can then be determined by solving
this context, the task of knowledge engineers is to figure out which the given problem. In knowledge-based recommendation scenarios,
constraints are responsible for the unintended behavior of the knowl- diagnoses for user requirements can be pre-compiled in such a way
edge base. Bakker et al. [1] show the application of model-based di- that for a given set of customer requirements, the diagnosis search
agnosis [19] to determine minimal sets of constraints in a knowledge task can be reduced to querying a relational table (see, for example,
base that are responsible for a given inconsistency. A variant thereof [14, 20]). All of the mentioned approaches either extend the approach
is documented in Felfernig et al. [6] where an approach to the auto- of Reiter [19] or improve efficiency by exploiting pre-generated in-
mated debugging of knowledge bases with test cases is introduced. formation about conflicts or diagnoses.
Felfernig et al. [6] also show how to diagnose customer requirements An alternative to conflict-directed diagnosis [19] are direct diag-
that are inconsistent with a configuration knowledge base. The un- nosis algorithms that determine minimal diagnoses without the need
derlying assumption is that the configuration knowledge base itself of pre-determing minimal conflict sets [9, 17, 21]. The FAST D IAG
is consistent but combined with a set of requirements is inconsistent. algorithm [9] is a divide-and-conquer based algorithm that supports
All diagnosis approaches mentioned so far are based on conflict- the determination of diagnoses without a preceding conflict detec-
directed hitting set determination [15, 19]. These approaches typ- tion. In this paper we show how this algorithm can be converted into
ically determine diagnoses in a breadth-first search manner which an anytime diagnosis algorithm (F LEX D IAG) that is able to improve
allows the identification of minimal cardinality diagnoses. The ma- performance by disregarding the aspect of minimality, i.e., the algo-
jor disadvantage of applying these approaches is the need of pre- rithm allows for tradeoffs between diagnosis quality (e.g., minimal-
determining minimal conflicts which is inefficient especially in cases ity) and performance of diagnostic search. In this paper we focus on
where only the leading diagnoses (the most relevant ones) are sought. reconfiguration scenarios, i.e., we show how F LEX D IAG can be ap-
plied in situations where a given configuration (solution) has to be
1 Applied Software Engineering Group, Institute for Software adapted conform to a changed set of customer requirements.
Technology, TU Graz, Austria, email: {alexander.felfernig, ste- Our contributions in this paper are the following. First, we show
fan.reiterer}@ist.tugraz.at how to solve reconfiguration tasks with direct diagnosis. Second, we
2 Symbolic Computation Group, WSI Informatics, Universität Tübingen,
make direct diagnosis anytime-aware by including a parametrization
Germany, email: rouven.walter@uni-tuebingen.de
105 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
that helps to systematically reduce the number of consistency checks. ments. Examples thereof are changing requirements that have to be
Finally, we report the results of a F LEX D IAG-related evaluation con- taken into account in production schedules, failing components or
ducted on the basis of a configuration benchmark. overloaded network infrastructures in a mobile phone network, and
The remainder of this paper is organized as follows. In Section changes in the internal model of the environment of a robot. In the
2 we introduce an example configuration knowledge base from the following we assume that the palette of paper should be reassigned
domain of resource allocation. This knowledge base will serve as a to container 3 and the personal computer and games palettes should
working example throughout the paper. Thereafter (Section 3) we in- be assigned to the same container. Formally, the set of new require-
troduce a definition of a reconfiguration task. In Section 4 we discuss ments is represented by Rρ : {r10 : pc = games, r20 : paper = 3}.
basic principles of direct diagnosis on the basis of F LEX D IAG and In order to determine reconfigurations, we have to calculate a corre-
show how this algorithm can be applied in reconfiguration scenar- sponding diagnosis ∆ (see Definition 2).
ios. In Section 5 we present the results of a performance analysis. A Definition 2 (Diagnosis). A diagnosis ∆ (correction subset) is a
simple example of the application of F LEX D IAG in production envi- subset of S = {s1 : v1 = a1 , s2 : v2 = a2 , ..., sn : vn = an } such
ronments is given in Section 6. In Section 7 we discuss major issues that S − ∆ ∪ C ∪ Rρ is consistent. ∆ is minimal if there does not
for future work. With Section 8 we conclude the paper. exist a diagnosis ∆0 with ∆0 ⊂ ∆.
On the basis of the definition of a minimal diagnosis, we can in-
2 Example Configuration Knowledge Base troduce a formal definition of a reconfiguration task.
Definition 3 (Reconfiguration Task and Reconfiguration). A recon-
A configuration system determines configurations (solutions) on the figuration task can be defined as a CSP (V, D, C, S, Rρ ) where V
basis of a given set of customer requirements [13]. In many cases, is a set of variables, D represents variable domain definitions, C
constraint satisfaction problem (CSP) representations [16] are used is a set of constraints, S represents an existing configuration, and
for the definition of a configuration task. A configuration task and a Rρ = {r10 , r20 , ..., rk0 } (Rρ consistent with C) represents a set of
corresponding configuration (solution) can be defined as follows. reconfiguration requirements. A reconfiguration is a variable assign-
Definition 1 (Configuration Task and Configuration). A con- ment S∆ = {s1 : v1 = a01 , s2 : v2 = a02 , ..., sl : vl = a0l } where
figuration task can be defined as a CSP (V, D, C) where V = si ∈ ∆, a0i 6= ai , and S − ∆ ∪ S∆ ∪ C ∪ Rρ is consistent.
{v1 , v2 , ..., vn } is a set of variables, D = ∪dom(vi ) represents do- If Rρ is inconsistent with C, the new requirements have to be an-
main definitions, and C = {c1 , c2 , ..., cm } is a set of constraints. Ad- alyzed and changed before a corresponding reconfiguration task can
ditionally, user requirements are represented by a set of constraints be triggered [4, 8]. An example of a reconfiguration task in the con-
R = {r1 , r2 , ..., rk }. A configuration (solution) for a configuration text of our configuration knowledge base is the following.
task is a set of assignments (constraints) S = {s1 : v1 = a1 , s2 : Example (Reconfiguration Task). In the resource allocation prob-
v2 = a2 , ..., sn : vn = an )} where ai ∈ dom(vi ) which is consis- lem, the original customer requirements R are substituted by the re-
tent with C ∪ R. quirements Rρ = {r10 : pc = games, r20 : paper = 3}. The result-
An example of a configuration task represented as a constraint sat- ing reconfiguration task instance is the following.
isfaction problem is the following.
Example (Configuration Task). In this resource allocation problem • V = {f uel, paper, f ireworks, pc, games, oil, roof, pipes}
example, items (a barrel of fuel, a stack of paper, a pallet of fire- • dom(f uel) = dom(paper) = dom(f ireworks) =
works, a pallet of personal computers, a pallet of computer games, a dom(pc) = dom(games) = dom(oil) = dom(roof ) =
barrel of oil, a palette of roof tiles, and a palette of rain pipes) have to dom(pipes) = {1, 2, 3}
be assigned to three different containers. There are a couple of con- • C = {c1 : f ireworks 6= f uel, c2 : f ireworks 6= paper, c3 :
straints (ci ) to be taken into account, for example, fireworks must not f ireworks 6= oil, c4 : pipes = roof, c5 : paper 6= f uel}
be combined with fuel (c1 ). Furthermore, there is one requirement • S = {s1 : pc = 3, s2 : games = 1, s3 : paper = 2, s4 :
(r1 ) which indicates that the palette of fireworks has to be assigned f uel = 3, s5 : f ireworks = 1, s6 : oil = 2, s7 : roof =
to container 1. On the basis of this configuration task definition, a 1, s8 : pipes = 1}
configurator can determine a configuration S. • Rρ = {r10 : pc = games, r20 : paper = 3}
• V = {f uel, paper, f ireworks, pc, games, oil, roof, pipes} To solve a reconfiguration task (see Definition 3), conflict-directed
• dom(f uel) = dom(paper) = dom(f ireworks) = diagnosis approaches [19] would determine a set of minimal conflicts
dom(pc) = dom(games) = dom(oil) = dom(roof ) = and then determine a hitting set that resolves each of the identified
dom(pipes) = {1, 2, 3} conflicts. In this context, a minimal conflict set CS ⊆ S is a min-
• C = {c1 : f ireworks 6= f uel, c2 : f ireworks 6= paper, c3 : imal set of variable assignments that trigger an inconsistency with
f ireworks 6= oil, c4 : pipes = roof, c5 : paper 6= f uel} C ∪ Rρ , i.e., CS ∪ C ∪ Rρ is inconsistent and there does not exist a
• R = {r1 : f ireworks = 1} conflict set CS 0 with CS 0 ⊂ CS. In our working example, the min-
• S = {s1 : pc = 3, s2 : games = 1, s3 : paper = 2, s4 : imal conflict sets are CS1 : {s1 : pc = 3, s2 : games = 1},
f uel = 3, s5 : f ireworks = 1, s6 : oil = 2, s7 : roof = CS2 : {s3 : paper = 2}, and CS3 : {s4 : f uel = 3}.
1, s8 : pipes = 1} The corresponding minimal diagnoses are ∆1 : {s1 , s3 , s4 } and
∆2 : {s2 , s3 , s4 }. The elements in a diagnosis indicate which vari-
On the basis of the given definition of a configuration task, we now able assignments have to be adapted such that a reconfiguration
introduce the concept of reconfiguration (see also [12, 18, 25, 28]). 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
3 Reconfiguration Task call C ∪ Rρ ∪ (S − ∆1 ). The resulting configuration S 0 can be
It can be the case that an existing configuration S has to be adapted {s1 : pc = 1, s2 : games = 1, s3 : paper = 3, s4 : f uel = 2, s5 :
due to a change or extension of the given set of customer require- f ireworks = 1, s6 : oil = 2, s7 : roof = 1, s8 : pipes = 1}. For
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 106
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
a detailed discussion of conflict-based diagnosis we refer to Reiter If m > 1, the number of needed consistency checks can be sys-
[19]. In the following we introduce an approach to the determination tematically reduced if we accept the tradeoff of possibly loosing the
of minimal reconfigurations which is based on a direct diagnosis al- property of diagnosis minimality (see Definition 2). If we allow set-
gorithm, i.e., diagnoses are determined without the need of determin- tings with m > 1, we can reduce the upper bound of the number
2n
ing related minimal conflict sets. of consistency checks to 2δ × log2 ( δ×m ) in the worst case. These
upper bounds regarding the number of needed consistency checks al-
low to estimate the worst case runtime performance of the diagnosis
4 Reconfiguration with F LEX D IAG algorithm which is extremely important for realtime scenarios. Con-
sequently, if we are able to estimate the upper limit of the runtime
In the following discussions, the set AC = C ∪ Rρ ∪ S represents needed for completing one consistency check (e.g., on the basis of
the union of all constraints that restrict the set of possible solutions simulations with an underlying constraint solver), we are also able
for a given reconfiguration task. Furthermore, S represents a set of to figure out lower bounds for m that must be chosen in order to
constraints that are considered as candidates for being included in a guarantee a F LEX D IAG runtime within predefined time limits.
diagnosis ∆. The idea of F LEX D IAG (Algorithm 1) is to systemati- Table 1 depicts an overview of consistency checks needed depend-
cally filter out the constraints that become part of a minimal diagnosis ing on the setting of the parameter m and the diagnosis size δ for
using a divide-and-conquer based approach. |S| = 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 cor-
Algorithm 1 − F LEX D IAG. responding consistency checks does not increase anymore. Figures
1 and 2 depict F LEX D IAG search trees depending on the setting of
1 func F LEX D IAG(S, AC = C ∪ Rρ ∪ S) : ∆
2 if isEmpty(S) or inconsistent(AC − S) return ∅ granularity parameter m.
3 else return F LEX D(∅, S, AC);
4 func F LEX D(D, S = {s1 ..sq }, AC) : ∆ δ m=1 m=2 m=4 m=8
5 if D 6= 0 and consistent(AC) return ∅; 1 10 8 6 4
6 if size(S) ≤ m return S; 2 16 12 8 4
q 4 24 16 8 4
7 k= ;
2 8 32 16 16 16
8 S1 = {s1 ..sk }; S2 = {sk+1 ..sq };
9 D1 = F LEX D(S1 , S2 , AC − S1 );
10 D2 = F LEX D(D1 , S1 , AC − D1 ); Table 1. Worst-case estimates for the number of needed consistency
11 return(D1 ∪ D2 ); checks depending on the granularity parameter m and the diagnosis size δ
for |S| = 16.
In our example reconfiguration task, the original configuration F LEX D IAG determines one diagnosis at a time which indicates
S = {s1 , s2 , s3 , s4 , s5 , s6 , s7 , s8 } and the new set of customer re- variable assignments of the original configuration that have to be
quirements is Rρ = {r10 , r20 }. Since S ∪ Rρ ∪ C is inconsistent, we changed such that a reconfiguration conform to the new requirements
are in the need of a minimal diagnosis ∆ and a reconfiguration S∆ (Rρ ) is possible. The algorithm supports the determination of lead-
such that S −∆∪S∆ ∪Rρ ∪C is consistent. In the following we will ing diagnoses, i.e., diagnoses that are preferred with regard to given
show how the F LEX D IAG (Algorithm 1) can be applied to determine user preferences [9]. F LEX D IAG is based on a strict lexicographi-
a minimal diagnosis ∆. cal ordering of the constraints in S: the lower the importance of a
The F LEX D IAG algorithm is assumed to be activated under the constraint si ∈ S the lower the index of the constraint in S. For
assumption that AC is inconsistent, i.e., the consistency of AC is example, s1 : pc = 3 has the lowest ranking. The lower the rank-
not checked by the algorithm. If AC is inconsistent but AC − S is ing, the higher the probability that the constraint will be part of a
also inconsistent, F LEX D IAG will not be able to identify a diagnosis reconfiguration S∆ . Since s1 has the lowest priority and it is part of
in S; therefore ∅ is returned. Otherwise, a recursive function F LEX D a conflict, it is element of the diagnosis returned by F LEX D IAG. For
is activated which is in charge of determining one minimal diagnosis a discussion of the properties of lexicographical orderings we refer
∆. In each recursive step, the constraints in S are divided into two to [9, 15].
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. 5 Evaluation
F LEX D IAG is based on the concepts of FAST D IAG [9], i.e., it re-
turns one diagnosis (∆) at a time and is complete in the sense that In order to evaluate F LEX D IAG, we analyzed the two major aspects
if a diagnosis is contained in S, then the algorithm will find it. A of (1) algorithm performance and (2) diagnosis quality in terms of
corresponding reconfiguration can be determined by a solver call minimality and accuracy. We analyzed both aspects by varying the
C ∪ Rρ ∪ (S − ∆). The determination of multiple diagnoses at a value of parameter m. Our hypothesis in this context was that the
time can be realized on the basis of the construction of a HSDAG higher the value of m, the lower the number of needed consistency
[19]. If m = 1 (see Algorithm 1), the number of consistency checks checks (the higher the efficiency of diagnosis search) and the lower
needed for determining one minimal diagnosis is 2δ × log2 ( nδ ) + 2δ diagnosis quality in terms of the share of diagnosis-relevant con-
in the worst case [9]. In this context, δ represents the set size of the straints returned by F LEX D IAG. Diagnosis quality can, for example,
minimal diagnosis ∆ and n represents the number of constraints in be measured by the degree of minimality of the constraints contained
solution S. in a diagnosis ∆ returned by F LEX D IAG (see Formula 1).
107 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
Figure 1. F LEX D IAG: determining one minimal diagnosis with m = 1 (∆ = {s1 , s3 , s4 }).
Figure 2. F LEX D IAG: determining a minimal diagnosis with m = 2 (∆ = {s1 , s2 , s3 , s4 }).
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 108
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
id |V | |C| |Rρ | |∆min | avg. runtime (ms) minimality (accuracy)
m=1 m=2 m=4 m=6 m=10 m=1 m=2 m=4 m=6 m=10
1 47 285 5 4 772 647 561 429 350 1.0(1.0) 0.56(1.0) 0.45(1.0) 0.21(1.0) 0.15(1.0)
2 55 73 10 7 359 273 203 180 85 1.0(1.0) 0.55(0.91) 0.31(0.91) 0.30(0.83) 0.41(0.58)
3 73 150 10 5 733 593 343 304 195 1.0(1.0) 0.64(0.91) 0.83(0.55) 0.83(0.55) 1.07(0.30)
4 158 242 20 24 2176 1864 1451 1419 819 1.0(1.0) 0.66(0.89) 0.43(0.82) 0.41(0.67) 0.33(0.65)
Table 2. Avg. runtime and minimality of F LEX D IAG evaluated with feature models from www.splot-research.org (calculation of the first diagnosis: 1: Dell
laptops, 2: Smarthomes, 3: Cars, 4: Xerox printers). |Rρ | is the number of changed requirements and |∆min | the average cardinality of minimal diagnoses.
|∆min | this example setting we do not take into account configurable pro-
minimality(∆) = (1) duction equipment (configurable machines) and limit the reconfigu-
|∆|
ration to the assignment of orders to corresponding machines. The
assignment of an order oi to a certain machine mj is represented by
If m > 1, there is no guarantee that the diagnosis ∆ determined the corresponding variable oi mj . The domain of each such variable
for S is a superset of the diagnosis ∆min determined for S in the case represents the different possible slots in which an order can be pro-
m = 1. Besides minimality, we introduce accuracy as an additional cessed, for example, o1 m1 = 1 denotes the fact that the processing
quality indicator (see Formula 2). The higher the share of elements of of order o1 on machine m1 is performed during and finished after
∆min in ∆, the higher the corresponding accuracy (the algorithm is time slot 1.
able to reproduce the elements of the minimal diagnosis for m = 1). Further constraints restrict the way in which orders are allowed
to be assigned to machines, for example, o1 m1 < o1 m2 denotes
|∆ ∩ ∆min | the fact that order o1 must be completed on machine m1 before a
accuracy(∆) = (2) further processing is started on machine m2 . Furthermore, no two
|∆min |
orders must be assigned to the same machine during the same time
In order to evaluate F LEX D IAG with regard to both aspects we ap- slot, for example, o1 m1 6= o2 m1 denotes the fact that order o1 and
plied the algorithm to the configuration benchmark from www.splot- o2 must not be processed on the same machine in the same time slot
research.org - the configuration models are feature models which in- (slots 1..3). Finally, the definition of our reconfiguration task is com-
clude requirement constraints, compatibility constraints, and differ- pleted with an already determined schedule S and a corresponding
ent types of structural constraints such as mandatory relationships reconfiguration request represented by the reconfiguration require-
and alternatives. The feature models were represented as CSP on the ment Rρ = {r10 : o3 m3 < 5}, i.e., order o3 should be completed
basis of the Java-based Choco library.3 For each setting (see Table within less than 5 time units.
2) in the benchmark, we randomly generated |Rρ | new requirements
that were inconsistent with an already determined configuration (10 • V = {o1 m1 , o1 m2 , o1 m3 , o2 m1 , o2 m2 , o2 m3 , o3 m1 ,
iterations per setting). The average cardinality of a minimal diagno- o3 m2 , o3 m3 }
sis for m = 1 is |∆min |. Related average runtimes (in milliseconds)4 • dom(o1 m1 ) = dom(o2 m1 ) = dom(o3 m1 ) = {1, 2, 3}.
and degrees of minimality and accuracy (see Formula 1) are depicted dom(o1 m2 ) = dom(o2 m2 ) = dom(o3 m2 ) = {2, 3, 4}.
in Table 2. As can be seen in Table 2, increasing the value of m leads dom(o1 m3 ) = dom(o2 m3 ) = dom(o3 m3 ) = {3, 4, 5}.
to an improved runtime performance in our example cases. Mini- • C = {c1 : o1 m1 < o1 m2 , c2 : o1 m2 < o1 m3 ,
mality and accuracy depend on the configuration domain and are not c3 : o2 m1 < o2 m2 , c4 : o2 m2 < o2 m3 , c5 : o3 m1 < o3 m2 ,
necessarily monotonous. For example, since a diagnosis determined c6 : o3 m2 < o3 m3 , c7 : o1 m1 6= o2 m1 ,
by F LEX D IAG is not necessarily a superset of a diagnosis determined c8 : o1 m1 6= o3 m1 , c9 : o2 m1 6= o3 m1 ,
with m = 1, it can be the case that the minimality of a diagnosis de- c10 : o1 m2 6= o2 m2 , c11 : o1 m2 6= o3 m2 ,
termined with m > 1 is greater than 1 (if F LEX D IAG determines c12 : o2 m2 6= o3 m2 , c13 : o1 m3 6= o2 m3 ,
a diagnosis with lower cardinality than the minimal diagnosis deter- c14 : o1 m3 6= o3 m3 , c15 : o2 m3 6= o3 m3 }
mined with m = 1). • S = {s1 : o1 m1 = 1, s2 : o1 m2 = 2, s3 : o1 m3 = 3,
Note that in this paper we did not compare F LEX D IAG with more s4 : o2 m1 = 2, s5 : o2 m2 = 3, s6 : o2 m3 = 4,
traditional diagnosis approaches – for related evaluations we refer s7 : o3 m1 = 3, s8 : o3 m2 = 4, s9 : o3 m3 = 5}
the reader to [9] were detailed related analyses can be found. The • Rρ = {r10 : o3 m3 < 5}
outcome of these analyses is that direct diagnosis approaches such as
F LEX D IAG clearly outperform standard diagnosis approaches based This reconfiguration task can be solved using F LEX D IAG. If we
on the resolution of minimal conflicts [19]. keep the ordering of the constraints as defined in S, F LEX D IAG (with
m = 1) returns the diagnosis ∆ : {s4 , s5 , s6 , s7 , s8 } which can be
used to determine the new solution S = {s1 : o1 m1 = 1, s2 :
6 Reconfiguration in Production o1 m2 = 2, s3 : o1 m3 = 3, s4 : o2 m1 = 3, s5 : o2 m2 = 4, s6 :
o2 m3 = 5, s7 : o3 m1 = 2, s8 : o3 m2 = 3, s9 : o3 m3 = 4}. Pos-
The following simplified reconfiguration task is related to scheduling
sible ordering criteria for constraints in such rescheduling scenarios
in production where it is often the case that, for example, schedules
can be, for example, customer value (changes related to orders of
and corresponding production equipment has to be reconfigured. In
important customers should occur with a lower probability) and the
3 choco-solver.org. importance of individual orders. If some orders in a schedule should
4 Test platform: Windows 7 Professional 64 Bit, Intel(R) Core(TM) i5-2320 not be changed, this can be achieved by simply defining such re-
3.00 GHz CPU with 8.00 GB of memory. quests as requirements (Rρ ), i.e., change requests as well as stability
109 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
requests can be included as constraints ri0 in Rρ . [11] Gerhard Fleischanderl, Gerhard E. Friedrich, Alois Haselböck, Herwig
Schreiner, and Markus Stumptner, ‘Configuring large systems using
generative constraint satisfaction’, IEEE Intelligent Systems, 13(4), 59–
7 Ongoing And Future Work 68, (1998).
We are currently evaluating F LEX D IAG with a more complex (indus- [12] G. Friedrich, A. Ryabokon, A. Falkner, A. Haselböck, G. Schenner, and
H. Schreiner, ‘ (Re)configuration using Answer Set Programming’, in
trial) benchmark from three different German car manufacturers on IJCAI 2011 Workshop on Configuration, pp. 17–24, (2011).
the level of type series. In this context we include further evaluation [13] L. Hotz, A. Felfernig, M. Stumptner, A. Ryabokon, C. Bagley, and
metrics that help to better estimate the quality of diagnoses (reconfig- K. Wolter, ‘Configuration Knowledge Representation & Reasoning’, in
urations) – for example, the currently applied accuracy metric does Knowledge-based Configuration – From Research to Business Cases,
not take into account the importance of the different constraints con- eds., A. Felfernig, L. Hotz, C. Bagley, and J. Tiihonen, chapter 6, 59–
tained in a diagnosis. Furthermore, we will extend the F LEX D IAG 96, Morgan Kaufmann Publishers, (2013).
algorithm in order to make it applicable in scenarios where knowl- [14] D. Jannach, ‘Finding preferred query relaxations in content-based rec-
ommenders’, in 3rd Intl. IEEE Conference on Intelligent Systems, pp.
edge bases are tested [6]. Our goal in this context is to improve the
355–360, London, UK, (2006).
performance of existing automated debugging approaches and to in- [15] Ulrich Junker, ‘QUICKXPLAIN: preferred explanations and relax-
vestigate to which extent diagnoses resulting from m > 1 are con- ations for over-constrained problems’, in 19th Intl. Conference on Artif-
sidered as relevant by knowledge engineers. Finally, we will compare ical Intelligence (AAAI’04), eds., Deborah L. McGuinness and George
F LEX D IAG with local search approaches such as genetic algorithms. Ferguson, pp. 167–172. AAAI Press, (2004).
[16] A. Mackworth, ‘Consistency in Networks of Relations’, Artificial Intel-
ligence, 8(1), 99–118, (1977).
8 Conclusions [17] J. Marques-Silva, F. Heras, M. Janota, A. Previti, and A. Belov, ‘On
Efficient reconfiguration functionalities are needed in various scenar- computing minimal correction subsets’, in IJCAI 2013, pp. 615–622,
ios such as the reconfiguration of production schedules, the reconfig- Peking, China, (2013).
[18] I. Nica, F. Wotawa, R. Ochenbauer, C. Schober, H. Hofbauer, and
uration of the settings in mobile phone networks, and the reconfig-
S. Boltek, ‘Kapsch: Reconfiguration of Mobile Phone Networks’, in
uration of robot context information. We analyzed the F LEX D IAG Knowledge-based Configuration – From Research to Business Cases,
algorithm with regard to potentials of improving existing direct di- eds., A. Felfernig, L. Hotz, C. Bagley, and J. Tiihonen, chapter 19, 287–
agnosis algorithms. When using F LEX D IAG, there is a clear tradeoff 300, Morgan Kaufmann Publishers, (2013).
between performance of diagnosis calculation and diagnosis quality [19] R. Reiter, ‘A theory of diagnosis from first principles’, Artificial Intel-
(measured, for example, in terms of minimality and accuracy). ligence, 32(1), 57–95, (1987).
[20] M. Schubert and A. Felfernig, ‘BFX: Diagnosing Conflicting Require-
ments in Constraint-based Recommendation’, International Journal on
REFERENCES Artificial Intelligence Tools, 20(2), 297–312, (2011).
[1] R. Bakker, F. Dikker, F. Tempelman, and P. Wogmim, ‘Diagnosing and [21] I. Shah, ‘Direct algorithms for finding minimal unsatisfiable subsets in
solving over-determined constraint satisfaction problems’, in 13th In- over-constrained csps’, International Journal on Artificial Intelligence
ternational Joint Conference on Artificial Intelligence, pp. 276–281, Tools, 20(1), 53–91, (2011).
Chambery, France, (1993). [22] Carsten Sinz, Andreas Kaiser, and Wolfgang Küchlin, ‘Formal meth-
[2] S.K. Card, G.G. Robertson, and J.D. Mackinlay, ‘The information vi- ods for the validation of automotive product configuration data’, Artifi-
sualizer, an information workspace’, in CHI ’91 Proceedings of the cial Intelligence for Engineering Design, Analysis and Manufacturing,
SIGCHI Conference on Human Factors in Computing Systems, pp. 17(1), 75–97, (2003).
181–188, New Orleans, Louisiana, USA, (1991). ACM. [23] G. Steinbauer, M. Mörth, and F. Wotawa, ‘Real-Time Diagnosis and
[3] J. DeKleer, ‘Using crude probability estimates to guide diagnosis’, AI Repair of Faults of Robot Control Software’, in RoboCup 2005, LNAI,
Journal, 45(3), 381–391, (1990). pp. 13–23. Springer, (2005).
[4] A. Falkner, A. Felfernig, and A. Haag, ‘Recommendation Technologies [24] M. Stumptner, ‘An Overview of Knowledge-based Configuration’, AI
for Configurable Products’, AI Magazine, 32(3), 99–108, (2011). Communications, 10(2), 111–126, (1997).
[5] A. Falkner and H. Schreiner, ‘SIEMENS: Configuration and Recon- [25] M. Stumptner and F. Wotawa, ‘Reconfiguration using model-based di-
figuration in Industry’, in Knowledge-based Configuration – From Re- agnosis’, in 10th International Workshop on Principles of Diagnosis
search to Business Cases, eds., A. Felfernig, L. Hotz, C. Bagley, (DX-99), pp. 266–271, (1999).
and J. Tiihonen, chapter 16, 251–264, Morgan Kaufmann Publishers, [26] J. Tiihonen and A. Anderson, ‘VariSales’, in Knowledge-based Config-
(2013). uration – From Research to Business Cases, eds., A. Felfernig, L. Hotz,
[6] A. Felfernig, G. Friedrich, D. Jannach, and M. Stumptner, C. Bagley, and J. Tiihonen, chapter 26, 377–388, Morgan Kaufmann
‘Consistency-based diagnosis of configuration knowledge bases’, Ar- Publishers, (2013).
tificial Intelligence, 152(2), 213–234, (2004). [27] J. Tiihonen, W. Mayer, M. Stumptner, and M. Heiskala, ‘Configuring
[7] A. Felfernig, L. Hotz, C. Bagley, and J. Tiihonen, Knowledge-based Services and Processes’, in Knowledge-based Configuration – From
Configuration: From Research to Business Cases, Elsevier/Morgan Research to Business Cases, eds., A. Felfernig, L. Hotz, C. Bagley,
Kaufmann Publishers, 1st edn., 2014. and J. Tiihonen, chapter 21, 313–324, Morgan Kaufmann Publishers,
[8] A. Felfernig, M. Schubert, G. Friedrich, M. Mandl, M. Mairitsch, and (2013).
E. Teppan, ‘Plausible repairs for inconsistent requirements’, in 21st In- [28] R. Walter and W. Küchlin, ‘ReMax - A MaxSAT aided Product (Re-)
ternational Joint Conference on Artificial Intelligence (IJCAI’09), pp. Configurator’, in Workshop on Configuration 2014, pp. 55–66, (2014).
791–796, Pasadena, CA, USA, (2009). [29] R. Walter, C. Zengler, and W. Küchlin, ‘Applications of maxsat in auto-
[9] A. Felfernig, M. Schubert, and C. Zehentner, ‘An efficient diagnosis al- motive configuration’, in Workshop on Configuration 2013, pp. 21–28,
gorithm for inconsistent constraint sets’, Artificial Intelligence for En- (2013).
gineering Design, Analysis and Manufacturing (AI EDAM), 26(1), 53– [30] K. Wang, Z. Li, Y. Ai, and Y. Zhang, ‘Computing Minimal Diagnosis
62, (2012). with Binary Decision Diagrams Algorithm’, in 6th International Con-
[10] A. Fijany and F. Vatan, ‘New approaches for efficient solution of hit- ference on Fuzzy Systems and Knowledge Discovery (FSKD’2009), pp.
ting set problem’, in Winter International Symposium on Information 145–149, (2009).
and Communication Technologies, pp. 1–6, Cancun, Mexico, (2004). [31] F. Wotawa, ‘A variant of reiter’s hitting-set algorithm’, Information
Trinity College Dublin. Processing Letters, 79(1), 45–51, (2001).
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 110
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria