NASA Logo, National Aeronautics and Space Administration

Overview

The main points of our approach are illustrated in the figure below. We use three different models - system specifications, Bayesian networks, and arithmetic circuits - during development and deployment. We explicitly represent EPS health using random variables in Bayesian networks and arithmetic circuits, thus supporting different diagnostic queries of interest. Finally, we take a component-oriented and causal approach, where the structure of our probabilistic models reflects the components and structure of an EPS, resulting in fast and exact computation of diagnostic queries.

pca approach v3 portable

Our approach uses three distinct models that play different roles in the development process: a system specification, a Bayesian network, and an arithmetic circuit. The system specification and the Bayesian network are processed off-line, while the arithmetic circuit is used to compute diagnoses in an efficient and predictable manner on-line.

We consider two challenges, regarding modeling and real-time performance, often encountered in real-world diagnostic applications. To meet the modeling challenge, we have introduced a high-level specification language which supports auto-generation of Bayesian networks (the Offline Generation process in the figure above). A key benefit of the specification language is that it is tailored to EPSs and is much more succinct than a Bayesian network (which again is much more succinct than an arithmetic circuit). To meet the real-time challenge, we compile Bayesian networks into arithmetic circuits (the Offline Compilation process). Arithmetic circuits typically have small footprints and are optimized for the real-time avionics systems found in spacecraft and aircraft. Using our approach, we present how Bayesian networks with over 400 nodes are auto-generated and then compiled into arithmetic circuits. Using real-world data from ADAPT as well as simulated data, we obtain average inference times smaller than one millisecond when computing diagnostic queries using arithmetic circuits that model our real-world electrical power system (the Online Inference process).

Offline Generation

The Offline Generation process depicted in the figure below supports the automatic generation of an EPS Bayesian network from a high-level EPS system specification. Here is a small example of a system specification, along with the Bayesian network generated from it.

pca approach v3 portable

An example showing how a Bayesian network (bottom) is auto-generated, off-line, from a high-level specification (top) of a small electrical power system containing a battery, a voltage sensor, a current sensor, a circuit breaker, a relay, a feedback mechanism, and a load.

As an example, the line Relay1 : relay : 0.0005 : Wire2 in the system specification expresses that we have a relay, Relay1, with failure probability 0.0005 connected to Wire2. The line Feedback1 : sensorTouch : 0.0005 : Relay1 shows that a feedback sensor, Feedback1, is attached to Relay1. These two lines result in five BN nodes (Health_Relay1, Command_Relay1, Closed_Relay1, Health_Feedback1, and Sensor_Feedback1) being auto-generated as shown in the upper right corner of the figure above. We will explore these five nodes in more detail shortly.

Our specification language is quite general and supports an interesting range of EPSs beyond ADAPT. The algorithm that auto-generates a Bayesian network from a system specification works by merging small BNs representing different components into an overall BN, which is composed according to the EPS topology as it is reflected in the system specification. In addition to making the BN and AC technologies available to a much broader user community, this approach accommodates rapid changes in EPS topology as well as in individual EPS components.

Offline Compilation

A designer of diagnostic systems for aircraft and spacecraft must carefully align resource consumption with the resource bounds imposed by the computational platform of the vehicle. The compilation approach to probabilistic inference is attractive in such settings. We mention two compilation paradigms, namely compilation to clique trees and compilation to arithmetic circuits. The arithmetic circuit paradigm, which we have used to implement the Offline Compilation process, is based on the observation that a BN can be represented as a multi-variate polynomial (MVP) in which terms consist of probabilities from the BN's CPTs and indicators take into account evidence. Unfortunately, an MVP grows exponentially with the size of a BN, hence one typically uses more compact arithmetic circuits instead of MVPs as a target for BN compilation. An example is shown in the figure below. In many cases, sparse arithmetic circuits exist for BNs with 100s or 1000s of nodes. The arithmetic circuit's size depends on a BN's graphical and local structure: if BN has local structure, the arithmetic circuit may be small despite large treewidth. A range of probabilistic queries can be computed using arithmetic circuits.

pca approach v3 portable

An example showing how an arithmetic circuit is auto-generated, off-line, from a Bayesian network representing a relay and its feedback mechanism, both part of a small electrical power system.

Online Inference

For NASA, decision support for manned missions and autonomous action for unmanned missions are both of great interest. The avionics of both manned and unmanned vehicles often utilize a hard real-time operating system (RTOS). These RTOSs are typically based on priority-based preemptive scheduling, where higher-priority tasks preempt lower-priority tasks. Each periodic RTOS task has a priority, a period, a deadline, and a worst-case execution time (WCET).

An embedded diagnostic engine, which is part of a vehicle's avionics, should therefore be designed within the RTOS framework. For example, an RTOS task needs to declare a worst-case execution time (WCET). Unfortunately, BN inference problems are inherently computationally hard. In addition, many inference algorithms are associated with high expectations and/or variances in their execution times, and their WCETs are unknown. The real-time reasoning challenge is to develop real-time diagnostic systems, despite the computational hardness of diagnosis problems. We meet this challenge by offline compilation into an arithmetic circuit, which is then used to answer diagnostic queries in an Online Inference process.

First Gov logo
NASA Logo - nasa.gov