On the Practical Performance of Minimal Hitting Set Algorithms from a Diagnostic Perspective
##plugins.themes.bootstrap3.article.main##
##plugins.themes.bootstrap3.article.sidebar##
Published
Nov 11, 2020
Ingo Pill
Thomas Quaritsch
Franz Wotawa
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.
##plugins.themes.bootstrap3.article.details##
Keywords
Model-based diagnosis, Minimal Hitting Set
References
Abreu, R., & van Gemund, A. (2009). A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis. In 8th Symposium on Abstraction Reformulation, and Approximation.
Asín, R., Nieuwenhuis, R., Oliveras, A., & Rodríguez- Carbonell, E. (2009). Cardinality networks and their applications. Theory and Applications of Satisfiability Testing – SAT 2009, 5584, 167–180.
Batcher, K. (1968). Sorting networks and their applications. In Proceedings of the april 30–may 2, 1968, spring joint computer conference (pp. 307–314).
Bonet, B., & Helmert, M. (2010). Strengthening landmark heuristics via hitting sets. In 19th European Conference on Artificial Intelligence (pp. 329–334).
de Kleer, J. (1986). Problem solving with the ATMS. Artificial Intelligence, 28(2), 197–224. doi: 10.1016/0004-3702(86)90082-2
de Kleer, J. (2008). An improved approach for generating max-fault min-cardinality diagnoses. Int. Workshop on Principles of Diagnosis, 247–252.
de Kleer, J. (2011). Hitting set algorithms for model-based diagnosis. In 22nd Int. Workshop on the Principles of Diagnosis (pp. 100–105).
de Kleer, J., & Williams, B. C. (1987). Diagnosing multiple faults. Artificial Intelligence, 32(1), 97–130.
Eiter, T., Makino, K., & Gottlob, G. (2008). Computational aspects of monotone dualization: A brief survey. Discrete Applied Mathematics, 156(11), 2035–2049. doi: 10.1016/j.dam.2007.04.017
Feldman, A., Provan, G., de Kleer, J., Robert, S., & van Gemund, A. (2010). Solving model-based diagnosis problems with Max-SAT solvers and vice versa. In 21st Int. Workshop on Principles of Diagnosis.
Feldman, A., Provan, G. M., & van Gemund, A. J. C. (2008). Computing observation vectors for max-fault min-cardinality diagnoses. In 23rd AAAI conference on artificial intelligence (pp. 919–924).
Greiner, R., Smith, B. A., & Wilkerson, R.W. (1989). A correction to the algorithm in Reiter’s theory of diagnosis. Artificial Intelligence, 41(1), 79–88.
Hansen, M., Yalcin, H., & Hayes, J. P. (1999, July-Sept.). Unveiling the ISCAS-85 benchmarks: A case study in reverse engineering. IEEE Design and Test, 6, 72–80. (Available at http://www.cbl.ncsu.edu:16080/-benchmarks/ISCAS85/)
Koitz, R., & Wotawa, F. (2016). On Structural Properties to Improve FMEA-Based Abductive Diagnosis. In IJCAI 2016 Workshop on Knowledge-based Techniques for Problem Solving and Reasoning. (Vol. 1648 of CEUR workshop proceedings)
Lin, L., & Jiang, Y. (2003). The computation of hitting sets: review and new algorithms. Information Processing Letters, 86, 177–184.
Metodi, A., Stern, R., Kalech, M., & Codish, M. (2012). Compiling model-based diagnosis to Boolean satisfaction. In 26th AAAI Conference on Artificial Intelligence.
Nica, I., Pill, I., Quaritsch, T.,&Wotawa, F. (2013). The route to success - A performance comparison of diagnosis algorithms. In 23rd International Joint Conference on Artificial Intelligence (IJCAI) (pp. 1039–1045).
Nyberg, M. (2011). A generalized minimal hitting-set algorithm to handle diagnosis with behavioral modes. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 41(1), 137–148.
Pill, I., & Quaritsch, T. (2012). Optimizations for the Boolean approach to computing minimal hitting sets. In 20th European Conference on Artificial Intelligence (ECAI) (p. 648-653).
Pill, I., Quaritsch, T., & Wotawa, F. (2011). From conflicts to diagnoses: An empirical evaluation of minimal hitting set algorithms. In 22nd Int. Workshop on the Principles of Diagnosis (pp. 203–210). (no archival proceedings, author version available at http://www.ist.tugraz.at/pill)
Pill, I., Quaritsch, T., & Wotawa, F. (2015). Parse tree structure in LTL requirements diagnosis. In 2015 IEEE International Symposium on Software Reliability Engineering (ISSRE) Supplementary Proceedings (p. 100-107).
Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, 32(1), 57–95.
Shi, L., & Cai, X. (2010). An exact fast algorithm for minimum hitting set. In 3rd Int. Joint Conference on Computational Science and Optimization (Vol. 1, pp. 64–67).
Wotawa, F. (2001). A variant of Reiter’s hitting-set algorithm. Information Processing Letters, 79, 45–51.
Wotawa, F. (2002). On the relationship between model-based debugging and program slicing. Artificial Intelligence, 135, 125–143.
Asín, R., Nieuwenhuis, R., Oliveras, A., & Rodríguez- Carbonell, E. (2009). Cardinality networks and their applications. Theory and Applications of Satisfiability Testing – SAT 2009, 5584, 167–180.
Batcher, K. (1968). Sorting networks and their applications. In Proceedings of the april 30–may 2, 1968, spring joint computer conference (pp. 307–314).
Bonet, B., & Helmert, M. (2010). Strengthening landmark heuristics via hitting sets. In 19th European Conference on Artificial Intelligence (pp. 329–334).
de Kleer, J. (1986). Problem solving with the ATMS. Artificial Intelligence, 28(2), 197–224. doi: 10.1016/0004-3702(86)90082-2
de Kleer, J. (2008). An improved approach for generating max-fault min-cardinality diagnoses. Int. Workshop on Principles of Diagnosis, 247–252.
de Kleer, J. (2011). Hitting set algorithms for model-based diagnosis. In 22nd Int. Workshop on the Principles of Diagnosis (pp. 100–105).
de Kleer, J., & Williams, B. C. (1987). Diagnosing multiple faults. Artificial Intelligence, 32(1), 97–130.
Eiter, T., Makino, K., & Gottlob, G. (2008). Computational aspects of monotone dualization: A brief survey. Discrete Applied Mathematics, 156(11), 2035–2049. doi: 10.1016/j.dam.2007.04.017
Feldman, A., Provan, G., de Kleer, J., Robert, S., & van Gemund, A. (2010). Solving model-based diagnosis problems with Max-SAT solvers and vice versa. In 21st Int. Workshop on Principles of Diagnosis.
Feldman, A., Provan, G. M., & van Gemund, A. J. C. (2008). Computing observation vectors for max-fault min-cardinality diagnoses. In 23rd AAAI conference on artificial intelligence (pp. 919–924).
Greiner, R., Smith, B. A., & Wilkerson, R.W. (1989). A correction to the algorithm in Reiter’s theory of diagnosis. Artificial Intelligence, 41(1), 79–88.
Hansen, M., Yalcin, H., & Hayes, J. P. (1999, July-Sept.). Unveiling the ISCAS-85 benchmarks: A case study in reverse engineering. IEEE Design and Test, 6, 72–80. (Available at http://www.cbl.ncsu.edu:16080/-benchmarks/ISCAS85/)
Koitz, R., & Wotawa, F. (2016). On Structural Properties to Improve FMEA-Based Abductive Diagnosis. In IJCAI 2016 Workshop on Knowledge-based Techniques for Problem Solving and Reasoning. (Vol. 1648 of CEUR workshop proceedings)
Lin, L., & Jiang, Y. (2003). The computation of hitting sets: review and new algorithms. Information Processing Letters, 86, 177–184.
Metodi, A., Stern, R., Kalech, M., & Codish, M. (2012). Compiling model-based diagnosis to Boolean satisfaction. In 26th AAAI Conference on Artificial Intelligence.
Nica, I., Pill, I., Quaritsch, T.,&Wotawa, F. (2013). The route to success - A performance comparison of diagnosis algorithms. In 23rd International Joint Conference on Artificial Intelligence (IJCAI) (pp. 1039–1045).
Nyberg, M. (2011). A generalized minimal hitting-set algorithm to handle diagnosis with behavioral modes. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 41(1), 137–148.
Pill, I., & Quaritsch, T. (2012). Optimizations for the Boolean approach to computing minimal hitting sets. In 20th European Conference on Artificial Intelligence (ECAI) (p. 648-653).
Pill, I., Quaritsch, T., & Wotawa, F. (2011). From conflicts to diagnoses: An empirical evaluation of minimal hitting set algorithms. In 22nd Int. Workshop on the Principles of Diagnosis (pp. 203–210). (no archival proceedings, author version available at http://www.ist.tugraz.at/pill)
Pill, I., Quaritsch, T., & Wotawa, F. (2015). Parse tree structure in LTL requirements diagnosis. In 2015 IEEE International Symposium on Software Reliability Engineering (ISSRE) Supplementary Proceedings (p. 100-107).
Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, 32(1), 57–95.
Shi, L., & Cai, X. (2010). An exact fast algorithm for minimum hitting set. In 3rd Int. Joint Conference on Computational Science and Optimization (Vol. 1, pp. 64–67).
Wotawa, F. (2001). A variant of Reiter’s hitting-set algorithm. Information Processing Letters, 79, 45–51.
Wotawa, F. (2002). On the relationship between model-based debugging and program slicing. Artificial Intelligence, 135, 125–143.
Section
Technical Papers