Diagnosability Analysis and Sensor Selection in Discrete-Event Systems with Permanent Failures

In this paper, the problems of failure diagnosability and sensor selection for failure detection and isolation in discrete-event systems are studied. The system could operate in normal condition, or in a set of faulty conditions each corresponding to a combination of failure modes of the system. A polynomial algorithm is proposed that verifies diagnosability by examining the distinguishability of two conditions at a time. Furthermore, a polynomial procedure is presented that first finds minimal sensor sets for distinguishing one condition from another (minimal distinguishers), and then combines these sensor sets to obtain a minimal sensor set for failure detection and isolation. It is shown that taking advantage of the structure of the system, as done in the algorithms proposed in this paper, reduces the time and space complexity of testing diagnosability and sensor selection. A benefit of using minimal distinguishers is that their computation (thus, the computations for sensor selection) may be speeded up using heuristics and expert knowledge.