Escaping Diagnosability and Entering Uncertainty in Temporal Diagnosis of Discrete-Event Systems

Diagnosis is the task of explaining the abnormal behavior of a system based on a symptom. In a discrete-event system (DES), the symptom is a temporal sequence of observations. At the occurrence of each observation, the diagnosis engine has to output a set of candidate diagnoses, each candidate being a set of faults. This process requires deep (and costly) model-based reasoning, hence a variety of knowledge compilation techniques have been proposed to speed it up. A novel technique for DES diagnosis that exploits knowledge compilation is presented, which is sound and complete irrespective of the diagnosability of the DES. The DES model is compiled offline into a temporal dictionary, a deterministic finite automaton whose regular language equals the (possibly infinite) set of symptoms of the DES. When the DES is being monitored online, a temporal explanation is generated efficiently at the occurrence of each observation. The correctness of the diagnosis results is supported by abduction-based backward-pruning