基于GMEC转换算法的Petri网结构控制器综合方法

郁希　黎良

摘 要：针对含不可控变迁Petri网系统禁止状态控制器设计问题，提出了一种基于矩阵变换和整数线性规划的结构控制器综合方法。该方法的关键是对代表系统合法状态的广义互斥约束（generalized mutual exclusion constraint，GMEC）进行转换。首先，根据Petri网系统的关联矩阵，将库所集分为无关库所集、不可控库所集和补足库所集。其次，通过对非允许GMEC中补足库所的权值和不可控库所的权值进行处理，并运用整数线性规划将非允许GMEC转换为允许GMEC。在允许GMEC的基础上，根据库所不变量原理设计出Petri网系统的结构控制器。最后，以某零件加工系统为例验证了所提方法的泛用性和高效性，为实际智能制造系统的监督控制器设计提供有效参考方案。

关键词：监督控制；离散事件系统；Petri网；约束转换

中图分类号：TP271 文献标志码：A 文章编号：1001-3695（2023）10-027-3059-05

doi：10.19734/j.issn.1001-3695.2023.02.0063

Synthesis of Petri net structural controller based on

GMEC transformation algorithm

Yu Xi，Li Liang

（School of Information Science & Engineering，Wuhan University of Science & Technology，Wuhan 430081，China）

Abstract：This paper proposed a controller synthesis method based on matrix transformation and integer linear programming to address the problem of forbidden state controller design for Petri net systems with uncontrollable transitions.The key idea behind this method involved transforming GMEC that represented the legal states of a Petri net system.Based on the incidence matrix of a Petri net，it divided the set of places into irrelevant places，uncontrollable places，and complementary places.By modifying the weights of complementary places and uncontrollable places in the given GMEC，it then converted the given GMEC into an allowable one by solving integer linear programming problems.Using the allowable GMEC，this paper designed a structural controller for Petri nets based on the principle of place invariants.Finally，it took a part processing system as an example to show that the application is versatile and efficient，offering an effective solution for the controller design of intelligent manufacturing systems.

Key words：supervisory control；discrete event system；Petri net；constraint transformation

0 引言

離散事件系统（discrete event system，DES）是指系统状态演化由事件驱动且状态空间呈离散分布的一类复杂动态系统，如交通系统、通信系统和智能制造系统等在逻辑层面上都可以抽象为DES。通常，在DES运行过程中某些状态（一般称为禁止状态）会导致系统故障或阻塞，因此设计相应的监督控制器来避免系统到达禁止状态至关重要［1，2］。Petri网和自动机作为DES的主要建模工具，广泛应用于以DES为模型的系统监督控制和故障诊断中［3，4］。例如，Zhang等人［3］提出一种基于学习自动机和DES监督控制理论来控制黑匣子嵌入式系统的方法。Veras等人［4］通过混合自动机模型提出了一种DES分布式同步诊断架构，其建模成本相比于传统分散同步诊断方法较低。由于Petri网可以利用图形直观地模拟DES的特征，尤其是在并发、同步和因果等关系上具有很强的描述能力，所以本文主要关注基于Petri网的DES监督控制研究。

在以Petri网为模型的DES监督控制中，Giua等人［5］提出用一组称为广义互斥约束（generalized mutual exclusion constraint，GMEC）的线性不等式来描述系统的合法状态，并基于库所不变量的原理求解由控制库所和有向弧构成的结构控制器来实现GMEC。Moody等人［6］在含不可控变迁Petri网中引入可允许标识和可允许GMEC概念，并基于矩阵变换提出非允许GMEC的转换算法。Basile等人［7］提出一种次优甚至最优的控制器以实现GMEC的监督控制，该方法可避免可达标识集的计算，减少了状态空间的计算代价。Cordone等人［8］和高蕾等人［9］从含不可控变迁Petri网的可达标识集出发，基于整数线性规划和分支定界方法求出了允许GMEC，从而分离合法标识与禁止标识。Wang等人［10］提出一种将GMEC转换为可接受的析取线性约束的方法，并基于转换后的约束求出有效的控制器。Chen等人［11］在非纯Petri网中提出一种运用自循环结构来减少整数线性规划约束条件的方法，通过实验表明，所得GMEC可以实现控制要求，并显著提高计算效率。

