不确定观测条件下基于模型诊断的故障检测方法

doi:10.13229/j.cnki.jdxbgxb.20240723

摘要/Abstract

摘要：

为解决因传感器故障或其他因素常常导致观测是不确定的情况下，基于模型的诊断（MBD）方法耗时较长的问题，提出了基于桶排序（BSD）的方法。该方法利用最大可满足性对程序频谱进行约简，并使用桶排序确定诊断的优先级。在每个划分的桶中，使用基于频谱的缺陷定位方法（SBFL）计算各个组件的怀疑度，最终返回有序的诊断集合。实验将BSD方法与最新算法MstLikeDiag及Incremental-O2D进行对比，结果表明，针对350组测试实例，在TOP-1度量指标下，BSD方法识别的故障数量分别是MstLikeDiag及Incremental-O2D的3.91倍及7.56倍，在TOP-5指标下分别是其6.15倍及4.79倍，在TOP-10指标下分别是其6.43倍及4.13倍。同时，BSD方法的平均求解效率分别是MstLikeDiag及Incremental-O2D方法的92.1倍及106.5倍。

关键词: 模型诊断, 最大可满足性问题, 不确定观测, 最小基数诊断

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

中图分类号:

TP277

欧阳丹彤,郝闯,蒋璐宇,张立明. 不确定观测条件下基于模型诊断的故障检测方法[J]. 吉林大学学报(工学版), 2026, 56(3): 811-818.

Dan-tong OUYANG,Chuang HAO,Lu-yu JIANG,Li-ming ZHANG. Fault detection method with model-based diagnosis under uncertain observation conditions[J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(3): 811-818.

图/表 6

表1

图1

表2

图2

图3

图4

参考文献 27

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

	c₁	c₂	e
t₁	1	0	1
t₂	0	1	0
t₃	1	1	1

硬子句		软子句
权重	子句	权重	子句
4	1 3 0	1	-1 0
4	2 3 0	1	-2 0
		1	-3 0