基于Petri网可达性和结构的最大许可控制器设计

陈鹤峰，伍乃骐

（广东工业大学 机电工程学院，广东 广州 510006）

死锁是自动化制造系统(AMS)资源分配问题中的一个严重问题. 它的出现逼使系统出现停顿甚至引发灾难性的后果[1]. 目前，主要有两种死锁问题的解决方法： 死锁避免(deadlock avoidance)[2-4]和死锁预防(deadlock prevention)[5-9]. 二者的主要区别是前者是在线(on-line)策略，后者是离线(off-line)策略. 死锁预防策略的目标是，合成的监督控制器阻止系统陷入不期望的状态，即，防止系统从合法状态(可达的安全状态)向非法状态(可达的不安全状态)演化[10-11]. 考虑到合成的监控器的性能， 三个问题有待解决： (1)受控系统的行为许可性[12-13]；(2) 合成监控器的计算复杂性[14]；(3) 合成监控器的结构复杂性[10]. 本文主要关注前两个问题.

一个行为约束(或策略)强加到系统后，得到的系统称为受控系统. 一个约束使得某个标识不可达，或者说该标识不满足添加的约束，称为该标识被约束禁止(forbid). 一个行为约束/策略被称为是最大许可的(maximally permissive)或者最优的(optimal)，如果它至少禁止掉一个不期望的标识，同时没有一个期望的标识被它禁止. (下文中，期望的与不期望的标识，采用Petri网术语，分别定义为合法的与非法的标识.)

考虑到计算复杂性，结构分析技术[5，15]可以获得计算上易处理(tractable)且被证明是正确的策略[2]，例如，资源上游策略(resource upstream neighborhood-RUN)、资源排序策略(resource ordering policy-RO)、状态排序策略、银行家算法以及基于信标(siphon)的控制策略[5，16]. 然而，结构分析策略在通常情况下不能获得最大许可( maximal permissiveness)或者最优(optimality)控制，往往会导致系统过分受到限制，行为许可性低.

最大许可行为的监控器可以使得受控系统拥有较高的资源利用率[2]. 一个非最大许可的策略可能还存在二级死锁问题[2]，意味着某些合法的状态在受控系统也变得不可达. 通常，合成自动化系统的最大许可控制器是NP-问题[11]. 通过计算系统的可达图，可以得到最大许可监控器. 然而，两个挑战性的问题有待解决:(1) 枚举系统的可图状态是困难的，因为系统的可达状态数域系统规模呈指数关系；(2) 为了获取最优控制器，不可避免地要设计和求解混合整数规划(mixed integer linear programming-ILP)问题，目前还没有有效的算法求解该问题.

基于文献[10-11]的工作， 提出了标识覆盖技术去搜寻缩减的首遇坏标识(first-met bad markings-FBM)， 在文献[10-11]中称为安全可达的边界标识(“boundary” reachable unsafe states)与缩减的合法标识. 这两个缩减的标识集合分别表示为and. 计算出一个线性约束来最大许可地禁止等价于将标识从集合线性分离开来. 该线性分离器的存在性在文献[17]已经给出. 另外， 在不能线性分离的情况下， 生成最大许可非线性控制的策略在文献[18]已经做过研究. 采用整数规划方法， 假设其最优解存在， 从而合成具有最小结构的最优控制器[10]， 它禁止了所有的而保留所有的. 该方法的计算开销巨大， 特别是对于大规模的AMS， 计算耗时非常可观. 在众多后续的研究中， 都在专注如何加速合成最优的控制器，想方设法减少混合整数的的变量个数与约束条件的个数. 遗憾的是， 这些方法均需求解整数规划.智能制造中的资源分配属于离散事件系统[19-20].Petri网(PNs)[21-23]准确而形象地描述AMS的动态演化过程. Petri网可达图计算与可达状态的分类提取是本文的工作基础，但不属于本文研究范围. 假设与均已由可达性分析计算得出. 具体过程可参阅文献[13].

下一节简单地回顾了与Petri网、带资源简单顺序加工系统(system of simple sequential processes with resources (S3PR[5]))相关的概念和性质. 概括了标识覆盖技术. 该节最后还给出了最大许可控制的线性规划(LP)方法. 在第2节， 通过结构分析， 具有特定结构的部分非法标识被识别出， 非常简便地构建了这些标识的最大许可约束. 第3节通过两个常见的例子，展示了本策略的有效性， 比较了本方法与现有方法的优劣. 最后， 第4节对本文的工作进行了总结.

