A polynomial algorithm for diagnosability of fair discrete event systems
Pradeep Kumar Biswal, Santosh Biswas · Systems Science & Control Engineering · 2015
The discrete event system (DES) has been used for failure detection and diagnosis (FDD) of a wide range of systems. The major reason for resorting to the DES framework is the simplicity in modelling and the low complexity of the FDD algorithms. Pure DES models cannot directly capture systems with continuous dynamics. However, the DES paradigm surmounts the problem by partitioning the continuous state space and capturing each subspace as a discrete state. Conventional methods for FDD consist in constructing a diagnoser, the complexity of which is exponential in the number of system states. In the case of non-diagnosability, the diagnoser needs to be reconstructed after taking suitable measures such as increase in measurements, etc. The conventional schemes have two issues, namely, exponential complexity of diagnoser and erroneous diagnosability conclusions for fair systems. Several works address the first issue where checking diagnosability does not involve a diagnoser and has polynomial time complexity. Once a fault is diagnosable, a diagnoser is constructed for concurrent system monitoring. Regarding the second issue, the abstraction employed in DES modelling may obliterate the fairness property for systems having continuous dynamics, leading to erroneous inferences. Works addressing this issue have augmented fairness to the model and the diagnoser, and new diagnosability conditions have been proposed for fair systems. However, all the Fair DES diagnosability frameworks are based on diagnoser and hence have exponential complexity. In this paper, we purpose a new DES diagnosability framework that suffices for fair systems but at the same time has polynomial complexity.