Research On Key Algorithms In Model-Based Diagnosis

Model-based diagnosis is a new type of intelligent reasoning technology,overcoming traditional fault-diagnosis methods' shortcomings. Andmodel-based diagnosis is one of the active branches of ArtificialIntelligence, and more and more widely applied. In addition to circuitdiagnosis and medical diagnosis, nowadays, MBD has been applied to morepractical aspects, such as fault detection and location in VHDL, diagnosis ofasynchronization discrete systems, diagnosis of network communications,automotive systems diagnosis, monitoring of gas turbines, and so on.Traditional rule-based diagnosis mainly depends on experts' experiences.And it has strict domain-dependency too. However, model-based diagnosishas strong device-independency. In model-based diagnosis, domains andsystem models are apart, so that it can be used to diagnosis another system,with the corresponding system model be replaced only. Struss calledmodel-based diagnosis as an important challenge and verify for ArtificialIntelligence.Generally, there are several steps towards to the final diagnosis results:building system models, conflict recognition, candidate generation anddiagnosis authentication.It is a very important step of building a fittest model, according tocorresponding domain knowledge, which should be able to express therelationship of the components in a system, and be simulated and forecastedwhen the real system is running, in order to infer and diagnosis. Reiter gavea formal description of model-based diagnosis in 1-order logic. Moreover,some scholars made use of qualitative equation to build system models.Candidate generation, which is a procedure of generating all minimalhitting sets (MHSs), is proved as an NP-complete problem. Manyresearchers have studied the problem. However, some solutions may be lostby pruning in some methods, or a tree or a graph needs to be constructed,and the corresponding data structure and algorithm are quite complex, orcomputing by recursion, which is rather inefficient in some methods, etc. Inorder to overcome the shortcomings mentioned above, we propose a novelmethod of judging a hitting set by the number of conflict sets correspondingto components. Furthermore, the procedure is formalized by combiningSE-tree with closed nodes to generate all MHSs. The proposed methodHSSE-tree is easy to be understood and implemented. Comparing withother effective algorithms with completeness in some experimental tests,results show that the diagnosis efficiency is higher, particularly for single-and double-fault diagnosis. Furthermore, we gave a brief summary aboutnearly all the methods so far. And we have a simply discussion finally.Conflict recognition, aiming at generating all minimal conflict sets(MCSs) by comparing the real observation and the prediction of the systemmodels, is also an important step towards to final diagnosis results. And it isan NP-complete problem too. J. de Kleer firstly introduced the importantconcept of a conflict set, which we have appropriated for model-baseddiagnostic algorithms. Afterwards, he proposed some conflict recognitionstrategies and a widely used inference engine ATMS. Methods of usingtheorem prover (TP), such as DART, etc., can also be used for conflictrecognition. In addition, several researchers such as Luan Shangmin, havestudied the problem in China. And we suppose that the inference engine hasbeen given, just like ATMS, TP, etc. As it is an NP-hard problem, conflictset recognition must be avoided as possible. Then how to derive all MCSs?A.Hou proposed a method named CS-tree. However, the results derivedfrom A.Hou's method depend on the order of node generation in CS-trees.As a result, some MCSs would be lost by pruning. And there may be manyduplicate redundant nodes in CS-trees. B.Han improved A.Hou's method,proposed a method of an inverse CS-tree and a method of a CS-tree withMark Set, both of which do not need redundant tests. However, there aremany backtracks by an inverse CS-tree, and it is more complex as Mark Setis introduced by a CS-tree with Mark Set. In order to overcome theshortcomings, an SE-tree based method (CSSE-tree) for deriving all MCSsis proposed in this paper. In addition, an inverse SE-tree (ISE-tree) is putforward which can also be used as a universal irredundant subset searchalgorithm. Moreover, an ISE-tree based method (CSISE-tree) for derivingall MCSs is presented. Considering the similarity of generation of all MCSsand all MHSs, a uniform framework for deriving all MCSs and MHSs isdiscussed accordingly. Furthermore, all the correct methods can also beused computing both prime implicants and prime implicates. We haveimplemented all the four algorithms and compared the efficiencies of them, and thenanalysed the fittest situation for each of them.There may be many groups of candidate results after the step ofcandidate generation. In order to reduce the candidate results, it needs todifferentiate all the candidate ones by measurements to find the realdiagnosis results, and the procedure is called diagnosis authentication.However, there may be many observable components in a system generally,how to choose a good order of the measurements by the least cost in orderto discover the real diagnosis? So that it is related to an optimizationproblem. Many researchers have studied it, such as methods based onentropy, method based probability, etc. And we firstly gave some correctionof Inc-Diagnosis proposed by Ng applied to a real example. And then wepresented some improvement of the algorithm and its application on theexample, considering the order of the measurements. Finally, we have asimply discussion about methods of optimization of choosing the order ofmeasurements.