### Topics

### features

### Publications

### Issue Archive

# An Efficient Reachability Analysis Algorithm

- Thursday, 30 October 2008

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.

Please Login at the top of the page to download.

### White Papers

| ||||||