Active Prediction in Discrete-event Systems

Abstract

This paper investigates the problem of prediction of failures that may lead to violations of critical safety requirements if they are not dealt with in a timely manner. The main contributions are as follows. First, the new notion of active predictability of discrete-event systems (DESs) is introduced and formalized to capture the feature that the occurrences of failure events can not only be predicted based on observed sequences of events, but also be prevented from occurring by properly controlling system behavior. The control actions are posed and addressed in the framework of supervisory control theory, which could be required to prevent failure events from developing into safety hazards. It is indicate through comparison that active predictability is stronger than the predictability proposed by Genc and Lafortune. Second, in order to achieve the performance of active prediction, a nondeterministic automaton called verifier is constructed and the necessary and sufficient condition for verifying the active predictability of DESs based on the verifier is presented. Third, an algorithm is developed to verify the active predictability, which can be applied to the control of robots. It is worth noting that both constructing the verifier and verifying the active predictability can be realized with polynomial complexity in the number of states and events of the system.