Research On Model-based Diagnosis Problem Of Combinational Circuit

The model-based diagnosis(MBD)problem is one of the important research directions in the field of artificial intelligence.It can be traced back to the significant work of De Kleer,Williams and Reiter in 1987.So far,the MBD problem has involved a variety of different models,such as discrete event model,qualitative model,incomplete causal model,and hybrid model.And it also has been applied to many fields,such as aerospace industry,automobile manufacturing,telecommunications network,gas turbine condition monitoring,software verification,circuit diagnosis and troubleshooting.The consistency based MBD method on combinational circuit models the system in the form of logical formulas,aiming to efficiently obtain all diagnoses and high-quality health state.This paper mainly focuses on the single observation diagnosis method and its extended methods,i.e.multi-observation diagnosis method and healthy state method.This paper aims to improve solution efficiency and solution quality.The main contents are as follows:1)Satisfiability(SAT)based MBD method is one of direct diagnosis methods.Because of its solution characteristics,other structures are needed in the process of solving the MBD problem to generate candidate solution spaces.SAT solver is used to determine whether the candidate solution is a diagnosis.However,this type of method has the deficiency of consistency detection of redundant solutions in the candidate solution space.Thus,this paper proposes a SAT based grouped diagnosis(GD)approach for grouping the circuit components and pruning these redundant spaces to improve the efficiency of the algorithm.This method combines circuit characteristics and unit propagation rules to obtain fault outputs.Then it groups circuit components according to circuit logic and fault outputs.Combined with the characteristics of the diagnosis problem and the SAT solution process,the non-diagnostic theorem and the grouped diagnosis method are given.And the grouped circuit is used to accelerate the pruning of the redundancy in set enumeration tree.Thereby the efficiency of the diagnosis algorithm has been improved.The experimental results show that for the all minimal subset diagnoses,compared to the state-of-the-art SAT and set enumeration tree based diagnosis algorithm,the GD method is more efficient.2)Maximal satisfiability(MaxSAT)based MBD method is also one of direct diagnosis methods.It does not require additional structural assistance.Thus,abstracting the circuit system is another way to improve the efficiency of the algorithm,which can reduce the scale of the problem.The previous abstraction algorithms are mainly based on the hierarchical abstraction method.Hierarchical abstraction method obtains top-level diagnosis(TLD)on the abstract circuit,and then replaces the TLD via iterative enumeration to obtain all the minimal cardinality diagnoses.But the drawback of the method is that it is necessary to check the consistency of the expanded diagnosis one by one,which is very time consuming.Thus,this paper presents a zonal diagnosis(ZD)approach with MaxSAT.Combined with the circuit characteristics,a new abstract model is proposed,which divides the circuit into different zones,and uses the MaxSAT solver to obtain minimal cardinality abstraction diagnoses on the abstract circuit composed of these zones.A new propagation extension method is proposed by using the value propagation characteristics.It extends the minimal cardinality abstraction diagnoses to obtain all minimal cardinality diagnoses effectively.More important is that it can avoid checking consistency and thus improves solution efficiency.The experimental results show that,for all minimal cardinality diagnoses,the ZD algorithm uses shorter time than the state-of-the-art hierarchical abstraction algorithm with same diagnoses number limitation,and significantly improves the efficiency of the algorithm.3)The health state represents the quality of the diagnosis algorithm,which indicates the faulty possibility of all components of the system.And it has important applications in troubleshooting and other issues.The health state is calculated from a list of diagnoses and score on each diagnosis.And not all diagnoses need to participate in the calculation to obtain a health state of quality convergence.But the disadvantage is that the diagnosis in the list of diagnoses only explains one observation,and the accuracy of the diagnosis is low.Thus the quality of the health state is affected.Therefore,this paper designs an improved quality of health of the state(IHSD)method to solve this problem for obtaining a higher quality health state.Combining the characteristics of obtaining health state of quality convergence without all diagnoses,this method first gives a multiple observation MBD method suitable for health state computing.It uses MBD method with multiple observations to integrate the diagnoses,and obtains accurate diagnoses that simultaneously satisfies multiple observations.The difference degree is used to modify the scoring mechanism to score accurate diagnosis.The score is as close as possible to the real fault condition,thereby improving the quality of the health state.The experimental results show that the IHSD algorithm significantly improves the quality of the health state by setting the same convergence parameters,which compared with the state-of-the-art health state method.4)Compared with the single-observation MBD method,the multi-observation MBD method can jointly diagnose multiple observations to identify common fault locations.In addition,it has been successful in program fault localization.For consistency-based multi-observation MBD problem on combinational circuit,some scholars have given two complete methods,namely the diagnosis combination method and the hitting set dualization method.Considering the case of incremental observation,the diagnosis combination method is suitable.However,the non-minimum solutions still exist in the process of obtaining accurate diagnosis that satisfies multiple observations.It needs subset detection process to assist the algorithm,which is very time consuming.Therefore,this paper proposes an incremental MBD with multiple observations method(IMBDMO).The method firstly gives the minimal subset accurate diagnosis theorem and the diagnosis combination rules.It ensures the subset-minimal of the accurate diagnosis and avoiding the subset detection process.Thereby it improves the efficiency of the algorithm.Secondly,it realizes the incremental observation.The experimental results show that compared with the state-of-the-art diagnosis combination method,the IMBDMO algorithm significantly improves the efficiency of the algorithm and ensures the efficiency of the algorithm in the case of incremental observation.