DiagDO: an efficient model based diagnosis approach with multiple observations
Tóm tắt
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.
Tài liệu tham khảo
Reiter R. A theory of diagnosis from first principles. Artificial Intelligence, 1987, 32(1): 57–95
Struss P, Price C. Model-based systems in the automotive industry. AI Magazine, 2003, 24(4): 17–34
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
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
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
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
Jannach D, Schmitz T. Model-based diagnosis of spreadsheet programs: a constraint-based debugging approach. Automated Software Engineering, 2016, 23(1): 105–144
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
Stern R, Juba B. Safe partial diagnosis from normal observations. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence. 2019, 3084–3091
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
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
Ignatiev A, Morgado A, Marques-Silva J. Model based diagnosis of multiple observations with implicit hitting sets. 2017, arXiv preprint arXiv: 1707.01972
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
Liu M, Ouyang D, Cai S, Zhang L. Efficient zonal diagnosis with maximum satisfiability. Science China Information Sciences, 2018, 61(11): 112101
Siddiqi S, Huang J. Hierarchical diagnosis of multiple faults. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence. 2007, 581–586
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
Feldman A, Provan G, Van Gemund A. Approximate model-based diagnosis using greedy stochastic search. Journal of Artificial Intelligence Research, 2010, 38: 371–413
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
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
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
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
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
Lamperti G, Zanella M, Zhao X. Diagnosis of deep discrete-event systems. Journal of Artificial Intelligence Research, 2020, 69: 1473–1532
Lai Y, Liu D, Yin M. New canonical representations by augmenting OBDDs with conjunctive decomposition. Journal Of Artificial Intelligence Research, 2017, 58: 453–521
Torasso P, Torta G. Computing minimum-cardinality diagnoses using OBDDs. In: Proceeding of the 26th Annual Conference on Artificial Intelligence. 2003, 224–238
Darwiche A. Model-based diagnosis using structured system descriptions. Journal of Artificial Intelligence Research, 1998, 8(1): 165–222
Console L, Dupre D T, Torasso P. On the relationship between abduction and deduction. Journal of Logic and Computation, 1991, 1(5): 661–690
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
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
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
Zhou H, Ouyang D, Zhang L, Tian N. Model-based diagnosis with improved implicit hitting set dualization. Applied Intelligence, 2022, 52(2): 2111–2118
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
Siddiqi S. Computing minimum-cardinality diagnoses by model relaxation. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 2011, 1087–1092
De Kleer J. Minimum cardinality candidate generation. In: Proceedings of the 20th International Workshop on the Principles of Diagnosis. 2009, 397–402
Ignatiev A, Morgado A, Marques-Silva J. RC2: an efficient MaxSAT solver. Journal on Satisfiability, Boolean Modeling and Computation, 2019, 11(1): 53–64
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