Time Decomposition for Diagnosis of Discrete Event Systems

Abstract

Artificial intelligence diagnosis is a research topic of knowledge representation and reasoning. This work addresses the problem of on-line model-based diagnosis of Discrete Event Systems (DES). A DES model represents state dynamics in a discrete manner. This work concentrates on the models whose scales are finite, and thus uses finite state machines as the DES representation. 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 behaviours.

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 in the literature has proposed exact diagnosis, which means that a diagnostic algorithm attempts to compute a belief state at any time that is consistent with the observation flow from the time when the system starts operating to the current time. The main drawback of such a conservative strategy 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 Thesis has four contributions. First, Chapter 3 proposes the concept of simulation to verify the precision of an imprecise diagnostic algorithm w.r.t. a diagnosable DES model. A simulation is a finite state machine that represents how a diagnostic algorithm works for a particular DES model. Second, Chapter 4 proposes diagnosis using time decomposition, and studies 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. The precision of this approach is assessed by constructing a simulation. Third, Chapter 5 proposes a compromise between the two extreme strategies of exact diagnosis and IWAs. This work looks 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. Chapter 5 proposes Time-Window Algorithms (TWAs), which are extensions to IWAs. TWAs carry over some information about the current state of the system from one time window to the next. The precision is verified by constructing a simulation. Fourth, Chapter 6 evaluates IWAs and TWAs through experiments, and compares their performance with the exact diagnosis encoded by Binary Decision Diagrams (BDD). Chapter 6 also examines the impact of the time window selections on the performance of IWAs and TWAs.