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 nlog 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 email address is being protected from spambots. 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.
Don't have an account?
Overview
The document titled "Technical Support Package for Fast Algorithms for Model-Based Diagnosis" (NPO-30582) from NASA discusses advancements in model-based diagnosis systems, particularly in the context of aerospace applications. As the complexity of space missions increases, the need for efficient fault diagnosis becomes critical. The document outlines the challenges faced in diagnosing faults in complex systems and presents a structured approach to address these challenges.
Key highlights include the introduction of the Minimal Diagnosis Hypothesis, which is essential for establishing a framework for diagnosing faults in systems with multiple components. The document emphasizes that a reasonable system satisfying this hypothesis is deemed strongly reasonable, facilitating the identification of minimal diagnoses—essentially the smallest set of components that can explain a fault.
The diagnosis problem is formally defined, focusing on finding small minimal diagnoses or prime implicants of a monotone function. This is crucial for ensuring the reliability and functionality of systems, especially in high-stakes environments like space exploration. The document also discusses the inherent complexity of the diagnosis problem, noting that it is NP-complete, which indicates the computational challenges involved in finding solutions.
To overcome these limitations, the document proposes the development of Fault Protection Modes, which consist of Symptoms-to-Cause Rules. This approach leverages human expertise to analyze potential faults and their causes, although it is acknowledged that this method can be time-consuming and prone to errors due to the unpredictability of faults.
Additionally, the document explores the relationship between model-based diagnosis and Boolean functions, highlighting how these concepts can be translated into practical applications. It discusses the combinatorial problem of hitting sets and its relevance to the diagnosis problem, suggesting that improvements in algorithms can be achieved through this mapping.
The document concludes by proposing a new method for solving the hitting set problem, which in turn aids in addressing the diagnosis problem. This method involves formulating the problem as an optimization challenge, specifically through integer linear programming, which can provide bounds on the size of the minimal diagnosis.
Overall, the document serves as a comprehensive resource for understanding the complexities of model-based diagnosis in aerospace systems and presents innovative approaches to enhance fault diagnosis capabilities.
