Inexpensive Cost-Optimized Measurement Proposal
for Sequential Model-Based Diagnosis

arXiv:1705.09879v1 [] 28 May 2017

Patrick Rodler1 and Wolfgang Schmid1 and Konstantin Schekotihin1
1
Alpen-Adria Universität, Klagenfurt, Austria
e-mail: firstname.lastname@aau.at

Abstract
In this work we present strategies for (optimal)
measurement selection in model-based sequential
diagnosis. In particular, assuming a set of leading diagnoses being given, we show how queries
(sets of measurements) can be computed and optimized along two dimensions: expected number of
queries and cost per query. By means of a suitable decoupling of two optimizations and a clever
search space reduction the computations are done
without any inference engine calls. For the full
search space, we give a method requiring only a
polynomial number of inferences and guaranteeing
query properties existing methods cannot provide.
Evaluation results using real-world problems indicate that the new method computes (virtually) optimal queries instantly independently of the size and
complexity of the considered diagnosis problems.

1

Introduction

Model-based diagnosis (MBD) is a widely applied approach
to finding explanations, called diagnoses, for unexpected behavior of observed systems including hardware, software,
knowledge bases, discrete event systems, feature models,
user interfaces, etc. [Reiter, 1987; Dressler and Struss, 1996;
Mateis et al., 2000; Pencolé and Cordier, 2005; Kalyanpur
et al., 2007; Felfernig et al., 2009; White et al., 2010]. In
case the provided observations are insufficient for successful fault localization, sequential diagnosis (SQD) methods
collect additional information by generating a sequence of
queries [de Kleer and Williams, 1987; Pietersma et al., 2005;
Feldman et al., 2010; Siddiqi and Huang, 2011; Shchekotykhin et al., 2012].1 As query answering is often costly, the
goal of SQD is to minimize the diagnostic cost, like time or
manpower, required to achieve a diagnostic goal, e.g. a highly
probable diagnosis. To this end, the cited SQD works minimize the number of queries by a one-step lookahead measure
m, e.g. entropy [de Kleer and Williams, 1987], but do not optimize the query cost, such as the time required to perform
measurements [Heckerman et al., 1995].
1

Following the arguments of [Pietersma et al., 2005] we do not
consider non-MBD sequential methods [Pattipati and Alexandridis,
1990; Shakeri et al., 2000; Zuzek et al., 2000; Brodie et al., 2003].

Contributions. We present a novel query optimization
method that is generally applicable to any MBD problem in
the sense of [de Kleer and Williams, 1987; Reiter, 1987] and
(1) defines a query as a set of first-order sentences and
thus generalizes the measurement notion of [de Kleer and
Williams, 1987; Reiter, 1987],
(2) given a set of leading diagnoses [de Kleer and Williams,
1989], allows the two-dimensional optimization of the next
query in terms of the expected number of subsequent queries
(measure m) and query cost (measure c),
(3) for an aptly refined (yet exponential) query search space,
finds – without any reasoner calls – the globally optimal
query wrt. measure c that globally optimizes measure m,
(4) for the full query search space, finds – with a polynomial
number of reasoner calls – the (under reasonable assumptions) globally optimal query wrt. m that includes, if possible,
only “cost-preferred” sentences, such as those answerable automatically using built-in sensors,
(5) guarantees the proposal of queries that discriminate between all leading diagnoses and that unambiguously identify
the actual diagnosis.
The efficiency of our approach is possible by the recognition that the optimizations of m and c can be decoupled
and by using logical monotonicity as well as the inherent (already inferred) information in the (⊆-minimal) leading diagnoses. In particular, the method is inexpensive as it (a) avoids
the generation and examination of unnecessary (non-discriminating) or duplicate query candidates, (b) actually computes
only the single best query by its ability to estimate a query’s
quality without computing it, and (c) guarantees soundness
and completeness wrt. an exponential query search space independently of the properties and output of a reasoner. Modern SQD methods like [de Kleer and Williams, 1987] and its
derivatives [Feldman et al., 2010; Shchekotykhin et al., 2012;
Rodler et al., 2013] do not meet all properties (a) – (c) and extensively call a reasoner for (precomputed) inferences while
computing a query. Moreover, by the generality of our query
notion, our method explores a more complex search space
than [de Kleer and Williams, 1987; de Kleer and Raiman,
1993], thereby guaranteeing property (5) above.

2

Preliminaries

