Comparing the Performance of Traditional and Novel Heuristics
                               for Sequential Diagnosis

                                       Patrick Rodler∗ and Wolfgang Schmid
                                         Alpen-Adria Universität Klagenfurt
                                          e-mail: firstname.lastname@aau.at


Extended Abstract                                                  is observed for a heuristic choosing the query that maximi-
                                                                   zes the probability of eliminating a maximal number of fault
Given a malfunctioning system, sequential diagnosis aims           candidates. (7) Finally, and interestingly, the very popular
at identifying the root cause of the failure in terms of ab-       entropy measure only manifested good (albeit not best) be-
normally behaving system components. As initial system             havior in a single set of scenarios.
observations usually do not suffice to deterministically pin
down just one explanation of the system’s misbehavior, ad-
ditional system measurements can help to differentiate bet-
ween possible explanations. The goal is to restrict the space
of explanations until there is only one (highly probable) ex-
planation left. To achieve this with a minimal-cost series of
measurements, various heuristics for selecting the best next
measurement have been proposed.
   In this work we focus on one-step lookahead heuristics
that try to optimize measurements formulated as binary true-
false queries. Examples of such queries are tests of systems
such as hardware or software, inspections of system com-
ponents, questions to an expert, or probes. We present the
results of comprehensive experiments on real-world diagno-
sis cases, where we evaluated both well-known and recently
suggested novel heuristics with regard to the required mea-
surement cost until the actual fault was located.
   Our main findings are the following: (1) Using an appro-
priate heuristic for a particular diagnosis scenario is crucial,
as otherwise the user effort to diagnose the system is dou-
bled on average; in some cases, cost overheads through the
use of inadequate heuristics even exceeded 250%. (2) The
main factors influencing sequential diagnosis cost – besides
the obvious factor given by the number of possible fault ex-
planations – are the bias and the quality of the prior fault
probability distribution. The effect of the particular diag-
nosis problem as such or the size of the diagnoses sample
used for measurement selection, by contrast, appeared to be
rather minor in our tests. (3) The one and only (generally)
best heuristic does not exist (or has not yet been found). In
fact, different heuristics prevail in various scenarios, depen-
ding on the type and quality of the given fault information.
(4) If the fault information is plausible, one of the novel me-
asures, which favors queries for which the highest number
of fault candidates is invalidated with a probability larger
than 50%, performs best. (5) When probabilities are mis-
leading, notably, the random selection strategy shows the
best results, which suggests that a built-in random compo-
nent might make heuristics less susceptible to low-quality
meta information. (6) In cases where available probabili-
ties are neither very good nor very bad, the best behavior
   ∗
   This work was supported by the Carinthian Science Fund
(KWF), contract KWF-3520/26767/38701.