Algorithm Improvement Of Hierarchical Model-based Diagnosis Based On Structural Abstraction

As we all know, from the traditional method of the Expert System diagnostic system is plagued with defects, such as the incomplete knowledge, the system's dependence on the knowledge, expert knowledge inconsistency, a lack of expert knowledge and so on. Model-based diagnosis which is the diagnosis of an Intelligent Reasoning Technology is to overcome such serious defects of the traditional expert system. Model-based diagnostic methods use only description of the internal structure of the system and external behavior of components without the need to conduct a large number of expert knowledge, diagnostic algorithm is universal and independent of the system model. If the model can be given in the process of product design and production, model-based diagnosis method will directly use the common algorithm for fault diagnosis to the system dependent on the external performance of the system. It is precisely because the model-based diagnosis has so many advantages and practical value, from the mid-1980s it attracts more and more researchers, until the 1990s it has become a very active branch of artificial intelligence research.From a theoretical point model-based diagnosis can be divided into two categories: First is consistency-based diagnosis and the other is abductive diagnosis. Consistency-based diagnosis deals only with the normal behavior model of the system to be diagnosed and diagnosis results must be consistent with system descriptions and observations. Abductive diagnosis deals with a number of behavioral models for every component and from diagnosis results observations can be deduced. However, as the diagnostic system to be more complex, an increasing number of system components huge, the search space of diagnostic reasoning is the growing rapidly. Thus, the traditional model-based diagnostic methods should be improved. In order to narrow the search space of diagnosis, and improve the diagnostic efficiency, some scholars turned to abstract and hierarchical approach. Hierarchical diagnosis is established based on the consistency-based diagnosis and abductive diagnosis. The basic idea of hierarchical diagnosis algorithm is that system model should be described in some levels. The level is higher; the granularity (such as components, variable values and so on) which describes the attributes of the system is larger. In a more abstract level system models the diagnosis task will be faced with relatively small search space. The diagnosis task of the detail level simply searches the candidates which are related to the diagnosis in abstract level. So the search space of the detail level has also been greatly reduced. Then diagnostic efficiency gets a relatively large increase.Mozetic studied the hierarchical diagnosis algorithm. They expressed a formal method for hierarchical system. The method maps the specific level system description to abstract level. Many specific level candidates that do not have to be verified are isolated in the abstract level. Hierarchical diagnosis process starts in the abstract level, with relatively simple description of this system. The abstract level contains only a few components or abstract qualitative behavior and candidates that are fewer are very easy to be verified. Then abstract level results in the diagnosis will be used to guide diagnosis process in the more specific level. In the detail level the diagnosis process only verifies the candidates corresponding to the abstract candidates that have been verified to be right. This reduces the search space of the detail level. At the same time Mozetic express consistency conditions and the introduction of proof: If the hierarchical models of the system meet this consistency conditions, then the detail level candidates which are corresponding to the abstract level candidates that have been verified to be wrong must also not be verified right. This condition ensures hierarchical diagnosis algorithm will not lose diagnosis in detail level. Dependent on hierarchical model description, narrowing the diagnostic search space and improving the efficiency of the diagnosis, completeness of the results of the diagnosis is ensured. Chittaro and Ranon also used Mozetic's diagnosis strategy with traditional consistency-based diagnostic methods to define hierarchical model description and introduced constraint condition which is similar with Mozetic's consistency conditions to ensure the completeness of hierarchical diagnosis.Mozetic's hierarchical diagnostic methods use abstraction to gain hierarchical system description. Moreover consistency conditions are satisfied to eliminate impossible candidates earlier. Nevertheless, the diagnosis process must continue with top-down manner until the concrete level. If the diagnosis process can also stop in the abstract level, just searching diagnosis result in the relatively high level of abstraction, without having to search diagnosis result in a relatively low level, efficiency of diagnosis will be further enhanced . This paper presents that if the system description of this paper can be achieved and the system prior abstracts the collection of sub-components system in which there is no internal observation as a super-component, then top-down hierarchical diagnosis process can stop at the level whose super-components do not contain an internal observation, and from the adjacent next level to the concrete level results of diagnosis could be get directly by refining diagnosis results in the front level. Thus, many searching process of the levels are needless and the efficiency of hierarchical diagnosis is improved. Only considering diagnose problems of abstract level is achieved without having to concern details of the matter. In previous diagnosis the hierarchical model is constructed by human, and it is needed to verify whether to meet certain conditions (such as consistency condition). In this paper, the abstraction mode is based on structure abstraction. In this paper, an approach of automatic abstraction to produce hierarchical model description is presented by limiting description mode. The main idea is that if the constraint functions of the adjacent subcomponents can generate a complex constraint function by combining themselves, then the normal behavior of super-component can be expressed on this complex constraint function. The abstraction of the observed values is the same as other structure abstraction methods. For the super-component with internal variables having observed value the observed value will be stripped in the abstract level. In this way, abstract automatically become a relatively easy matter. Followed, the paper also shows that the hierarchical model description from this automatic abstraction directly ensures the correctness and completeness of the diagnosis results. In the past, while manual hierarchical description is constructed, certain conditions should be satisfied (such as consistency condition). Further, the paper also presents a discussion by more detailed the calculation for how the scale of the sub-components system which are combined into a super-component to impact on diagnosis efficiency. It is showed that the scale is larger complexity of the diagnosis is higher providing some guidance for the abstraction mode. Finally, in view of the past hierarchical diagnosis algorithm using plain candidate generate-test algorithm in each level, it is presented in this paper to introduce testing conflict and computing hitting set into the hierarchical diagnosis to substitute candidates generate-test algorithm on some degree. The main idea is that the system uses each diagnostic result of abstraction level without considering the super-component to do constraint propagation and then results of the dissemination join into the sub-components system refined from the super-component as the observed values of the sub-components system, coupled with the sub-components system's internal observations. Then the method of conflict testing and hitting set computing is used to diagnose the sub-components system. Finally the diagnostic search results are used instead of the state of super-component of the diagnosis result just mentioned in the abstract level to get some certain candidates in the detailed level. This approach avoids the simple use of candidates'generation-test methods to test candidates in every level. It is helpful for improving the efficiency of the diagnosis on the condition that the sub-components system is relatively large-scale.