StaticHS: A Variant of Reiter’s Hitting Set Tree for Efﬁcient Sequential Diagnosis
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 deﬁnition of the problem and that (2) tackling the more speciﬁc problem might sufﬁce 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 signiﬁcant superiority of StaticHS to an application of Reiter’s tree in terms of measurement costs when solving both types of sequential diagnosis problems.