上述Petri网系统禁止状态控制器通常可分为逻辑控制器和结构控制器［12，13］。逻辑控制器从Petri网可达标识集出发，通过限制系统的可达状态来禁止可控变迁的发射［14，15］；结构控制器从Petri网结构出发，通过实际控制要求限制库所中托肯的数量得出对应的GMEC，但根据该GMEC设计的控制器不一定是最优［16～18］。简而言之，逻辑控制器设计算法没有普遍性且计算复杂，结构控制器设计不能求出最优控制器但应用广泛且计算简便［2］。限于篇幅，本文关注Petri网的结构控制器设计。

目前，含不可控变迁的Petri网禁止状态结构控制器的算法应用范围有限，大部分只能用于某些特殊结构Petri网［19～21］。本文从Petri网结构出发，通过对给定GMEC中库所的权值进行处理，将约束权值应该满足的大小关系作为约束条件；然后，将相关库所的权值和的最小值作为目标函数，利用整数线性规划对GMEC进行转换；最后，基于转换后的GMEC利用库所不变量原理求出对应控制库所的托肯数量和关联矩阵，由此实现Petri网结构控制器设计。本文提出的GMEC转换算法不仅在计算复杂度上优于现有算法，且应用范围更广。

1 预备知识

3.2 基于转换GMEC的Petri网控制器设计

Petri网结构控制器设计就是根据控制库所pc在新Petri网中的关联矩阵-w′D确定与变迁的连接关系，最后计算pc的托肯数量M′0（pc）。给定一个Petri网系统（N，M0）和允许GMEC（w′，k），算法2描述了Petri网控制器设计的详细步骤。

算法2 允许GMEC的Petri网控制器设计

输入：Petri网系统（N，M0）和允许GMEC（w′，k）。

输出：含控制库所pc的Petri网（N′，M′0）。

a）求出Petri网（N，M0）的关联矩阵D；

b）求出Petri网（N′，M′0）中pc在关联矩阵D′对应n维整数向量D′（pc，·）=-w′D；

c）设计控制库所pc；

（a）对于所有t∈T，若D′（pc，t）>0，则添加一条从t指向pc的弧，并赋值为D′（pc，t）；若D′（pc，t）<0，则添加一条从pc指向t的弧，并赋值为|D′（pc，t）|；

（b）对于所有p∈P，M′0（p）=M0（p）；

（c）M′0（pc）=k-w′·M0。

3.3 算法复杂度对比分析

与现有基于线性规划的约束转换算法［22］相比，算法1所做的改进工作主要体现在两个方面：

a）从适用范围来看，该算法可以应用于有向弧权值大于或等于1的一般Petri网；事实上，大部分实际系统都采用一般Petri网建模。

b）从算法复杂度来看，一般应用整数线性规划进行约束转换的目标函数参数为|P|个，约束条件为|P|+|T|个，而算法1应用整数线性规划的目标函数参数只有||个，约束条件最多也只有|T|+||个。如果约束为不可控约束，约束条件仅有|T|个。

4 实例分析

零件加工系统如图3所示，工作流程为原料进入机器开始加工，将原料加工为零件1和2，当加工完成或机器故障时放入工件暂存区。若机器正常运行，则将零件1进行检测和抛光，最后零件1和2统一包装完成放入库房。若机器发生故障，则需等待机器修理。修理成功后将零件1和2加工包装，修理失败则机器停止工作。根据该零件加工系统构建的Petri網模型如图3所示，其中不可控变迁t2表示机器加工完成，不可控变迁t6表示机器出现故障。库所与变迁的含义如表2所示。

