高级检索
    欧阳丹彤, 高菡, 徐旖旎, 张立明. 结合故障逻辑关系的极小冲突集求解方法[J]. 计算机研究与发展, 2020, 57(7): 1472-1480. DOI: 10.7544/issn1000-1239.2020.20190338
    引用本文: 欧阳丹彤, 高菡, 徐旖旎, 张立明. 结合故障逻辑关系的极小冲突集求解方法[J]. 计算机研究与发展, 2020, 57(7): 1472-1480. DOI: 10.7544/issn1000-1239.2020.20190338
    Ouyang Dantong, Gao Han, Xu Yini, Zhang Liming. Minimal Conflict Set Solving Method Combined with Fault Logic Relationship[J]. Journal of Computer Research and Development, 2020, 57(7): 1472-1480. DOI: 10.7544/issn1000-1239.2020.20190338
    Citation: Ouyang Dantong, Gao Han, Xu Yini, Zhang Liming. Minimal Conflict Set Solving Method Combined with Fault Logic Relationship[J]. Journal of Computer Research and Development, 2020, 57(7): 1472-1480. DOI: 10.7544/issn1000-1239.2020.20190338

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

    Minimal Conflict Set Solving Method Combined with Fault Logic Relationship

    • 摘要: 基于模型诊断是人工智能研究与发展中的重要方向之一,而求解极小冲突集(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.

       

    /

    返回文章
    返回