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