郁?！±枇?/p>

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

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

中圖分類號(hào)：TP271 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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)演化由事件驅(qū)動(dòng)且狀態(tài)空間呈離散分布的一類復(fù)雜動(dòng)態(tài)系統(tǒng)，如交通系統(tǒng)、通信系統(tǒng)和智能制造系統(tǒng)等在邏輯層面上都可以抽象為DES。通常，在DES運(yùn)行過程中某些狀態(tài)（一般稱為禁止?fàn)顟B(tài)）會(huì)導(dǎo)致系統(tǒng)故障或阻塞，因此設(shè)計(jì)相應(yīng)的監(jiān)督控制器來避免系統(tǒng)到達(dá)禁止?fàn)顟B(tài)至關(guān)重要［1，2］。Petri網(wǎng)和自動(dòng)機(jī)作為DES的主要建模工具，廣泛應(yīng)用于以DES為模型的系統(tǒng)監(jiān)督控制和故障診斷中［3，4］。例如，Zhang等人［3］提出一種基于學(xué)習(xí)自動(dòng)機(jī)和DES監(jiān)督控制理論來控制黑匣子嵌入式系統(tǒng)的方法。Veras等人［4］通過混合自動(dòng)機(jī)模型提出了一種DES分布式同步診斷架構(gòu)，其建模成本相比于傳統(tǒng)分散同步診斷方法較低。由于Petri網(wǎng)可以利用圖形直觀地模擬DES的特征，尤其是在并發(fā)、同步和因果等關(guān)系上具有很強(qiáng)的描述能力，所以本文主要關(guān)注基于Petri網(wǎng)的DES監(jiān)督控制研究。

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

上述Petri網(wǎng)系統(tǒng)禁止?fàn)顟B(tài)控制器通常可分為邏輯控制器和結(jié)構(gòu)控制器［12，13］。邏輯控制器從Petri網(wǎng)可達(dá)標(biāo)識(shí)集出發(fā)，通過限制系統(tǒng)的可達(dá)狀態(tài)來禁止可控變遷的發(fā)射［14，15］；結(jié)構(gòu)控制器從Petri網(wǎng)結(jié)構(gòu)出發(fā)，通過實(shí)際控制要求限制庫所中托肯的數(shù)量得出對(duì)應(yīng)的GMEC，但根據(jù)該GMEC設(shè)計(jì)的控制器不一定是最優(yōu)［16～18］。簡而言之，邏輯控制器設(shè)計(jì)算法沒有普遍性且計(jì)算復(fù)雜，結(jié)構(gòu)控制器設(shè)計(jì)不能求出最優(yōu)控制器但應(yīng)用廣泛且計(jì)算簡便［2］。限于篇幅，本文關(guān)注Petri網(wǎng)的結(jié)構(gòu)控制器設(shè)計(jì)。

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

1 預(yù)備知識(shí)

3.2 基于轉(zhuǎn)換GMEC的Petri網(wǎng)控制器設(shè)計(jì)

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

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

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

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

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

b）求出Petri網(wǎng)（N′，M′0）中pc在關(guān)聯(lián)矩陣D′對(duì)應(yīng)n維整數(shù)向量D′（pc，·）=-w′D；

c）設(shè)計(jì)控制庫所pc；

（a）對(duì)于所有t∈T，若D′（pc，t）>0，則添加一條從t指向pc的弧，并賦值為D′（pc，t）；若D′（pc，t）<0，則添加一條從pc指向t的弧，并賦值為|D′（pc，t）|；

（b）對(duì)于所有p∈P，M′0（p）=M0（p）；

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

3.3 算法復(fù)雜度對(duì)比分析

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

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

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

4 實(shí)例分析

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

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

求解可得w′（p1）=1。由于w′（pd）和w′（pu）值保持不變，故轉(zhuǎn)換后的約束為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，其對(duì)應(yīng)的受控Petri網(wǎng)（N′，M′0）如圖4所示。

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

5 結(jié)束語

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

參考文獻(xiàn)：

［1］李大成，羅繼亮，孫莎莎，等.基于平行Petri網(wǎng)的制造系統(tǒng)調(diào)度與控制一體化方法 ［J］.自動(dòng)化學(xué)報(bào)，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)控器設(shè)計(jì) ［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］羅繼亮，邵輝，吳維敏，等.邏輯控制器設(shè)計(jì)與離散事件系統(tǒng)監(jiān)控理論 ［J］.控制理論與應(yīng)用，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)控器設(shè)計(jì)［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)禁止?fàn)顟B(tài)控制器綜合方法［J］.電子測量與儀器學(xué)報(bào)，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基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（62303359）；湖北省自然科學(xué)基金資助項(xiàng)目（2021CFB036）

作者簡介：郁希（1998-），男，江蘇連云港人，碩士研究生，主要研究方向?yàn)镻etri網(wǎng)理論及其應(yīng)用；黎良（1989-），男（通信作者），副教授，博士，主要研究方向?yàn)镻etri網(wǎng)理論與應(yīng)用、離散事件系統(tǒng)監(jiān)督控制、復(fù)雜系統(tǒng)的建模分析與控制（liangli@wust.edu.cn）.