On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective

Abstract

Minimal hitting sets (MHSs) meliorate our reasoning in many applications, including AI planning, CNF/DNF conversion, and program debugging. When following Reiter’s ”theory of diagnosis from first principles”, minimal hitting sets are also essential to the diagnosis problem, since diagnoses can be characterized as the minimal hitting sets of conflicts in the behavior of a faulty system. While the large amount of application options led to the advent of a variety of corresponding MHS algorithms, for diagnostic purposes we still lack a comparative evaluation assessing performance characteristics. In this paper, we thus empirically evaluate a set of complete algorithms relevant for diagnostic purposes in synthetic and real-world scenarios. We consider in our experimental evaluation also how cardinality constraints on the solution space, as often established in practice for diagnostic purposes, influence performance in terms of run-time and memory usage.

Keywords

• model-based diagnosis
• minimal hitting set