Algorithms Of Computing Minimal Conflict Sets Based On Pruning Rule And Fault Output

Model-based diagnosis,as an emerging intelligent fault diagnosis technology,plays a vital role in the development of artificial intelligence.Today,model-based diagnosis is becoming more widely used.Model-based diagnosis is used for fault diagnosis in areas such as electronic circuits,medical problems,communication networks,and aerospace.The main idea of model-based diagnosis is to infer the expected output under normal conditions of the system to be diagnosed according to the logic of components,the connection relationship between the components,and the input of the system.If the expected output is different from the actual output,the system to be diagnosed has faulty components.Then determine which components are faulty to explain the difference between the expected behavior and the observed behavior using logical reasoning.The set of components that cause the fault of system is the diagnosis.The solution step of model-based diagnosis to first find all the minimal conflict sets of the diagnostic system,and then solve the minimal hit sets of the minimal conflict set clusters.The minimal hitting sets are diagnosis.Therefore,computing the minimal conflict set is an important step in the process of solving model-based diagnosis.Improving the efficiency of the minimal conflict resolution algorithm will greatly improve the efficiency of solving model-based diagnosis.As the SAT solver efficiency increases,transforming problem of computing minimal conflict sets into the SAT problem solving has gradually become one of the mainstream methods for computing minimal conflict sets.The CSRDSE algorithm is an efficient way to find minimal conflict sets using the SAT solver.The CSDRSE algorithm proposes three pruning rules according to the characteristics of the conflict set.While the SE-Tree is reversely depth-first traversed,the proper subsets of the sets that are not conflict and the proper supersets of the conflict set are pruned according to the pruning rules,thereby reducing the usage of the SAT solver.The efficiency of solving the minimal conflict sets also improves.In this paper,the CSRDSE2 algorithm is proposed,which is improving the pruning rules of the CSRDSE algorithm.It is proposed in the CSRDSE algorithm that when traversing SE-Tree,if a leaf node which is not a conflict set is encountered,it should jump to the next leaf node.The CSRDSE2 algorithm proposes that the sub leaf nodes of the leaf node which is not a conflict set are not conflict sets.Therefore,when accessing this leaf node,its sub leaf nodes should be skipped,and jump directly to the leftmost node of the subtree with the same layer brother node of this leaf node as the root node.The CSRDSE2 algorithm reduces the number of access nodes and also reduces the number of subset detections for non-conflicting clusters.Experimental evidence indicates that compared with CSRDSE,the efficiency of CSRDSE2 algorithm for solving minimal conflict sets is improved.Based on the CSRDSE2 algorithm,this paper proposes an algorithm of computing minimal conflict sets based on the structural feature of fault output—MCS-SFFO.The MCS-SFFO algorithm first proposes the concepts of component set independent of fault output and related to fault output,and gives the method of computing component set independent of fault output,according to the system description and observation.Secondly,a theorem about non-conflict set is proposed,that is,the component set independent of fault output and its subset are not conflict set.According to the non-conflict set theorem,the subset of component set independent of fault output is pruned while the SE-Tree is reversely depth-first traversed.Therefore the number of times the SAT solver is called is reduced.Experimental evidence indicates that MCS-SFFO algorithm has a better computational efficiency than CSRDSE algorithm.