A document discusses a new algorithm for generating higher-order dependencies for diagnostic and sensor placement analysis when a system is described with a causal modeling framework. This innovation will be used in diagnostic and sensor optimization and analysis tools. Fault detection, diagnosis, and prognosis are essential tasks in the operation of autonomous spacecraft, instruments, and in-situ platforms. This algorithm will serve as a power tool for technologies that satisfy a key requirement of autonomous spacecraft, including science instruments and in-situ missions.
In the causal modeling, the system is modeled in terms of first-order cause-and-effect dependencies; i.e., how the fault propagates from a faulty component to its immediate neighbors. For diagnostic purpose, also global (or higher-order) dependencies are needed, which is the effect of a fault on non-neighbor components. The global dependencies should be inferred from the first-order dependencies. The method that finds these dependencies is called a reachability analysis algorithm. The result of this algorithm determines at each test point (or sensor position) which of the failure sources can be observed.
The standard reachability analysis algorithm uses a “token propagation” method. The complexity of this algorithm is proportional to the product EN, where E is the number of links (edges) of the graph of the system and N is the number of components. Here a new algorithm is introduced. The complexity of this algorithm is proportional to the product dN, where d is the length of the longest (directed) path in the graph of the system. To compare the performance of these two algorithms, first it is noted that always d ≤ E. But typically, d is of the order of log(E); thus the new algorithm, in general, outperforms the standard algorithm.
This work was done by Farrokh Vatan and Amir Fijany of Caltech for NASA’s Jet Propulsion Laboratory.
NPO-45797
This Brief includes a Technical Support Package (TSP).
An Efficient Reachability Analysis Algorithm
(reference NPO-45797) is currently available for download from the TSP library.
Don't have an account?
Overview
The document is a Technical Support Package from NASA's Jet Propulsion Laboratory, detailing an efficient reachability analysis algorithm aimed at improving fault diagnosis in complex systems. The primary objective of diagnosis technology is to identify the source of faults by observing their effects at various monitoring points or sensors. The document discusses the spectrum of modeling approaches for fault diagnosis, emphasizing that while detailed models yield more accurate diagnoses, they also require significant computational resources and extensive information, which may not always be available.
The proposed algorithm focuses on first-order cause-and-effect dependencies, which illustrate how faults propagate from one component to its immediate neighbors. To enhance diagnostic capabilities, the algorithm also considers global dependencies, which reflect the effects of faults on non-neighboring components. The method for determining these dependencies is known as reachability analysis, which traditionally employs a "token propagation" method with a complexity of O(E N), where E represents the number of links in the system's graph and N is the number of components.
In contrast, the new algorithm introduced in the document has a complexity of O(d N), where d is the length of the longest directed path in the graph. This new approach is generally more efficient, as it typically outperforms the standard algorithm due to the relationship between d and E, where d is often of the order of log(E).
The document also includes a description of the data structure used to represent the system, which consists of triples that define components, their inputs, and outputs. An example is provided to illustrate how a 12-component system can be represented using this structure.
Additionally, the document presents a dependency matrix (D-matrix) summarizing the cause-effect relationships among components and test points, where "1" indicates a relationship. This matrix serves as a crucial tool for understanding the interactions within the system and aids in the diagnostic process.
Overall, the document highlights the advancements in reachability analysis for fault diagnosis, showcasing the potential of the new algorithm to enhance the efficiency and effectiveness of diagnostic technologies in aerospace and other fields.
