郁?！±枇?/p>

摘 要：針對含不可控變遷Petri網(wǎng)系統(tǒng)禁止狀態(tài)控制器設計問題，提出了一種基于矩陣變換和整數(shù)線性規(guī)劃的結構控制器綜合方法。該方法的關鍵是對代表系統(tǒng)合法狀態(tài)的廣義互斥約束（generalized mutual exclusion constraint，GMEC）進行轉換。首先，根據(jù)Petri網(wǎng)系統(tǒng)的關聯(lián)矩陣，將庫所集分為無關庫所集、不可控庫所集和補足庫所集。其次，通過對非允許GMEC中補足庫所的權值和不可控庫所的權值進行處理，并運用整數(shù)線性規(guī)劃將非允許GMEC轉換為允許GMEC。在允許GMEC的基礎上，根據(jù)庫所不變量原理設計出Petri網(wǎng)系統(tǒng)的結構控制器。最后，以某零件加工系統(tǒng)為例驗證了所提方法的泛用性和高效性，為實際智能制造系統(tǒng)的監(jiān)督控制器設計提供有效參考方案。

關鍵詞：監(jiān)督控制；離散事件系統(tǒng)；Petri網(wǎng)；約束轉換

中圖分類號：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 引言

離散事件系統(tǒng)（discrete event system，DES）是指系統(tǒng)狀態(tài)演化由事件驅動且狀態(tài)空間呈離散分布的一類復雜動態(tài)系統(tǒng)，如交通系統(tǒng)、通信系統(tǒng)和智能制造系統(tǒng)等在邏輯層面上都可以抽象為DES。通常，在DES運行過程中某些狀態(tài)（一般稱為禁止狀態(tài)）會導致系統(tǒng)故障或阻塞，因此設計相應的監(jiān)督控制器來避免系統(tǒng)到達禁止狀態(tài)至關重要［1，2］。Petri網(wǎng)和自動機作為DES的主要建模工具，廣泛應用于以DES為模型的系統(tǒng)監(jiān)督控制和故障診斷中［3，4］。例如，Zhang等人［3］提出一種基于學習自動機和DES監(jiān)督控制理論來控制黑匣子嵌入式系統(tǒng)的方法。Veras等人［4］通過混合自動機模型提出了一種DES分布式同步診斷架構，其建模成本相比于傳統(tǒng)分散同步診斷方法較低。由于Petri網(wǎng)可以利用圖形直觀地模擬DES的特征，尤其是在并發(fā)、同步和因果等關系上具有很強的描述能力，所以本文主要關注基于Petri網(wǎng)的DES監(jiān)督控制研究。

在以Petri網(wǎng)為模型的DES監(jiān)督控制中，Giua等人［5］提出用一組稱為廣義互斥約束（generalized mutual exclusion constraint，GMEC）的線性不等式來描述系統(tǒng)的合法狀態(tài)，并基于庫所不變量的原理求解由控制庫所和有向弧構成的結構控制器來實現(xiàn)GMEC。Moody等人［6］在含不可控變遷Petri網(wǎng)中引入可允許標識和可允許GMEC概念，并基于矩陣變換提出非允許GMEC的轉換算法。Basile等人［7］提出一種次優(yōu)甚至最優(yōu)的控制器以實現(xiàn)GMEC的監(jiān)督控制，該方法可避免可達標識集的計算，減少了狀態(tài)空間的計算代價。Cordone等人［8］和高蕾等人［9］從含不可控變遷Petri網(wǎng)的可達標識集出發(fā)，基于整數(shù)線性規(guī)劃和分支定界方法求出了允許GMEC，從而分離合法標識與禁止標識。Wang等人［10］提出一種將GMEC轉換為可接受的析取線性約束的方法，并基于轉換后的約束求出有效的控制器。Chen等人［11］在非純Petri網(wǎng)中提出一種運用自循環(huán)結構來減少整數(shù)線性規(guī)劃約束條件的方法，通過實驗表明，所得GMEC可以實現(xiàn)控制要求，并顯著提高計算效率。

上述Petri網(wǎng)系統(tǒng)禁止狀態(tài)控制器通?？煞譃檫壿嬁刂破骱徒Y構控制器［12，13］。邏輯控制器從Petri網(wǎng)可達標識集出發(fā)，通過限制系統(tǒng)的可達狀態(tài)來禁止可控變遷的發(fā)射［14，15］；結構控制器從Petri網(wǎng)結構出發(fā)，通過實際控制要求限制庫所中托肯的數(shù)量得出對應的GMEC，但根據(jù)該GMEC設計的控制器不一定是最優(yōu)［16～18］。簡而言之，邏輯控制器設計算法沒有普遍性且計算復雜，結構控制器設計不能求出最優(yōu)控制器但應用廣泛且計算簡便［2］。限于篇幅，本文關注Petri網(wǎng)的結構控制器設計。

目前，含不可控變遷的Petri網(wǎng)禁止狀態(tài)結構控制器的算法應用范圍有限，大部分只能用于某些特殊結構Petri網(wǎng)［19～21］。本文從Petri網(wǎng)結構出發(fā)，通過對給定GMEC中庫所的權值進行處理，將約束權值應該滿足的大小關系作為約束條件；然后，將相關庫所的權值和的最小值作為目標函數(shù)，利用整數(shù)線性規(guī)劃對GMEC進行轉換；最后，基于轉換后的GMEC利用庫所不變量原理求出對應控制庫所的托肯數(shù)量和關聯(lián)矩陣，由此實現(xiàn)Petri網(wǎng)結構控制器設計。本文提出的GMEC轉換算法不僅在計算復雜度上優(yōu)于現(xiàn)有算法，且應用范圍更廣。

