An Efficient Reachability Analysis Algorithm

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

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.

Please Login at the top of the page to download.


White Papers

3D Printing Materials: Choosing the Right Material
Sponsored by stratasys
The Sun’s Surface in Stunning Detail
Sponsored by mikrotron
IEC 61131-3 Now in Motion
Sponsored by Trio Motion
1000 Watts of Compact, Lightweight, High Reliability Power – CM1000S28 Design and Electrical Function
Sponsored by abbott
Adapt or Die: Making the Case for Resilient PLM
Sponsored by aras
Antenna Basics
Sponsored by rohde and schwarz a and d

White Papers Sponsored By: