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

Minimal Conflict Set Solving Method Combined with Fault Logic Relationship

作　　者：欧阳丹彤[1,2,3] 高菡 徐旖旎 张立明[1,2,3] Ouyang Dantong;Gao Han;Xu Yini;Zhang Liming(College of Software Engineering,Jilin University,Changchun 130012;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)

机构地区：[1]吉林大学软件学院,长春130012 [2]吉林大学计算机科学与技术学院,长春130012 [3]符号计算与知识工程教育部重点实验室(吉林大学),长春130012

出　　处：《计算机研究与发展》2020年第7期1472-1480,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(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方法求解效率有显著提高.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.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]