假设机器加工完后的工件暂存区只能存放单个零件或原料，因此该加工系统需满足的GMEC为M（p2）+M（p6）≤1，即w=［0，1，0，0，0，1，0，0］，k=1。显然，该GMEC是非允许的。因此，首先对（w，k）进行约束转换。根据算法1可得如下线性规划问题：

求解可得w′（p1）=1。由于w′（pd）和w′（pu）值保持不变，故转换后的约束为M（p1）+M（p2）+M（p6）≤1，即w′=［1，1，0，0，0，1，0，0］，k=1。由此可得M′0（pc）=k-w′·M0=1，其对应的受控Petri网（N′，M′0）如图4所示。

表3为不同文献对本文实例应用各自所提算法的应用范围、方法和算法复杂度对比。目前，矩阵变换和线性规划是处理禁止状态控制器问题的两种主流方法。矩阵变换方法通过对加入控制库所的关联矩阵D′进行行变换来获得控制库所关联矩阵Dc，具有较广泛的应用范围。然而，随着Petri网规模的扩大，相应的矩阵运算成本也随之增加。相比之下，线性规划方法将转换后GMEC中的库所权值作为目标函数参数进行求解，计算效率高于矩阵变换。由表3可知，本文提出的基于矩阵变换和线性规划的控制器综合方法在适用范围和算法复杂度上具有明显优势。

5 结束语

在具有不可控变迁的Petri网系统监督控制中，根据表征系统合法状态的GMEC往往很难直接求出结构控制器，因此这类GMEC通常需要转换成允许的GMEC。为此，本文提出了一种基于矩阵变换和整数线性规划的约束转换算法。本文算法的关键是从Petri网的关联矩阵中提取去零不可控变迁关联矩阵，并将Petri网的库所分为无关库所、不可控库所以及补足库所；然后，基于给定的GMEC利用整数线性规划方法处理不可控库所和补足库所对应的约束权值，以获得允许的GMEC；最后，根据允许GMEC设计出结构控制器。与现有算法相比，本文方法计算代价小，且可应用在一般Petri网中。未来工作将研究含不可控变迁的一般Petri网监督控制器设计。

参考文献：

［1］李大成，罗继亮，孙莎莎，等.基于平行Petri网的制造系统调度与控制一体化方法 ［J］.自动化学报，2023，49（4）：845-856.（Li Dacheng，Luo Jiliang，Sun Shasha，et al.The integrated method of scheduling and control for manufacturing systems based on parallel Petri nets［J］.Acta Automatica Sinica，2023，49（4）：845-856.）

［2］Bashir M，Zhou Jian，Muhammad B B.Optimal supervisory control for flexible manufacturing systems model with Petri nets：a place-transition control ［J］.IEEE Access，2021，9：58566-58578.

［3］Zhang Huimin，Feng Lei，Li Zhiwu.Control of black-box embedded systems by integrating automaton learning and supervisory control theory of discrete-event systems［J］.IEEE Trans on Automation Science and Engineering，2019，17（1）：361-374.

［4］Veras M Z M，Cabral F G，Moreira M V.Distributed synchronous diagnosis of discrete event systems modeled as automata［J］.Control Engineering Practice，2021，115：104892.

［5］Giua A，DiCesare F，Silva M.Generalized mutual exclusion constraints on nets with uncontrollable transitions［C］//Proc of IEEE Internatio-nal Conference on Systems，Man，and Cybernetics.Piscataway，NJ：IEEE Press，1992：974-979.

［6］Moody J O，Antsaklis P J.Petri net supervisors for DES with uncontrollable and unobservable transitions［J］.IEEE Trans on Automatic Control，2000，45（3）：462-476.