1 预备知识

1.1 Petri网

一个Petri网[21]被定义为四元组，其中和分别是有限的非空的库所集和变迁集， 并且满足.是有向弧的集合， 每条弧方向要么从一个库所指向一个变迁， 或者反过来， 从变迁指向库所.是一个权值分配函数， 为中的每条弧指定一个整数权值.表示一个带有标识的Petri网系统. 标识也称为状态. 标识通常被写为多集的形式.是一个非负整数， 给定了在标识下库所中令牌(token)的数量.通常用来标识系统的初 始 标 识 . 例 如 ，， 有. 假设是库所子集上的标识表示为中所有库所令牌数总和， 即用来代表t ()的前集(preset).()为t ()的后集(postset)， 即，

本文研究带有资源的简单顺序加工系统(a system of simple sequential processes with resources-S3PR). 这类系统通常用来为具有柔性路径的单资源分配系统(Disjunctive-Single-Unit AMS)建模. 它是普通(ordinary)守恒(conservative)Petri网的一个子类[21]. 文献[5]给出了S3PR的详细定义. S3PR类型的网包含三种库所集： 闲置(idle)库所， 行为(activity)库所和资源(resource)库所，分别表示为和. 或者写成.表明在系统中可以同时被处理的最大作业的数量. 行为库所中的令牌表示工件正在被某个资源加工处理. 在初始状态下，所有的行为库所均是没有令牌的. 资源库所通常为AMS中机器、机械手、缓冲器建模， 代表系统中的资源. 其中的令牌数代表目前状态下可用资源的数目.初始状态下，资源库所中的令牌数表示可利用该资源的最大数目. 假设是一个资源库所是S3PR上的标识. 由于不同种类库所上的标识是相互依赖的，为了简单起见通常仅用行为库所集上的多集表示. 资源的持有者定义为一些行为库所的集合，记为.在标识下的当前持有者记为. 行为库所的指标集写为. 在下， 非空的行为库所的指标集记为. 除了之外， 在下使能的的变迁集合表示为. 全部行为库所中所有的令牌总数写成给定一个库所，所需要的支撑资源库所集为. 对于一个变迁t ， 定义为t的资源前集.

定义1 在S3PR中， 假定为一个资源库所，是一个可达标识. 资源在下被唯一占用，如果;在下被饱和占用，如果;在下被垄断占用，如果既被唯一占用又被饱和占用. 假设.是唯一占用/垄断占用的标识， 如果而且在标识下是被单独占用/垄断占用的.

定义2 S3PR的一个标识称为向前一步死锁的(one-step-ahead deadlock)，如果对于所有，， 并且存在一个信标满足.

定理1[5]假设是S3PR的一个可达标识.称为非法死锁的，当且仅当存在一个信标满足， 即清空.

定理2[2]在S3PR中， 如果对于任意， 则可达状态不含有非法非死锁的标识.

例1 本例选自文献[5]的一个AMS，其S3PR模型见图1，其中圆圈表示库所，矩形表示变迁.，与. 工件A有可选择的柔性加工顺序序列：或者. 工件B具有确定的加工序列：. 由此可见与.是一个最小严格信标.假设在 M 下， M (a)=M(e)=M(c′)=M(d)=M(c)=0，M(b)=M(a′)=2， M (b′)=1， H (r2,M)={b}， S 在 M下是被清空的.

图1 例1的S3PR模型

1.2 可达图分析与标识覆盖

可达图分析的详细过程，读者可以参阅文献[10-12]. 为了下文阐述之方便，本节仅列出与死锁问题有关的概念与结论. 此外，还将合成最优控制的整数线性规划(ILP)方案改造成线性规划(linear programming-LP)的解决方案. 在规模相近的情况下，求解线性规划复杂度远小于求解整数规划的复杂度.

首遇坏标识(first-met bad marking-FBM)是可达图中位于的边界标识， 它可以从中的某个标识，通过一步变迁发射到达. 集合FBMs在数学上表示为：