Model-Based Diagnosis (MBD). In this section we recap
on important MBD concepts and draw on definitions of [Re-

SD
COMPS

normal
behavior
beh(ci ) of components ci ∈ COMPS
N

{¬AB(ci ) → beh(ci ) | ci ∈
{c1 , c2 , c3 , c4 , c5 }
beh(c1 ) : A → B ∧ L
beh(c3 ) : B ∨ F → H
beh(c5 ) : ¬H → G ∧ ¬A
n1 : {A → H}

COMPS }

beh(c2 ) : A → F
beh(c4 ) : L → H
OBS, P

=∅

Table 1: Running Example DPI Ex
iter, 1987] to characterize a system and diagnoses.
Notation (*): Let X be a collection of sets, then UX and IX
denote the union and intersection of all elements of X, resp.
K |= S for a set S is a shorthand for K |= s for all s ∈ S.
A system consists of a set of components COMPS and a
system description SD where {¬AB(c) → beh(c) | c ∈
COMPS } ⊆ SD . The first-order sentence beh(c) describes
the normal behavior of c and AB is a distinguished abnormality predicate. Any behavior different from beh(c) implies that component c is at fault, i.e. AB(c) holds.2 Note,
SD ∪ {¬ AB (c) | c ∈ COMPS } is required to be consistent.
From the viewpoint of system diagnosis, evidence about
the system behavior in terms of observations OBS, positive
(P ) and negative (N ) measurements [Reiter, 1987; de Kleer
and Williams, 1987; Felfernig et al., 2004] is of interest.
Definition 1 (DPI). Let COMPS be a finite set of constants
and SD, OBS, all p ∈ P , all n ∈ N be finite sets of consistent first-order sentences. Then (SD, COMPS, OBS, P , N ) is a
diagnosis problem instance (DPI).
Definition 2. Let (SD, COMPS, OBS, P , N ) be a DPI. Then
SD∗ [∆] := SD ∪ OBS ∪ UP ∪ { AB (c) | c ∈ ∆} ∪ {¬ AB (c) |
c ∈ COMPS \∆} denotes the behavior description of a system
(SD, COMPS) given observations OBS, union of positive measurements UP as well as that all components ∆ ⊆ COMPS
are faulty and all components in COMPS \ ∆ are healthy.
The solutions of a DPI, i.e. the hypotheses that explain a
given (faulty) system behavior, are called diagnoses:
Definition 3 (Diagnosis). ∆ ⊆ COMPS is a diagnosis for the
DPI (SD, COMPS, OBS, P , N ) iff ∆ is ⊆-minimal such that
• SD∗ [∆] is consistent (∆ explains OBS and P ), and
• ∀n ∈ N : SD∗ [∆] 6|= n (∆ explains N ).
We denote the set of all diagnoses for a DPI X by DX .
A diagnosis for a DPI exists iff SD∗ [COMPS] 6|= n for all
n ∈ N [Friedrich and Shchekotykhin, 2005, Prop. 1].
Example: Consider DPI Ex (Tab. 1). Using e.g. HS-T REE
[Reiter, 1987] we get (denoting components ci by i) the set
of all diagnoses DEx = {∆1 , ∆2 , ∆3 } = {{1, 2, 5}, {1, 3, 5},
{3, 4, 5}}. E.g. ∆2 ∈ DEx due to Def. 3 and as SD∗ [∆2 ] =
[SD ∪ {AB(c1 ), AB(c3 ), AB(c5 )} ∪ {¬AB(c2 ), ¬AB(c4 )}] ∪
OBS ∪ UP = [{beh(c2 ), beh(c4 )}] ∪ ∅ ∪ ∅ = {A → F, L →
H} 6|= {A → H} = n1 ∈ N and is consistent.
Sequential Diagnosis (SQD). Given multiple diagnoses for
a DPI, SQD techniques extend the sets P and N by asking a user or an oracle (e.g. an automated system) to perform additional measurements in order to rule out irrelevant diagnoses. In line with the works of [Settles, 2012;
2
We make the stationary health assumption [Feldman et al.,
2010]: behavior of each c ∈ COMPS is constant during diagnosis.

Shchekotykhin et al., 2012; Rodler, 2015] we call a proposed
measurement query and define it very generally as a set of
first-order sentences (this subsumes the notion of measurement e.g. in [de Kleer and Williams, 1987; Reiter, 1987]).
The task of the oracle is to assess the correctness of the sentences in the query, thereby providing the required measurements. A query Q is true (t) if all sentences in Q are correct
and false (f ) if at least one sentence in Q is incorrect.
Usually only a small computationally feasible set of leading diagnoses D (e.g. minimum cardinality [Feldman et al.,
2010] or most probable [de Kleer, 1991] ones) are exploited
for measurement selection [de Kleer and Williams, 1989].
Any sets of diagnoses and first-order sentences satisfy:
Property 1. Let X be a set of first-order sentences and
D ⊆ DDPI for DPI = (SD, COMPS, OBS, P, N ). Then X
induces a partition PD (X) := D+ (X), D− (X), D0 (X)
on D where D+ (X) := {∆ ∈ D | SD∗ [∆] |= X},
D− (X) := {∆ ∈ D | ∃s ∈ N ∪ {⊥} : SD∗ [∆] ∪ X |= s}
and D0 (X) = D \ (D+ (X) ∪ D− (X)).
From a query, we postulate two properties, it must for any
outcome (1) invalidate at least one diagnosis (search space
restriction) and (2) preserve the validity of at least one diagnosis (solution preservation). In fact, the sets D+ (X) and
D− (X) are the key in deciding whether a set of sentences X
is a query or not. Based on Property 1, we define:
Definition 4 (Query, q-Partition). Let DPI = (SD, COMPS,
OBS , P, N ), D ⊆ DDPI and Q be a set of first-order sentences with PD (Q) = D+ (Q), D− (Q), D0 (Q) . Then Q
is a query for D iff Q 6= ∅, D+ (Q) 6= ∅ and D− (Q) 6= ∅.
The set of all queries for D is denoted by QD .
PD (Q) is called the q-partition (QP) of Q iff Q is a query.
Inversely, Q is called a query with (or: for) the QP PD (Q).
Given a QP P, we sometimes denote its three entries in
turn D+ (P), D− (P) and D0 (P).
D+ (Q) and D− (Q) denote those diagnoses in D consistent only with Q’s positive and negative outcome, respectively, and D0 (Q) those consistent with both outcomes. Since
Q ∈ QD implies that both D+ (Q) and D− (Q) are nonempty, clearly Q’s outcomes both dismiss and preserve at
least one diagnosis. Note, in many cases a query also invalidates some (unknown) non-leading diagnoses DDPI \ D.
We point out that the size of the set D0 (Q) (the diagnoses
that cannot be eliminated given any outcome) should be minimal, i.e. zero at best, for optimal diagnoses discrimination.
The algorithm presented hereafter guarantees the computation of only Q’s with D0 (Q) = ∅. For example, the methods
of [de Kleer and Williams, 1987; Shchekotykhin et al., 2012;
Rodler et al., 2013] cannot ensure this important property.
Example (cont’d): Let D = DEx = {∆1 , ∆2 , ∆3 }.
Then, Q = {F → H} is a query in QD . To verify this,
let us consider its QP PD (Q) = h{∆1 } , {∆2 , ∆3 } , ∅i.
Since both D+ (Q) and D− (Q) are non-empty, Q is in
QD . ∆1 = {1, 2, 5} ∈ D+ (Q) holds as SD∗ [∆1 ] |=
{beh(c3 ), beh(c4 )} = {B ∨ F → H, L → H} which in turn
entails Q. On the other hand, e.g. ∆2 = {1, 3, 5} ∈
D− (Q) since SD∗ [∆2 ]∪Q |= {A → F, L → H, F → H} |=
{A → H} = n1 ∈ N . Hence, the outcome Q = t im-

