Diagnosis as Approximate Belief State Enumeration for Probabilistic Concurrent Constraint Automata
Oliver B. Martin & Brian C. Williams
The purpose of estimation is to determine the current state of the system. An estimator infers the current state by reasoning over a model of the system dynamics along with the commands that have been executed and the resulting sensory observations. In many embedded systems, this knowledge of the current state is then used by a controller to drive the system state towards a specific target or goal. The ability for a system to accurately and reliably deduce its current state can dictate whether it is able to achieve its objectives. This is particularly important for highly complex robotic space exploration systems that operate in uncertain environments. Furthermore, deep space communication delays and severely constrained onboard computing capabilities present tremendous challenges to traditional methods of estimation in support of robust autonomous spacecraft operations.
Unfortunately, within the model-based programming paradigm, complete online mode estimation for any realistic system is intractable due to the combinatorial nature of concurrently operating components. Even a simplified Mars Entry Decent and Landing (EDL) subsystem , similar to the one used for the MER rovers operating on Mars, has 10 components with an average of 4.4 modes per component. When modeled as a Probabilistic Concurrent Constraint Automata (PCCA), the complete belief state is 4.410 and already too large to fully enumerate online. Fortunately, the vast majority of the belief state is probabilistically sparse and maintaining only a few leading estimates can capture the true behavior of the system with a high level of confidence.
Previous work in model-based monitoring and fault diagnosis, including GDE/Sherlock [1,2], GDE+ , Livingstone [6,4], and Titan Mode Estimation ; have achieved reactivity, while maintaining reliability, by framing mode estimation as a best-first shortest-path problem, enumerating estimates in order of likelihood using a variant of the Viterbi algorithm. This approach is known as Best-First Trajectory Enumeration (BFTE), shown in Figure 1a, and works well when determining the "most likely explanation" to a sequence of observations. Unfortunately, approximating the current state by the most likely trajectory can significantly underestimate the true state probability and result in misdiagnosis. Figure 2 shows this dramatic loss in belief state probability density over time for the Mars EDL model, where the BFTE results are depicted with hexagon marks.
This research introduces a novel mode estimation technique, called Best-First Belief State Enumeration (BFBSE), that approximates the belief state by generating the set of most likely estimates and achieves greater accuracy by computing the estimate probabilities directly from the Hidden Markov Model (HMM) Belief State Update equations (illustrated in Figure 1b) instead of approximating them by their trajectory probability. This contribution significantly increases the accuracy of the estimator as seen by the square marks in Figure 2.
Both BFTE and BFBSE efficiently enumerate the most likely states in best-first order by framing mode estimation as an Optimal Constraint Satisfaction Problem (OCSP) and solving it using Conflict-directed A* . The computational difference between these two algorithms reside in the heuristic function, where BFTE enumerates states in terms of trajectory probability and BFBSE uses the HMM Belief State Update equations. Although BFBSE incurs additional arithmetic computations, the runtime (Figure 3) is relatively unaffected for moderate sized models and requires less memory (Figure 4) when tracking more than a couple states (k > 2).
Although BFBSE has been shown to increase estimator accuracy while using less memory and, under certain conditions, less computational time; further improvements to BFBSE should result from our current work to correctly update the prior state probabilities with a valid observation probability distribution. Efficient use of the observation probabilities in the OCSP objective function should also lead to better diagnostic discrimination, pruning lower probability states earlier in the search.
This research was funded in part by the Jet Propulsion Laboratory, through the JPL Director’s Research and Development Fund.
 B. C. Williams, M. D. Ingham, S. H. Chung, and P. H. Elliott. Model-based programming of intelligent embedded systems and robotic space explorers. In Proceedings of the IEEE, 91(1):212--237, January 2003.