DiagDO: an efficient model based diagnosis approach with multiple observations

Abstract

Model-based diagnosis (MBD) with multiple observations shows its significance in identifying fault location. The existing approaches for MBD with multiple observations use observations which is inconsistent with the prediction of the system. In this paper, we proposed a novel diagnosis approach, namely, the Diagnosis with Different Observations (DiagDO), to exploit the diagnosis when given a set of pseudo normal observations and a set of abnormal observations. Three ideas are proposed in this paper. First, for each pseudo normal observation, we propagate the value of system inputs and gain fanin-free edges to shrink the size of possible faulty components. Second, for each abnormal observation, we utilize filtered nodes to seek surely normal components. Finally, we encode all the surely normal components and parts of dominated components into hard clauses and compute diagnosis using the MaxSAT solver and MCS algorithm. Extensive tests on the ISCAS'85 and ITC'99 benchmarks show that our approach performs better than the state-of-the-art algorithms.

Graphical abstract

Keywords

model based diagnosis / maximum satisfiability / top-level diagnosis / cardinality-minimal diagnosis / subset-minimal diagnosis

Huisi Zhou received her MS degree from Jilin University, China in 2020. She is currently a PhD candidate of Jilin University, China. Her research interests include model-based diagnosis and partial maximum satisfiability problem

Dantong Ouyang received her PhD degree from Jilin University, China in 1998 and she is currently the professor of Jilin University, China. Her research interests include the model-based diagnosis, satisfiability problem and model checking

Xinliang Tian received his MS degree from Jilin Univercity, China in 2018. He is currently a PhD candidate of Jilin Univercity, China. His main research interests include model-based diagnosis and combinatorial optimization problem

Liming Zhang received his MS and PhD degree from Jilin Univercity, China in 2009 and 2012, respectively. He is currently a Senior Engineer of Jilin Univercity, China. His main research interests are satisfiability, integrated circuit diagnosis and testing and maximum satisfiability

References

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

[2] Struss P, Price C. Model-based systems in the automotive industry. AI Magazine, 2003, 24( 4): 17–34

[3] Ardissono L, Console L, Goy A, Petrone G, Picardi C, Segnan M. Cooperative model-based diagnosis of web services. In: Proceeding of the 16th International Workshop on Principles of Diagnosis. 2005, 125–132

[4] 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

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

[6] 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

[7] Jannach D, Schmitz T. Model-based diagnosis of spreadsheet programs: a constraint-based debugging approach. Automated Software Engineering, 2016, 23( 1): 105–144

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

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

[10] 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

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

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

[13] Brglzz F, Fujiwara H. A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN. In: Proceeding of the International Symposium on Circuits and Systems. 1985, 695–698

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

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

[16] Jannach D, Schmitz T, Shchekotykhin K. Parallelized hitting set computation for model-based diagnosis. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 1503–1510

[17] Feldman A, Provan G, Van Gemund A. Approximate model-based diagnosis using greedy stochastic search. Journal of Artificial Intelligence Research, 2010, 38: 371–413

[18] Feldman A B, Provan G, De Kleer J, Robert S, Van Gemund A J C. Solving model-based diagnosis problems with Max-SAT solvers and vice versa. In: Proceedings of the 21st International Workshop on the Principles of Diagnosis. 2010, 185–192

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

[20] Williams B C, Ragno R J. Conflict-directed A^* and its role in model-based embedded systems. Discrete Applied Mathematics, 2007, 155( 12): 1562–1595

[21] Feldman A, Provan G M, Van Gemund A. Computing minimal diagnoses by greedy stochastic search. In: Proceeding of the 23rd National Conference on Artificial Intelligence. 2008, 911–918

[22] Diedrich A, Feldman A, Perdomo-Ortiz A, Abreu R, Niggemann O, de Kleer J. Applying simulated annealing to problems in model-based diagnosis. In: Proceeding of International Workshop on the Principles of Diagnosis. 2016, 4–7

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

[24] Lai Y, Liu D, Yin M. New canonical representations by augmenting OBDDs with conjunctive decomposition. Journal Of Artificial Intelligence Research, 2017, 58: 453–521

[25] Torasso P, Torta G. Computing minimum-cardinality diagnoses using OBDDs. In: Proceeding of the 26th Annual Conference on Artificial Intelligence. 2003, 224–238

[26] Darwiche A. Model-based diagnosis using structured system descriptions. Journal of Artificial Intelligence Research, 1998, 8( 1): 165–222

[27] Console L, Dupre D T, Torasso P. On the relationship between abduction and deduction. Journal of Logic and Computation, 1991, 1( 5): 661–690

[28] Metodi A, Stern R, Kalech M, Codish M. Compiling model-based diagnosis to Boolean satisfaction. In: Proceeding of the 26th AAAI Conference on Artificial Intelligence. 2012, 793–799

[29] 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

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

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

[32] Lei Z, Cai S. Solving (Weighted) partial MaxSAT by dynamic local search for SAT. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. 2018, 1346–1352

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

[34] De Kleer J. Minimum cardinality candidate generation. In: Proceedings of the 20th International Workshop on the Principles of Diagnosis. 2009, 397–402

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

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

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 62076108, 61972360, and 61872159).

RIGHTS & PERMISSIONS

2023 Higher Education Press