On diagnosis and predictability of partially-observed discrete -event systems.
Stéphane Lafortune, Şahika Genç · Deep Blue (University of Michigan) · 2006
In this thesis problems of diagnosis and prediction of event sequences in dynamic systems modeled using discrete-event formalisms are studied. Monolithic and distributed on-line fault detection and isolation of modular dynamic systems modeled as sets of partially-observed place-bordered Petri nets are considered. The common places among the set of Petri nets modeling a system capture coupling of various system components. The transitions are labeled by events, some of which are unobservable, i.e., not directly recorded by the sensors attached to the system. The events whose occurrences must be diagnosed have unobservable transition labels. These events model faults or other significant changes in the system state. The existing theory of diagnosis of discrete-event systems is extended in the context of the above model. The modular structure of the system is exploited by a distributed algorithm for fault diagnosis. A Petri net diagnoser is associated to every Petri net and the diagnosers communicate in real-time during the diagnostic process when the token count of common places changes. A merge function is defined to combine the individual diagnoser states and recover the complete diagnoser state that would be obtained under a monolithic approach. Strategies that reduce the communication overhead are presented. The software implementation of the distributed algorithm is discussed. The problem of diagnosis of a pattern of events in a partially-observed discrete-event system is studied. Two different types of pattern diagnosability are defined in the context of formal languages: (i) S-type for patterns in the form of subsequences of sequences of events and (ii) T-type for patterns in the form of substrings of sequences of events. These two notions of pattern diagnosability generalize the notion of diagnosability of single events in prior works. Implementable necessary and sufficient conditions for both types of pattern diagnosability in systems modeled by regular languages are presented. Finally, the problem of predicting occurrences of a significant event in a discrete-event system is considered. The notion of predictability of event occurrences in a system is defined in the context of formal languages. The predictability of a language is a stronger condition than the diagnosability of the language. Implementable necessary and sufficient conditions for predictability of event occurrences in systems modeled by regular languages are presented. It is shown that predictability in systems modeled by regular languages can be tested in polynomial-time.