0 概述

Petri网是一种用于离散事件系统建模、分析和控制的工具，具有图形和数学的双重表现形式且可有效描述系统行为。近年来，Petri网被应用于交通系统^[1]和柔性装配制造系统^[2]等多种实际系统中，且在系统安全及可靠性分析^[3-4]、业务流程分析^[5-6]、交互控制^[7]以及Web服务分析和替代^[8]中也有广泛应用。随着实际系统规模的增大，标识估计对离散事件系统的诊断^[9]和控制器设计^[10-11]等具有重要的作用。

关于Petri网中标识估计问题的研究已经取得显著成果^[12-13]。文献[12]基于对标注序列的观察，讨论了初始标识已知的Petri网中的标识估计问题，并指出标识集可用一组具有固定结构的线性不等式来描述。文献[13]也研究了标识估计问题，并证明所有可能的标识数目是关于k的函数。最小初始标识的估计成为当今研究的热点之一，例如文献[14]讨论了含有可观测变迁的标注Petri网中的最小初始标识估计问题，并提出一种最小初始标识估计算法。文献[15]将文献[14]中的结果扩展到含有不可观测变迁的标注Petri网中。文献[16]提出一种用于估计由标注Petri网中的最小代价计划序列的算法。文献[17]通过使用基可达图寻找标注Petri网中最小代价变迁序列。

针对不可观测变迁的存在给求解标注Petri网建模制造系统中的最小资源带来困难的问题，本文放宽对不可观测变迁发生个数的限制，且允许可观测在变迁前至多有2个不可观测变迁发生。为了更好地实现估计最小初始标识的目标，本文以标注Petri网为工具，进一步讨论了文献[14-15]提出的最小初始标识估计问题，并提出一种基于动态规划的新算法，以估计最小的初始标识。

1 基本概念

本节给出下文将会用到的Petri网和标注Petri网的相关定义，更多详细介绍可参阅文献[14]。

定义1^[18-19]  将一个Petri网定义为一个四元组N=（P，T，F，W），其中：1）P={p₁，p₂，…，p_n}是一个有限的库所集，库所使用空心圆圈表示；2）T={t₁，t₂，…，t_m}是一个有限的变迁集，变迁使用实心竖条表示；3）P∪T≠Ø，P∩T=Ø；4）F⊆（P×T）∪（T×P）为流关系集合；5）W：F→$ \mathbb{N} $={0，1，2，…}称为权函数。

如果p_i和t_j之间没有弧，则W（p_i，t_j）=W（t_j，p_i）=0。如果N没有直接的循环存在，则称N是无环的。

定义2^[17]  在一个Petri网N=（P，T，F，W）中，若P={p₁，p₂，…，p_n}，T={t₁，t₂，…，t_m}，则N的结构可用关联矩阵A表示，其中：1）A=A⁺-A^-；2）A^-为N的输入关联矩阵，A^-=[$ {a}_{ij}^{-} $]是一个n行m列的整数矩阵，$ {a}_{ij}^{-} $=W（p_i，t_j）（1≤i≤n，1≤ j≤m）；3）A⁺为N的输出关联矩阵，A⁺=[$ {a}_{ij}^{+} $]是一个n行m列的整数矩阵，$ {a}_{ij}^{+} $=W（t_j，p_i）；4）若p_i和t_j之间没有弧，则$ {a}_{ij}^{-} $=$ {a}_{ij}^{+} $=0；5）A（：，t）（或者A^-（：，t），A⁺（：，t））是A（或者A^-，A⁺ ）中对应于变迁t的列，且A（：，t），A^-（：，t），A⁺（：，t）均为列向量。

定义3  （N，M₀）是一个初始化的网系统，M₀是系统的初始标识。映射M：P→$ \mathbb{N} $称为Petri网N的一个标识，标识M的每个分量都对应相应库所中托肯的数目，托肯用实心圆点表示。对于p∈P，库所p中的托肯数记为M（p），标识M的所有库所中的托肯总数记为||M||=$ \sum \limits_{i=1}^{n}\mathit{M}\left(p\right) $。

