标注Petri 网中的最小初始标识估计

徐淑琳，周广瑞，岳 昊，2

（1.青岛大学自动化学院，山东青岛 266071；2.青岛大学复杂性科学研究所，山东青岛 266071）

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=｛p1，p2，…，pn｝是一个有限的库所集，库所使用空心圆圈表示；2）T=｛t1，t2，…，tm｝是一个有限的变迁集，变迁使用实心竖条表示；3）P∪T≠∅，P∩T=∅；4）F⊆（P×T）∪（T×P）为流关系集合；5）W：F→ℕ=｛0，1，2，…｝称为权函数。

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

定义2［17］在一个Petri 网N=（P，T，F，W）中，若P=｛p1，p2，…，pn｝，T=｛t1，t2，…，tm｝，则N的结构可用关联矩阵A表示，其中：1）A=A+−A−；2）A−为N的输入关联矩阵，A−=［］是一个n行m列的整数矩阵，=W（pi，t）j（1≤i≤n，1≤j≤m）；3）A+为N的输出关联矩阵，A+=［］是一个n行m列的整数矩阵，=W（tj，pi）；4）若pi和tj之间没有弧，则==0；5）A（：，t）（或者A−（：，t），A+（：，t））是A（或者A−，A+）中对应于变迁t的列，且A（：，t），A−（：，t），A+（：，t）均为列向量。

定义3（N，Μ0）是一个初始化的网系统，Μ0是系统的初始标识。映射Μ：P→ℕ 称为Petri 网N的一个标识，标识Μ的每个分量都对应相应库所中托肯的数目，托肯用实心圆点表示。对于p∈P，库所p中的托肯数记为Μ（p），标识Μ的所有库所中的托肯总数记为。

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

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

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

定义5［20］Petri 网N=（P，T，F，W）的可达性可定义为：若存在t∈T使得Μ［t〉Μ΄，则称标识Μ΄从Μ直接可达；若存在一个变迁序列σ=t1t2…tk，其中ti∈T，使得Μ［t1〉Μ1［t2〉…Μk−1［tk〉Μk=Μ΄，则称标识Μ΄从Μ可达。按此规定，从Μ可达的一切标识集合记为R（Μ）。

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

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

由于本文考虑的是含有不可观测变迁的标注Petri网，因此可以将变迁集合T划分为所有不可观测变迁的集合Tu和所有可观测变迁的集合To这2 个集合，且满足Tu∪To=T和Tu∩To=∅。对于一个标注l∈L，用Tl=｛t∈T|l（t）=l｝表示与非空标注l对应的所有可观测变迁的集合，Tu=｛t∈T|l（t）=ɛ｝表示与空标注ɛ对应的所有不可观测变迁的集合，用|Tl|（或者|Tu|）表示对应于非空标注l（或者空标注ɛ）的变迁数目，且满足1≤|Tl|≤m，1≤|Tu|≤m。对于一个变迁序列σ=t1t2…tk，其对应的标注序列可定义为w=（σ）≡l（t1）l（t2）…l（tk）。

2 最小初始标识的求取

2.1 问题描述

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

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

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

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

根据假设2，在观察到标注lj后，所有可能的变迁发生序列形如σu t，其中t∈To，l（t）=lj，σu∈T*u，σu可能为一个空串ɛ。

考虑一个含有不可观测变迁且初始标识未知的标注Petri 网N=（N，Μ0，L∪｛ɛ｝，l）以及一个标注序列w=l1l2…lk，其中lj∈L，j∈｛1，2，…，k｝，本文的目标为寻找最小初始标识估计，即具有最小托肯总数的标识估计。

定义8［15］考虑一个标注Petri 网N=（N，Μ0，L∪｛ɛ｝，l），给定一个标注序列w，将初始标识估计集合、极小初始标识估计集合、最小初始标识估计集合分别定义为：

假设Μ和Μ΄是2 个分量个数相同的标识向量，其中Μ=［Μ（p1），Μ（p2），…，Μ（pn）］T，Μ΄=［Μ ΄（p1），Μ ΄（p2），…，Μ ΄（pn）］T，如果对任意的i∈｛1，2，…，n｝满足Μ（pi）≤Μ ΄（pi），则有Μ≤Μ΄成立。假设一个标识集合Z=｛Μ1，Μ2，…，Μn｝，若对任意的i，j∈｛1，2，3，…｝且i≠j，都不存在Μj使得Μj≤Μi成立，则Μi为标识集合Z中的极小标识。由于小于等于关系是一种偏序关系，因此极小标识并不是唯一的。

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