plies that diagnoses in D− (Q) = {∆2 , ∆3 } are invalidated,
whereas Q = f causes the dismissal of D+ (Q) = {∆1 }.
Applicability and Diagnostic Accuracy. For any nonsingleton set of leading diagnoses, a discriminating query exists [Rodler, 2015, Sec. 7.6]:
Property 2. ∀DPI : D ⊆ DDPI , |D| ≥ 2 =⇒ QD 6= ∅.
This has two implications: First, we need only precompute
two diagnoses to generate a query and proceed with SQD.
Despite its NP-completeness [Bylander et al., 1991], the generation of two (or more) diagnoses is practical in many realworld settings [de Kleer, 1991; Shchekotykhin et al., 2014],
making query-based SQD commonly applicable. Second, the
query-based approach guarantees perfect diagnostic accuracy,
i.e. the unambiguous identification of the actual diagnosis.

3

Query Optimization for Sequential MBD

Measurement Selection.
As argued, the (q-)partition
PD (Q) enables both the verification whether a candidate
Q is indeed a query and an estimation of the impact Q’s
outcomes have in terms of diagnoses invalidation. And,
given (component) fault probabilities, it enables to gauge
the probability of observing a positive or negative query
outcome [de Kleer and Williams, 1987]. Active learning
query selection measures (QSMs) m : Q 7→ m(Q) ∈
R [Settles, 2012] use exactly these query properties characterized by the QP to assess how favorable a query is.
They aim at selecting queries such that the expected number of queries until obtaining
a deterministic diagnostic reP
sult is minimized, i.e. ∆⊆COMPS p(∆)q# (∆) → min where
p(∆) is the (a-priori) probability that {AB(c) | c ∈ ∆} ∪
{¬AB(c) | c ∈ COMPS \ ∆} is the actual system state wrt.
component functionality and q# (∆) is the number of queries
required, given the initial DPI, to derive that ∆ must be the
actual diagnosis. Solving this problem is known to be NPcomplete as it amounts to optimal binary decision tree construction [Hyafil and Rivest, 1976]. Hence we restrict our
algorithm to the usage of QSMs that make a locally optimal query selection through a one-step lookahead. This has
been shown to be optimal in many cases and nearly optimal in
most cases [de Kleer et al., 1992]. Several different QSMs m
such as split-in-half, entropy, or risk-optimization have been
proposed, well studied and compared against each other [de
Kleer and Williams, 1987; Shchekotykhin et al., 2012; Rodler
et al., 2013]. E.g. using entropy as QSM, m would be exactly
the scoring function $() derived in [de Kleer and Williams,
1987]. Note, we assume w.l.o.g. that the optimal query wrt.
any m is the one with minimal m(Q).
Besides minimizing the number of queries in a diagnostic session, a further goal can be the minimization of the
query cost (e.g. time, manpower). To this end, one can specify a query cost measure (QCM) c : Q 7→ c(Q) ∈ R+ .
Pk
Examples of QCMs are cΣ (Q) :=
i=1 ci (prefer query
with minimal overall cost, e.g. when ci represents time) or
cmax (Q) := maxi∈{1,...,k} ci (prefer query with minimal
maximal cost of a single measurement, e.g. when ci represents human cognitive load) where Q = {q1 , . . . , qk } and ci
is the cost of evaluating the truth of the first-order sentence

Algorithm 1 Optimized Query Computation
Input: DPI := (SD, COMPS, OBS, P, N ), D ⊆ DDPI , |D| ≥ 2, QSM m, QCM c,
component fault probabilities FP = {pi | pi = p(ci ), ci ∈ COMPS}, threshold tm (i.e. |m(Q) − mopt | ≤ tm ⇒ Q regarded optimal; mopt := optimal
value of m), sound and complete inference engine Inf , set ET of entailment types
Output: an optimized query Q∗ ∈ QD wrt. m, tm and c (cf. Theorems 2 and 3)
1: P ← OPTIMIZE QPARTITION(D, FP, m, tm )
. P1
2: Q∗ ← OPTIMIZE Q UERY F OR QPARTITION(P, FP, c)
. P2
3: if enhance = true then
4:
Q0 ← EXPAND Q UERY(DPI, P, Inf , ET )
. (optional) P3
5:
Q∗ ← OPTI M INIMIZE Q UERY(Q0 , P, DPI, FP, Inf )
. (optional) P3
6: return Q∗

qi . The QCM c|·| (Q) = |Q| is a special case of cΣ (Q) where
ci = cj for all i, j is assumed. Now, the problem addressed
in this work is:
Problem 1. Given: DPI := (SD, COMPS, OBS, P, N ),
D ⊆ DDPI with |D| ≥ 2, QSM m, QCM c, query
search space S ⊆ QD . Find: A query Q∗ satisfying
Q∗ = arg minQ∈OptQ(m,S) c(Q) where OptQ(m, S) :=
{Q0 | Q0 = arg minQ∈S m(Q)}, i.e. Q∗ has minimal cost
wrt. c among all queries in S that are optimal wrt. m.
Note there can be multiple equally good queries Q∗ ∈ QD .
The Algorithm we propose to solve Problem 1 is given by
Alg. 1. The described query computation procedure can be
divided into three phases: P1 (line 1), P2 (line 2) and (optionally) P3 (lines 4-5). We next give the intuition and explanation of these phases.
Phase P1. At this stage, we optimize the given QSM m – for
now without regard to the QCM c, which is optimized later
in P2. This decoupling of optimization steps is possible since
the QSM value m(Q) of a query Q is only affected by the
(unique) QP of Q and not by Q itself. On the contrary, the
QCM value c(Q) is a function of Q only and not of Q’s QP.
Therefore, the search performed in P1 will consider only QPs.
To verify whether a given 3-partition of D is a QP, however, we need a query Q for this QP which lets us determine
whether D+ (Q) 6= ∅ and D− (Q) 6= ∅ (cf. Def. 4). But:
Property 3. For one query there is exactly one QP (immediate from Property 1). For one QP there might be an exponential number of queries (cf. Propos. 6 later).
Therefore, we use the notion of a canonical query (CQ),
which is one well-defined query representative for a QP. From
a CQ, we postulate easiness of computation and exclusion of
suboptimal QPs with D0 6= ∅ (cf. Sec. 2). The key to realizing these postulations is:
Definition 5. X ⊆ COMPS, BEH[X] := {beh(ci ) | ci ∈ X}.
The following property is immediate from Def. 2:
Property 4. X ⊆ COMPS =⇒ SD∗ [X] |= BEH[COMPS \X]
From Property 1 and Def. 4 we can directly conclude:
Property 5. A query Q ∈ QD is a subset of the common
entailments of all KBs in the set {SD∗ [∆] | ∆ ∈ D+ (Q)}.
Using Properties 4 and 5, the idea is now to restrict the
space of entailments of the SD∗ [·] KBs to the behavioral descriptions beh(·) of the system components. That is, each CQ
should be some query Q ⊆ BEH[COMPS]. This assumption
along with Def. 4 and the ⊆-minimality of diagnoses yields:

