Least-Cost Firing Sequence Estimation in Labeled Petri Nets with Unobservable Transitions

This paper develops a recursive algorithm for estimating the least-cost transition firing sequences that match the observation of a sequence of labels produced by transition activity in a given labeled Petri net. The Petri nets we consider have transitions that are observable (i.e., their firing produces a not necessarily unique label) or unobservable (i.e., their firing does not produce any label). We assume that each transition in the given net (including unobservable transitions) is associated with a nonnegative cost which captures its likelihood (e.g., the cost could be inversely proportional to the amount of workload or power required to execute the transition). Assuming full knowledge of the structure of a given labeled Petri net, we aim at finding the firing sequence(s) that has (have) the least total cost and is (are) consistent with the observed label sequence. The existence of unobservable transitions in the net makes this task extremely challenging since the number of firing sequences that is consistent with the label observations can potentially be infinite. Under some conditions on the unobservable transitions of the Petri net, we show that it is possible to use a recursive algorithm that finds the least-cost firing sequence(s) while reconstructing only a finite number of such firing sequences. In particular, if the unobservable transitions in the net are contact- free and have strictly positive costs, this algorithm has storage and computational complexity that is polynomial in the length of the observed sequence of labels.