Efficient Model-Based Diagnosis Engine

A system as large as several thousand components can be diagnosed efficiently.

An efficient diagnosis engine — a combination of mathematical models and algorithms — has been developed for identifying faulty components in a possibly complex engineering system. This model-based diagnosis engine embodies a twofold approach to reducing, relative to prior model-based diagnosis engines, the amount of computation needed to perform a thorough, accurate diagnosis. The first part of the approach involves a reconstruction of the general diagnostic engine to reduce the complexity of the mathematical-model calculations and of the software needed to perform them. The second part of the approach involves algorithms for computing a minimal diagnosis (the term “minimal diagnosis” is defined below).

A somewhat lengthy background discussion is prerequisite to a meaningful summary of the innovative aspects of the present efficient model-based diagnosis engine. In model-based diagnosis, the function of each component and the relationships among all the components of the engineering system to be diagnosed are represented as a logical system denoted the system description (SD). Hence, the expected normal behavior of the engineering system is the set of logical consequences of the SD. Faulty components lead to inconsistencies between the observed behaviors of the system and the SD (see figure). Diagnosis — the task of finding faulty components — is reduced to finding those components, the abnormalities of which could explain all the inconsistencies. The solution of the diagnosis problem should be a minimal diagnosis, which is a minimal set of faulty components. A minimal diagnosis stands in contradistinction to the trivial solution, in which all components are deemed to be faulty, and which, therefore, always explains all inconsistencies.

The general diagnosis engine (GDE) is widely used in the discipline of automated diagnosis. The GDE combines a model of each component of an engineering system with observations of the actual behavior of the component to detect discrepancies and diagnose root causes. The GDE uses an inference engine to compute the consequences of observations and uses an assumption- based truth maintenance system (ATMS) to manage the assumptions underlying each computation. One of the side effects of managing the assumptions is the detection of inconsistent sets of assumptions, which leads to conflict sets used in calculating minimal diagnoses. Unfortunately the GDE has two major limitations:

• The combination of the inference engine and ATMS must be represented by software that is so complex that the use of the GDE is too difficult and impractical for many complex engineering systems.
• The calculation of a minimal diagnosis is inherently a hard problem. Using typical prior algorithms, the conversion from conflict sets to a minimal diagnosis requires amounts of computation time and memory that increase exponentially with the number of components of the engineering system.

This concludes the background discussion.

In the present efficient model-based diagnosis engine, the first-mentioned limitation of the GDE is overcome by the reconstructed general diagnostic engine (RGDE). Like the GDE, the RGDE combines a model of each component of an engineering system (represented graphically as a network) with observations of the actual behavior of the component to detect discrepancies and diagnose root causes. Also like the GDE, the RGDE performs a causal simulation by taking variable observations and using rules to compute the values of other variables in the network.

Although assumptions underly the computations in the RGDE as in the GDE, the RGDE does not include an ATMS. Instead, taking advantage of the discovery that the ATMS and the inference engine have many similarities, the RGDE combines the ATMS with the inference engine to simplify the diagnosis-engine algorithm and the software that implements it. In this approach, the value of each variable is tagged with the set of assumptions that contribute to its computation. This set of tags comprises the collective union of the tags of values that feed into the computation with a tag representing the computation itself. A discrepancy arises when two incompatible values are assigned to the same variable. In general, whenever the RGDE computes two incompatible values for the same variable, the union of the two supporting assumption sets is incompatible; that is, it is a conflict set. Typically in the course of causal simulation, no discrepancies are found, but when failures occur, multiple incompatible assumption sets appear. This process continues to determine new incompatible sets until the causal simulation is completed.