结合问题特征的分组式诊断方法

doi:10.3969/j.issn.0372-2112.2018.03.011

电子学报 ›› 2018, Vol. 46 ›› Issue (3): 589-594.DOI: 10.3969/j.issn.0372-2112.2018.03.011

结合问题特征的分组式诊断方法

刘梦^1,2, 欧阳丹彤^1,2, 刘伯文^1,2, 张立明^1,2, 张永刚^1,2

1. 吉林大学计算机科学与技术学院, 吉林长春 130012;
2. 吉林大学符号计算与知识工程教育部重点实验室, 吉林长春 130012

收稿日期:2016-10-12 修回日期:2017-01-12 出版日期:2018-03-25
- 通讯作者:
- 张永刚
- 作者简介:
- 刘梦,女,1993年生于河南洛阳,吉林大学硕士研究生,研究方向为基于模型诊断、SAT问题.E-mail:2238356051@qq.com;欧阳丹彤,女,1968年生于吉林长春,吉林大学教授,主要研究方向为基于模型的诊断、自动推理和模型检测.E-mail:ouyangdantong@163.com;刘伯文,男,1993年生于吉林延边,吉林大学硕士研究生,研究方向为基于模型诊断.E-mail:1591365445@qq.com;张立明,男1980年生于吉林长春,吉林大学博士,主要研究方向为基于模型诊断.E-mail:limingzhang@jlu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61272208，No.61402196，No.61672261）; 浙江省自然科学基金 (No.LY16F020004）

Grouped Diagnosis Approach Using the Feature of Problem

LIU Meng^1,2, OUYANG Dan-tong^1,2, LIU Bo-wen^1,2, ZHANG Li-ming^1,2, ZHANG Yong-gang^1,2

1. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun, Jilin 130012, China

Received:2016-10-12 Revised:2017-01-12 Online:2018-03-25 Published:2018-03-25
- Corresponding author:
- ZHANG Yong-gang

摘要/Abstract

摘要： 模型诊断方法是人工智能领域重要的系统故障自动检测方法，被广泛应用于软件故障检测和硬件诊断.近年来由于电路规模和复杂度不断增大，其诊断难度也不断增大.本文通过对电路模型特征的研究，结合LLBRS-tree（Last-Level Based on Reverse Search-tree）诊断算法提出分组式诊断方法GD（Grouped Diagnosis）：首先结合电路特征确定组件的故障相关性并对电路组件进行分组，可缩减电路中需检测的规模；其次，利用分组后电路并结合非诊断解定理和SAT（SATisfiability）求解特征定位部分非诊断解，从而避免该部分的一致性检测来加速求解.本文算法可应用于电子电路故障诊断领域，并且实验结果表明该算法与LLBRS-tree算法相比求解效率平均提高了1.5倍，最多提高了3倍.

关键词: 基于模型的诊断, 问题特征, 分组, SAT求解器, 集合枚举树

Abstract: Model-based diagnosis is an automatic fault detection approach in artificial intelligence. It is used in software fault detection and hardware diagnosis. Recently, the difficulty of circuit diagnosis is increasing with the increasing size and complexity of the circuit. After studying the characteristics of the circuit model, this paper proposes the grouped diagnosis (GD) approach based on the LLBRS-tree (Last-Level Based on Reverse Search-tree) algorithm. Firstly, the component grouped method is used to identify the component's faulty correlation and group the components. And the scale of the circuit to be detected can be reduced. Secondly, through the grouped circuit, the non-diagnostic solution theorem is given to locate some non-diagnostic solutions with the feature of satisfiability. It can help us avoid checking consistency on these non-diagnostic solutions so as to accelerate the processing. Our algorithm can be used in electronic circuit fault diagnosis. And the experimental results show that it improves the efficiency by 1.5 times and even 3 times compared with the LLBRS-tree algorithm.

Key words: model-based diagnosis, the feature of problem, grouped, SAT solver, set-enumeration-tree

中图分类号:

TP306

刘梦, 欧阳丹彤, 刘伯文, 张立明, 张永刚. 结合问题特征的分组式诊断方法[J]. 电子学报, 2018, 46(3): 589-594.

LIU Meng, OUYANG Dan-tong, LIU Bo-wen, ZHANG Li-ming, ZHANG Yong-gang. Grouped Diagnosis Approach Using the Feature of Problem[J]. Acta Electronica Sinica, 2018, 46(3): 589-594.

参考文献

[1] de Kleer J,Kurien J.Fundamentals of model-based diagnosis[A].Proceedings of the 5th IFAC Symposium on Fault Detection Supervision and Safety of Technical Processes (Safeprocess)[C].Portugal:Elsevier,2004.25-36.
[2] Wang Y,Cai S,Yin M.Two efficient local search algorithms for maximum weight clique problem[A].Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence[C].USA:AAAI Press,2016.805-811.
[3] Wang Y,Ouyang D T,Zhang L,et al.A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity[J].Sci China Inf Sci,2017,60(6):062103.
[4] Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-95.
[5] 姜云飞,林笠.用对分HS-树计算最小碰集[J].软件学报,2002,13(12):2267-2274. Jiang Yun-fei,Lin Li.Computing the minimal hitting sets with binary HS-tree[J].Journal of Software,2002,13(12):2267-2274.(in Chinese)
[6] 王肖,赵相福.用CHS-tree基于集合势的方法计算极小碰集[J].计算机集成制造系统,2014,20(2):401-406. Wang Xiao,Zhao Xiang-fu.Computing minimal hitting set with CHS-tree method[J].Computer Integrated Manufacturing Systems,2014,20(2):401-406.(in Chinese)
[7] 张立明,欧阳丹彤,曾海林.基于动态极大度的极小碰集求解方法[J].计算机研究与发展,2011,48(2):209-215. Zhang Li-ming,Ouyang Dan-tong,Zeng Hai-lin.Computing the minimal hitting set based on dynamic maximum degree[J].Journal of Computer Reach and Development,2011,48(2):209-215.(in Chinese)
[8] Nica I,Pill I,Quaritsch T,et al.The route to success-a performance comparison of diagnosis algorithms[A].Proceedings of the 23rd International Joint Conference on Artificial Intelligence[C].China:AAAI Press,2013.1039-1045.
[9] 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.
[10] Siddiqi S A,Huang J.Hierarchical diagnosis of multiple faults[A].Proceedings of the 20th International Joint Conference on Artificial Intelligence[C].India:Morgan Kaufmann Publisher,2007.581-586.
[11] Kirkland T,Mercer M R.A topological search algorithm for ATPG[A].Proceedings of the 24th ACM/IEEE Design Automation Conference[C].USA:ACM,1987.502-508.
[12] Metodi A,Stern R,Kalech M,et al.Compiling model-based diagnosis to boolean satisfaction[A].Proceedings of the 26th Conference on Artificial Intelligence[C].Canada:AAAI Press,2012.793-799.
[13] Metodi A,Stern R,Kalech M,et al.A novel sat-based approach to model based diagnosis[J].Journal of Artificial Intelligence Research,2014,51:377-411.
[14] Marques-Silva J,Janota M,Ignatiev A,et al.Efficient model based diagnosis with maximum satisfiability[A].Proceedings of the 24th International Joint Conference on Artificial Intelligence[C].Argentina:AAAI Press,2015.1966-1972.
[15] 周建华,欧阳丹彤,刘伯文,张立明.基于模型诊断中结合问题特征的新方法[J].计算机研究与发展,2017,54(3):502-213. Zhou Jian-hua,Ouyang Dan-tong,Liu Bo-wen,Zhang Li-ming.A new algorithm combining with the characteristic of the problem for model-based diagnosis[J].Computer Research and Development,2017,54(3):502-213.(in Chinese)
[16] Nieuwenhuis R,Oliveras A,Tinelli C.Solving SAT and SAT modulo theories:from an abstract davis——putnam——logemann-loveland procedure to DPLL (T)[J].Journal of the ACM (JACM),2006,53(6):937-977.
[17] Xiang-fu,Zhao,Zhang,et al.Deriving all minimal consistency-based diagnosis sets using SAT solvers[J].Progress in Natural Science:Materials International,2009,19(4):489-494.
[18] 赵相福,欧阳丹彤.使用SAT求解器产生所有极小冲突部件集[J].电子学报,2009,37(4):804-810. Zhao Xiang-fu,Ouyang Dan-tong.Deriving all minimal conflict sets using satisfiability algorithms[J].Acta Electronica Sinica,2009,37(4):804-810.(in Chinese)

结合问题特征的分组式诊断方法

Grouped Diagnosis Approach Using the Feature of Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	邓海刚, 王传旭, 李成伟, 林晓萌. 深度学习框架下群组行为识别算法综述[J]. 电子学报, 2022, 50(8): 2018-2036.
[2]	王玉龙, 吴迪, 胡涛. 一种同型空时分组码的识别算法[J]. 电子学报, 2022, 50(11): 2754-2764.
[3]	张聿远, 张立民, 闫文君. 基于深度多级残差网络的低信噪比下空频分组码识别方法[J]. 电子学报, 2022, 50(1): 79-88.
[4]	管永明, 王刚, 骆凯波, 吕梁, 吕晓雯, 史玉良. 基于极端不平衡学习的泛化低压异常箱表关系识别研究与应用[J]. 电子学报, 2021, 49(8): 1507-1514.
[5]	左小寒, 梁华国, 倪天明, 杨兆, 束月, 蒋翠云, 鲁迎春. 基于间隔分组的TSV聚簇故障冗余结构[J]. 电子学报, 2021, 49(4): 805-811.
[6]	欧庆于, 罗芳, 吴晓平, 杨鹏. 基于电压毛刺故障扰动的分组密码安全性度量方法研究[J]. 电子学报, 2021, 49(3): 417-423.
[7]	马宿东, 金晨辉, 关杰. 一类ARIA型扩散结构分支数的研究[J]. 电子学报, 2020, 48(3): 449-455.
[8]	李航, 任炯炯, 陈少真. 减轮LEA密码算法的积分攻击[J]. 电子学报, 2020, 48(1): 17-27.
[9]	王念平. 一类分组密码变换簇抵抗线性密码分析的安全性评估[J]. 电子学报, 2020, 48(1): 137-142.
[10]	王宏, 李建华, 赖成喆, 曲宁. 基于纠错码理论的群组认证[J]. 电子学报, 2019, 47(7): 1393-1400.
[11]	何嫱君, 赵相福, 欧阳丹彤, 张立明. 极小碰集求解算法的性能分析与比较[J]. 电子学报, 2019, 47(5): 1101-1110.
[12]	刘良桂, 孙辉, 贾会玲, 张宇. 面向高效加密云数据排序搜索的类别分组索引方法[J]. 电子学报, 2019, 47(2): 331-336.
[13]	任炯炯, 张仕伟, 李曼曼, 陈少真. 基于SAT的ARX不可能差分和零相关区分器的自动化搜索[J]. 电子学报, 2019, 47(12): 2524-2532.
[14]	熊兵, 左明科, 黎维, 王进. 面向软件定义核心网的OpenFlow分组转发优先制排队模型研究[J]. 电子学报, 2019, 47(10): 2040-2049.
[15]	杜怡然, 南龙梅, 戴紫彬, 李伟. 可重构分组密码逻辑阵列加权度量模型及高能效映射算法[J]. 电子学报, 2019, 47(1): 82-91.