图1 节点演化示意图Fig.1 Schematic diagram of nodes evolution

图2所示为一个标注Petri网（N，Μ0，L∪｛ɛ｝，l），P=｛p1，p2，p3｝，T=｛t1，t2，t3，t4｝，其中To=｛t1，t4｝，Tu=｛t2，t3｝，（lt1）=a，（lt4）=b，（lt2）=（lt3）=ɛ。给定一个标注序列w=ab，对w进行观察后，利用式（4）计算极小初始标识估计，得到节点演化示意图如图3 所示，节点信息如表1 所示。观察到标注序列ab后，当变迁序列t1t2t3t4发生时，得到极小初始标识估计集合为（w）=｛［0000］T｝，最小初始标识估计集合为I（w）=｛［0000］T｝，I（w）对应的变迁序列集合为｛t1t2t3t4｝，I（w）对应的发生数向量集合为｛［1111］T｝。

图2 标注Petri 网示意图Fig.2 Schematic diagram of labeled Petri nets

图3 Petri 网的节点演化示意图Fig.3 Schematic diagram of node evolution of Petri nets

表1 图3 中每个节点对应的信息Table 1 Corresponding information of each node in Fig.3

2.2 最小初始标识算法估计

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

2.3 复杂性分析

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

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

式（6）可简化为：

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

3 应用实例

本节通过一个实例来验证算法1 的有效性，并将运行结果与现有算法得到的结果进行对比分析。图4给出了一个2台并行机器的标注Petri网模型N=（N，Μ0，L∪｛ɛ｝，l），库所集P=｛p1，p2，p3，p4｝，变迁集T=｛t1，t2，t3，t4，t5，t6｝，其中To=｛t1，t2，t5，t6｝，Tu=｛t3，t4｝，l（t1）=a，l（t2）=b，l（t5）=c，l（t6）=d，l（t3）=l（t4）=ɛ。p1为存放工件的资源库所，变迁t1和t2表示由机器人分别将工件装载至1 号机器和2 号机器上，p2表示工件被1 号机器加工，t3表示机器人将一部分工件从1 号机器上卸载并装载至2 号机器上，p3表示工件被2 号机器加工，t5表示机器人将剩余的工件从1 号机器上卸载，t4表示机器人将工件从2 号机器上卸载，p4表示将来自1 号机器和2 号机器的工件进行再加工，t6表示将工件卸载。给定一个标注序列w=ad，运行算法1 后得到节点演化示意过程如图5 所示，节点信息和弧上的标记信息分别如表2和表3所示。如图5 所示，当观察到标注a时，所有可能的变迁序列集合为｛t1，t3t1，t4t1，t3t4t1，t4t3t1，t3t3t1，t4t4t1｝，应该存在7个节点，但变迁序列t3t4t1和t4t3t1对应的发生数向量均为［101100］T，两者对应的极小初始标识估计分别为［1100］T和［1110］T，显然［1100］T≤［1110］T，根据算法1，当出现相同的发生数向量时，仅保留极小初始标识估计，因此删掉变迁序列t4t3t1对应的初始标识估计及当前标识。当标注序列w=ad全部被观察到后，得到极小初始标识估计集合为（w）=｛［1000］T｝，最小初始标识估计集合为Ι（w）=｛［1000］T｝，与Ι（w）对应的变迁序列集合为｛t1t3t4t6｝，与Ι（w）对应的发生数向量集合为｛［101101］T｝。

图4 标注Petri 网系统示意图Fig.4 Schematic diagram of labeled Petri net system

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

图5 运行算法1 后的节点演化示意图Fig.5 Schematic diagram of node evolution after running algorithm 1

表2 图5 中每个节点对应的信息Table 2 Corresponding information of each node in Fig.5

表3 图5 中每条弧上的标记信息Table 3 Marking information of each arc in Fig.5

4 结束语

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