定义4^[14]  Petri网N =（P，T，F，W）具有以下变迁发生规则：

1）对于变迁t ∈ T，如果t的每个输入库所p_input都有至少A^-（p_input，t）个托肯，则变迁t在标识M下具有发生权，并定义为M [t〉。

2）如果变迁t发生，则t的每个输入库所p_input都被移除A^-（p_input，t）个托肯，并且t的每个输出库所p_output都增加A⁺（p_output，t）个托肯，变迁t在标识M下发生会使得系统到达一个新标识M΄ =M+ A（：，t），并记为M [t 〉 M΄。

定义5^[20]  Petri网N =（P，T，F，W）的可达性可定义为：若存在t ∈ T使得M [t 〉 M΄，则称标识M΄从M直接可达；若存在一个变迁序列σ = t₁ t₂ …t_k，其中t_i ∈ T，使得M[t₁ 〉 M₁ [t₂ 〉 … M_k-1 [t_k〉 M_k = M΄，则称标识M΄从M可达。按此规定，从M可达的一切标识集合记为R（M）。

定义6  给定一个变迁序列σ∈T^*，其中T^*表示一系列有限长度的变迁序列集合。令π：T^* →$ \mathbb{N} $ⁿ为一个映射，y=π（σ）是一个m维非负向量，称为σ的发生数向量。y（i）表示变迁序列σ中变迁t出现的次数。对于零长度的空串ɛ∈T^*，其发生数向量为零向量，即π（ɛ）=0_m。

定义7^[17]  将一个标注Petri网定义为一个四元组（N，M₀，L∪{ɛ}，$ l $），其中：1）N=（P，T，A，W）是一个Petri网，M₀是Petri网N的初始标识；2）L是非空标注的集合，标注用一个字母表示；3）$ l $：T→L∪{ɛ}是标注函数，其中每个变迁都对应一个字母或者一个空字符串∫。

由于本文考虑的是含有不可观测变迁的标注Petri网，因此可以将变迁集合T划分为所有不可观测变迁的集合T_u和所有可观测变迁的集合T_o这2个集合，且满足T_u∪T_o=T和T_u∩T_o=Ø。对于一个标注l∈L，用T_l={t∈T|$ l $（t）=l}表示与非空标注l对应的所有可观测变迁的集合，T_u={t∈T|$ l $（t）=ɛ}表示与空标注ɛ对应的所有不可观测变迁的集合，用|T_l|（或者|T_u|）表示对应于非空标注l（或者空标注ɛ）的变迁数目，且满足1≤|T_l|≤m，1≤|T_u|≤m。对于一个变迁序列σ=t₁ t₂… t_k，其对应的标注序列可定义为w=（σ）≡$ l $（t₁）$ l $（t₂）…$ l $（t_k）。

2 最小初始标识的求取 2.1 问题描述

文献[14]考虑的是仅含有可观测变迁的标注Petri网，而本文的研究对象是含有不可观测变迁的标注Petri网，在观察到一个标注后，所有可能的变迁发生序列的数目会呈指数级增长。因此，为了降低计算复杂度，本文进行以下假设：

假设1  不可观测变迁组成的子网是无环的。

根据假设1，在标注Petri网N中，不可观测变迁组成的子网没有直接的循环存在。

假设2  对于每个标注的观察，可观测变迁之前至多允许2个不可观测变迁发生。

根据假设2，在观察到标注l_j后，所有可能的变迁发生序列形如σ_ut，其中t∈T_o，$ l $（t）=l_j，σ_u∈$ {T}_{u}^{\mathrm{*}} $，σ_u可能为一个空串ɛ。

考虑一个含有不可观测变迁且初始标识未知的标注Petri网N=（N，M₀，L∪{ɛ}，$ l $）以及一个标注序列w=l₁l₂…l_k，其中l_j∈L，j∈{1，2，…，k}，本文的目标为寻找最小初始标识估计，即具有最小托肯总数的标识估计。

定义8^[15]  考虑一个标注Petri网N=（N，M₀，L ∪{ɛ}，$ l $），给定一个标注序列w，将初始标识估计集合、极小初始标识估计集合、最小初始标识估计集合分别定义为：

$ I(w)=\left\{\boldsymbol{M} \in \mathbb{N}^{n} \mid \exists \sigma \in T^{*}: \boldsymbol{M}[\sigma\rangle, l(\sigma)=w\right\} $

(1)

$ \mathbb{I}(w)=\left\{\boldsymbol{M} \in I(w) \mid \nexists \boldsymbol{M}^{\prime} \in I(w): \boldsymbol{M}^{\prime} \leqslant \boldsymbol{M}, \boldsymbol{M}^{\prime} \neq \boldsymbol{M}\right\} $

(2)

$ \mathcal{I}(w)=\left\{\boldsymbol{M} \in \mathbb{I}(w) \mid\|\boldsymbol{M}\| \leqslant\left\|\boldsymbol{M}^{\prime}\right\|, \boldsymbol{M}^{\prime} \in \mathbb{I}(w)\right\} $

(3)

显然，由定义8可知$\mathbb{I}(w) \subseteq I(w) $成立，并且对任意标识$M \in \mathbb{I}(w)$都不存在M΄ ∈ I（w）使得M΄ < M，同理 $I(w) \subseteq \mathbb{I}(w) $成立，对任意标识$\boldsymbol{M} \in \mathcal{I}(w) $都不存在$\boldsymbol{M}^{\prime} \in \mathbb{I}(w) $使得|| M΄|| < || M||。

假设M和M΄是2个分量个数相同的标识向量，其中M=[M（p₁），M（p₂），…，M（p_n）]^T，M΄=[M ΄（p₁），M ΄（p₂），…，M΄（p_n）]^T，如果对任意的i∈{1，2，…，n}满足M（p_i）≤ M ΄（p_i），则有M≤M΄成立。假设一个标识集合Z={M₁，M₂，…，M_n}，若对任意的i，j∈{1，2，3，…}且i≠j，都不存在M_j使得M_j≤M_i成立，则M _i为标识集合Z中的极小标识。由于小于等于关系是一种偏序关系，因此极小标识并不是唯一的。

在文献[15]中，式（4）给出了极小初始标识的计算方法：

$ \boldsymbol{M}_{j}^{0}=\max \left\{\boldsymbol{M}_{j-1}^{0}+\boldsymbol{A} \cdot \boldsymbol{y}_{j-1}, \boldsymbol{A}^{-}\left(:, \boldsymbol{t}_{i j}\right)\right\}-\boldsymbol{A} \cdot \boldsymbol{y}_{j-1}$

(4)

其中，j=1，2，…，k，$ \boldsymbol{M}_{j}^{0} $为一个n维向量，$ {\boldsymbol{M}}_{\mathrm{ }0}^{0} $=0_n，A^-（：，t_ij）是关联矩阵A中对应变迁$ {t}_{ij} $的列。对于一个变迁序列σ =$ {t}_{{i}_{1}}{t}_{{i}_{2}}...{t}_{{i}_{j}} $，y_j是第j阶段（观察到第j个标注）对应于σ的发生数向量，y₀=0_m。$ \boldsymbol{M}_{j-1}^{0} $和$ \boldsymbol{M}_{j}^{0} $分别表示变迁$ {t}_{ij} $发生前、后的初始标识。要得到最小初始标识估计，当变迁$ {t}_{ij} $发生时，应该在$ {t}_{ij} $的所有前集库所中放入满足$ {t}_{ij} $发生条件的最小数目的托肯。图 1给出了节点演化示意过程，每个节点为一个三元组（$ {\boldsymbol{y}}_{{j}_{i}}, {\boldsymbol{M}_{{j}_{i}}^{0}}, {\boldsymbol{M}}_{c{j}_{i}} $），其中$ {\boldsymbol{M}}_{{j}_{i}}^{0} $表示一组与所观察到的标注序列$ \sigma ={\sigma }_{{u}_{1}}{t}_{{i}_{1}}{\sigma }_{{u}_{2}}{t}_{{i}_{2}}...{\sigma }_{{u}_{j}}{t}_{{i}_{j}} $一致的极小初始标识，$ {\boldsymbol{y}}_{{j}_{i}} $表示在$ {\boldsymbol{M}}_{{j}_{i}}^{0} $下发生的变迁序列所对应的发生数向量，$ {\boldsymbol{M}}_{c{j}_{i}} $表示与$ {\boldsymbol{M}}_{{j}_{i}}^{0} $对应的当前标识。图 1显示了节点信息的演化过程。当一个长度为k的标注序列w=l₁l₂…l_k全部被观察到后，即可找到第k个阶段极小初始标识估计的集合，通过比较托肯总数可得到最小初始标识估计集合。

图 2所示为一个标注Petri网（N，M₀，L∪{ɛ}，$ l $），P={ p₁，p₂，p₃}，T={t₁，t₂，t₃，t₄}，其中T_o={t₁，t₄}，T_u={t₂，t₃}，$ l $（t₁）=a，$ l $（t₄）=b，$ l $（t₂）=$ l $（t₃）=ɛ。给定一个标注序列w=ab，对w进行观察后，利用式（4）计算极小初始标识估计，得到节点演化示意图如图 3所示，节点信息如表 1所示。观察到标注序列ab后，当变迁序列t₁ t₂ t₃ t₄发生时，得到极小初始标识估计集合为$ \mathbb{I}$（w）={[0000]^T }，最小初始标识估计集合为I（w）={[0000]^T}，I（w）对应的变迁序列集合为{t₁ t₂ t₃ t₄}，I（w）对应的发生数向量集合为{[1111]^T}。

2.2 最小初始标识算法估计

在算法1中，对于第j阶段，R_j表示单个节点，V（j）表示所有节点的集合，节点演化示意图中某个节点的信息用一个三元组R_j=（y_j，$ {\mathit{\boldsymbol{M}}}_{j}^{0} $，M_cj）表示，其中3个元素的含义分别为：1）y_j表示在观察到第j个标注后，形如σ_ut_j的变迁发生序列对应的发生数向量，t_j∈l_j，y_j= y_j-1 + π（σ_u） + π（t_j）；2）$ {\mathit{\boldsymbol{M}}}_{j}^{0} $表示与y_j对应的极小初始标识估计；3）M_cj表示与$ {\mathit{\boldsymbol{M}}}_{j}^{0} $对应的当前标识。

u.y_i、u.$ {\mathit{\boldsymbol{M}}}_{i}^{0} $和 u.M_ci分别表示发生不可观测变迁时的发生数向量、初始标识估计和当前标识。R_j.M_minimal表示单个节点处的极小初始标识估计集合，R_j.M_cminimal表示与R_j.M_minimal对应的当前标识集合。当观察到标注l_j时，所有需要考虑的形如σ_ut_j的变迁序列的个数为$ \sum \limits_{s=0}^{2}{m}_{u}^{s} $，其中m_u为标注Petri网中不可观测变迁的数目。

算法1  最小初始标识估计算法

输入  一个含有无环不可观测变迁子网的标注Petri网N和一个长度为k的标注序列w=l₁l₂…l_k

输出  第k阶段集合R_k.M_minimal中具有最小托肯总数的初始标识估计

1.$ {\mathrm{M}}_{0}^{0} $= 0_n，y₀ = 0_m，M_c0 = 0_n

2.R₀ =（y₀，$ {\mathrm{M}}_{0}^{0} $，M_c0）

3.考虑标注l_j

4.令V（j）=Ø

5.For j∈{1，2，…，k}

6.For所有节点R_j-1 ∈V（j-1），$ {{M}_{\mathrm{j}}^{0}}^{\mathrm{\text{'}}} $∈ _j-1.M_minimal

7.For 所有的变迁发生序列σ_ut_j ∈T^*

8.For变迁发生序列σ_u t_j 中的所有变迁t，σ_u=t_i，t_i∈T_u，i∈{1，2}

9.If t ∈ T_u

10.For i ∈{1，2}

11.u.$ {\mathrm{M}}_{\mathrm{i}}^{0} $=max{M_cj-1，A^-（：，t）}-A·y_j-1，u.y_i=y_j-1+ π（t），M_ci=$ {\mathrm{M}}_{\mathrm{i}}^{0} $+A·u.y_i

12.End For

13.Else t ∈ l_j，$ {\mathrm{M}}_{\mathrm{j}}^{0} $=max{u.M_ci，A^-（：，t）}-A·u.y_i，y_j = u.y_i + π（t），M_cj =$ {\mathrm{M}}_{j}^{0} $+ A·y_j，储存 R_j =（ y_j，$ {\mathrm{M}}_{\mathrm{j}}^{0} $，M_cj）

14.End If

15.If y_j已在节点 R_j ∈ V（j）中出现过

16.For所有满足$ {{\mathrm{M}}_{\mathrm{j}}^{0}}^{\mathrm{\text{'}}} $∈ R_j.M_minimal 和M$ \mathrm{\text{'}} $_cj ∈ R_j.M_cminimal 的标识

17.If $ {\mathrm{M}}_{\mathrm{j}}^{0} $与$ {{\mathrm{M}}_{\mathrm{j}}^{0}}^{\mathrm{\text{'}}} $不能比较，或者$ {\mathrm{M}}_{\mathrm{j}}^{0} $=$ {{\mathrm{M}}_{\mathrm{j}}^{0}}^{\mathrm{\text{'}}} $then

18.更新集合V（j）=V（j）∪（y_j，{$ {\mathrm{M}}_{j}^{0} $}，{M_cj}），R_j.M_minimal=R_j.M_minimal∪{$ {\mathrm{M}}_{\mathrm{j}}^{0} $}

19.Else $ {\mathrm{M}}_{\mathrm{j}}^{0} $ < $ {{\mathrm{M}}_{\mathrm{j}}^{0}}^{\mathrm{\text{'}}} $ then

20.更新集合V（j）=V（j）∪（y_j，{$ {\mathrm{M}}_{\mathrm{j}}^{0} $-{$ {{\mathrm{M}}_{\mathrm{j}}^{0}}^{\mathrm{\text{'}}} $}}，{M_cj-{M$ \mathrm{\text{'}} $_cj}}），R_j.M_minimal = R_j.M_minimal∪{$ {\mathrm{M}}_{\mathrm{j}}^{0} $-{$ {{\mathrm{M}}_{\mathrm{j}}^{0}}^{\mathrm{\text{'}}} $}}

21.End If

22.End For

23.Else y_j未在集合V（j）中出现过

24.更新V（j）=V（j）∪（y_j，{$ {\mathrm{M}}_{\mathrm{j}}^{0} $}，{M_cj}），R_j.M_minimal=R_j.M_minimal∪{$ {\mathrm{M}}_{\mathrm{j}}^{0} $}

25.End If

26.If不同的σ_ut_j被搜索的次数少于$ \sum \limits_{\mathrm{s}=0}^{2}{\mathrm{m}}_{\mathrm{u}}^{\mathrm{s}} $

27.设置 Flag==FALSE，返回步骤8

28.Else设置 Flag==TRUE，返回步骤5

29.End If

30.End For

31.End For

32.End For

33.End For

在上述算法中，给定长度为k的标注序列 w=l₁l₂…l_k，目标是找到最小的初始标识估计集合。当观察到第 j个标注时，若发生数向量 y_j已经在第 j阶段的某个节点R_j中出现过，则会存在以下两种情形：情形1，$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $与$ {{\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0}}^{\mathrm{\text{'}}} $不能比较大小或者$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $=$ {{\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0}}^{\mathrm{\text{'}}} $，此时会更新集合V（j）=V（j）∪（y_j，{$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $}，{M_cj}），即储存新的极小初始标识估计的相关信息，同时更新极小初始标识集合R_j.M_minimal=R_j.M_minimal∪{$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $}；情形2，$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $ < $ {{\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0}}^{\mathrm{\text{'}}} $，此时会更新集合V（j）=V（j）∪（ y_j，{$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $-{$ {{\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0}}^{\mathrm{\text{'}}} $}}，{M_cj-{M_cj΄}}），即删掉原来的极小初始标识估计的相关信息并储新的信息，同时更新极小初始标识集合R_j.M_minimal=R_j.M_minimal∪{$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $-{$ {{\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0}}^{\mathrm{\text{'}}} $}}。若y_j没有出现过，则更新集合V（j）=V（j）∪（y_j，{$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $}，{M_cj}），并且更新极小初始标识集合R_j.M_minimal=R_j.M_minimal∪{$ {\mathit{\boldsymbol{M}}}_{\mathit{j}}^{0} $}。当j=k时，此时输出极小初始标识集合R_k.M_minimal中托肯总数最小的初始标识估计，即最小初始标识估计。

2.3 复杂性分析

由文献[14]可知，第j阶段的发生数向量的数目为n_j=O（j ^b），b是一个依赖于Petri网结构的参数。给定一个含有n个库所、m个变迁的标注Petri网，其中可观测变迁和不可观测变迁的个数分别为m_o和m_u，且有m=m_o+m_u成立。在观察到一个标注后，所有可能不同的不可观测发生数向量的数目为：

$ r=2{C}_{{m}_{u}}^{1}+{C}_{{m}_{u}}^{2}=2{m}_{u}+\frac{{m}_{u}\cdot ({m}_{u}-1)}{2} $

(5)

综合考虑可观测变迁和不可观测变迁，基于假设2，可知第j阶段发生数向量的数目为n_j=（r∙ j）^b。在第j-1阶段，一个发生数向量至多能产生r∙m₀个不同的发生数向量，因此第j阶段新产生的发生数向量的总数为r∙m₀∙n_j-1=O[r∙m₀∙（r∙j）^b]。在Petri网中仅含有可观测变迁的情况下，第j阶段极小初始标识的数目为q_j=O（jⁿ），根据假设2，发生序列长度的最大值为3j，因此q_j=O（（3j）ⁿ）=O（j ⁿ）。针对每个发生数向量，需要进行n_j次比较以确定其是否已经出现在节点R_j中，若已出现过，则需要q_j次比较来确定极小的初始标识估计。基于以上分析，算法1的计算复杂度为：

$ \begin{array}{l} \sum \limits_{j=1}^{k}\left[O\right(r\cdot {m}_{o}\cdot {n}_{j-1}\cdot (m\cdot {n}_{j}+{q}_{j-1}\cdot {q}_{j}\cdot n)\left)\right]=\\ \sum \limits_{j=1}^{k}\left[O\right(r\cdot {m}_{o}\cdot {(r\cdot j)}^{b}\cdot [m\cdot r\cdot {(r\cdot j)}^{b}+{j}^{n}\cdot {j}^{n}\cdot n]\left)\right] \end{array}$

(6)

式（6）可简化为：

$ O({m}_{o}m{r}^{2b+2}{j}^{2b}+{m}_{o}m{r}^{b+1}{j}^{2n+b})= $

$ O({m}_{o}m{r}^{2b+2}{k}^{2b+1}+{m}_{o}m{r}^{b+1}{k}^{2n+b+1})= $

$ O({k}^{2b+1}+{k}^{2n+b+1}) $

(7)

因此，算法1的计算复杂度是关于k的多项式。

3 应用实例

本节通过一个实例来验证算法1的有效性，并将运行结果与现有算法得到的结果进行对比分析。图 4给出了一个2台并行机器的标注Petri网模型N=（N，M₀，L ∪ {ɛ}，$ l $），库所集P={ p₁，p₂，p₃，p₄}，变迁集T={t₁，t₂，t₃，t₄，t₅，t₆}，其中T_o={t₁，t₂，t₅，t₆}，T_u={t₃，t₄}，$ l $（t₁）=a，$ l $（t₂）=b，$ l $（t₅）=c，$ l $（t₆）=d，$ l $（t₃）=$ l $（t₄）=ɛ。p₁为存放工件的资源库所，变迁t₁和t₂表示由机器人分别将工件装载至1号机器和2号机器上，p₂表示工件被1号机器加工，t₃表示机器人将一部分工件从1号机器上卸载并装载至2号机器上，p₃表示工件被2号机器加工，t₅表示机器人将剩余的工件从1号机器上卸载，t₄表示机器人将工件从2号机器上卸载，p₄表示将来自1号机器和2号机器的工件进行再加工，t₆表示将工件卸载。给定一个标注序列w=ad，运行算法1后得到节点演化示意过程如图 5所示，节点信息和弧上的标记信息分别如表 2和表 3所示。如图 5所示，当观察到标注a时，所有可能的变迁序列集合为{t₁，t₃ t₁，t₄ t₁，t₃ t₄ t₁，t₄ t₃ t₁，t₃ t₃ t₁，t₄ t₄ t₁}，应该存在7个节点，但变迁序列t₃ t₄ t₁和t₄ t₃ t₁对应的发生数向量均为[101100]^T，两者对应的极小初始标识估计分别为[1100]^T和[1110]^T，显然[1100]^T≤[1110]^T，根据算法1，当出现相同的发生数向量时，仅保留极小初始标识估计，因此删掉变迁序列t₄ t₃ t₁对应的初始标识估计及当前标识。当标注序列w=ad全部被观察到后，得到极小初始标识估计集合为$\mathbb{I} $（w）={ [1000]^T }，最小初始标识估计集合为Ι（w）={[1000]^T}，与 Ι（w） 对应的变迁序列集合为{t₁t₃t₄t₆}，与Ι（w）对应的发生数向量集合为{[101101]^T}。

文献[15]中限定可观测变迁发生之前至多允许一个不可观测变迁发生，则最小初始标识估计集合为Ι΄（w）={[1001]^T}，发生数向量集合为{[100001]^T，[101001]^T}，变迁序列为{t₁ t₆，t₁ t₃ t₆ }。假设M∈Ι（w），M΄∈Ι΄（w），则||M||=1，||M΄||=2，由此可知||M|| < ||M΄||，因此，应用本文方法得到的最小初始标识具有更小的托肯总数，即系统完成指定的任务序列所需的初始资源更少。

4 结束语

针对制造系统中的最小资源问题，本文建立标注Petri网模型，并提出一种用于估计最小初始标识的算法。该算法放宽了不可观测变迁发生个数的限制，并规定可观测变迁之前至多允许2个不可观测变迁发生，以有效避免最小初始标识估计的穷举计算。实验结果表明，在含有不可观测变迁的标注Petri网中，应用本文算法估计的最小初始标识较现有算法得到的结果更优。下一步将利用时延Petri网结构对本文算法进行优化，使得初始标识估计的托肯总数更小。