Proposition 1. Any query Q ⊆ BEH[COMPS] in QD must
include some formulas in BEH[UD ], need not include any formulas in BEH[COMPS \ UD ], and must not include any formulas in BEH[ID ]. (Please refer to (*) in Sec. 2 for notation.)
Moreover, the deletion of any sentences in BEH[COMPS \
UD ] from Q does not alter the QP PD (Q).
Hence, we define:
Definition 6. DiscD := BEH[UD ]\ BEH[ID ] = BEH[UD \ID ]
the discrimination sentences wrt. D (i.e. those essential for
discrimination between diagnoses in D).
CQs can now be characterized as follows:
Definition 7 (CQ). Let ∅ ⊂ D+ ⊂ D. Then Qcan (D+ ) :=
BEH [ COMPS \ UD+ ] ∩DiscD is the canonical query (CQ) wrt.
seed D+ if Qcan (D+ ) 6= ∅. Else, Qcan (D+ ) is undefined.
Note, BEH[COMPS \ UD+ ] are exactly the common beh(·)
entailments of {SD∗ [∆] | ∆ ∈ D+ } (cf. Property 5). The CQ
extracts DiscD from these entailments, thereby removing all
elements that do not affect the QP (cf. Propos. 1). By Defs. 4
and 7 and the ⊆-minimality of diagnoses, we get:
Proposition 2. If Q is a CQ, then Q is a query.
The QP for a CQ is called canonical q-partition:
Definition 8 (CQP). A QP P0 for which a CQ Q exists with
QP P0 , i.e. P(Q) = P0 , is called a canonical QP (CQP).
Since a CQ is a subset of BEH[COMPS] and diagnoses are
⊆-minimal, we can derive:
Proposition 3. Let P be a CQP. Then D0 (P) = ∅.
Discussion: The restriction to CQs during P1 has some nice
implications: (1) CQs can be generated by cheap set operations (no inference engine calls), (2) each CQ is a query in
QD for sure (Propos. 2), no verification of its QP (as per
Def. 4) required, thence no unnecessary (non-query) candidates generated, (3) automatic focus on favorable queries
wrt. the QSM m (those with empty D0 , Propos. 3), (4) no
duplicate QPs generated as there is a one-to-one relationship
between CQs and CQPs (Property 3, Def. 7), (5) the explored
search space for QPs is not dependent on the particular (entailments) output by an inference engine.
We emphasize that all these properties do not hold for normal (i.e. non-canonical) queries and QPs. The overwhelming
impact of this will be demonstrated in Sec. 4.
Example (cont’d): Given D as before, DiscD = BEH[UD \
ID ] = BEH[{1, 2, 3, 4, 5} \ {5}] = BEH[{1, 2, 3, 4}]. Let
us consider the seed D+ = {∆1 } = {{1, 2, 5}}. Then the
CQ Q1 := Qcan (D+ ) = (BEH[{1, 2, 3, 4, 5} \ {1, 2, 5}]) ∩
BEH [{1, 2, 3, 4}] = BEH [{3, 4}]. The associated CQP is
P1 = h{∆1 } , {∆2 , ∆3 } , ∅i. Note, ∆ ∈ D+ (P1 ) (∆ ∈
D− (P1 )) for a ∆ ∈ D iff BEH[COMPS \ ∆] ⊇ (6⊇)Q1 . E.g.
∆3 ∈ D− (P1 ) since BEH[COMPS \ ∆3 ] = BEH[{1, 2}] 6⊇
BEH [{3, 4}] = Q1 . That is, using CQs and CQPs, reasoning
is traded for set operations and comparisons.
The seed D+ = {∆1 , ∆3 } yields Q2 := Qcan (D+ ) =
(BEH[{1, . . . , 5} \ {1, . . . , 5}]) ∩ BEH[{1, . . . , 4}] = ∅,
i.e. there is no CQ wrt. seed D+ and the partition
h{∆1 , ∆3 } , {∆2 } , ∅i with the seed D+ as first entry is no
CQP (and also no QP).

