Least-cost Transition Sequence Estimation in Partially Observable Labeled Time Petri Nets

Aiming at the problem of planning sequences in automated manufacturing systems, this study proposes an approach to solve the least-cost transition sequence estimation problem in a partially observable labeled time Petri net (LTPN). In particular, the considered LTPN is bounded, where each transition has a nonnegative cost. Based on time-label sequences (TLS), we first introduce a graph called observed-modified state class graph (OSCG) that represents the partial state space of an LTPN system. Then, all transition sequences logically consistent with the observed TLS can be found in the OSCG. By exploiting the transition-related timing constraints in an OSCG, we propose a procedure for determining which logic-consistent transition sequences are timing consistent with the observed TLS. Then, we develop an algorithm for estimating the least-cost transition sequences. Finally, the effectiveness of the proposed method is verified using an experimental example.