Reconstruction of Transition Firing Sequences Based on Asynchronous Observations of Place Token Changes

This paper proposes a methodology for reconstructing the possible transition firing sequences in a given Petri net based on asynchronous observations of token changes at different places of the Petri net. The observed sequences of token changes are provided by local sensors and are asynchronous, i.e., they only contain partial information about the ordering of the token changes that occur due to the firing of transitions. The task of a centralized observer is to optimally combine this information and reconstruct all transition firing sequences that are consistent with the structure of the Petri net. More specifically, given the observed sequences of token changes (for different sets of places in the net), the paper develops an algorithm that is able to reconstruct all firing sequences that are consistent with the asynchronous observations and the structure of the given Petri net. Since Petri nets are a powerful tool to model, analyze, and control large-scale dynamic systems, the proposed method is useful for event reconstruction and fault monitoring based on asynchronous observations.