Model-based Monitoring and Diagnosis of Mixed Hardware-Software Systems
Tsoline Mikaelian & Brian C. Williams
Model-based diagnosis of devices has traditionally operated on hardware systems . For instance, given an observation sequence, the Livingstone  diagnostic engine estimates the state of hardware components based on hidden Markov models that describe each component's behavior in terms of nominal and faulty modes. At the other end of the spectrum, researchers have applied model-based diagnosis to software debugging . This work explores the middle ground between the two, in particular the monitoring and diagnosis of systems with combined hardware and software behavior.
Many complex systems today, such as spacecraft, robotic networks (Fig. 1), automobiles and medical devices consist of hardware components whose functionality is extended or controlled by embedded software. The embedded software in each of these systems interacts with the hardware components and influences their behavior. In order to correctly estimate the state of these devices, it is essential to consider their software-extended behavior. We introduce a monitoring and fault diagnosis capability based on software-extended bebavioral models, motivated by the need for robustness and safety of increasingly ambitious applications.
As an example of a complex system, consider vision-based navigation for an autonomous rover. The camera in the navigation system is an instance of a device that has software-extended behavior: the image processing software embedded within the camera module augments the functionality of the camera by processing each image and determining whether it is corrupt. A sensor measuring the camera voltage may be used for estimating the physical state of the camera. A hardware model of the camera describes its physical behavior in terms of inputs, outputs and available sensor measurements. A diagnosis engine that uses only hardware models will not be able to reason about a corrupt image. Consider, for instance, a scenario in which the camera sensor measures a zero voltage. Based solely on hardware models of the camera, the measurement sensor and the battery, the most likely diagnoses will include camera failure, low battery voltage and sensor failure. However, given a software-extended model of the camera that incorporates the behavior of the image processing software, the quality of the image may be used to correctly diagnose the navigation system. Given that the processed image is not corrupt, the most likely diagnosis, that the measurement sensor is broken, may be deduced (Fig. 2).
Fig. 1: MERS Group Rovers
Fig. 2: State trajectories representing the most likely diagnoses of the navigation system based on software-extended models
This scenario demonstrates that a diagnostic engine for systems with software-extended behavior must:
We introduce a novel monitoring and diagnostic system that operates on software-extended behavior models, to meet the above requirements. In contrast to previous work on model-based software debugging, the purpose of this work is to leverage information within the embedded software to refine the diagnoses of physical systems. Capturing the behavior of software is more complex than that of hardware, due to the hierarchical structure of a program and the use of complex constructs. We address this complexity by using probabilistic, hierarchical, constraint-based automata (PHCA)  which can compactly represent complex behaviors. Building upon this previous work, we introduce a PHCA-based monitoring and diagnostic engine that can handle delayed symptoms. Given a history of observations and commands within a receding N-Stage time horizon, we enumerate and track the most likely trajectories of system state that are consistent with the observations, commands and the PHCA models. Our approach consists of two phases: an offline compilation phase and an online solution phase, as shown in Fig. 3.
The following are highlights of each phase.
Online Trajectory Tracking:
We have implemented the above system in C++, and are in the process of evaluating it on representative scenarios from the aerospace and automotive domain. Our implementation uses the decomposition-based constraint optimization solver presented in . For the above scenario with N = 2, the COP has ~150 variables and ~100 constraints and is solved online in ~1 sec. Future work includes optimizing the COP formulation by minimizing the number of variables and constraints generated, investigating the optimal size of the diagnosis horizon and its relationship to the number of trajectories tracked.
This research is sponsored in part by NASA CETDP under contract NNA04CK91A and by the DARPA SRS program under contract FA8750-04-2-0243.
 de Kleer, J., and Williams, B.C. Diagnosing multiple faults. In Artificial Intelligence 32(1), pp. 97-130, 1987.
 Dressler, O., and Struss, P. The consistency-based approach to automated diagnosis of devices. In Proc. KR-96, pp. 267-311, 1996.
 Williams, B.C., and Nayak, P. A model-based approach to reactive self-configuring systems. In Proc. AAAI-96, pp. 971-978, 1996.
 Mayer, W., and Stumptner, M. Approximate modeling for debugging of program loops. In Proc. DX-04, 2004.
 Kurien, J., and Nayak, P. Back to the future for consistency-based trajectory tracking. In Proc. AAAI-00, 2000.
 Williams, B.C., Chung, S. and Gupta, V. Mode estimation of model-based programs: monitoring systems with complex behavior. In Proc. IJCAI-01, 2001.
 Schiex, T., Fargier, H., and Verfaillie, G. Valued constraint satisfaction problems: hard and easy problems. In Proc. IJCAI-95, 1995.
 Gottlob, G., Leone, N., and Scarcello, F. A comparison of structural CSP decomposition methods. Artificial Intelligence, 124(2), pp. 243-282, 2000.
 Sachenbacher, M., and Williams, B.C. Diagnosis as semiring-based constraint optimization. In Proc. ECAI-04, 2004.