A spectrum of symbolic on-line diagnosis approaches

Abstract

This paper deals with the monitoring and diagnosis of large discrete-event systems. The problem is to determine, online, all faults and states that explain the flow of observations. Model-based diagnosis approaches that first compile the diagnosis information off-line suffer from space explosion, and those that operate on-line without any prior compilation have poor time performance. Our contribution is a broader spectrum of approaches that suits applications with diverse time and space requirements. Approaches on this spectrum differ in the amount of reasoning and compilation performed off-line and therefore in the way they resolve the tradeoff between the space occupied by the compiled information and the time taken to produce a diagnosis. We tackle the space and time complexity of diagnosis by encoding all approaches in a symbolic framework based on binary decision diagrams. This allows for the compact representation of the compiled diagnosis information, and for its handling across many states at once rather than for each state individually. Our experiments demonstrate the diversity and scalability of our symbolic methods spectrum, as well as its superiority over the corresponding enumerative implementations.