Enhancing model-based diagnosis with multiple pseudo-normal observations by Key nodes and IterativeDFS

Abstract

Model-based diagnosis (MBD) with multiple pseudo-normal observations enables the effective detection of latent faults even when some actual observations are consistent with the system’s expected observations. Current state-of-the-art algorithms overlook this diagnostically rich scenario and incorporate too many components, which frequently leads to stack overflow errors in large-scale experiments. To address these challenges, we introduce our algorithm DKIPNO (Diagnosis with Key node and IterativeDFS for Pseudo-Normal Observations) in this paper, which mainly focuses on MBD with multiple pseudo-normal observations and incorporates two original proposed ideas. Firstly, we introduce the novel concept of the ‘key node’. By virtually flipping the outputs of key nodes and comparing flipped observations with the system’s expected observations, we effectively identify more functionally normal components and significantly reduce the number of potentially faulty components in the diagnostic process. Secondly, we present the IterativeDFS method, an original iterative traversal technique that can prevent stack overflow errors commonly encountered with the recursive method used in previous algorithms. We evaluate the performance of DKIPNO using the ISCAS’85 benchmark in our experiment. Experimental results demonstrate that DKIPNO not only significantly reduces the time required for diagnosis but also prevents stack overflow errors, thereby outperforming other state-of-the-art algorithms.

Graphical abstract

Keywords

model-based diagnosis / multiple observations / pseudo-normal observations / subset-minimal diagnoses / cardinality-minimal diagnoses

References

[1] Reiter R . A theory of diagnosis from first principles. Artificial intelligence, 1987, 32( 1): 57–95

[2] De Kleer J, Williams B C . Diagnosing multiple faults. Artificial Intelligence, 1987, 32( 1): 97–130

[3] De Kleer J, Williams B C. Diagnosis with behavioral modes. In: Proceedings of the 11th International Joint Conference on Artificial Intelligence. 1989, 1324−1330

[4] De Kleer J, Mackworth A K, Reiter R . Characterizing diagnoses and systems. Artificial Intelligence, 1992, 56( 2−3): 197–222

[5] De Kleer J, Kurien J . Fundamentals of model-based diagnosis. IFAC Proceedings Volumes, 2003, 36( 5): 25–36

[6] Keren B, Kalech M, Rokach L. Model-based diagnosis with multi-label classification. In: Proceedings of the 22nd International Workshop on Principles of Diagnosis. 2011

[7] Nica I, Pill I, Quaritsch T, Wotawa F. The route to success: a performance comparison of diagnosis algorithms. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 2013, 1039−1045

[8] Pencolé Y, Cordier M O . A formal framework for the decentralised diagnosis of large scale discrete event systems and its application to telecommunication networks. Artificial Intelligence, 2005, 164( 1−2): 121–170

[9] Torlak E, Chang F S H, Jackson D. Finding minimal unsatisfiable cores of declarative specifications. In: Proceedings of the 15th International Symposium on Formal Methods. 2008, 326−341

[10] Narasimhan S, Biswas G . Model-based diagnosis of hybrid systems. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2007, 37( 3): 348–361

[11] Rodler P, Herold M. StaticHS: A variant of Reiter’s hitting set tree for efficient sequential diagnosis. In: Proceedings of the 11th International Symposium on Combinatorial Search. 2018, 72−80

[12] Rodler P . DynamicHS: Streamlining Reiter’s hitting-set tree for sequential diagnosis. Information Sciences, 2023, 627: 251–279

[13] Rodler P. Random vs. best-first: Impact of sampling strategies on decision making in model-based diagnosis. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 5869−5878

[14] Rodler P . Sequential model-based diagnosis by systematic search. Artificial Intelligence, 2023, 323: 103988

[15] Rodler P . Memory-limited model-based diagnosis. Artificial Intelligence, 2022, 305: 103681

[16] Ignatiev A, Morgado A, Marques-Silva J. Model based diagnosis of multiple observations with implicit hitting sets. 2017, arXiv preprint arXiv: 1707.01972

[17] Ignatiev A, Morgado A, Weissenbacher G, Marques-Silva J. Model-based diagnosis with multiple observations. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 1108−1115

[18] Kalech M, Stern R, Lazebnik E . Minimal cardinality diagnosis in problems with multiple observations. Diagnostics, 2021, 11( 5): 780

