Methods based on Boolean functions and linear programming are more practical for complex systems.

Two improved new methods for automated diagnosis of complex engineering systems involve the use of novel algorithms that are more efficient than prior algorithms used for the same purpose. Both the recently developed algorithms and the prior algorithms in question are instances of model-based diagnosis, which is based on exploring the logical inconsistency between an observation and a description of a system to be diagnosed.

As engineering systems grow more complex and increasingly autonomous in their functions, the need for automated diagnosis increases concomitantly. In model-based diagnosis, the function of each component and the interconnections among all the components of the system to be diagnosed (for example, see figure) are represented as a logical system, called the system description (SD). Hence, the expected behavior of the system is the set of logical consequences of the SD. Faulty components lead to inconsistency between the observed behaviors of the system and the SD. The task of finding the faulty components (diagnosis) reduces to finding the components, the abnormalities of which could explain all the inconsistencies. Of course, the meaningful solution should be a minimal set of faulty components (called a minimal diagnosis), because the trivial solution, in which all components are assumed to be faulty, always explains all inconsistencies. Although the prior algorithms in question implement powerful methods of diagnosis, they are not practical because they essentially require exhaustive searches among all possible combinations of faulty components and therefore entail the amounts of computation that grow exponentially with the number of components of the system.

For the purpose of establishing the basis of an algorithmic approach that entails more efficient computation, and, more specifically, translating the diagnosis problem from a logical problem to a computational problem, it was shown that the calculation of minimal diagnosis can be mapped as the solution of two well-known problems — the Boolean satisfiability and the integer-programming. The first new method is based on the connection between the diagnosis problem and the Boolean satisfiability problem. This connection makes it possible to use Boolean function theory to reduce the diagnosis problem to the problem of finding prime-implicants (which is one of the basic problems in the theory of Boolean functions). This, in turn, makes it possible to utilize powerful and efficient algorithms, recently developed 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^{log n}), where n is the number of components of the system.

The second new method is based on the mapping of the diagnosis problem onto the integer-programming problem. This mapping makes it possible to utilize the large and versatile body of computational techniques developed previously for linear integer programming optimization to solve the diagnosis problem in an approach more practical than that of the prior exhaustive search algorithms. Some of the integer programming techniques, modified to make them suitable for solving the diagnosis problem, can efficiently diagnose a system that contains as many as several thousand components.

This work was done by Amir Fijany, Anthony Barrett, Farrokh Vatan, and Ryan Mackey of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.

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
(818) 354-2240
E-mail: This e-mail address is being protected from spam bots, you need JavaScript enabled to view it

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

This Brief includes a Technical Support Package (TSP).

Fast Algorithms for Model-Based Diagnosis (reference NPO-30582) is currently available for download from the TSP library.

Login first to download.

Username

Password

Remember me


Lost Password? Register