Now, having at hand the notion of a CQP, we describe
the (heuristic) depth-first, local best-first (i.e. chooses only
among best direct successors at each step) backtracking CQP
search procedure performed in P1.
A (heuristic) search problem [Russell and Norvig, 2010] is
defined by the initial state, a successor function enumerating
all direct neighbor states of a state, the step costs from a state
to a successor state, the goal test to determine if a given state
is a goal state or not, (and some heuristics to estimate the
remaining effort towards a goal state).
We define the initial state hD+ , D− , D0 i as h∅, D, ∅i. The
idea is to transfer diagnoses step-by-step from D− to D+ to
construct all CQPs systematically. The step costs are irrelevant, only the found QP as such counts. Heuristics derived
from the QSM m (cf. e.g. [Shchekotykhin et al., 2012]) can
be (optionally) integrated into the search to enable faster convergence to the optimum. A QP is a goal if it optimizes m up
to the given threshold tm (cf. [de Kleer and Williams, 1987],
see Alg. 1). In order to characterize a suitable successor function, we define a direct neighbor of a QP as follows:
−
+
−
Definition 9. Let Pi := hD+
i , Di , ∅i, Pj := hDj , Dj , ∅i
be partitions of D. Then, Pi 7→ Pj is a minimal D+ +
transformation from Pi to Pj iff Pj is a CQP, D+
i ⊂ Dj
−
+
+
+
and there is no CQP hD+
k , Dk , ∅i with Di ⊂ Dk ⊂ Dj .
0
A CQP P is called a successor of a partition P iff P0 results from P by a minimal D+ -transformation.
For the initial state successors we get [Rodler, 2015, p. 98]:
Proposition 4. The CQPs h{∆} , D \ {∆} , ∅i for ∆ ∈ D
are exactly all successors of h∅, D, ∅i.
To specify the successors of an intermediate CQP Pk in
the search, we draw on diagnoses’ traits:
−
Definition 10. Let Pk = hD+
k , Dk , ∅i be a CQP and ∆i ∈
(k)
D−
of ∆i is defined as BEH[∆i \ UD+ ].
k . Then the trait ∆i
k

D−
k

The relation ∼k associating two diagnoses in
iff their
trait is equal is obviously an equivalence relation. Now,
Defs. 7, 8 and 9 let us derive:
Proposition 5. Let EC := {E1 , . . . , Es } be the set of all
equivalence classes wrt. ∼k . Pk has successors iff s ≥ 2. In
−
this case, all successors are given by D+
k ∪ E, Dk \ E, ∅
where E ∈ EC and E has a ⊆-minimal trait among all
classes E 0 ∈ EC .
By Def. 9 which demands both minimal changes between
state and successor state and the latter to be a CQP, we have:
Theorem 1. Usage of the successor function as given in
Propos. 4 (for initial state) and Propos. 5 (for intermediate
states) makes the search for CQPs sound and complete.
Since it can be proven that P = hD+ , D− , ∅i is a CQP iff
UD+ ⊂ UD and as there are at least |D| CQPs (Propos. 4):
Proposition 6. Let CQPD denote the set of CQPs for diagnoses D with |D| ≥ 2. Then |CQPD | = |{UD+ | ∅ ⊂ D+ ⊂
D, UD+ 6= UD }| ≥ |D|.
Whether QPs hD+ , D− , ∅i exist which are no CQPs is not
yet clarified, but both theoretical and empirical evidence indicate the negative. E.g., an analysis of ≈ 900 000 QPs we

ran for different diagnoses D and DPIs showed that all QPs
were indeed CQPs. And, in all evaluated cases (see Sec. 4)
optimal CQPs wrt. all QSMs m given in diagnosis literature
[de Kleer and Williams, 1987; Shchekotykhin et al., 2012;
Rodler et al., 2013] were found. Hence:
Conjecture 1. Let (C)QPD denote the sets of (C)QPs (all
with D0 = ∅) for diagnoses D. Then CQPD = QPD .
Example (cont’d): Reconsider the CQP P1 = h{∆1 } , {∆2 ,
(1)
∆3 }, ∅i. The traits are ∆2 = BEH[{1, 3, 5} \ {1, 2, 5}] =
(1)
BEH [{3}] and ∆3 = BEH [{3, 4}], representing two equivalence classes wrt. ∼1 . There is only one class with ⊆minimal trait, i.e. {∆2 }. Hence, there is just a single successor CQP P2 = h{∆1 , ∆2 }, {∆3 }, ∅i of P1 . Recall, we
argued that h{∆1 , ∆3 }, {∆2 }, ∅i is indeed no CQP. By Propos. 6, there are |{{1, 2, 5} , {1, 3, 5} , {3, 4, 5} , {1, 2, 3, 5},
{1, 3, 4, 5}}| = 5 different CQPs wrt. D. Note, Conject. 1 is
true here, i.e. the CQPD search is complete wrt. QPD .
Phase P2. Phase P1 returns an optimal (C)QP Pk wrt. the
QSM m. Property 3 indicates that there might be still a large
search space for an optimal query wrt. the QCM c for this QP.
The task in P2 is to find such query efficiently.
From Pk , we can obtain the associated CQ Qk (as per
Def. 7). However, usually a least requirement of any QCM
c is i.a. the ⊆-minimality of a query to avoid unnecessary
measurements. To this end, let Tr(Pk ) denote the set of
all ⊆-minimal traits wrt. ∼k . Given a collection of sets
X = {x1 , . . . , xn }, a set H ⊆ UX is a hitting set (HS) of
X iff H ∩ xi 6= ∅ for all xi ∈ X. Then:
Proposition 7. Q ⊆ DiscD is a ⊆-minimal query with QP
Pk iff Q = H for some ⊆-minimal HS H of Tr(Pk ).
Hence, all ⊆-minimal reductions of CQ Qk under preservation of the (already fixed and optimal) QP Pk can be computed e.g. using the classical HS-T REE [Reiter, 1987]. However, there is a crucial difference to standard application scenarios of HS-T REE, namely the fact that all sets to label
the tree nodes (i.e. the ⊆-minimal traits) are readily available (without further computations). Consequently, the construction of the tree runs swiftly, as our evaluation will confirm. Note also, in principle we only require a single minimal
hitting set, i.e. query. Moreover, HS-T REE can be used as
uniform-cost (UC) search (cf. e.g. [Rodler, 2015, Chap. 4]),
incorporating the QCM c to find queries in best-first order
wrt. c. In fact, all QCMs (i.e. cΣ , cmax , c|·| ) discussed above
can be optimized using UC HS-T REE. In case some QCM c
is not suitable for UC search, a brute force HS-T REE search
over all ⊆-minimal queries will be practical as well (no expensive operations involved). Hence, P1 and P2 provide a
solution to Problem 1 without a single inference engine call.
Theorem 2. P1 and P2 compute a solution Q∗ to Problem 1
where S := {BEH[X] | X ⊆ COMPS}.
Example (cont’d): Recall the CQP P1 and let the QCM be
c := c|·| . Then Tr(P1 ) = {BEH[{3}]}, i.e. by Propos. 7 there
is a single c-optimal query BEH[{3}] for P1 , a proper subset
of the CQ BEH[{3, 4}] for P1 . Considering the CQP P3 :=
h{∆2 } , {∆1 , ∆3 } , ∅i, Tr(P3 ) = {BEH[{2}], BEH[{4}]} and

