Bounds on the number of markings consistent with label observations in petri nets

Abstract

In this paper, we consider state estimation in discrete-event systems (DESs) modeled by labeled Petri nets and present upper bounds on the number of system states (or markings) that are consistent with an observed sequence of labels. Our analysis is applicable to Petri nets that may have nondeterministic transitions (i.e., transitions that share the same label) and/or unobservable transitions (i.e., transitions that are associated with the null label). More specifically, given knowledge of a labeled Petri net structure and its initial state, we show that the number of consistent markings in a Petri net with nondeterministic transitions is at most polynomial in the length of the observation sequence (i.e., polynomial in the number of labels observed). This polynomial dependency of the number of consistent markings on the length of the observation sequence also applies to Petri nets with unobservable transitions under the assumption that their unobservable subnets are structurally bounded. The bounds on the number of markings established in this paper imply that the state estimation problem in labeled Petri nets can be solved with complexity that is polynomial in the length of the observation sequence. Note to Practitioners-A variety of systems, such as manufacturing systems, computer networks, traffic systems, and others, can be modeled as DESs at a higher level of abstraction. These models can then be used for the purpose of state estimation, supervisory control, and fault diagnosis. Knowledge of the system state is always critical for controller design and fault diagnosis. In this paper, we study state estimation in DESs modeled by labeled Petri nets. This is a challenging problem because two different types of uncertainty can arise due to sensor limitations: a) occurrences of different activity (different transitions) may generate the same observation; b) occurrences of unobservable activity (silent transitions) go unrecorded.We show that, under some reasonable assumptions on the nature of the given Petri net's unobservable transition structure, the number of possible system states that are consistent with an observed sequence of events is upper bounded by a function polynomial in the length of the observation sequence. The implications are twofold: a) the state estimation problem can be solved in a very general setting with complexity that is polynomial in the length of the observation sequence and b) the polynomial bound can guide the design of systems, especially when configuring the state transition sensors, to reduce the uncertainty introduced in the state estimation stage. © 2006 IEEE.