结合故障输出结构特征的极小冲突求解算法

Algorithm of Computing Minimal Conflict Sets Based on the Structural Feature of Fault Output

基于模型诊断(model-based diagnosis)是人工智能领域中的重要研究方向,而基于极小冲突求诊断是求解诊断问题的经典方法,因此求解极小冲突是诊断中的一个重要步骤.通过对电路模型特征的研究,结合CSRDSE极小冲突集求解算法,提出结合故障输出结构特征的极小冲突求解算法MCSSFFO:首先对CSRDSE算法的剪枝规则进行了改进,避免对集合枚举树SE-Tree中非冲突集叶节点对应子叶节点的访问;其次,提出故障输出无关元件集与故障输出相关元件集等相关概念,并根据系统描述和观测给出求解故障输出无关元件集的方法;最后,提出非冲突集定理,即故障输出无关元件集的子集不是冲突集,并根据非冲突集定理,给出极小冲突集求解算法MCS-SFFO.MCS-SFFO算法在基于CSRDSE算法求冲突集方法的基础上对无解空间进一步剪枝,减少了调用SAT求解器的次数.实验结果表明:与CSRDSE算法相比,MCS-SFFO算法求解效率明显提升.

Model-based diagnosis is an important research in the field of artificial intelligence,and the diagnosis based on minimal conflict is a classical method to solve the problem of diagnosis.Therefore computing minimal conflict is an important step in model-based diagnosis.After studying the characteristics of the circuit model,this paper proposes an algorithm of computing minimal conflict sets based on the structural feature of fault output(MCS-SFFO)based on the CSRDSE algorithm.Firstly,the pruning rule of CSRDSE algorithm is improved,and it avoids the access to child leaf nodes of leaf nodes which are not conflict sets.Secondly,the concepts of component set independent of fault output and related to fault output are presented,and the method of computing component set independent of fault output is provided according to the system description and observation.Finally,a theorem about non-conflict set is proposed,that is,the component set independent of fault output and its subset are not conflict sets.MCS-SFFO algorithm that computes minimal conflict set is presented according to the non-conflict set theorem.Compared with CSRDSE algorithm,MCS-SFFO algorithm further prunes the non-solution space and reduces the number of calls to the SAT solver.Experimental evidence indicates that MCS-SFFO algorithm has better computational efficiency than CSRDSE algorithm.