死锁预防就是禁止集合 MB， 系统受控后，这些标识不可达. 显然， 只需要禁止 MFBM就达到预防死锁的目的， 因为 MB中的任何一个标识必定来自于MFBM中的某个标识. 遗憾的是， 虽然| MFBM|≪|MB|，MFBM也可能仍然是一个规模巨大的集合. 标识覆盖技术可以进一步降低需要处理的对象的规模， 从而明显减轻计算工作负担.

定义3[10-12]假定 M 与 M′是S3PR的两个标识. 如果M(p)≥ M′(p)， p ∈PA， 则MA-覆盖(activity-cover)M′(或 者 M′被MA-覆 盖)， 记 为 M≥AM′(或 者M′≤AM ); 如果 M≥AM′， ∃ p∈PA满足 M(p)＞ M′(p)，则 M 真地A-覆盖 M′(或者 M′被 M真地 A-覆盖)， 记为M≩AM′(or M′≨AM).

定义4[10-12]标识集 M∗FBM ⊆ MFBM称为首遇坏标识集 MFBM的最小被覆盖集，如果满足下列条件：

(1) ∀ M ∈ MFBM,∃M′∈ M∗FBM,M ≥AM′;

(2) ∀ M ∈ M∗FBM,∄M′∈ M∗FBM,M ≥AM′且 M≠M′.

类似地， ML的一个子集M∗L可以由标识覆盖计算得到， 定义如下：定义5[10-12]假设 M∗L⊆ ML为合法标识集的子集.被称为是集合ML的最小覆盖集， 如果满足下列条件：

(1) ∀ M ∈ ML,∃M′∈ M∗L,M′≥AM;

(2) ∀ M ∈ M∗L,∄M′∈ M∗L,M′≥AM 而且.

如果一个线性的代数约束的系数均为非负整数，且该约束最大许可地禁止了标识 M ∈ M∗FBM. 那么， 对于任意的满足 M′≥AM 的 M′， 均可被该约束最大许可地禁止[11].

根据上述可达图分析与标识覆盖的概念， 容易导出以下两个结论.

引理1 假设 M and M′为S3PR N的两个标识. 满足M∈R(N,M0)与 M≥AM′. 那么， M′∈R(N,M0).

证明 由于 M∈R(N,M0)，则存在一个变迁发射序列， ti1ti2···tik， 使得系统状态从 M0演化到 M. 又M≥AM′，在状态 M′下， p∈PA中的每个令牌都对应位于状态 M 下同一个库所 p 中. 状态 M′一定可以由M0开始，通过发射ti1ti2···tik的某个子序列而到达. 故M′∈R(N,M0).

定理3 在S3PR中，如果任意的标识M∈M∗FBM均被某策略最大许可地禁止，则受控后的网系统是活的.

以下设计的线性规划算法，可以作为求最大许可线性约束的通用方法. 目标是求出一个超平面，分离开 Mj∈M∗FBM与M∗L. 如果分离超平面存在，最大许可地禁止 Mj的非负整系数线性约束可由超平面方程导出.

显而易见， LP1必定至少含有一个可行解，即可行域非空. 如果目标函数的最优解， 构造线性约束它最大许可地禁止掉标识Mj∈ M∗FBM，其中是与行为库所 pi相关的一个标识变量. 另一方面， 如果LP1得出的最优解 ε∗≤0， 则不存在线性约束最大许可地禁止标识 Mj∈M∗FBM， 因为， 在几何上， 非法标识位于离散点集M∗L的闭包(convex hull)内部， 从而无法线性分离合法标识与非法标识.

众所周知线性规划问题可以被有效地求解. 然而， LP1存在一个问题： 求解出的最优解与系数一定不是整数，甚至可能是无理数. 对于任何一个实数，都存在一个有理数序列收敛于该实数. 可以通过在线性约束不等式两边乘以某个整数因子使之变为整系数约束. 该约束为最大许可约束. 第3节的例子将说明这一点.

线性规划LP1方法是一类纯数学的方法来计算最大许可的约束， 文献[11]称之为最优分类器. 这种方法没有考虑到Petri网的结构特性. 如果能够分析非法标识与Petri网结构的关系， 建立最大许可约束，将进一步减少计算量. 与求解线性规划LP1比较， 基于结构分析的方法更有效. 因此， 本文首先需要识别标识的结构特征， 为满足特定结构特征的标识综合出最优控制器.

2 基于结构分析的最优控制

