Minimum Initial Marking Estimation in Labeled Petri Nets With Unobservable Transitions Based on Minimal Explanations
针对含不可观变迁的Petri网，提出算法估计最小初始标识，即满足观测序列且总令牌数最小的初始状态，并给出两种启发式方法降低计算成本。
Marking estimation is crucial in the area of discrete event systems. This paper proposes algorithms for addressing the problem of minimum initial markings (MuIMs) estimation in a known Petri net (PN) structure. The existence of unobservable transitions makes this problem challenging since the number of transition sequences consistent with an observed label sequence can potentially be infinite. It is assumed that only minimal explanations can fire before the firing of each observable transition (OT). We present the definition of minimal explanation places, which allows potential minimal explanations to fire before the firing of each OT to obtain more minimal initial markings. Since the number of initial markings may be infinite, we aim to obtain the initial markings that not only enable at least one transition sequence consistent with both the observed label sequence and the PN structure, but also exhibit the minimum total number of tokens (i.e., the minimum total number of tokens when summed over all places). After developing the algorithms, we also propose two heuristic methods to reduce the computational cost, resulting in a subset or an approximation of the final MuIMs. An illustrative example is provided to indicate how the proposed algorithms and heuristics can be utilized to reveal the minimum number of resources required which are indispensable at the initial state for the completion of a specified task sequence.