Hierarchical Diagnosis For Static System Based On Structural Abstraction

Model-based diagnosis is a type of intelligent reasoning technology, overcoming the shortcoming of traditional fault-diagnosis methods. It is one of the active branches of Artificial Intelligence, and is applied widely. Nowadays, model-based diagnosis has been applied to more practical aspects. Nevertheless, one of the main issues is its high computational complexity in real-world application which limit the applicability of model-based diagnosis. The main reason for the complexity is the overwhelming number of solutions that have to be considered. And the number of solutions is exponential in the number of components of the system to be diagnosed. Especially, computational complexity of multi-fault diagnosis system is one of the issues to be resolved.Abstraction is a powerful strategy widely used to cope with complex problems by humans. A hierarchical approach is one of the most typical forms for abstraction: reasoning is started at abstract levels, where the problem is usually very simple, and where solutions can be determined with less effort. The abstract solution is then used at more detailed levels in order to constrain the search for detailed solutions.In this paper, we build on seminal work on hierarchical diagnosis for static system based on structural abstraction. In general, two basic processes are included: hierarchical abstraction and refining diagnosis. These two processes have been improved and added new functional modules in order to perfect diagnostic capabilities and improve efficiency.HD is hierarchical model-based diagnostic algorithm, which directly applies Mozetic's approach to multi-level hierarchies of structural abstraction. The formation of HD is divided into two separate procedures. The first one (Abstract-Observation) associates the available observation to the proper abstract levels of the hierarchical representation. Then, the second one (Top-Down-Diagnosis) performs the diagnosis. By taking advantage of the smaller search space at the more abstract levels, HD is able to outperform diagnostic reasoning applied only to the most detailed level in many cases.From the theoretical point of view, the speed up that can be achieved in the ideal case is exponential. But the limit to the previous hierarchical diagnosis methods is the fact that often a single, fixed hierarchical representation is employed. The same hierarchical representation can improve the performance of diagnosis in some cases, but also lead to a performance which is identical to non-hierarchical diagnosis in other cases. On the other hand, only a few of the given observations are available at those abstract levels where diagnosis can be performed. In this case, diagnosing those levels could be scarcely effective in reducing the candidate space, or even be counterproductive, resulting in a loss of efficiency.Algorithm EX is proposed by Chittaro and Ranon as an extension of HD that tackle the problems highlighted in the last paragraph. EX dynamically determines a multi-level hierarchical representation suited to diagnose the specific situation described by the current observations, which not only overcomes the limit of a single, fixed hierarchical representation, also improves the efficiency of diagnosis. EX adds two extensions are called Rearrange and Bottom-up on the basis of algorithm HD. Both extensions exploit an additional data structure, called structural tree, and use some strategies to improve the diagnostic efficiency. The characteristics of algorithm EX are the following: (1) EX dynamically determines a multi-level hierarchical representation suited to diagnose according to available observations of the current level. (2) EX can avoid the situations that the performance is identical to non-hierarchical diagnosis. (3) EX keeps the useful information of observations that is only available at more detailed level during the abstraction process and is used to eliminate impossible diagnosis.Algorithm IM is proposed by us in order to further improve the diagnostic efficiency on the basis of algorithm EX, which not only possesses the characteristics of EX, also can diagnose faulty system more efficiently than EX. The formation of IM is divided into three procedures: Abstraction, Bottom-up and Refinement. The key point of the procedure Abstraction is that two abstract processes are achieved simultaneously when a new abstract level is derived: one is a fixed abstract process according to the given hierarchical representation; the other is an automatic process according to the abstract conditions. The procedure Bottom-up is used to keep the diagnostic information during the abstract process which is identical with the procedure Bottom-up of algorithm EX. And the last procedure Refinement is performed to refine the abstract diagnosis.Comparing with the algorithm EX, the advantage of IM is summarized by us as follow: (1) Additional levels are minimized and the number of diagnosis problems is reduced on condition that the equal candidate space of the most abstract level. (2) The final diagnosis can be derived by the refined process at level l ( l >0 ) without detailing each abstract level until the original level in any case.The experimental activity are carried out by us to evaluate the three algorithms (HD, EX and IM). We implement a simple hydraulic system to compare the diagnostic efficiency from the views of the numbers of candidate and the time spent on the diagnosis. Finally, experimental results show that the efficiency of IM is better than the other algorithms for model-based hierarchical diagnosis.The three hierarchical model-based diagnosis algorithms for static system based on structural abstraction are described previously, which have the same inputs: the given hierarchical representation of diagnosed system and the available observations of the most detailed level. These algorithms improve the diagnostic efficiency at different degrees and resolve the problem of computational complexity. At last, an algorithm about hierarchical diagnosis for static system based on automatic structural abstraction is proposed by us, called BuildZone. The main characteristics of BuildZone are following: there is no need to give the hierarchical representation as inputs of BuildZone. The aggregate processes of components and hierarchical abstraction can be obtained dynamically from the structural connections between components, which are implemented only according to the current observations.The data structure of BuildZone is adjacent list. The key idea of BuildZone is that the whole system is divided into some zones; each zone has a controller component which must be passed by the outputs of the components or sub-zone within a zone. By the means of division, some components which are irrelative with observation can be deleted easily when diagnosis happened at the abstract level. So the process of diagnosis is further simplified.Hierarchical diagnostic algorithm BuildZone is divided into three procedures. The first procedure Build-Zone: the whole system is automatically partitioned into some zones on the condition that the given observations aren't lost. The second procedure Abdiagnosis: the components or zones which are irrelative with the given observations are deleted from the system; and then diagnostic process is carried out to obtain the abstract minimal diagnostic results. The last procedure RefineAbDiag refines the abstract minimal diagnostic results: only the zones with faulty component are considered in the process of refinement, which is refined repeatedly until all of the faulty components belong to the initial set of components.Finally, some advantages of BuildZone are summarized by us according to the analysis of algorithm and experiment. (1) There is no need to give the hierarchical representation as inputs of BuildZone, and the process of abstraction can be obtained dynamically only according to the current observations. (2) BuildZone can be used to diagnose the system with multi-faulty behavioral mode. (3) The process of keeping the observable information can be ignored on the reason that there are not any observation would be lost at the process of abstraction. (4) Some components or zones that are independent with observation can be deleted easily from the whole system, which is benefit for decreasing the number of candidates and improving the efficiency of diagnosis. And at the process of refinement, BuildZone refines the zones with fault and other zones can be ignored. On the other hand, BuildZone is inapplicable to circular system in which the components can be controlled by each other, and the behavior modes of the components may be more complicated after abstracting which refers to the area of behavioral abstraction and is our future work.