[19] Zhou H, Ouyang D, Zhang L, Tian N . Model-based diagnosis with improved implicit hitting set dualization. Applied Intelligence, 2022, 52( 2): 2111–2118

[20] Zhou H, Ouyang D, Tian X, Zhang L . DiagDO: an efficient model based diagnosis approach with multiple observations. Frontiers of Computer Science, 2023, 17( 6): 176407

[21] Brglez F, Fujiwara H. A neutral netlist of 10 combinational benchmark circuits and a target translator. In: Proceedings of the IEEE International Symposium on Circuits and Systems. 1985

[22] Stern R, Kalech M, Feldman A, Provan G. Exploring the duality in conflict-directed model-based diagnosis. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence. 2012, 828−834

[23] Lamraoui S M, Nakajima S. A formula-based approach for automatic fault localization of imperative programs. In: Proceedings of the 16th International Conference on Formal Engineering Methods. 2014, 251−266

[24] Lamraoui S M, Nakajima S . A formula-based approach for automatic fault localization of multi-fault programs. Journal of Information Processing, 2016, 24( 1): 88–98

[25] Liu M, Ouyang D, Zhang L . A novel approach for improving quality of health state with difference degree in circuit diagnosis. Applied Intelligence, 2018, 48( 11): 4371–4381

[26] Stern R, Kalech M, Rogov S, Feldman A . How many diagnoses do we need?. Artificial Intelligence, 2017, 248: 26–45

[27] Siddiqi S, Huang J. Hierarchical diagnosis of multiple faults. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence. 2007, 581−586

[28] Metodi A, Stern R, Kalech M, Codish M . A novel sat-based approach to model based diagnosis. Journal of Artificial Intelligence Research, 2014, 51: 377–411

[29] Liu M, Ouyang D, Cai S, Zhang L . Efficient zonal diagnosis with maximum satisfiability. Science China Information Sciences, 2018, 61( 11): 112101

[30] Zhou H, Ouyang D, Zhao X, Zhang L. Two compacted models for efficient model-based diagnosis. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 3885−3893

[31] Tai R, Ouyang D, Liu W, Jiang L, Zhang L . A novel approach to model-based diagnosis with multiple observations. Engineering Applications of Artificial Intelligence, 2025, 141: 109768

[32] Marques-Silva J, Janota M, Ignatiev A, Morgado A. Efficient model based diagnosis with maximum satisfiability. In: Proceedings of the 24th International Conference on Artificial Intelligence. 2015, 1966−1972

[33] Ignatiev A, Morgado A, Marques-Silva J . RC2: an efficient MaxSAT solver. Journal on Satisfiability, Boolean Modeling and Computation, 2019, 11( 1): 53–64

[34] Provan G. Model-based diagnosis with probabilistic models. In: Escobet T, Bregon A, Pulido B, Puig V, eds. Fault Diagnosis of Dynamic Systems: Quantitative and Qualitative Approaches. Cham: Springer, 2019, 295−318

[35] Feldman A, Pill I, Wotawa F, Matei I, De Kleer J. Efficient model-based diagnosis of sequential circuits. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 2814−2821

[36] Wotawa F. On the use of answer set programming for model-based diagnosis. In: Proceedings of the 33rd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. 2020, 518−529

[37] Moddemann L, Steude H S, Diedrich A, Niggemann O . Discret2Di-deep learning based discretization for model-based diagnosis. IFAC-PapersOnLine, 2024, 58( 4): 640–645

[38] Feldman A, Provan G, De Kleer J, Robert S, Van Gemund A. Solving model-based diagnosis problems with max-sat solvers and vice versa. In: Proceedings of 21st International Workshop on the Principles of Diagnosis. 2010

[39] Stern R, Juba B. Safe partial diagnosis from normal observations. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence. 2019, 3084−3091

[40] de Kleer J. Mininimum cardinality candidate generation. In: Proceedings of the 20th International Workshop on Principles of Diagnosis. 2009, 397

[41] Siddiqi S. Computing minimum-cardinality diagnoses by model relaxation. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 2011, 1087−1092

[42] Lamperti G, Zanella M, Zhao X . Diagnosis of deep discrete-event systems. Journal of Artificial Intelligence Research, 2020, 69: 1473–1532

[43] Mencía C, Previti A, Marques-Silva J. Literal-based MCS extraction. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2015, 1973−1979

RIGHTS & PERMISSIONS

Higher Education Press