On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective
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 ch...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The Prognostics and Health Management Society
2016-06-01
|
| Series: | International Journal of Prognostics and Health Management |
| Subjects: | |
| Online Access: | https://papers.phmsociety.org/index.php/ijphm/article/view/2363 |
| _version_ | 1818580072055963648 |
|---|---|
| author | Ingo Pill Thomas Quaritsch Franz Wotawa |
| author_facet | Ingo Pill Thomas Quaritsch Franz Wotawa |
| author_sort | Ingo Pill |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-16T07:11:47Z |
| format | Article |
| id | doaj.art-db6117d27c70405291aca1deb54cd7a1 |
| institution | Directory Open Access Journal |
| issn | 2153-2648 2153-2648 |
| language | English |
| last_indexed | 2024-12-16T07:11:47Z |
| publishDate | 2016-06-01 |
| publisher | The Prognostics and Health Management Society |
| record_format | Article |
| series | International Journal of Prognostics and Health Management |
| spelling | doaj.art-db6117d27c70405291aca1deb54cd7a12022-12-21T22:39:53ZengThe Prognostics and Health Management SocietyInternational Journal of Prognostics and Health Management2153-26482153-26482016-06-0172doi:10.36001/ijphm.2016.v7i2.2363On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic PerspectiveIngo Pill0Thomas Quaritsch1Franz Wotawa2Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, AustriaHTL Pinkafeld, Meierhofplatz 1, 7423 Pinkafeld, Austria (this author was also with the Institute for Software Technology when contributing)Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, AustriaMinimal 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.https://papers.phmsociety.org/index.php/ijphm/article/view/2363model-based diagnosisminimal hitting set |
| spellingShingle | Ingo Pill Thomas Quaritsch Franz Wotawa On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective International Journal of Prognostics and Health Management model-based diagnosis minimal hitting set |
| title | On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective |
| title_full | On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective |
| title_fullStr | On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective |
| title_full_unstemmed | On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective |
| title_short | On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective |
| title_sort | on the practical performance of minimal hitting set algorithms from a diagnostic perspective |
| topic | model-based diagnosis minimal hitting set |
| url | https://papers.phmsociety.org/index.php/ijphm/article/view/2363 |
| work_keys_str_mv | AT ingopill onthepracticalperformanceofminimalhittingsetalgorithmsfromadiagnosticperspective AT thomasquaritsch onthepracticalperformanceofminimalhittingsetalgorithmsfromadiagnosticperspective AT franzwotawa onthepracticalperformanceofminimalhittingsetalgorithmsfromadiagnosticperspective |