Time Decomposition for Diagnosis of Discrete Event Systems (Extended Abstract) / 4030
Xingyu Su

This extended abstract outlines my PhD research, which addresses the problem of on-line model-based diagnosis of Discrete Event Systems (DES). A DES model represents state dynamics in a discrete manner. Given a flow of observable events generated by a DES model, diagnosis aims at deciding whether a system is running normally or is experiencing faulty behaviors. The main challenge is to deal with the complexity of a diagnosis problem, which has to monitor an observation flow on the fly and generate a succession of the states that the system is possibly in, called belief state. Previous work has proposed exact diagnosis, which attempts to compute a belief state at any time consistent with the observation flow from the time when the system starts operating to the current time. The main drawback is the inability to follow the observation flow for a large system because the size of each belief state has been proved to be exponential in the number of system states. Furthermore, the temporal complexity to handle the exact belief states remains a problem. Because diagnosis of DES is a hard problem, the use of faster diagnostic algorithms that do not perform an exact diagnosis is often inevitable. However, those algorithms may not be as precise as an exact model-based diagnostic algorithm to diagnose a diagnosable system. This work has four contributions. First, it proposes to verify the precision of an imprecise diagnostic algorithm w.r.t. a diagnosable DES model by constructing a simulation, which is a finite state machine that represents how a diagnostic algorithm works for a DES model. Second, this work proposes window-based diagnostic algorithms, called Independent-Window Algorithms (IWAs). IWAs only diagnose on the very last events of the observation flow and forget about the past. Third, this work proposes a compromise between the two extreme strategies of exact diagnosis and IWAs by looking for the minimum piece of information to remember from the past so that a window-based algorithm ensures the same precision as using the exact diagnosis. This work proposes Time-Window Algorithms (TWAs), which are extensions to IWAs. TWAs carry over some information about the current system state from one time window to the next. Fourth, this work evaluates IWAs and TWAs through experiments and compares their performance with the exact diagnosis encoded by Binary Decision Diagrams. This work also examines the impact of the time window selections on the performance of IWAs and TWAs.

PDF