Diagnosing Complex Systems with Software-Extended Behavior using Constraint Optimization
Tsoline Mikaelian, Brian C. Williams, Martin Sachenbacher · 2005
Model-based diagnosis has traditionally operated on hardware systems. However, in most complex systems today, hardware is augmented with software functions that influence the system’s behavior. In this paper hardware models are extended to include the behavior of associated embedded software, resulting in more comprehensive diagnoses. Capturing the behavior of software is much more complex than that of hardware due to the potentially enormous state space of a program. This complexity is addressed by using probabilistic, hierarchical, constraint-based automata (PHCA) that allow the uniform and compact encoding of both hardware and software behavior. We introduce a novel approach that frames PHCA-based diagnosis as a soft constraint optimization problem over a finite time horizon. The problem is solved using efficient, decomposition-based optimization techniques. The solutions correspond to the most likely evolutions of the software-extended system. 1