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

Ingo Pill, Thomas Quaritsch, and Franz Wotawa
Publication Target: 
Publication Issue: 
Submission Type: 
Full Paper
Supporting Agencies (optional): 
Austrian Science Fund
ijphm_16_010.pdf407.39 KBJuly 26, 2016 - 11:15pm

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.

Publication Year: 
Publication Volume: 
Publication Control Number: 
Page Count: 
Submission Keywords: 
Model-based diagnosis
Minimal Hitting Set
Submission Topic Areas: 
Model-based methods for fault detection, diagnostics, and prognosis
Submitted by: 

follow us

PHM Society on Facebook Follow PHM Society on Twitter PHM Society on LinkedIn PHM Society RSS News Feed