Length-Bounded Least-Cost Transition Firing Sequence Estimation in Petri Nets with Unobservable Transitions

This work studies the problem of estimating the Transition Firing Sequences (TFSs) for Petri nets, where each transition is supposed to be either observable or unobservable. Due to the existence of cycles of unobservable transitions, the number of transition firing sequences may potentially be infinite. In this paper, based on the notion of minimal explanation, we can find a finite number of TFSs for which the number of observable transitions is less than or equal to a given bound. In particular, we assume that the initial and target markings are known. We propose a backtracking algorithm to find the least-cost transition firing sequences that will lead to the target state from the initial one. Moreover, two heuristic methods are proposed to reduce computational effort further. A wireless sensor network system example is provided to illustrate the proposed approaches. According to the example and comparative analysis, we verify that the proposed method can achieve the maximum number of least-cost path solutions. Finally, we present a survey and some comparative studies of various approaches in the relevant literature.