结合电路结构基于分块的诊断方法

doi:10.3969/j.issn.0372-2112.2018.07.005

电子学报 ›› 2018, Vol. 46 ›› Issue (7): 1571-1577.DOI: 10.3969/j.issn.0372-2112.2018.07.005

结合电路结构基于分块的诊断方法

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

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

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

A Block-Based Diagnostic Method Combining with the Circuit Structure

OUYANG Dan-tong^1,2, LIU Bo-wen^1,2, LIU Meng^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. Jilin University Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Changchun, Jilin 130012, China

Received:2016-12-29 Revised:2017-09-07 Online:2018-07-25 Published:2018-07-25
- Corresponding author:
- ZHANG Yong-gang
- Supported by:
- National Natural Science Foundation of China (No.61672261, No.61502199, No.61402196, No.61373052); National Natural Science Foundation of Zhejiang Province, China (No.LY16F020004)

摘要/Abstract

摘要： 基于模型的诊断问题在人工智能领域内一直备受关注，将诊断问题转换成SAT （Satisfiable）问题成为解决基于模型诊断问题的一个重要方法.基于目前高效诊断方法LLBRS-Tree （Last-Level Based on Reverse Search-Tree）的研究，本文提出电路分块诊断方法ACDIAG （Abstract Circuit Diagnosis）方法，对电路进行分块来缩减电路规模，利用LLBRS-Tree方法对分块后抽象电路求得极小块诊断解；提出诊断解拓展方法，结合分块后电路结构特征对每个极小块诊断解进行直接扩展得到极小诊断解，避免对抽象电路还原后才能得到所有解的问题.

关键词: 基于模型诊断, SAT问题, 枚举树, 抽象

Abstract: Model-based diagnosis problem has been attracting much attention in the field of artificial intelligence.It is an important technique for solving model-based diagnosis problem by converting diagnosis problem to SAT.Based on the research of LLBRS-Tree,this paper proposes an ACDIAG method.Firstly,the circuit blocking method is used to block the circuit via circuit structure so as to downscale circuit.Then,minimal block diagnoses are acquired on the abstract circuit after blocking via LLBRS-Tree.Secondly,diagnosis extending method is given to extend minimal block diagnoses to obtain other diagnoses directly via circuit structure.It avoids the drawback that extending diagnoses need to restore the abstract circuit.

Key words: model-based diagnosis, SAT problem, enumeration tree, abstract

中图分类号:

TP306

欧阳丹彤, 刘伯文, 刘梦, 等. 结合电路结构基于分块的诊断方法[J]. 电子学报, 2018, 46(7): 1571-1577.

OUYANG Dan-tong, LIU Bo-wen, LIU Meng, et al. A Block-Based Diagnostic Method Combining with the Circuit Structure[J]. Acta Electronica Sinica, 2018, 46(7): 1571-1577.

参考文献

