StaticHS: A Variant of Reiter’s Hitting Set Tree for Efficient Sequential Diagnosis

Proceedings of the International Symposium on Combinatorial Search, 11

Volume

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search

Full Papers

Sequential Diagnosis methods aim at suggesting a minimal-cost sequence of measurements to identify the root cause of a system failure among the possible fault explanations, called diagnoses. Hitting set algorithms are often used by such methods to precompute a set of diagnoses serving as a decision basis for iterative measurement selection.We show that there are two natural interpretations of the sequential diagnosis problem and argue that (1) existing methods consider only the more general definition of the problem and that (2) tackling the more specific problem might suffice under assumptions commonly met in practice. Thus, we present StaticHS, a novel variant of Reiter’s hitting set tree usable for solving both formulations of the sequential diagnosis problem. Like Reiter’s algorithm, StaticHS is logics- and reasoner-independent and thus generally applicable to various (diagnosis) domains. Theoretical and empirical analyses show the significant superiority of StaticHS to an application of Reiter’s tree in terms of measurement costs when solving both types of sequential diagnosis problems.

10.1609/socs.v9i1.18449