thus we have (Propos. 7) a single c-optimal query BEH[{2, 4}]
which happens to be equal to the CQ for P3 .
Phase P3. The query Q∗ optimized along two dimensions
(# of queries and cost per query) output by P2 can be directly proposed as next measurement. A BEH[·] query like
Q∗ would correspond to a direct examination of one or more
system components, e.g. to ping servers in a distributed system [Brodie et al., 2003], to test gates using a voltmeter in circuits [de Kleer and Williams, 1987] or to ask the stakeholders
of a (software/configuration/KB) system whether specified
code lines/constraints/sentences are correct [Wotawa, 2002;
Felfernig et al., 2004; Friedrich and Shchekotykhin, 2005].
Alternatively, the already optimal CQP Pk returned by P1
can be regarded as intermediate solution to building a solution
query to Problem 1 with full search space S = QD . To this
end, first, using the CQ Qk of Pk , a (finite) set Qexp of firstorder sentences of types ET (e.g. atoms or sentences of type
A → B) are computed. Qexp must meet: (1) SD∗ [X] |= Qexp
where X is some (superset of a) diagnosis such that Qk ⊆
SD ∗ [X] (entailed by a consistent system behavior KB), (2) no
qi ∈ Qexp is an entailment of SD∗ [X] \ Qk (logical dependence on Qk , no irrelevant sentences) and (3) the expansion
of Qk by Qexp does not alter the (already fixed and optimal)
q-partition Pk , i.e. Pk = P(Qk ∪ Qexp ).
Proposition 8. Let EntET (X) be a monotonic consequence
operator realized by some inference engine that computes a
finite set of entailments of types ET of a KB X. Postulations
(1) – (3) are satisfied if Qexp := EntET (SD∗ [UD ] ∪ Qk ) \
EntET (SD∗ [UD ]).
Finally, the expanded query Q0 := Qk ∪ Qexp can be minimized to get a ⊆-minimal subset of it under preservation of
the associated QP Pk . For this purpose, one can use a variant of the polynomial divide-and-conquer method Q UICK XP LAIN [Junker, 2004], e.g. the MIN Q procedure given in
[Rodler, 2015, p.111 ff.]. However, we propose to alter the
input to MIN Q as follows: Assume that Q0 can be partitioned
into a subset of cost-preferred sentences Q0C+ (e.g. those measurements executable automatically by available built-in sensors) and cost-dispreferred ones Q0C− = Q0 \ Q0C+ (e.g.
manual measurements). Let the input to MIN Q be the list
[Q0C+ , asc(Q0C− )] (reordering of Q0 ) where asc(Q0C− ) means
that Q0C− is sorted in ascending order by sentence cost. Then:
Proposition 9. MIN Q with input [Q0C+ , asc(Q0C− )] returns a
⊆-minimal query Q∗ ⊆ Q0 such that P(Q∗ ) = Pk . Further,
if such a query comprising only Q0C+ (and no Q0C− ) sentences
exists, then Q∗ ⊆ Q0C+ . Else, Q∗ optimizes the QCM cmax
(cf. page 3) among all ⊆-minimal subsets of Q0 with QP Pk .
Note, phase P3, i.e. query expansion (Propos. 8) together
with optimized minimization (Propos. 9), requires only a
polynomial number of inference engine calls [Junker, 2004].
Theorem 3. Let Conject. 1 hold and the QCM be cmax (cf.
page 3). Then P3, using the QP output by P1 and Propos. 8
and 9, solves Problem 1 with full search space S = QD .
Example (cont’d): Assume the QP P1 is returned by P1.
Let the cost ci of a sentence qi be the number of literals in
its clausal form. As shown before, the CQ of P1 is Q1 :=
BEH [{3, 4}] = {B ∨ F → H, L → H}. Using Propos. 8

with ET set to “definite clauses with singleton body”, we get
Qexp = EntET (Q1 )\EntET (∅) = {B → H, F → H, L →
H}. So, Q0 = {B → H, F → H, L → H, B ∨ F → H}.
Suppose ET defines exactly the cost-preferred sentences, i.e.
Q0c+ = Qexp . Running MIN Q with input [Qexp , {B ∨ F →
H}] yields Q∗ = {F → H}, a query that includes only
cost-preferred elements (cf. Propos. 9). It is easily verified by
means of Property 1 that Q∗ has still the QP P1 .

a
b
c

4

Evaluation

To evaluate our method, we used real-world inconsistent
knowledge-based (KB) systems as (1) they pose a hard challenge for query selection methods due to the implicit nature
of the possible queries (must be derived by inference; not directly given such as wires in a circuit), (2) any MBD system in
the sense of [Reiter, 1987] is described by a KB, (3) the type
of the underlying system is irrelevant to our method, only its
size and (reasoning) complexity – for the optional phase P3 –
and the DPI structure, e.g. size, # or probability of diagnoses
– for phases P1, P2 – are critical. To account for this, we used
systems (see Tab. 2, col. 1) of different size (# of components,
i.e. logical axioms in the KB, see Tab. 2, col. 2), complexity
(see Tab. 2, col. 3) and DPI structure (see Tab. 2, col. 4).
In our experiments, for each faulty system’s DPI Sys in
Tab. 2 and each n ∈ {10, 20, . . . , 80}, we randomly generated 5 different D ∈ DSys with |D| = n using I NV-HS-T REE
[Shchekotykhin et al., 2014] with randomly shuffled input.
Each D ∈ D was assigned a uniformly random probability.
For each of these 5 D-sets, we used (a) entropy (ENT)
[de Kleer and Williams, 1987] and (b) split-in-half (SPL)
[Shchekotykhin et al., 2012] as QSM m and c|·| (cf. page 3) as
QCM c, and then ran phases (i) P1+P2 and (ii) P3 to compute
an optimized query as per Theorems 2 and 3, respectively.
We specified the optimality threshold tm as 0.01 in (a) and 0
in (b), cf. Alg. 1. The search in P1 (cf. Sec. 3) used the greedy
heuristic discussed in [Shchekotykhin et al., 2012, p. 11]. In
P3 simple definite clauses of the form ∀x(A(x) → B(x))
were considered cost-preferred (cf. last Example above).
Experimental Results are shown in Fig. 1. Times for SPL
are omitted for clarity as they were quasi the same as for
ENT. The dark gray area shows the # of CQPs addressed by
P1, and the light gray line the time for P1+P2 using ENT. It is
evident that P1+P2 always finished in less than 0.03 sec outputting an optimized query wrt. m and c. Note, albeit P1+P2
solve Prob. 1 for a restricted search space S (cf. Theor. 2),
|CQPD |, a fraction of |S|, already averaged to e.g. 300 (over
|D| = 10 cases) and > 530 000 (|D| = 80). That |S| is sufficiently large for all sizes |D| is also substantiated by the fact
that in each single run an optimal query wrt. the very small tm
1
( 10
of tm used in [Shchekotykhin et al., 2012]) was found in
S. Also, a brute force (BF) search (dashed line) iterating over
all possible CQPs is feasible in most cases – finishing within
1 min for all runs (up to search space sizes > 120 000) except the |D| ≥ 30 cases for system CE (where up to 3 million
CQPs were computed). This extreme speed is possible due to
the complete avoidance of costly reasoner calls. The optional
further query enhancement in P3 using a reasoner [Sirin et al.,
2007] always finished within 4 sec and returned the globally

|COMPS|
Complexity a
#D/min/max b
49
SOIN (D)
90/3/4
173
ALCN
48/3/3
458
SIN (D)
934/2/16
491
SHIN (D)
953/3/10
1300
ALCH(D)
1782/6/9
1781
ALCH(D)
864/4/8
9664
ALEHIF (D)
110/2/6
33203
SHF
15/1/5
Description Logic expressivity, cf. [Baader et al., 2003, p. 525 ff.].
#D, min, max denote #, min. and max. size of all diagnoses (computable in ≤ 8 h).
Sufficiently complex systems (#D ≥ 40) used in [Shchekotykhin et al., 2012].
Hardest diagnosis problems mentioned in [Stuckenschmidt, 2008].
Hardest diagnosis problems tested in [Shchekotykhin et al., 2012].

System
University (U) c
MiniTambis (M) c
CMT-Conftool (CC) d
Conftool-EKAW (CE) d
Transportation (T) c
Economy (E) c
Opengalen-no-propchains (O) e
Cton (C) e

d
e

Table 2: Systems used in Experiments
10000000

M

U

T

E

C

O

CE

CC

1000000
100000

10000
1000
100
10
1
0.1
0.01
0.001

0.0001
ȁ۲ȁ
|D|
ENT: time P3

ȁ۱‫۾ۿ‬۲ ȁ
|CQP_D|
BF: time P1+P2

ENT: time P1+P2

Figure 1: Results for systems in Tab. 2 (x-axis): # of leading diagnoses |D|, associated size |CQPD | of CQP search space, and
computation time (sec) required by phases P1+P2 and P3 for QSM
ENT with threshold tm = 0.01 and brute force (BF) search (y-axis).

optimal query wrt. QCM cmax (Theor. 3). The median output
query size after P1+P2+P3 was 3.4. In additional scalability
tests using |D| = 500 for the large enough DPIs (CC, CE, T,
E) P1+P2 always ended in < 0.6 sec, P3 in < 40 sec.
We also simulated P1 by a method using non-canonical
QPs, thus relying on a reasoner. For no DPI in Tab. 2 a result
for |D| > 15 could be found in ≤ 1 h. And, the quality of the
returned QP (if any) wrt. m was never better than for P1.

5

Conclusion

We present a search that addresses the optimal measurement
(query) selection problem for sequential diagnosis and is applicable to any model-based diagnosis problem conforming
to [de Kleer and Williams, 1987; Reiter, 1987]. In particular,
we allow a query to be optimized along two dimensions, i.e.
number of queries and cost per query. We show that the optimizations of these properties can be decoupled and considered in sequence. For a suitably restricted (still exponential)
query search space (very close approximations of) global optima wrt. given query quality measures are found without any
calls to an inference engine in negligible time for diagnosis
problems of any size and complexity (given the precomputation of ≥ 2 diagnoses is feasible). E.g. query search spaces
of size up to 3 million can be handled instantaneously (< 0.1
sec). For the full search space, under reasonable assumptions,
the globally optimal query wrt. a cost-preference measure can
be found within 4 sec for up to 80 leading diagnoses.

References
[Baader et al., 2003] F Baader, D Calvanese, D McGuinness, D Nardi, and P Patel-Schneider, (eds.). The Description Logic Handbook. Cambridge University Press, 2003.
[Brodie et al., 2003] M Brodie, I Rish, S Ma, and N
Odintsova. Active probing strategies for problem diagnosis in distributed systems. In IJCAI, pp. 1337–1338, 2003.
[Bylander et al., 1991] T Bylander, D Allemang, M Tanner,
and J Josephson. The computational complexity of abduction. Artif. Intell., 49:25–60, 1991.
[de Kleer and Raiman, 1993] J de Kleer and O Raiman. How
to diagnose well with very little information. In Working
Notes of the 4th DX Workshop, pp. 160–165, 1993.
[de Kleer and Williams, 1987] J de Kleer and B C Williams.
Diagnosing multiple faults. Artif. Intell., 32:97–130, 1987.
[de Kleer and Williams, 1989] J de Kleer and B C Williams.
Diagnosis with behavioral modes. In IJCAI, pp. 1324–
1330, 1989.
[de Kleer et al., 1992] J de Kleer, O Raiman, and M Shirley.
One step lookahead is pretty good. In Readings in modelbased diagnosis, pp. 138–142. Morgan Kaufmann, 1992.
[de Kleer, 1991] J de Kleer. Focusing on probable diagnoses.
In AAAI, pp. 842–848, 1991.
[Dressler and Struss, 1996] O Dressler and P Struss. The
consistency-based approach to automated diagnosis of devices. Principles of Knowl. Repr., pp. 269–314, 1996.
[Feldman et al., 2010] A Feldman, G M Provan, and A J C
van Gemund. A model-based active testing approach to
sequential diagnosis. JAIR, 39:301–334, 2010.
[Felfernig et al., 2004] A Felfernig, G Friedrich, D Jannach,
and M Stumptner. Consistency-based diagnosis of configuration KBs. Artif. Intell., 152(2):213–234, 2004.
[Felfernig et al., 2009] A Felfernig, G Friedrich, K Isak, K
Shchekotykhin, E Teppan, and D Jannach. Automated debugging of recommender user interface descriptions. Applied Intell., 31(1):1–14, 2009.
[Friedrich and Shchekotykhin, 2005] G Friedrich and K
Shchekotykhin. A General Diagnosis Method for Ontologies. In ISWC, pp. 232–246, 2005.
[Heckerman et al., 1995] D Heckerman, J S Breese, and K
Rommelse. Decision-theoretic troubleshooting. Communications of the ACM, 38(3):49–57, 1995.
[Hyafil and Rivest, 1976] L Hyafil and R L Rivest. Constructing optimal binary decision trees is NP-complete. Information processing letters, 5(1):15–17, 1976.
[Junker, 2004] U Junker. QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems.
In AAAI, pp. 167–172, 2004.
[Kalyanpur et al., 2007] A Kalyanpur, B Parsia, M Horridge,
and E Sirin. Finding all Justifications of OWL DL Entailments. In ISWC, pp. 267–280, 2007.
[Mateis et al., 2000] C Mateis, M Stumptner, D Wieland,
and F Wotawa. Model-Based Debugging of Java Programs. In AADEBUG’00, 2000.

[Pattipati and Alexandridis, 1990] K R Pattipati and M G
Alexandridis. Application of heuristic search and information theory to sequential fault diagnosis. IEEE Trans.
on Systems, Man, and Cybernetics, 20(4):872–887, 1990.
[Pencolé and Cordier, 2005] Y Pencolé and M-O Cordier. A
formal framework for the decentralised diagnosis of large
scale discrete event systems and its application to telecommunication networks. Artif. Intell., 164(1):121–170, 2005.
[Pietersma et al., 2005] J Pietersma, A J C van Gemund, and
A Bos. A model-based approach to sequential fault diagnosis. In IEEE Autotestcon, pp. 621–627. IEEE, 2005.
[Reiter, 1987] R Reiter. A Theory of Diagnosis from First
Principles. Artif. Intell., 32(1):57–95, 1987.
[Rodler et al., 2013] P Rodler, K Shchekotykhin, P Fleiss,
and G Friedrich. RIO: Minimizing User Interaction in Ontology Debugging. In RR, pp. 153–167, 2013.
[Rodler, 2015] Patrick Rodler. Interactive Debugging of
Knowledge Bases. PhD thesis, Alpen-Adria Universität
Klagenfurt, 2015. http://arxiv.org/pdf/1605.05950v1.pdf.
[Russell and Norvig, 2010] S J Russell and P Norvig. Artif.
Intell.: A Modern Approach. Pearson Education, 2010.
[Settles, 2012] B Settles. Active Learning. Morgan and Claypool Publishers, 2012.
[Shakeri et al., 2000] M Shakeri, V Raghavan, K R Pattipati,
and A Patterson-Hine. Sequential testing algorithms for
multiple fault diagnosis. IEEE Trans. on Systems, Man,
and Cybernetics, Part A, 30(1):1–14, 2000.
[Shchekotykhin et al., 2012] K Shchekotykhin, G Friedrich,
P Fleiss, and P Rodler. Interactive Ontology Debugging:
Two Query Strategies for Efficient Fault Localization. J.
of Web Semantics, 12-13:88–103, 2012.
[Shchekotykhin et al., 2014] K Shchekotykhin, G Friedrich,
P Rodler, and P Fleiss. Sequential diagnosis of high cardinality faults in knowledge-bases by direct diagnosis generation. In ECAI, pp. 813–818, 2014.
[Siddiqi and Huang, 2011] S Siddiqi and J Huang. Sequential diagnosis by abstraction. JAIR, 41:329–365, 2011.
[Sirin et al., 2007] E Sirin, B Parsia, B Cuenca Grau, A
Kalyanpur, and Y Katz. Pellet: A practical OWL-DL reasoner. J. of Web Semantics, 5(2):51–53, 2007.
[Stuckenschmidt, 2008] H Stuckenschmidt.
Debugging
OWL Ontologies: Reality Check. In EON, pp. 1–12, 2008.
[Stumptner and Wotawa, 1999] M Stumptner and F Wotawa.
Debugging functional programs. In IJCAI, pp. 1074–1079,
1999.
[White et al., 2010] J White, D Benavides, D C Schmidt, P
Trinidad, B Dougherty, and A R Cortés. Automated diagnosis of feature model configurations. J. Syst. Software,
83(7):1094–1107, 2010.
[Wotawa, 2002] F Wotawa. On the relationship between
model-based debugging and program slicing. Artif. Intell.,
135(1-2):125–143, 2002.
[Zuzek et al., 2000] A Zuzek, A Biasizzo, and F Novak. Sequential diagnosis tool. MICPRO, 24(4):191–197, 2000.

