Given a malfunctioning system, sequential diagnosis aims at identifying the root cause of the failure in terms of abnormally behaving system components. As initial system observations usually do not suffice to deterministically pin down just one explanation of the system’s misbehavior, additional system measurements can help to differentiate between possible explanations. The goal is to restrict the space of explanations until there is only one (highly probable) explanation 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 truefalse queries. Examples of such queries are tests of systems such as hardware or software, inspections of system components, questions to an expert, or probes. We present the results of comprehensive experiments on real-world diagnosis cases, where we evaluated both well-known and recently suggested novel heuristics with regard to the required measurement cost until the actual fault was located.
Our main findings are the following: (1) Using an appropriate heuristic for a particular diagnosis scenario is crucial, as otherwise the user effort to diagnose the system is doubled 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 explanations – are the bias and the quality of the prior fault probability distribution. The effect of the particular diagnosis 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, depending on the type and quality of the given fault information. (4) If the fault information is plausible, one of the novel measures, 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 misleading, notably, the random selection strategy shows the best results, which suggests that a built-in random component might make heuristics less susceptible to low-quality meta information. (6) In cases where available probabilities are neither very good nor very bad, the best behavior is observed for a heuristic choosing the query that maximizes the probability of eliminating a maximal number of fault candidates. (7) Finally, and interestingly, the very popular entropy measure only manifested good (albeit not best) behavior in a single set of scenarios.