Research On Algorithms Of Minimal Conflict Set Based On Abnormal Probability And Position Mark

Model-based diagnosis is a hot research topic in the field of artificial intelligence,making up for many shortcomings of traditional diagnostic methods.The theoretical research results are abundant and widely used in actual production,which accelerates the development speed of artificial intelligence.It is usually solved in two steps: first,solve all the minimal conflict sets for a given circuit system;then,solve all the minimal hitting sets of all minimal conflict sets,that is,all the minimal diagnoses for a given circuit system.Satisfiability problem(SAT)is a classic NP problem,and its theoretical research and technical application are mature.Many problems can be translated into satisfiability problems.The SAT problem competition held regularly in the world has made the SAT solver develop rapidly.Therefore,it is a good research direction to convert the calculation of the minimal conflict sets problem into the SAT problem.The CSRDSE algorithm is an algorithm of computing minimal conflict sets in conjunction with the SAT problem.According to the characteristics of the enumeration tree structure and the inference of the conflict set,the true subset nodes of the non-conflict sets in the enumeration tree and the true superset nodes of the conflict sets are pruned,which reduces the number of access nodes and accelerates the solution of the problem.Based on the deep research of the CSRDSE algorithm and the analysis of the circuit structure,it is found that each component has different influence on the abnormal output,and the components associated with the abnormal output of the circuit system have greater influence on the abnormal output.And the combination between components that have greater impact on the abnormal output is more likely to be a conflict set.According to the above findings,a minimal conflict set solving algorithm(CSABP)based on abnormal probability is proposed.Firstly,the definition of abnormal probability is given,and the algorithm SolveABP for calculating the abnormal probability of components is given.Then,the enumeration tree is generated according to the order of abnormal probability of components,which can traverse nodes which are composed of the components that have greater influence on the abnormal output as soon as possible,so that the conflict set is found early,and the judgment of the superset node of the conflict set is reduced.Experimental results show that compared with the CSRDSE algorithm,the CSABP algorithm improves the efficiency.On the basis of the CSABP algorithm,combining the structural characteristics of the enumeration tree and the principle that the subset of the conflict set is more likely to be the minimal conflict set: moving the nodes where the conflict concentrating components are located along with theirs subtree to the left,and searching for these subtrees in advance is conducive to finding a minimal conflict set early.When judging the subsequent nodes,these nodes are compared with the found conflict sets.If it is a superset of a certain conflict set,it needn't be judged;otherwise,the solver is called to judge the conflict of the components set.Based on the above ideas,the concept of position mark is proposed to adjust the state of the enumeration tree.Finally,combining the abnormal probability with position mark methods,a minimal conflict set solving algorithm based on abnormal probability and position mark(CSABPPM)is proposed.The experimental results show that the CSABPPM algorithm reduces more redundant nodes and solves the problem of minimal conflict set better.