Diagnosis of Discrete Event Systems Using Ordered Binary Decision Diagrams
János Sztipanovits, Amit Misra · 1998
Diagnostic methods for engineering systems are typically model-based: functional and/or fault models are used to diagnose the root cause of anomalies. Discrete models are abstractions of systems in a discretized input, output and state space. These models provide an accurate description for a broad category of systems (switching networks, digital systems, etc.) but can also be used for approximating the behavior of continuous or hybrid systems. Diagnosis tasks require the exploration of the discrete state space, which frequently leads to a combinatorial explosion of alternatives. This paper describes an approach, which transforms domain specific discrete failure propagation models or physical models into relational models, and performs diagnosis symbolically. The underlying theory is based on Ordered Binary Decision Diagram (OBDD) representations and related algorithms.