1 預備知識

3.2 基于轉換GMEC的Petri網(wǎng)控制器設計

Petri網(wǎng)結構控制器設計就是根據(jù)控制庫所pc在新Petri網(wǎng)中的關聯(lián)矩陣-w′D確定與變遷的連接關系，最后計算pc的托肯數(shù)量M′0（pc）。給定一個Petri網(wǎng)系統(tǒng)（N，M0）和允許GMEC（w′，k），算法2描述了Petri網(wǎng)控制器設計的詳細步驟。

算法2 允許GMEC的Petri網(wǎng)控制器設計

輸入：Petri網(wǎng)系統(tǒng)（N，M0）和允許GMEC（w′，k）。

輸出：含控制庫所pc的Petri網(wǎng)（N′，M′0）。

a）求出Petri網(wǎng)（N，M0）的關聯(lián)矩陣D；

b）求出Petri網(wǎng)（N′，M′0）中pc在關聯(lián)矩陣D′對應n維整數(shù)向量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 算法復雜度對比分析

與現(xiàn)有基于線性規(guī)劃的約束轉換算法［22］相比，算法1所做的改進工作主要體現(xiàn)在兩個方面：

a）從適用范圍來看，該算法可以應用于有向弧權值大于或等于1的一般Petri網(wǎng)；事實上，大部分實際系統(tǒng)都采用一般Petri網(wǎng)建模。

b）從算法復雜度來看，一般應用整數(shù)線性規(guī)劃進行約束轉換的目標函數(shù)參數(shù)為|P|個，約束條件為|P|+|T|個，而算法1應用整數(shù)線性規(guī)劃的目標函數(shù)參數(shù)只有||個，約束條件最多也只有|T|+||個。如果約束為不可控約束，約束條件僅有|T|個。

4 實例分析

零件加工系統(tǒng)如圖3所示，工作流程為原料進入機器開始加工，將原料加工為零件1和2，當加工完成或機器故障時放入工件暫存區(qū)。若機器正常運行，則將零件1進行檢測和拋光，最后零件1和2統(tǒng)一包裝完成放入庫房。若機器發(fā)生故障，則需等待機器修理。修理成功后將零件1和2加工包裝，修理失敗則機器停止工作。根據(jù)該零件加工系統(tǒng)構建的Petri網(wǎng)模型如圖3所示，其中不可控變遷t2表示機器加工完成，不可控變遷t6表示機器出現(xiàn)故障。庫所與變遷的含義如表2所示。

假設機器加工完后的工件暫存區(qū)只能存放單個零件或原料，因此該加工系統(tǒng)需滿足的GMEC為M（p2）+M（p6）≤1，即w=［0，1，0，0，0，1，0，0］，k=1。顯然，該GMEC是非允許的。因此，首先對（w，k）進行約束轉換。根據(jù)算法1可得如下線性規(guī)劃問題：

求解可得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網(wǎng)（N′，M′0）如圖4所示。

表3為不同文獻對本文實例應用各自所提算法的應用范圍、方法和算法復雜度對比。目前，矩陣變換和線性規(guī)劃是處理禁止狀態(tài)控制器問題的兩種主流方法。矩陣變換方法通過對加入控制庫所的關聯(lián)矩陣D′進行行變換來獲得控制庫所關聯(lián)矩陣Dc，具有較廣泛的應用范圍。然而，隨著Petri網(wǎng)規(guī)模的擴大，相應的矩陣運算成本也隨之增加。相比之下，線性規(guī)劃方法將轉換后GMEC中的庫所權值作為目標函數(shù)參數(shù)進行求解，計算效率高于矩陣變換。由表3可知，本文提出的基于矩陣變換和線性規(guī)劃的控制器綜合方法在適用范圍和算法復雜度上具有明顯優(yōu)勢。

5 結束語

在具有不可控變遷的Petri網(wǎng)系統(tǒng)監(jiān)督控制中，根據(jù)表征系統(tǒng)合法狀態(tài)的GMEC往往很難直接求出結構控制器，因此這類GMEC通常需要轉換成允許的GMEC。為此，本文提出了一種基于矩陣變換和整數(shù)線性規(guī)劃的約束轉換算法。本文算法的關鍵是從Petri網(wǎng)的關聯(lián)矩陣中提取去零不可控變遷關聯(lián)矩陣，并將Petri網(wǎng)的庫所分為無關庫所、不可控庫所以及補足庫所；然后，基于給定的GMEC利用整數(shù)線性規(guī)劃方法處理不可控庫所和補足庫所對應的約束權值，以獲得允許的GMEC；最后，根據(jù)允許GMEC設計出結構控制器。與現(xiàn)有算法相比，本文方法計算代價小，且可應用在一般Petri網(wǎng)中。未來工作將研究含不可控變遷的一般Petri網(wǎng)監(jiān)督控制器設計。

參考文獻：

［1］李大成，羅繼亮，孫莎莎，等.基于平行Petri網(wǎng)的制造系統(tǒng)調(diào)度與控制一體化方法 ［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，F(xiàn)eng 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網(wǎng)的最優(yōu)監(jiān)控器設計 ［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］羅繼亮，邵輝，吳維敏，等.邏輯控制器設計與離散事件系統(tǒng)監(jiān)控理論 ［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網(wǎng)監(jiān)控器設計［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網(wǎng)禁止狀態(tài)控制器綜合方法［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網(wǎng)理論及其應用；黎良（1989-），男（通信作者），副教授，博士，主要研究方向為Petri網(wǎng)理論與應用、離散事件系統(tǒng)監(jiān)督控制、復雜系統(tǒng)的建模分析與控制（liangli@wust.edu.cn）.