死锁的产生是由于在系统中待处理的工作大量涌入， 它们竞争有限的资源和资源分配不当造成的.对于一个S3PR的非法标识， 我们迫使所有的合法标识的令牌总数严格少于该标识中的令牌数， 显然，被禁止了. 另外，线性约束不等式中的系数必须是整数，这样才能用Petri网的形式合成死锁控制器. 然后验证得出约束的最大许可性. 因此， 构造下列线性约束：

为了验证标识 M是否满足构造出的约束(1)， 将不等式左侧的 upi用 M(pi)来 代 替. 毫 无疑问， 约束(1)禁止了特定的标识 Mj∈M∗FBM使得它变得不可达.然而，将约束(1)加到系统中， 不一定能保证其最大许可性. 一种方法是， 将中的每个标识代入约束不等式， 验证其最大许可性. 然而， 在理论上是一个巨大的数字， 是网系统规模的指数型函数. 因此，在计算复杂性角度，该枚举算法不是一个好方法.

2.1 垄断占用的标识

垄断占用标识的结构特征明显，识别验证较容易. 由定理4归纳的策略，高效，简便，易于执行.

证明 (反证法). 假设存在一个标识M(≠ Mj)∈并且 M 被约束(1)禁止. 则公式|Mj|A必定成立. 由已知条件∀ i∈ ℕA(Mj)，Mj(pi)=M0(Req(pi))， 蕴含着， 在标识 Mj下， pi容纳了最大数量的令牌数. 因此， 在任意的标识 M∈R(N,M0)，成立; 否则， 与上述结论矛盾. 另也成立; 否则，， 与M∈ML相矛盾. 从而， 没有一个合法标识被约束(1)禁止掉.

为了验证一个标识 Mj∈M∗FBM是否属于垄断占用的， 对于每一个 pi∈PA满足 Mj(pi)≠0， 需要验证等式Mj(pi)=M0(Req(pi))是否成立. 根据 pi∈PA去搜寻Req(pi)的计算复杂度为 |P|+|T|. 从而， 验证定理4的条件具有的计算复杂度为O (|P|+|T|).

例1中， M3=2b+2a′是一个FBM，R eq(b)={r2}，Req(a′)={r4}， M3(b)=M0(r2)=2，M3(a′)=M0(r4)=2， 也就是说， 定理4的条件获得满足. 从而，ub+u′a≤2+2-1=3是一个最大许可约束. 同理可得， FBMs M1与 M2均为垄断占用的标识. 根据定理4， 它们的最大许可策略能够容易地构造. 换句话说， 对于这个系统， 由构造出的具有(1)形式的约束都是

2.2 向前一步死锁标识

2.3 唯一占用的标识

基于上述两种情形， 约束(1)禁止非法标识的同时没有禁止掉合法标识， 从而是最大许可的. 证毕.

运用定理6识别标识，需要验证给定的3个条件.前两个条件比较容易验证. 在验证第3个条件的时候，需要基于构 造标识集合， 基本操作为向某个库所添加令牌或者移走令牌. 这样的操作复杂度为. 尽管， 在一般情况下， 验证一个标识是否是非法属于NP-困难的. 然而， 如果只包含死锁非法标识与向前一步死锁标识， 可以获得具有多项式复杂度的死锁预防策略. 在下文第3节的例子中将会讨论这类标识.

针对具有不同的结构特性的非法标识，提出了构建最大许可约束的方法. 需要注意的是， 定理4～6给出的结构分析方法比采用LP1给出的线性规划方法更有效. 因此， 首先采用结构分析方法， 识别出具有定理中给定的结构的标识， 相应地设计出对应的控制方法. 至于目前还未能识别出具有特殊结构的非法标识， 姑且采用线性规划的算法寻求最大许可约束. 算法1给出了设计最大许可控制器的工作流程. 注意到验证上述定理中给定的条件的可满足性具有不同的复杂性，具有较低复杂性的策略总是优先考虑. 算法1按照从易到难的顺序去识别非法标识的结构特性. 综上所述， 对于任意， 如果是线性可控的， 本文都可以有效地得到最大许可控制策略， 避免目前文献中求解混合整数规划.

算法1 计算禁止 Mj∈ M∗FBM最优约束流程

输入: S3PR N =(P0∪PA∪PR,T,F)，Mj∈ M∗FBM

