Diagnosis as Approximate Belief State Enumeration for Probabilistic Concurrent Constraint AutomataOliver B. Martin & Brian C. WilliamsThe 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. ChallengeUnfortunately, within the modelbased 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 [3], 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.4^{10} 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 WorkPrevious work in modelbased monitoring and fault diagnosis, including GDE/Sherlock [1,2], GDE+ [5], Livingstone [6,4], and Titan Mode Estimation [8]; have achieved reactivity, while maintaining reliability, by framing mode estimation as a bestfirst shortestpath problem, enumerating estimates in order of likelihood using a variant of the Viterbi algorithm. This approach is known as BestFirst 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.
InnovationThis research introduces a novel mode estimation technique, called BestFirst 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. Performance ResultsBoth BFTE and BFBSE efficiently enumerate the most likely states in bestfirst order by framing mode estimation as an Optimal Constraint Satisfaction Problem (OCSP) and solving it using Conflictdirected A* [7]. 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).
Future WorkAlthough 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. Research SupportThis research was funded in part by the Jet Propulsion Laboratory, through the JPL Director’s Research and Development Fund. References:[1] J. de Kleer and B. C. Williams. Diagnosing multiple faults. Artificial Intelligence, 32(1):97130, 1987. [2] J. de Kleer and B. C. Williams. Diagnosis with behavioral modes. In Proceedings of IJCAI89, pages 13241330, 1989. [3] M. Ingham. Timed Modelbased Programming: Executable Specifications for Robust MissionCritical Sequences. PhD thesis, MIT, Department of Aeronautics and Astronautics, Cambridge, MA, 2003. [4] J. Kurien and P. Nayak. Back to the future for consistencybased trajectory tracking. In Proceedings of AAAI00, pages 370377, 2000. [5] P. Struss and O. Dressler. "Physical Negation"  Integrating fault models into the General Diagnostic Engine. In Proceedings of IJCAI89, pages 13181323, 1989. [6] B. C. Williams and P. Nayak. A modelbased approach to reactive selfconfiguring systems. In Proceedings of AAAI96, volume 2, pages 971978, Portland, OR, August 48, 1996. [7] B. C. Williams and R. Ragno. Conflictdirected A* and its role in modelbased embedded systems. Accepted for publication in the Journal of Discrete Applied Math, 2005. [8] B. C. Williams, M. D. Ingham, S. H. Chung, and P. H. Elliott. Modelbased programming of intelligent embedded systems and robotic space explorers. In Proceedings of the IEEE, 91(1):212237, January 2003. 

