An improved method of model-based diagnosis of a complex engineering system is embodied in an algorithm that involves considerably less computation than do prior such algorithms. This method and algorithm are based largely on developments reported in several NASA Tech Briefs articles: “The Complexity of the Diagnosis Problem” (NPO-30315), Vol. 26, No. 4 (April 2002), page 20; “Fast Algorithms for Model-Based Diagnosis” (NPO-30582), Vol. 29, No. 3 (March 2005), page 69; “Two Methods of Efficient Solution of the Hitting-Set Problem” (NPO-30584), Vol. 29, No. 3 (March 2005), page 73; and “Efficient Model-Based Diagnosis Engine” (NPO-40544), on the following page.
Some background information from the cited articles is prerequisite to a meaningful summary of the innovative aspects of the present method and algorithm. 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. 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.
The calculation of a minimal diagnosis is inherently a hard problem, the solution of which requires amounts of computation time and memory that increase exponentially with the number of components of the engineering system. Among the developments to reduce the computational burden, as reported in the cited articles, is the mapping of the diagnosis problem onto the integer-programming (IP) problem. This mapping makes it possible to utilize a variety of algorithms developed previously for IP to solve the diagnosis problem. In the IP 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. This concludes the background information.
The point of departure for the development of the present improved method and algorithm is the discovery that the mapping of the diagnosis problem onto the IP problem makes it possible to calculate lower and upper bounds on the number of faulty components before solving the diagnosis problem. A solution window for the problem is introduced, based on these bounds.
One of the algorithms heretofore commonly used to solve the IP problem is known in the art as the branch-and-bound algorithm. In terms that are necessarily oversimplified for the sake of brevity, the traditional version of the branch-and-bound algorithm includes the following:
- Using non-integer and integer solutions of the corresponding linear-programming (LP) relaxation problem (see figure), in which the variables of the IP problem are no longer constrained to be integers, to define lower and upper bounds, respectively;
- Successively dividing (branching) the IP problem into subproblems on the basis of the bounds; and
- Eliminating any subproblem, the LP lower bound of which exceeds the upper bound of another subproblem. The branching, bounding, and elimination are repeated until all subproblems are eliminated or an integer solution is found.
The present algorithm is an alternative version of the branch-and-bound algorithm. In this algorithm, the amount of computation required for execution is reduced, relative to that of the traditional version, by exploiting the structure of the problem. The amount of computation is further reduced by using the solution window to effect a massive pruning of branches. Yet another reduction is effected by dynamically updating and narrowing the window to enable further pruning. In simulation tests on systems of 40 components, the present algorithm was found to solve the diagnosis problem at an average speed about 300 times faster than that of the traditional branch-and-bound algorithm.
This work was done by Amir Fijany and Farrokh Vatan of Caltech for NASA’s Jet Propulsion Laboratory.
The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-41456.
This Brief includes a Technical Support Package (TSP).
High-Performance Algorithm for Solving the Diagnosis Problem
(reference NPO-41456) is currently available for download from the TSP library.
Don't have an account?
Overview
The document discusses a high-performance algorithm developed by NASA's Jet Propulsion Laboratory (JPL) aimed at addressing the diagnosis problem in industrial engineering, specifically through model-based diagnosis techniques. Diagnosis is crucial for identifying faulty components in complex systems, where the behavior of each component and their interconnections are represented logically in a system description (SD). When discrepancies arise between the expected behavior (as per the SD) and the actual behavior, it indicates potential faults in the components.
The diagnosis process begins by identifying symptoms that highlight inconsistencies, leading to the formation of conflict sets—groups of components that could potentially be faulty. The goal is to find a minimal diagnosis set, which is the smallest group of components that can explain all observed inconsistencies. Traditional model-based diagnosis methods, particularly those relying on Reiter’s algorithm, face significant challenges due to their exponential time and memory requirements, making them impractical for many real-world applications.
To overcome these limitations, the document introduces a novel approach that relates the diagnosis problem to the Integer Programming Problem. This new method allows for the determination of lower and upper bounds on the size of the solution, facilitating a more efficient search for the minimal diagnosis set. The proposed branch-and-bound technique is designed to be faster than existing methods by exploiting the problem's structure and dynamically updating a solution window to prune unnecessary branches during the search process.
The results presented in the document demonstrate the effectiveness of the new algorithm, showing a substantial performance improvement over traditional methods. For instance, the new algorithm reportedly solves problems involving 40 components over 300 times faster than standard algorithms. This significant speedup enhances the practical applicability of model-based diagnosis techniques in various systems, making it a valuable advancement in the field of industrial engineering.
Overall, the document highlights the innovative contributions of JPL in developing a more efficient algorithm for diagnosing faults in complex systems, emphasizing its potential impact on both aerospace and broader technological applications.
