A Method of Computing Minimal Diagnoses Based on Pseudo-Failure-Degree to Create New Enumeration Tree

Model-based diagnosis is a challenging problem in the field of artificial intelligence.In recent years, the SAT solver has evolved rapidly, which has been applied to solving the problems of model-based diagnosis and achieved significant results.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 is 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.