[1] Console L,Dressler O.Model-based diagnosis in the real world:lessons learned and challenges remaining[A].Proceedings of the 16th International Joint Conference on Artificial Intelligence[C].Stockholm,Sweden,1999.1393-1400.
[2] DeKleer J.Local Methods for Localizing Faults in Electronic Circuits[D].Cambridge,MA,MIT AI Memo 394,1976.
[3] Raymond Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-95.
[4] Genesereth M R.The use of design descriptions in automated diagnosis[J].Artificial Intelligence,1984,24(1-3):411-436.
[5] Haenni R.A query driven anytime algorithm for argument-active and abduction[A].Proceedings of the 17th National Conference on Artificial Intelligence[C].Texas,2000.337-342.
[6] 赵相福,欧阳丹彤.使用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)
[7] 姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924. JIANG Yun-fei,LIN Li.The computation of hitting sets with boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924.(in Chinese)
[8] Jannach D,Schmitz T,Shchekotykhin K M.Parallelized hitting set computation for model-based diagnosis[A].Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence[C].Austin Texas,USA,2015,15:1503-1510.
[9] 刘娟,欧阳丹彤,王艺源,张立明.结合特征学习的粒子群求解极小碰集方法[J].电子学报,2015,43(5):841-845. LIU Juan,OUYANG Dan-tong,WANG Yi-yuan,ZHANG Li-ming.Computing minimal hitting sets with particle swarm optimization combined characteristics learning[J].Acta Electronica Sinica,2015,43(5):841-845.(in Chinese)
[10] Zhao X F,Ouyang D T.Deriving all minimal hitting sets based on join relation[J].IEEE Transactions on Systems Man Cybernetics-Systems,2015,45(7):1063-1076.
[11] Smith A,Veneris A,Ali MF,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.
[12] 严晓浪,郑飞君,葛海通,杨军.结合二叉判决图和布尔可满足性的等价性验证算法[J].电子学报,2004,32(8):1233-1235. YAN Xiao-lang,ZHENG Fei-jun,GE Hai-tong,Yang Jun.Combining binary decision diagrams and boolean satisfiability for equivalence checking[J].Acta Electronica Sinica,2004,32(8):1233-1235.(in Chinese)
[13] Cook S A.The complexity of theorem-proving procedures[A].Proceedings of the 3rd Annual ACM Symposium on Theory of Computing[C].New York,1971.151-158.
[14] Zhang J,Ma F,Zhang Z.Faulty interaction identification Via constraint solving and optimization[A].Theory and Applications of Satisfiability Testing-SAT 2012[M].Berlin Heidelberg:Springer,2012.186-199.
[15] Luo C,Cai S,Wu W,et al.Double configuration checking in stochastic local search for satisfiability[A].Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence[C].Québec,Canada,2014.2623-2629.
[16] Feldman A,Provan G,de Kleer J,et al.Solving model-based diagnosis problems with max-sat solvers and vice versa[A].Proceedings of the International Workshop on the Principles of Diagnosis[C].Artificial Intelligence,2010.185-192.
[17] Siddiqi S A,Huang J.Hierarchical diagnosis of multiple faults[A].Proceedings of the 20th International Joint Conference on Artificial Intelligence[C].Hyderabad:India,2007.581-586.
[18] ZHAO Xiangfu,ZHANG Liming,et al.Deriving all minimal consistency-based diagnosis sets using SAT solvers[J].Progress in Natural Science,2009,19(4):489-494.
[19] 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(1):377-411.
[20] 周建华,欧阳丹彤,刘伯文,张立明.基于模型诊断中结合问题特征的新方法[J].计算机研究与发展,2017,54(3):502-513. ZHOU Jianhua,OUYANG Dantong,LIU Bowen,ZHANG Liming.A new algorithm combining with the characteristic of the problem for model-based diagnosis[J].Journal of Computer Research and Development,2017,54(3):502-513.(in Chinese)
[21] Rymon R.Search through systematic set enumeration[A].Proceedings of the 3rd Intenational Conference on Principles of Knowledge Representation and Reasoning[C].San Franasco:Morgan Kaufmann,1992.539-550.
[22] Biere A.PicoSAT essentials[J].Journal on Satisfiability,Boolean Modeling and Computation,2008,4:75-97.

结合电路结构基于分块的诊断方法

A Block-Based Diagnostic Method Combining with the Circuit Structure

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王桐, 李必信, 王东东. 一种基于MAAT两步匹配的架构多层次变更检测方法[J]. 电子学报, 2023, 51(3): 694-700.
[2]	赵相福, 黄森, 童向荣, 欧阳丹彤, 张立明, 章星林. IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J]. 电子学报, 2022, 50(11): 2722-2729.
[3]	王舜, 杜晔, 韩臻. 基于模块化Abstract-Refine算法框架的软件模型检测方法[J]. 电子学报, 2020, 48(5): 997-1002.
[4]	刘梦, 欧阳丹彤, 刘伯文, 张立明, 张永刚. 结合问题特征的分组式诊断方法[J]. 电子学报, 2018, 46(3): 589-594.
[5]	欧阳丹彤, 刘伯文, 周建华, 张立明. 结合问题特征利用SE-Tree反向深度求解冲突集的方法[J]. 电子学报, 2017, 45(5): 1175-1181.
[6]	马彬, 包小敏, 谢显中. 认知无线网络中频谱切换算法研究综述[J]. 电子学报, 2016, 44(6): 1496-1503.
[7]	徐勇, 毋国庆, 袁梦霆. 结合Craig插值分析的软件错误诊断方法[J]. 电子学报, 2016, 44(10): 2514-2521.
[8]	刘志锋, 孙博, 周从华. 概率实时时态认知逻辑模型检测中抽象技术的研究[J]. 电子学报, 2013, 41(7): 1343-1351.
[9]	周从华, 孙博, 刘志锋, 葛云. 概率时态认知逻辑模型检测中三值抽象技术的研究[J]. 电子学报, 2012, 40(10): 2052-2061.
[10]	王雅文;宫云战;肖庆;杨朝红. 基于抽象解释的变量值范围分析及应用[J]. 电子学报, 2011, 39(2): 296-303.
[11]	王皓, 高阳, 陈兴国. 强化学习中的迁移:方法和进展[J]. 电子学报, 2008, 36(S1): 39-43.
[12]	吕毅;王源;李晓林. 服务网格的用户3A使用模式[J]. 电子学报, 2007, 35(2): 292-298.
[13]	张爱波, 陆月明, 纪越峰. 基于非对称有向网络的拓扑抽象算法研究[J]. 电子学报, 2006, 34(1): 180-184.
[14]	刘晖, 李明禄. 基于抽象状态机的网格系统设计和分析[J]. 电子学报, 2003, 31(S1): 2096-2100.
[15]	董育宁. 一种高效执行并行图像旋转的新方法[J]. 电子学报, 2001, 29(12): 1671-1675.