Model-Based Monitoring and Diagnosis of Systems with Software-Extended Behavior

Abstract

Model-based diagnosis of devices has largely operated on hardware systems. However, in most complex systems today, such as aerospace vehicles, automobiles and medical devices, hardware is augmented with software functions that influence the system's behavior. As these sophisticated systems are required to perform increasingly ambitious tasks, there is a growing need to ensure their robustness and safety. Prior work introduced probabilistic, hierarchical, constraint automata (PHCA), to allow compact encoding of both hardware and software behavior. The contribution of this thesis is a capability for monitoring and diagnosing software-extended systems in the presence of delayed symptoms, based on the expressive PHCA modeling formalism. Hardware models are extended to include the behavior of associated embedded software, resulting in more comprehensive diagnoses. This work introduces a novel approach that frames diagnosis over a finite time horizon as a soft constraint optimization problem (COP), which is then decomposed into independent subproblems using tree decomposition techniques. There are two advantages to this approach. First, the approach enables finite-horizon diagnosis in the presence of delayed symptoms. Second, the soft COP formulation provides convenient expressivity for encoding the PHCA models and their execution semantics, and enables the use of decomposition-based, efficient optimal constraint solvers. The solutions to the COP correspond to the most likely state trajectories of the softwareextended system. These state trajectories are enumerated and tracked within the finite receding horizon, as observations and issued commands become available. The diagnostic capability has been implemented and demonstrated on several scenarios from the aerospace and robotic domains, including vision-based rover navigation, the global metrology subsystem of the MIT SPHERES satellites, and models of the NASA New Millennium Earth Observing One (EO-1) spacecraft.