Journal of Jilin University(Engineering and Technology Edition) ›› 2026, Vol. 56 ›› Issue (3): 811-818.doi: 10.13229/j.cnki.jdxbgxb.20240723

Previous Articles    

Fault detection method with model-based diagnosis under uncertain observation conditions

Dan-tong OUYANG1,2(),Chuang HAO1,2,Lu-yu JIANG1,2,Li-ming ZHANG1,2   

  1. 1.College of Computer Science and Technology，Jilin University，Changchun 130012，China
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education，Jilin University，Changchun 130012，China
  • Received:2024-06-29 Online:2026-03-01 Published:2026-03-31

RICH HTML

 0   

PDF (PC)

46

Abstract:

In order to solve the problem that model-based diagnosis （MBD） methods are time-consuming when observations are uncertain due to sensor failures or other factors. This paper mainly focuses on software fault detection and proposes the Bucket Sort for Diagnoses （BSD） method to solve the problem of MBD with uncertain observation.The BSD method reduces the program spectrum using maximum satisfiability， and then uses bucket sorting to determine the priority of diagnosis. Diagnosis based on feasible observations with fewer faulty sensors have higher priority. Within every bucket， the Spectrum-Based Fault Localization （SBFL） method is used to calculate the suspicion of the components， and the algorithm finally return an ordered diagnosis set. For 350 sets of test instances， the experimental results show that the number of faults identified by the BSD algorithm under the TOP-1 metric is increased by 3.91 times and 7.56 times compared with MstLikeDiag and Incremental-O2D， 6.15 times and 4.79 times under the TOP-5 metric， and 6.43 times and 4.13 times under the TOP-10 metric. Meanwhile， the average efficiency of the BSD method is 92.1 times and 106.5 times than that of the MstLikeDiag and Incremental-O2D methods for 350 test instances.

Key words: model-based diagnosis, maximum satisfiability, uncertain observations, cardinality-minimal diagnosis

CLC Number: 

  • TP277

Table 1

Program spectrum example"

c1c2e
t1101
t2010
t3111

Fig.1

Program spectrum generation process"

Table 2

Clauses corresponding to the program spectrum"

硬子句软子句
权重子句权重子句
41 3 01-1 0
42 3 01-2 0
1-3 0

Fig.2

Process of bucket sorting returning an ordered diagnostic list"

Fig.3

Performance of three algorithms under different indicators"

Fig.4

Average execution time of the algorithm for different programs"

