### 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.

The second-mentioned limitation of
the GDE is overcome by a combination
of two methods, embodied in
algorithms that, relative to prior algorithms
used for the same purpose,
require less computation to arrive at a
minimal diagnosis. These methods
and algorithms were described in
“Fast Algorithms for Model- Based
Diagnosis” (NPO-30582) and “Two
Methods of Efficient Solution of the
Hitting-Set Problem” (NPO-30584),
both published in *NASA Tech Briefs*,
Vol. 29, No. 3, March 2005, pages 69
and 74, respectively. To recapitulate:
One of the two improved methods is
based on mapping of the diagnosis
problem onto the Boolean satisfiability
problem. This mapping makes it
possible to utilize Boolean function
theory to reduce the diagnosis problem
to the prime-implicant problem
(one of the problems in the theory).
This, in turn, makes it possible to utilize
very efficient algorithms, developed
previously for the satisfiability
problem, to compute the minimal
diagnosis. The algorithm thus developed
to solve the diagnosis problem
requires an amount of computation
proportional to a superpolynomial
function of *n* (meaning that the computation
time is proportional to
*n ^{ln}(^{ n }*)), where

*n*is the number of components of the engineering system.

The other improved method is based on the mapping of the diagnosis problem onto the integer-programming problem. This mapping makes it possible to utilize a variety of algorithms developed previously for integer programming to solve the diagnosis problem. In the integer-programming approach, the diagnosis problem can be formulated as a linear integer optimization problem, which can be solved by use of well-developed integer-programming algorithms. Some of these algorithms, modified to make them suitable for solving the diagnosis problem, can efficiently diagnose a system that contains as many as several thousand components.

The development of this efficient model-based diagnosis engine has been accompanied by the derivation of a deep matrix analysis of the integer programming problem that makes it possible to extract bounds for the sizes of the solutions of the optimization problem, without solving the problem explicitly. This analysis could be helpful in the development of algorithms that would be much more efficient for solving specific problems.

*This work was done by Amir Fijany,
Farrokh Vatan, Anthony Barrett, Mark James,
Ryan Mackey, and Colin Williams of Caltech
for NASA’s Jet Propulsion Laboratory.*

*In accordance with Public Law 96-517,
the contractor has elected to retain title to this
invention. Inquiries concerning rights for its
commercial use should be addressed to:*

*Innovative Technology Assets Management
JPL
Mail Stop 202-233
4800 Oak Grove Drive
Pasadena, CA 91109-8099
E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.*

*Refer to NPO-40544, volume and number
of this *NASA Tech Briefs* issue, and the
page number.*

### This Brief includes a Technical Support Package (TSP).

** Efficient Model-Based Diagnosis Engine** (reference NPO-40544) is currently available for download from the TSP library.

Please Login at the top of the page to download.