Research On Model-Based Diagnosis Based On Pseudo-Failure-Degree

After Baidu had created driverless car and Lee Sedol who is a grandmaster was defeated by Google’s AlphaGo at 1: 4 in "Man Machine War",artificial intelligence was known quickly by all the people.Model-based diagnosis is an important branch of artificial intelligence.Since this question was proposed,many scientists are attracted by it and more and more people take part in studying it,and their work is remarkable.Model diagnosis has been widely used in aerospace diagnosis,chip diagnosis,automotive fault diagnosis,power grids and other fields.The main idea of model-based diagnosis is to diagnose the system according to the internal structure and the corresponding behavior of the system.The fault components of the system are deduced from the model and the actual observation to explain the differences between the expected behavior and the actual observation behavior.In theory,model-based diagnosis has two research directions,which are based on the consistency diagnosis and the abduction diagnosis.The requirements of the two directions to treat the diagnosis system are different.If the system to be diagnosed does not meet the requirements,abduction diagnosis will abuse some solutions,but it is more efficient than the consistency-based diagnosis.And the consistency diagnosis can obtain all the solutions of the system,but it has a huge diagnostic space.So model-based diagnosis has complete algorithm and the incomplete algorithm,and HS-Tree,a famous algorithm proposed by Reiter,is an incomplete algorithm.,which caused by the unreasonable pruning method.The study found that model-based diagnosis can be transformed into SAT problem,while SAT problem has been proved to be NP problem.Therefore,the study of model-based diagnosis problems has a good inspiration for solving NP problems.In recent years,many scholars are enthusiastic about the international SAT algorithm competition and participate in many contestants.This makes the SAT solver develop rapidly.Therefore,it is a good direction to combine the SAT solver and enumeration-tree to solve the problem.By the in-depth study of model-based-diagnosis algorithm LLBRS-Tree,we put forward the concept of component static pseudo-failure-degree and dynamic pseudo-failure-degree according to the topology information of circuit elements,the difference between observed behavior and expected behavior of the system,and the characteristics of set enumeration tree.First,the static pseudo-failure-degrees of all components are calculated.And then the new enumeration tree can be generated by reordering the components from large to small with the static pseudo-failure-degree.When the new minimal diagnose is found,the dynamic pseudo-failure-degrees of the related components are updated and the new enumeration tree is dynamically created.A large number of redundant solutions can be deleted and the number of times to call SAT solver reduced greatly,so it is faster to find all the minimal diagnoses.Experimental results show that the presented DYN-Tree algorithm runs faster than LLBRS-Tree algorithm with the increasing of the number of components and the increasing of the minimal diagnoses length in the diagnosis system.