1. Laboratory of Symbolic Computation and Knowledge Engineering, Jilin University, Changchun 130000, China 2. College of Computer Science and Technology, Jilin University, Changchun 130000, China
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.
R Reiter . A theory of diagnosis from first principles. Artificial Intelligence, 1987, 32( 1): 57–95
2
P, Struss C Price . Model-based systems in the automotive industry. AI Magazine, 2003, 24( 4): 17–34
3
L, Ardissono L, Console A, Goy G, Petrone C, Picardi M Segnan . Cooperative model-based diagnosis of web services. In: Proceeding of the 16th International Workshop on Principles of Diagnosis. 2005, 125–132
4
Y, Pencolé M O Cordier . 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
E, Torlak F S H, Chang D Jackson . Finding minimal unsatisfiable cores of declarative specifications. In: Proceeding of the 15th International Symposium on Formal Methods. 2008, 326–341
6
S, Narasimhan G Biswas . Model-based diagnosis of hybrid systems. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2007, 37( 3): 348–361
7
D, Jannach T Schmitz . Model-based diagnosis of spreadsheet programs: a constraint-based debugging approach. Automated Software Engineering, 2016, 23( 1): 105–144
8
S M, Lamraoui S Nakajima . 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
R, Stern B Juba . Safe partial diagnosis from normal observations. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence. 2019, 3084–3091
10
S M, Lamraoui S Nakajima . A formula-based approach for automatic fault localization of multi-fault programs. Journal of Information Processing, 2016, 24( 1): 88–98
11
A, Ignatiev A, Morgado G, Weissenbacher J Marques-Silva . Model-based diagnosis with multiple observations. In: Proceeding of the 28th International Joint Conference on Artificial Intelligence. 2019, 1108–1115
12
A, Ignatiev A, Morgado J Marques-Silva . Model based diagnosis of multiple observations with implicit hitting sets. 2017, arXiv preprint arXiv: 1707.01972
13
F, Brglzz H Fujiwara . 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
M, Liu D, Ouyang S, Cai L Zhang . Efficient zonal diagnosis with maximum satisfiability. Science China Information Sciences, 2018, 61( 11): 112101
15
S, Siddiqi J Huang . Hierarchical diagnosis of multiple faults. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence. 2007, 581–586
16
D, Jannach T, Schmitz K Shchekotykhin . Parallelized hitting set computation for model-based diagnosis. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 1503–1510
17
A, Feldman G, Provan Gemund A Van . Approximate model-based diagnosis using greedy stochastic search. Journal of Artificial Intelligence Research, 2010, 38: 371–413
18
A B, Feldman G, Provan Kleer J, De S, Robert Gemund A J C Van . 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
R, Stern M, Kalech A, Feldman G Provan . Exploring the duality in conflict-directed model-based diagnosis. In: Proceeding of the 26th AAAI Conference on Artificial Intelligence. 2012, 828–834
20
B C, Williams R J Ragno . Conflict-directed A* and its role in model-based embedded systems. Discrete Applied Mathematics, 2007, 155( 12): 1562–1595
21
A, Feldman G M, Provan Gemund A Van . Computing minimal diagnoses by greedy stochastic search. In: Proceeding of the 23rd National Conference on Artificial Intelligence. 2008, 911–918
22
A, Diedrich A, Feldman A, Perdomo-Ortiz R, Abreu O, Niggemann Kleer J de . Applying simulated annealing to problems in model-based diagnosis. In: Proceeding of International Workshop on the Principles of Diagnosis. 2016, 4–7
23
G, Lamperti M, Zanella X Zhao . Diagnosis of deep discrete-event systems. Journal of Artificial Intelligence Research, 2020, 69: 1473–1532
24
Y, Lai D, Liu M Yin . New canonical representations by augmenting OBDDs with conjunctive decomposition. Journal Of Artificial Intelligence Research, 2017, 58: 453–521
25
P, Torasso G Torta . Computing minimum-cardinality diagnoses using OBDDs. In: Proceeding of the 26th Annual Conference on Artificial Intelligence. 2003, 224–238
26
A Darwiche . Model-based diagnosis using structured system descriptions. Journal of Artificial Intelligence Research, 1998, 8( 1): 165–222
27
L, Console D T, Dupre P Torasso . On the relationship between abduction and deduction. Journal of Logic and Computation, 1991, 1( 5): 661–690
28
A, Metodi R, Stern M, Kalech M Codish . Compiling model-based diagnosis to Boolean satisfaction. In: Proceeding of the 26th AAAI Conference on Artificial Intelligence. 2012, 793–799
29
J, Marques-Silva M, Janota A, Ignatiev A Morgado . Efficient model based diagnosis with maximum satisfiability. In: Proceedings of the 24th International Conference on Artificial Intelligence. 2015, 1966–1972
30
A, Metodi R, Stern M, Kalech M Codish . A novel sat-based approach to model based diagnosis. Journal of Artificial Intelligence Research, 2014, 51( 1): 377–411
31
H, Zhou D, Ouyang L, Zhang N Tian . Model-based diagnosis with improved implicit hitting set dualization. Applied Intelligence, 2022, 52( 2): 2111–2118
32
Z, Lei S Cai . 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
S Siddiqi . Computing minimum-cardinality diagnoses by model relaxation. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 2011, 1087–1092
34
Kleer J De . Minimum cardinality candidate generation. In: Proceedings of the 20th International Workshop on the Principles of Diagnosis. 2009, 397–402
35
A, Ignatiev A, Morgado J Marques-Silva . RC2: an efficient MaxSAT solver. Journal on Satisfiability, Boolean Modeling and Computation, 2019, 11( 1): 53–64
36
C, Mencía A, Previti J Marques-Silva . Literal-based MCS extraction. In: Proceeding of the 24th International Conference on Artificial Intelligence. 2015, 1973–1979
