ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (7): 1472-1480.doi: 10.7544/issn1000-1239.2020.20190338

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

结合故障逻辑关系的极小冲突集求解方法

欧阳丹彤1,2,3,高菡1,3,徐旖旎2,3,张立明1,2,3   

  1. 1(吉林大学软件学院 长春 130012);2(吉林大学计算机科学与技术学院 长春 130012);3(符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (ouyangdantong@163.com)
  • 出版日期: 2020-07-01
  • 基金资助: 
    国家自然科学基金项目(61872159,61672261,61502199)

Minimal Conflict Set Solving Method Combined with Fault Logic Relationship

Ouyang Dantong1,2,3, Gao Han1,3, Xu Yini2,3, Zhang Liming1,2,3   

  1. 1(College of Software Engineering, Jilin University, Changchun 130012);2(College of Computer Science and Technology, Jilin University, Changchun 130012);3(Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun 130012)
  • Online: 2020-07-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61872159, 61672261, 61502199).

摘要: 基于模型诊断是人工智能研究与发展中的重要方向之一,而求解极小冲突集(minimal conflict set, MCS)是模型诊断的关键步骤.MCS-SFFO(minimal conflict set-structural feature of fault output)方法以反向深度的方式遍历集合枚举树(set enumeration tree, SE-Tree),然后针对故障输出无关元件的组合进行剪枝.在MCS-SFFO方法的基础上,结合电路的故障逻辑关系提出求解极小冲突集的进一步剪枝方法MCS-FLR(minimal conflict set-fault logic relationship):首先提出单元件非冲突集定理,对单元件集合进行剪枝,避免了对无解空间中单元件节点的访问;其次,提出非极小冲突集定理,推证得出故障输出相关元件集的超集都是冲突集,故对有解空间中的非极小解进行剪枝.MCS-FLR方法在MCS-SFFO方法基础上减少了大量有解空间和部分无解空间调用SAT求解器的次数,节省了求解时间.实验结果表明:相比于MCS-SFFO方法,MCS-FLR方法求解效率有显著提高.

关键词: 基于模型诊断, 非极小冲突, 集合枚举树, 故障输出相关元件集, 有解剪枝

Abstract: Model-based diagnosis is an important research direction in the field of artificial intelligence, and solving the MCS (minimal conflict set) is an important step to solve the diagnosis problem. The MCS-SFFO(minimal conflict set-structural feature of fault output) method searches the set enumeration tree (SE-Tree) by a reverse depth-first way and then prunes the combination of fault output-independent components. Based on the MCS-SFFO method, a further pruning method for solving the minimal conflict set MCS-FLR(minimal conflict set-fault logic relationship) is proposed based on the fault logic relationship of the circuit. The non-conflict theorem of the single-component is proposed, which prunes the single component, to avoid the solution-free space. Secondly, the non-minimum conflict set theorem is proposed, that is, the supersets of the fault output related is all conflict sets, and the non-minimum conflict set can be further pruned in the solution space. Based on the MCS-SFFO method, the MCS-FLR method further prunes both the solution space as well as the solution-free space, which reduces the number of times the solution space and part of the solution-free space call SAT solver, saving the solution times. The experimental results show that compared with the MCS-SFFO method, the efficiency of the MCS-FLR method is significantly improved.

Key words: model-based diagnosis, non-minimum conflict, set enumeration tree (SE-Tree), fault output related components, pruning in solution space

中图分类号: