DynamicHS: Streamlining Reiter’s Hitting-Set Tree for Sequential Diagnosis
Patrick Rodler · Information Sciences · 2022
Given a system that does not work as expected, sequential diagnosis aims at suggesting a series of system measurements to isolate the true explanation for the system’s misbehavior from a potentially large set of possible explanations. To reason about the best next measurement, sequential diagnosis methods usually require a sample of possible fault explanations at each step of the iterative diagnostic process. The computation of this sample can be accomplished by various diagnostic search algorithms. Among those, Reiter’s HS-Tree is one of the most popular due to its desirable properties and general applicability. Usually, HS-Tree is used in a stateless fashion throughout the diagnosis process to (re)compute a sample of possible fault explanations per iteration, each time given the latest (updated) system knowledge including all so-far collected measurements. At this, the built search tree is discarded between two iterations, albeit often large parts of the tree have to be rebuilt in the next iteration, involving redundant operations and calls to costly reasoning services. As a remedy to this, we propose DynamicHS, a variant of HS-Tree that maintains state throughout the diagnostic session and embraces special strategies to minimize the number of expensive reasoner invocations. DynamicHS provides an answer to a longstanding question posed by Raymond Reiter in his seminal paper from 1987, where he wondered if there is a reasonable strategy to reuse an existing search tree to compute fault explanations after new system information is obtained. We conducted extensive evaluations on real-world diagnosis problems from the domain of knowledge-based systems—a field where the usage of HS-Tree is state-of-the-art—under various diagnosis scenarios in terms of the number of fault explanations computed and the heuristic for measurement selection used. The results prove the reasonability of the novel approach and testify its clear superiority to HS-Tree wrt. computation time. More specifically: (1) DynamicHS required less time than HS-Tree in 96 % of the executed sequential diagnosis sessions. (2) DynamicHS exhibited substantial and statistically significant time savings over HS-Tree in most scenarios, with median and maximal savings of 52 % and 75 %, respectively. (3) The relative amount of saved time appears to neither depend on the number of computed fault explanations nor on the used measurement selection heuristic. (4) In the hardest (most time-intensive) cases per diagnosis scenario, DynamicHS achieved even higher savings than on average, and could avoid median and maximal time overheads of over 175 % and 800 %, respectively, as opposed to a usage of HS-Tree. Remarkably, DynamicHS achieves these performance improvements while preserving all desirable properties as well as the general applicability of HS-Tree.