Timely Diagnosis of Discrete-Event Systems

A major problem afflicting decision support systems based on automated diagnosis is a possibly large number of diagnoses explaining the observations, which may jeopardize the task of diagnosticians, owing to the cognitive overload raised by an overwhelming number of faulty scenarios to examine before undertaking effective recovery actions. This criticality is exacerbated when the recovery actions are expected to be performed automatically by an artificial agent in real-time, even in the order of milliseconds, like in an autonomous vehicle or in a defense system. To make diagnosis in the specific domain of discrete-event systems (DESs) viable in critical, real-time applications, a Timely Diagnosis Engine is presented, which is based on a parsimony principle: given a set of diagnoses implied by the observations, only minimal diagnoses are elicited as candidates, on the grounds that each minimal diagnosis is more likely than any non-minimal diagnosis that is a superset of it. Experimental results indicate that the search space of the diagnosis engine is reduced considerably, owing to the pruning of the trajectories of the DES that are not bound to generate minimal diagnoses, thereby resulting in a considerable reduction not only in the number of candidates but also in processing time.