Research On Some Problems In Consistency-Based Diagnosis

Model-based diagnosis is a new type of intelligent reasoning technology, overcoming traditional fault-diagnosis methods'shortcomings. And model-based diagnosis is one of the active branches of Artificial Intelligence, and more and more widely applied. In addition to circuit diagnosis and medical diagnosis, nowadays, MBD has been applied to more practical aspects, such as fault detection and location in VHDL, diagnosis of asynchronization 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 diagnosis has strong device-independency. In model-based diagnosis, domains and system models are apart, so that it can be used to diagnosis another system, with the corresponding system model be replaced only. Struss called model-based diagnosis as an important challenge and verify for Artificial Intelligence.Generally, there are several steps towards to the final diagnosis results: building system models, conflict recognition, candidate generation and diagnosis authentication.It is a very important step of building a fittest model, according to corresponding domain knowledge, which should be able to express the relationship of the components in a system, and be simulated and forecasted when the real system is running, in order to infer and diagnosis. Reiter gave a formal description of model-based diagnosis in 1-order logic. Moreover, some scholars made use of qualitative equation to build system models.Conflict recognition, aiming at generating all minimal conflict sets (MCSs) by comparing the real observation and the prediction of the system models, is also an important step towards to final diagnosis results. And it is an NP-complete problem too. J. de Kleer firstly introduced the important concept of a conflict set, which we have appropriated for model-based diagnostic algorithms. Afterwards, he proposed some conflict recognition strategies and a widely used inference engine ATMS. Methods of using theorem prover (TP), such as DART, etc., can also be used for conflict recognition. In addition, several researchers such as Luan Shangmin, have studied the problem in China. And we suppose that the inference engine has been given, just like ATMS, TP, etc. As it is an NP-hard problem, conflict set recognition must be avoided as possible. Then how to derive all MCSs? Hou proposed a method named CS-Tree. However, the results derived from 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 many duplicate redundant nodes in CS-Trees. Han improved Hou's method, proposed a method of an inverse CS-Tree and a method of a CS-Tree with Mark Set, both of which do not need redundant tests. However, there are many backtracks by an inverse CS-Tree, and it is more complex as Mark Set is introduced by a CS-Tree with Mark Set. In order to overcome the shortcomings, a new method for deriving all minimal conflict sets based ATMS is proposed in this paper. All minimal conflict sets can be derived with every component model calculated at most once, thus ATMS is avoided to be called more frequently, and the efficiency is improved as well. A concept of minimal dependence set is put forward, as a result of which, all minimal conflict sets based ATMS can be sorted by two classes. Then, the complexity is analyzed. Finally, related methods for deriving all conflict sets are compared with it. The program is easily implemented too.Candidate generation, which is a procedure of generating all minimal hitting sets (MHSs), is proved as an NP-complete problem. Many researchers have studied the problem. However, some solutions may be lost by pruning in some methods, or a tree or a graph needs to be constructed, and the corresponding data structure and algorithm are quite complex, or computing by recursion, which is rather inefficient in some methods, etc. In order to overcome the shortcomings mentioned above, we propose the concept of cover weight about the set, then a new method of computing the minimal hitting sets based on cover weight is proposed, and reduces the complexity of it correspondingly. Constraint checks are made before the computation, so that the set which can not be a hitting set is not to calculate. The computing procedure is formalized by combining SE-Tree (set enumeration tree) to produce all the resolutions gradually. As the closed nodes are added into the SE-Tree, the non-minimal hitting sets can never be produced, and the true resolutions can not be missed by pruning either. Results show that the corresponding algorithm is easily implemented, and the efficiency is highly improved.In order to improve the efficiency of generating diagnoses, a novel method of using causal relation in model-based diagnosis is proposed for computing all minimal diagnoses. Since this approach is fundamentally different from the classical model-based diagnosis methods, it can directly compute all the minimal diagnoses, without computing all the conflict sets and therefore the hitting sets of the collection of the corresponding conflict sets like the classical methods. And then the combinatorial explosion caused by calling ATMS, known as an NP-complete problem, can be avoided as well. The theory of composing minimal diagnosis and the theory of the number of elements in a minimal diagnosis are put forward, as a result of which, the non-minimal diagnoses can never be produced, and the true resolutions can not be missed. The program is easy to be implemented, and the diagnosis efficiency is highly improved by this method to satisfy real-time requirement, even for a complex system.