[1] Reiter R. A theory of diagnosis from first principles[J]. Artificial intelligence, 1987, 32(1): 57-95.
[2] 欧阳丹彤, 刘扬, 宋金彩, 等. 结合结构特征基于测试集重排序的故障诊断方法[J]. 电子学报,2022, 50(1): 63-71.
Ou yang Dan-tong, Liu Yang, Song Jin-cai, et al.Fault diagnosis method based on test set reordering combined with structural features[J]. Chinese Journal of Electronics, 2022, 50(1): 63-71.
[3] 欧阳丹彤, 许斌, 董博文,等. 结合测试点质量的混合测试点集合约简方法[J]. 电子学报,2023,51(6): 1552-1561.
Dan-tong Ou-Yang, Xu Bin, Dong Bo-wen, et al.Hybrid test point set reduction method based on test point quality[J]. Chinese Journal of Electronics, 2023, 51(6): 1552-1561.
[4] Feng Wen-quan, Du Min, Zhao Qi, et al.A method of combining HSSE-tree and binary label to compute all minimal hitting sets[C]∥2011 Fourth International Symposium on Computational Intelligence and Design, Hangzhou, China, 2011, 2: 23-26.
[5] Zhao Xiang-fu, Ou yang Dan-tong. A method of combining SE-tree to compute all minimal hitting sets[J]. Progress in Natural Science, 2006, 16(2): 169-174.
[6] Cai Shao-wei, Lei Zhen-dong. Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability[J]. Artificial Intelligence, 2020, 287: 103354.
[7] Smith A, Veneris A, Ali M F, et al.Fault diagnosis and logic debugging using Boolean satisfiability[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(10): 1606-1621.
[8] Feldman A B, Provan G, de Kleer J, et al.Solving model-based diagnosis problems with Max-SAT solvers and vice versa[C]∥21st International Workshop on the Principles of Diagnosis (DX'10), Portland, USA, 2010: 1-8.
[9] Marques-Silva J, Janota M, Ignatiev A, et al.Efficient model based diagnosis with maximum satisfiability[C]∥Association for the Advancement of Artificial Intelligence (AAAI), Austin, USA, 2015: 1966-1972.
[10] Liu Meng, Ou yang Dan-tong, Cai Shao-wei, et al. Efficient zonal diagnosis with maximum satisfiability[J]. Science China Information Sciences, 2018, 61: 1-14.
[11] Ignatiev A, Morgado A, Weissenbacher G, et al.Model-based diagnosis with multiple observations[C]∥IJCAI, Macao, China, 2019: 1108-1115.
[12] Zhou Hui-si, Ou yang Dan-tong, Zhang Li-ming, et al.Model-based diagnosis with improved implicit hitting set dualization[J]. Applied Intelligence, 2022, 52(2): 2111-2118.
[13] Zhou Hui-si, Ou yang Dan-tong, Zhao Xiang-fu, et al.Two compacted models for efficient model-based diagnosis[C]∥Proceedings of the AAAI Conference on Artificial Intelligence, Vancouver, Canada, 2022, 36(4): 3885-3893.
[14] 周慧思, 欧阳丹彤, 田新亮, 等. 基于模型诊断的一种新编码方法[J]. 计算机研究与发展, 2023, 60(1): 95-102.
Zhou Hui-si, Ou yang Dan-tong, Tian Xin-liang, et al.A novel encoding for model-based diagnosis[J]. Journal of Computer Research and Development, 2023, 60(1): 95-102.
[15] Robinson B, Ernst M D, Perkins J H, et al. Scaling up automated test generation: automatically generating maintainable regression unit tests for programs[C]∥2011 26th IEEE/ACM International Conference on Automated Software Engineering (ASE 2011), Lawrence, USA, 2011: 23-32.
[16] Lamperti G, Zanella M. Uncertain temporal observations in diagnosis[C]∥ECAI, Berlin, Germany, 2000: 151-155.
[17] Lamperti G, Zanella M. Monitoring of active systems with stratified uncertain observations[J]. IEEE Transactions on Systems,Man, and Cybernetics—Part A: Systems and Humans, 2010, 41(2): 356-369.
[18] Christopher C J, Cordier M O, Grastien A. Critical observations in a diagnostic problem[C]∥53rd IEEE Conference on Decision and Control, Los Angeles, USA, 2014: 382-387.
[19] Stern R, Kalech M, Rogov S, et al.How many diagnoses do we need?[J]. Artificial Intelligence, 2017, 248: 26-45.
[20] 欧阳丹彤, 孙睿, 田新亮, 等. 基于集合阻塞的不确定系统中传感器选择方法[J]. 吉林大学学报: 工学版, 2023, 53(2): 547-554.
Ou yang Dan-tong, Sun Rui, Tian Xin-liang, et al.Set blocking-based approach to sensor selection in uncertain systems[J]. Journal of Jilin University (Engineering and Technology Edition), 2023, 53(2):547-554.
[21] Cazes D, Kalech M. Model-based diagnosis with uncertain observations[C]∥Proceedings of the AAAI Conference on Artificial Intelligence, New York, USA, 2020, 34(3): 2766-2773.
[22] Cazes D, Kalech M. Model-based diagnosis with uncertain observations[J]. International Journal of Intelligent Systems, 2021, 36(7): 3259-3292.
[23] Zakari A, Lee S P, Abreu R, et al.Multiple fault localization of software programs: a systematic literature review[J]. Information and Software Technology, 2020, 124: 106312.
[24] Abreu R, Zoeteweij P, Van Gemund A J C. On the accuracy of spectrum-based fault localization[C]∥Testing: academic and industrial conference practice and research techniques-MUTATION, Windsor, UK, 2007: 89-98.
[25] Zhou Hui-si, Ou yang Dan-tong, Zhang Li-ming. Efficient static compaction of test patterns using partial MaxSAT[J].Tsinghua Science and Technology, 2020, 26(1): 1-8.
[26] 欧阳丹彤, 孙睿, 田新亮, 等. 基于部分最大可满足性问题的动态系统中最小故障检测隔离集求解方法[J]. 吉林大学学报:工学版, 2023, 53(4):1163-1173.
Ou yang Dan-tong, Sun Rui, Tian Xin-liang, et al.A method for solving the isolation set of minimum fault detection in a dynamic system based on the partial maximum satisfiability problem[J]. Journal of Jilin University (Engineering and Technology Edition), 2023, 53(4): 1163-1173.
[27] Ignatiev A, Morgado A, Marques-Silva J. RC2: an efficient Max-SATSolver[J]. Journal on Satisfiability, Boolean Modeling and Computation, 2019, 11(1): 53-64.
[1] Dan-tong OUYANG,Rui SUN,Xin-liang TIAN,Li-ming ZHANG,Ping-ping LIU. Approach for generating minimal fault detectability and isolability set in dynamic system based on partial maximum satisfiability problem [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(4): 1163-1173.
[2] Dan-tong OU-YANG,Rui SUN,Xin-liang TIAN,Bo-han GAO. Set blocking⁃based approach to sensor selection in uncertain systems [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 547-554.
[3] WANG Yi-yuan, OUYANG Dan-tong, ZHANG Li-ming. Min-length hitting set GRASP algorithm based on dynamic degree of components [J]. 吉林大学学报(工学版), 2017, 47(3): 930-936.
[4] WANG Xiao-yu,OUYANG Dan-tong,ZHAO Jian. Diagnoser-based incremental method of determining diagnosability [J]. 吉林大学学报(工学版), 2015, 45(1): 222-228.
[5] OUYANG Dan-tong, GENG Xue-na, GUO Jin-song, WANG Xiao-yu. Heuristic algorithm of computing minimal hitting sets matrix [J]. 吉林大学学报(工学版), 2013, 43(01): 106-110.
[6] LI Zhan-shan, JIN Zhi-min, YANG Feng-jie, XU Pei-zhi. Codiagnosability verification of discrete event systems [J]. 吉林大学学报(工学版), 2013, 43(01): 123-129.
[7] ZHAO Jian, OUYANG Dan-tong, WANG Xiao-yu, ZHANG Li-ming. Method to distributed diagnosis of hybrid systems [J]. , 2012, (06): 1498-1504.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd