ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (4): 782-790.doi: 10.7544/issn1000-1239.2018.20170016

• 人工智能 • 上一篇    下一篇

基于伪故障度生成枚举树的极小诊断求解方法

欧阳丹彤,智华云,刘伯文,张立明,张永刚   

  1. (吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (ouyangdantong@163.com)
  • 出版日期: 2018-04-01
  • 基金资助: 
    国家自然科学基金项目(61672261,61502199,61402196,61272208);浙江省自然科学基金项目(LY16F020004)

A Method of Computing Minimal Diagnoses Based on Pseudo-Failure-Degree to Create New Enumeration Tree

Ouyang Dantong, Zhi Huayun, Liu Bowen, Zhang Liming, Zhang Yonggang   

  1. (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)
  • Online: 2018-04-01

摘要: 基于模型诊断(model-based diagnosis, MBD)是人工智能领域一个极富有挑战性的问题.近年来,SAT求解器发展十分迅速,且已被应用于求解基于模型诊断问题并取得了显著成果.在对基于模型诊断问题求解方法LLBRS-Tree深入研究的基础上,根据电路组件的拓扑结构信息、系统的观测行为和预期行为之间的差异以及集合枚举树的特点,首次提出了组件静态伪故障度和动态伪故障度的概念.计算所有组件的静态伪故障度,并根据静态伪故障度从大到小对组件重新排序,生成新的枚举树;并且在遍历到新的极小诊断解时,更新相关组件的动态伪故障度,动态建立新的枚举树,从而能较快地搜索到极小诊断解,删除大量冗余解,较大程度地减少SAT求解器的调用次数.实验结果表明:随着诊断系统中组件个数的增多以及极小诊断解长度的增加,提出的方法较LLBRS-Tree方法效率提升明显.

关键词: 基于模型诊断, 静态伪故障度, 动态伪故障度, 枚举树, 极小诊断解

Abstract: 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.

Key words: model-based diagnosis (MBD), static pseudo-failure-degree, dynamic pseudo-failure-degree, enumeration tree, minimal diagnose

中图分类号: