摘要
基于模型诊断(model-based diagnosis,MBD)是人工智能领域一个极富有挑战性的问题.近年来,SAT求解器发展十分迅速,且已被应用于求解基于模型诊断问题并取得了显著成果.在对基于模型诊断问题求解方法 LLBRS-Tree深入研究的基础上,根据电路组件的拓扑结构信息、系统的观测行为和预期行为之间的差异以及集合枚举树的特点,首次提出了组件静态伪故障度和动态伪故障度的概念.计算所有组件的静态伪故障度,并根据静态伪故障度从大到小对组件重新排序,生成新的枚举树;并且在遍历到新的极小诊断解时,更新相关组件的动态伪故障度,动态建立新的枚举树,从而能较快地搜索到极小诊断解,删除大量冗余解,较大程度地减少SAT求解器的调用次数.实验结果表明:随着诊断系统中组件个数的增多以及极小诊断解长度的增加,提出的方法较LLBRS-Tree方法效率提升明显.
Model-based diagnosis is a challenging problem in the field of artificial intelligence.In recent years,the SAT solver has evolved rapidly,which has been applied to solving the problems of model-based diagnosis and achieved significant results.By the in-depth study of model-based-diagnosis algorithm LLBRS-Tree,we put forward the concept of component static pseudo-failure-degree and dynamic pseudo-failure-degree according to the topology information of circuit elements,the difference between observed behavior and expected behavior of the system,and the characteristics of set enumeration tree.First,the static pseudo-failure-degrees of all components are calculated.And then the new enumeration tree can be generated by reordering the components from large to small with the static pseudo-failure-degree.When the new minimal diagnose is found,the dynamic pseudo-failure-degrees of the related components are updated and the new enumeration tree is dynamically created.A large number of redundant solutions can be deleted and the number of times to call SAT solver is reduced greatly,so it is faster to find all the minimal diagnoses.Experimental results show that the presented DYN-Tree algorithm runs faster than LLBRS-Tree algorithm with the increasing of the number of components and the increasing of the minimal diagnoses length in the diagnosis system.
作者
欧阳丹彤
智华云
刘伯文
张立明
张永刚
Ouyang Dantong;Zhi Huayun;Liu Bowen;Zhang Liming;Zhang Yonggang(College of Computer Science and Technology,Jilin University,Changchun 130012;Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University),Ministry of Education,Changchun 130012)
出处
《计算机研究与发展》
EI
CSCD
北大核心
2018年第4期782-790,共9页
Journal of Computer Research and Development
基金
国家自然科学基金项目(61672261
61502199
61402196
61272208)
浙江省自然科学基金项目(LY16F020004)~~
关键词
基于模型诊断
静态伪故障度
动态伪故障度
枚举树
极小诊断解
model-based diagnosis(MBD)
static pseudo-failure-degree
dynamic pseudo-failure-degree
enumeration tree
minimal diagnose