［7］Basile F，Chiacchio P，Giua A.Suboptimal supervisory control of Petri nets in presence of uncontrollable transitions via monitor places［J］.Automatica，2006，42（6）：995-1004.

［8］Cordone R，Piroddi L.Parsimonious monitor control of Petri net models of flexible manufacturing systems ［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2013，43（1）：215-221.

［9］高蕾，武書彦，孙燕，等.部分可控Petri网的最优监控器设计 ［J］.控制工程，2017，24（5）：991-997.（Gao Lei，Wu Shuyan，Sun Yan，et al.Optimal supervisor design for partially controllable Petri nets［J］.Control Engineering of China，2017，24（5）：991-997.）

［10］Wang Shouguang，You Dan，Seatzu C.A novel approach for constraint transformation in Petri nets with uncontrollable transitions［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2017，48（8）：1403-1410.

［11］Chen Yufeng，Li Yuting，Li Zhiwu，et al.On optimal supervisor design for discrete-event systems modeled with Petri nets via constraint simplification［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2022，52（6）：3404-3418.

［12］Ma Ziyue，Li Zhiwu，Giua A.Petri net controllers for generalized mutual exclusion constraints with floor operators ［J］.Automatica，2016，74：238-246.

［13］罗继亮，邵辉，吴维敏，等.逻辑控制器设计与离散事件系统监控理论 ［J］.控制理论与应用，2018，35（1）：86-91.（Luo Jiliang，Shao Hui，Wu Weimin，et al.Synthesis of logical controllers and discrete-event systems supervisory control theory［J］.Control Theory & Applications，2018，35（1）：86-91.）

［14］Rezig S，Turki S，Rezg N.Compute optimization of Petri net controllers using the algebraic method［J］.Applied Sciences，2019，9（13）：2633.

［15］Basile F，Cordone R，Piroddi L.Integrated design of optimal supervisors for the enforcement of static and behavioral specifications in Petri net models［J］.Automatica，2013，49：3432-3439.

［16］Luo Jiliang，Zhou Mengchu.Petri-net controller synthesis for partially controllable and observable discrete event systems［J］.IEEE Trans on Automatic Control，2017，62（3）：1301-1313.

［17］Dideban A，Zeraatkar H.Petri net controller synthesis based on decomposed manufacturing models［J］.ISA Trans，2018，77：90-99.

［18］Wang Shouguang，Wang Chengying，Zhou Mengchu.Design of optimal monitor-based supervisors for a class of Petri nets with uncontrollable transitions［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2013，43（5）：1248-1255.

［19］張瑶瑶，吴敏，颜钢锋，等.含不可控变迁的Petri网监控器设计［J］.控制与决策，2008，23（5）：492-496，502.（Zhang Yaoyao，Wu Min，Yan Gangfeng，et al.Supervisor synthesis of Petri net with uncontrollable transitions［J］.Control and Decision，2008，23（5）：492-496，502.）

［20］Mohaman G，Hassane A，Bitjoka L.Structural design of supreme controller with uncontrollable transitions ［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2022，52（6）：3404-3418.

［21］郝真鸣，雷帅帅，刘军堂，等.一种Petri网禁止状态控制器综合方法［J］.电子测量与仪器学报，2022，36（1）：180-187.（Hao Zhenming，Lei Shuaishuai，Liu Juntang，et al.Supervisor synthesis for a class of Petri nets［J］.Journal of Electronic Measurement and Instrumentation，2022，36（1）：180-187.）

收稿日期：2023-02-23；修回日期：2023-04-20基金项目：国家自然科学基金资助项目（62303359）；湖北省自然科学基金资助项目（2021CFB036）

作者简介：郁希（1998-），男，江苏连云港人，硕士研究生，主要研究方向为Petri网理论及其应用；黎良（1989-），男（通信作者），副教授，博士，主要研究方向为Petri网理论与应用、离散事件系统监督控制、复杂系统的建模分析与控制（liangli@wust.edu.cn）.