Fault diagnosis of timed discrete event systems using Dioid Algebra

This paper deals with the fault diagnosis problem in a concurrent Timed Discrete Event System (TDES). In a TDES, concurrency leads to more complexity in the diagnoser and appears where, at a certain time, some user must choose among several resources. To cope with this problem, a new model-based diagnoser is proposed in this paper. This diagnoser uses Durational Graph (DG), a main subclass of timed automata for representing the time evolution of the TDES. The proposed diagnoser predicts all possible timed-event trajectories that may be generated by the DG. This prediction procedure is complicated for nondeterministic DG’s that are obtained for concurrent TDES’s. To solve this problem, a new Dioid Algebra, Union-Plus Algebra is introduced in this paper. Based on this Algebra, a reachability matrix is defined for a DG that plays an essential role in predicting the time behavior of TDES. By using reachability matrix, a prediction procedure is carried on via an effective equation set that is similar to linear system state equations in ordinary algebra. These results provide a suitable framework for designing an observer-based diagnoser that is illustrated by an example.