输出: c (Mj)//c (Mj)是禁止 Mj的最优约束.

1： if Mj满足定理4 then goto 7;

2： else if Mj是 非法死锁的(by DDA) then goto 7;

3： else if Mj满 足定理5 then goto 7;

4： else if Mj满足定理6 then goto 7;

5： else LP1最优解 ε∗＞0时，得到约束c (Mj)，goto 8;

6： endif

7： c (Mj)← 约束 (1);

8： return c (Mj);

3 两个规模稍大的范例

例2 本系统选取自文献[24]， 其S3PR显示于图2，其中为闲置库所; p14-p19为资源库所; 其余的库所为行为库所. 工件 A的 加工工序:p11t12p12t13p13t14p8. 工件 B的具有可选的加工工序:p1t1p2t2p3t5p5t6p6t7p7t8p1或者p1t1p2t3p4t4p5t6p6t7p7t8p1.

图2 例2的S3PR模型

例3 本例子选取自文献[5]， 图3显示了其S3PR模型，其中闲置库所 P0={p1,p5,p14}， 资源库所PR={p20,···,p26}， 行为库所PA={p2,···,p4,p6,···,p13,p15,···,p19}. 工件 A的 加工工序: p1t11p2t12p3t13p4t14p1. 工件 B 的具有可选的加工工序:p5t1p6t2p7t3p8t4p9t5p10t6p5或者 p 5t1p6t7p11t8p12t9p13t10p10t6p5. 工件C 的加工序列： p 14t15p15t16p16t17p17t18p18t19p19t20p14.

图3 例3的S3PR模型

本系统有 26750个可达状态， 其中| ML|=21581，|MFBM|=4211. 采用标识覆盖技术后， |M∗L|=393，|M∗FBM|=34. 由于数目的过大， 本文无法给出这些标识的详细信息和 M∗FBM中每个标识的许可约束. 就该系统而言， M∗FBM中的每个标识都可以最大许可地被禁止. M∗FBM中有1 8个属于非死锁非法的标识. 据作者所知， 目前的研究中还没有有效的方法处理这类非死锁非法的标识. 这个标识中个可以由定理4～6提出的方法实现最大许可控制， 也就是说， 对于这1 0个标识， 其对应的约束(1)是最优的. 例如， 在M∗FBM中， 下列三个标识2 p11+2p16，2p11+p13+p15+p16,2p11+p12+p15+p16分别满足据定理4～6的条件，易获得其最优控制策略. 对于另外剩下的 8个标识，目前还没有更好的结构控制策略. 如果采用(LP1)，能够获得它们的最优控制策略. 例如， 对于标识p6+2p7+p8+p9+p11+p13+p15+p16+p18， 无法用文中的定理识别出它的结构特征，采用线性规划的方法， 计算出约束

为了合成控制器， 将其等价变形整系数约束

它是一个最优约束. 尽管很多学者基于不同的方法也给出本例的最大许可控制策略， 这些策略不可避免地需要求解混合整数规划. 本文提出的方案不需要求解整数规划， 从计算复杂性的角度， 具有一定的优势.

4 结论

合成自动化制造系统最大许可死锁控制器， 不但保证系统的正常运行， 还确保系统的优化运行. 本工作的目的是， 在合成最优控制器时， 尽可能减少计算开销. 基于S3PR模型， 首先， 通过标记覆盖技术， 缩小待处理问题的规模. 其次， 分析利用网结构的特点，结合标识本身的特性， 揭示二者之间的联系. 识别出标识的特定结构， 避免了求解混合整数规划这一高复杂性的算法. 实验结果表明， 对于绝大数标识， 仅仅利用结构分析就可以获得最大许可控制. 特别是对于那些非死锁非法标识， 本策略也是有效的. 该问题是目前本领域的研究难点.

探索更多结构分析技术， 处理更多的非法标识具有现实意义. 比如， 对文中只能采用线性规划方法处理的非法标识， 转而采用结构分析来处理， 计算量会进一步降低. 此外，当将线性约束转换为具有整数系数的约束时，可能产生监督控制器难以实现的大乘数. 此外，决定如何最小化监督控制器结构仍然是一个重要问题. 本研究中关注S3PR， 并在未来的工作中将结果扩展到更一般的Petri网模型.