基于展開圖的安全網(wǎng)控制器設(shè)計

方偉波，趙志誠

(太原科技大學電子信息工程學院，太原 030024)

摘要：針對一類特殊Petri網(wǎng)—安全網(wǎng)，將Petri網(wǎng)展開技術(shù)應用于控制器設(shè)計，研究能實現(xiàn)給定性能指標的最大容許控制器的設(shè)計問題。引入了控制變遷集的概念，得到了基于展開圖的邏輯型控制器，在此基礎(chǔ)上，結(jié)合Petri網(wǎng)展開原理，設(shè)計出原網(wǎng)上的結(jié)構(gòu)型控制器，方便工程人員理解并能節(jié)省在線運行時控制動作的計算時間。

關(guān)鍵詞：離散事件系統(tǒng)；Petri網(wǎng)；安全網(wǎng)；展開圖；控制器

收稿日期：2015-03-18

作者簡介：方偉波(1989-)，男，碩士研究生，主要研究方向為離散事件系統(tǒng)建模與控制。

中圖分類號：TP301文獻標志碼：A

離散事件系統(tǒng)(DES)是一個在離散時間由事件驅(qū)動的人造系統(tǒng)?，F(xiàn)代社會常見的離散事件系統(tǒng)有網(wǎng)絡(luò)購物過程、通信網(wǎng)絡(luò)系統(tǒng)、交通控制系統(tǒng)、制造系統(tǒng)、物流自動化系統(tǒng)等。DES起源于上世紀八十年代初制造系統(tǒng)工程方面的研究。DES系統(tǒng)性能分析常用數(shù)學模型有隨機過程模型(如馬爾科夫鏈、排隊論等)，系統(tǒng)綜合的數(shù)學模型則有自動機、形式語言和Petri網(wǎng)等[1]。

隨著離散系統(tǒng)監(jiān)控理論[2]的發(fā)展，人們發(fā)現(xiàn)自動機和形式語言模型很難克服計算復雜性問題，特別是針對大系統(tǒng)時缺點明顯。因此，越來越多的學者將目光轉(zhuǎn)向了Petri網(wǎng)。與自動機比，Petri網(wǎng)具有更高的語言復雜性，是正規(guī)語言的嚴格超集，對系統(tǒng)的描述更加緊湊。另外，Petri網(wǎng)還可以進行模塊化綜合[3]。

DES控制器類型分為邏輯型控制器和結(jié)構(gòu)型控制器。以自動機和形式語言為工具得到的往往是邏輯型控制器，以Petri網(wǎng)為工具既可得到邏輯型控制器，也可得到結(jié)構(gòu)型控制器。與邏輯型控制器相比，結(jié)構(gòu)型控制器具有不需要在線計算、相同的Petri網(wǎng)演化算法可同時運用于被控對象和控制器子網(wǎng)的優(yōu)點。目前，基于Petri網(wǎng)的DES控制方法比較經(jīng)典的有Moody和Antsaklis等人提出的基于Petri網(wǎng)關(guān)聯(lián)矩陣的庫所不變量法[4]；Li和Wonham提出的向量離散事件系統(tǒng)(VDES)法[5]；Zhou和Li等人提出的信標法[6-8]；Holloway和Krogh等人提出的基于受控Petri網(wǎng)的路徑代數(shù)法[9]。其它關(guān)于離散系統(tǒng)監(jiān)控理論方面的研究主要有柔性制造系統(tǒng)的死鎖避免以及活性研究[10-11]。

以上的幾類控制器設(shè)計方法對特定Petri網(wǎng)建模的DES且滿足特定條件的監(jiān)控問題是有效的，但存在一些共同問題：較強的適用條件，應用范圍受限，計算效率有待提高，且大多得到的控制律不是最大容許能控的，在保證系統(tǒng)活性方面效果不理想。這主要是由于以上幾種理論的狀態(tài)搜索大都基于Petri網(wǎng)的可達圖，這是一種窮舉法，計算效率低下，易導致狀態(tài)空間爆炸問題。為了避免這一問題，有學者提出了Petri網(wǎng)展開理論[12]，實現(xiàn)以有限研究無限的目標，特別是對于具有不可控變遷的系統(tǒng)而言，將大大降低計算復雜性。

Giua等人針對普通安全網(wǎng)的禁止狀態(tài)問題，利用Petri網(wǎng)展開理論，提出了在展開圖上直接添加控制庫所的方式得到控制策略[13]，但是獲得的控制策略還不是結(jié)構(gòu)型控制器，本文在前人研究的基礎(chǔ)上，綜合出原網(wǎng)上等價的控制結(jié)構(gòu)，方便工程人員理解應用。

1Petri網(wǎng)及其展開理論

1.1Petri網(wǎng)

Petri網(wǎng)可對并發(fā)、異步、分布、并行、不確定和隨機系統(tǒng)建模，其圖形化的表示形式直觀易理解。

定義1：Petri網(wǎng)

一個Petri網(wǎng)可以定義為四元組PN=(P，T，F(xiàn)，W)，其中，P={p1，p2，p3…}代表庫所的有限集合，T={t1，t2，t3…}代表變遷的有限集合，F(xiàn)(P×T)∪(T×P)是代表流關(guān)系的弧的集合，W∶F→{1，2，3…}是弧的權(quán)函數(shù)，且滿足P∩T=?，P∪T≠?。?t={p/(p,t)∈F}，稱為變遷t的輸入庫所集合，t?相應的稱為變遷t的輸出庫所集合，?p={t/(t,p)∈F}稱為庫所p的輸入變遷集合，p?為庫所p的輸出變遷集合。

1.2Petri網(wǎng)展開理論

展開圖法的關(guān)鍵在于構(gòu)造Petri網(wǎng)展開圖的有限前綴，且該圖能完全表達Petri網(wǎng)的所有可達標識。

定義2：事件網(wǎng)[12]

(2)F的傳遞閉包是非周期的，不存在自我沖突的變遷t∈T；

(3)?t∈T′∶h(?t)=?h(t)，且h(t?)=h(t)?；

(4)?t1,t2∈T′，若h(t1)=h(t2)，?t1=?t2則t1=t2；

(5)h(M0′)=M0.

事件網(wǎng)中元素間的三類關(guān)系如下：

(1)因果，x1x2)；

(2)沖突，x1#x2，如果?t1,t2∈T,?t1∩?t2≠Φ且ti

(3)并發(fā)，x1‖x2，如果x1，x2既不是前后關(guān)系也不是沖突關(guān)系。

定義3：配置

變遷集合C是一個配置，如果:

(1)若t∈C，t′

(2)變遷集合C是無沖突的，即任意t1，t2∈C，不存在t1#t2

令[t]={t′∈T′|t′?C，Cut(C)常代表原Petri網(wǎng)的可達標識。在展開圖中，配置代表了所有可能的行為動作?？芍魎代表原Petri網(wǎng)的一個標識，則必有一配置C滿足M(h(Cut(C)))=u.

算法1:根據(jù)文獻[12]的Petri網(wǎng)展開圖構(gòu)造方法。

(1)將PN中的每一個初始標識所在的庫所復制到事件網(wǎng)中；

(2)從PN中選取一個變遷t；

(3)對于?t中的每個庫所，在事件網(wǎng)中尋找其映射庫所，若無法全找到，則返回(2)；若找到的庫所不是并發(fā)的，也返回(2)；

(4)將t復制到事件網(wǎng)中，記為t′，從(3)中找到的每個庫所畫一條弧到t′；

(5)對于t?中的每個庫所，將其映射到事件網(wǎng)中，并從t′畫一條弧到這些庫所；

重復步驟(2)-(5).

這一展開過程可以無限的進行下去，其中，定義其有限前綴意義重大。

定義4：截止變遷

變遷t∈T′是一個截止變遷，如果存在t′∈T′，[t′]?[t]，h(Cut([t′]))=h(Cut([t]))或h(Cut([t]))=M0.

展開圖的有限前綴(用β表示)，通過移去所有截止變遷及其后繼庫所、變遷而得到。圖1所示是一個關(guān)于某工廠加工兩個零件的Petri網(wǎng)建模及其展開的簡單例子。

庫所r1，r2分別代表零件加工過程中要使用的兩個工具R1，R2，庫所p1，p3分別代表零件A、B處于待加工狀態(tài)，庫所p2代表零件A的加工占用了工具R1，庫所p4代表零件B的加工占用了工具R2.從展開圖中，可以較容易的看出，如果同時開始加工兩個零件，系統(tǒng)將到達狀態(tài)(p2，p4)，無法繼續(xù)加工。

圖1　Petri網(wǎng)展開實例

2基于展開圖法的控制器設(shè)計

利用展開圖法進行狀態(tài)空間的搜索能有效避免狀態(tài)空間爆炸問題，但優(yōu)勢是相對的，如果Petri網(wǎng)是低并發(fā)的，利用展開圖法的效果則不是很明顯，如果Petri網(wǎng)是高度并發(fā)的，則其展開圖的規(guī)模要遠小于其可達圖，優(yōu)勢相對明顯。

下面針對禁止狀態(tài)問題，利用展開圖法設(shè)計出原網(wǎng)上等價的控制結(jié)構(gòu)。所謂禁止狀態(tài)，就是為滿足給定的系統(tǒng)性能指標，必須禁止系統(tǒng)進入某些狀態(tài)，這些狀態(tài)就構(gòu)成了系統(tǒng)的禁止狀態(tài)，用集合F表示。

假設(shè)禁止狀態(tài)滿足可達性要求，即：如果標識M∈F，若M→M′，即標識M′是從標識M可達的，則M′∈F.

乳糖通透酶是屬于主要輔助因子超家族（MFS）的次級活性轉(zhuǎn)運蛋白（SAT）。已經(jīng)確定了胞質(zhì)開放的乳糖通透酶結(jié)構(gòu)。乳糖通透酶和β-半乳糖苷酶共同作用下可以加速乳糖分解。乳糖通透酶先將乳糖磷酸化后進入細胞內(nèi)，并在β-半乳糖苷酶的水解作用下，分解成葡萄糖和半乳糖[33]。其中，一部分葡萄糖優(yōu)先被乳酸菌代謝掉，通過EMP途徑，最終產(chǎn)生乳酸。大腸桿菌的乳糖通透酶利用其中糖和H+結(jié)合位點交替進入膜兩側(cè)的機制來催化半乳糖苷與H+的化學計量協(xié)調(diào)[34]。

定義5：控制變遷集

對于展開圖有限前綴中的標識M′，h(M′)∈F，且存在對應配置C，有Cut(C)=M′，則定義標識M′的控制變遷集：C′={t∈C|不存在t′∈C，t∈[t′]}.

從控制變遷集的定義知變遷t∈C′是并發(fā)的，下面針對展開圖有限前綴中禁止狀態(tài)標識M′，在展開圖中直接添加控制庫所達到最大容許能控。

算法2：由定義5，對于標識M′及其控制變遷集C′，其中控制變遷集包含k個變遷，則在展開圖中直接添加控制庫所pc，它的托肯數(shù)為k-1，且從pc處各添加一條弧指向控制變遷集C′中的對應變遷。對于多個標識情況，最終的控制庫所可能出現(xiàn)冗余，根據(jù)Giua等人的方法，可以通過線性規(guī)劃的方法去除冗余的控制庫所。

通過算法2得到的控制策略是最大容許能控的，證明見文獻[12].

針對圖1(b)所示的Petri網(wǎng)展開圖的有限前綴，為了使生產(chǎn)過程連續(xù)進行，可得到一個禁止狀態(tài)為M(p2)+M(p4)=2，即F=(p2，p4)，在展開圖中對應的標識為(p2，p4)，則根據(jù)算法2，得到圖2所示的控制策略。

目前為止得到的只是展開圖上的控制策略，考慮到展開圖和原Petri網(wǎng)的映射關(guān)系，進一步獲得原網(wǎng)上的等價控制結(jié)構(gòu)，即原網(wǎng)上的結(jié)構(gòu)型控制器。

算法3：針對算法2得到的控制策略，對展開圖中的每一控制庫所pc，t∈pc?，在原網(wǎng)中添加對應控制庫所pc，托肯數(shù)與pc中相同，并分別添加從pc到變遷h(t)的有向弧，若存在變遷t′，t

圖2　圖1的控制策略

圖3　圖1中Petri網(wǎng)滿足禁止狀態(tài)要求的結(jié)構(gòu)型控制器

對于圖2，利用算法3，可以得到如圖3所示的結(jié)構(gòu)控制器，滿足禁止狀態(tài)要求。

可以證明此控制結(jié)構(gòu)與運用庫所不變量法得到的結(jié)構(gòu)相同。

控制庫所pc的托肯數(shù)uc0=1-LM0=1，局部關(guān)聯(lián)矩陣Dc=-LDp=[-11-11]，同樣可以得到圖3中的控制器結(jié)構(gòu)。

從此例可以看出應用展開法設(shè)計控制器的優(yōu)勢，它直接在有限的展開圖上添加控制庫所，得到滿足給定禁止狀態(tài)問題的控制策略，而不需要一一檢索系統(tǒng)的所有狀態(tài)，也不需要運用系統(tǒng)的關(guān)聯(lián)矩陣，對大系統(tǒng)而言，它的關(guān)聯(lián)矩陣維數(shù)是非常大的。這也是基于可達圖的控制策略最迫切需要解決的問題。算法3在算法2的基礎(chǔ)上進一步綜合得到原網(wǎng)上的等價控制結(jié)構(gòu)，相對于算法2的控制策略，算法3實現(xiàn)的結(jié)構(gòu)控制器能節(jié)省在線運行時的計算時間，更具意義。當然本文給出的方法目前只適用于普通安全網(wǎng)，對于更復雜的Petri網(wǎng)，例如推廣Petri網(wǎng)，由于受Petri網(wǎng)展開算法本身的制約，其實用性有待改進，但可以預見的是，一旦復雜Petri網(wǎng)的展開算法本身取得進步，本文給出的算法也就具備了實用意義。

3結(jié)論

針對一類禁止狀態(tài)問題，研究了安全Petri網(wǎng)的控制器設(shè)計問題。利用Petri網(wǎng)展開圖法，在前人的研究成果基礎(chǔ)上，根據(jù)直接添加在展開圖上的邏輯型控制器，綜合得到原網(wǎng)上等價的結(jié)構(gòu)型控制器，因為結(jié)構(gòu)型控制器具有不需要在線計算、相同的Petri網(wǎng)演化算法可同時運用于被控對象和控制器子網(wǎng)的優(yōu)點。此方法利用Petri網(wǎng)展開圖搜索狀態(tài)空間以避免狀態(tài)空間爆炸問題，對于高并發(fā)的Petri網(wǎng)效果明顯。目前的結(jié)論尚只適用于變遷完全可控的安全網(wǎng)，未來可將本文的結(jié)論推廣至更一般的Petri網(wǎng)，且希望利用展開原理解決存在不可控變遷的情況下控制器的設(shè)計問題。進一步，能否在本文的算法基礎(chǔ)上，解決基于Petri網(wǎng)的離散事件系統(tǒng)活性控制器[14-15]設(shè)計問題。

參考文獻：

[1]LIZW，WUNQ，ZHOUMC.DeadlockcontrolofautomatedmanufacturingsystemsbasedonPetrinets-Aliteraturereview[J].IEEETransSyst，Man，Cybern，C，ApplandRev，2012，42(4)：437-462.

[2]WONHAMWM.SupervisorycontrolofDiscrete-EventSystems[EB/OL].http：//www.control.toronto.edu/people/profs/Wonham/Wonham.html，2014-07-01.

[3]GIUAA.PNtechniquesforsupervisorycontrolofdiscreteeventsystems[R].InProcof1stIntWorkshoponManufandPNs，Osaka，Japan，1996：1-21.

[4]IORDACHEMV，ANTSAKLISPJ.Supervisionbasedonplaceinvariants：Asurvey[J].DiscreteEventDynamicSystems：TheoryApply，2006，16(4)：451-492.

[5]LIY，WONHAMWM.ControlofVectorDiscreate-EventSystemsI-thebaseModel[J].IEEETransactionsonAutomaticControl，1993，38(8)：1214-1227.

[6]LIZW，ZHOUMC，JENGMD.AmaximallypermissivedeadlockpreventionpolicyforFMSbasedonPetrinetsiphoncontrolandthetheoryofregions[J].IEEETrans.Autom.Sci.Eng.，2008，5(1)：182-188.

[7]LIZW，ZHOUMC.ControlofelementaryanddependentsiphonsinPetrinetsandtheirapplication[J].IEEETransSyst，Man，Cybern，A：Syst，Humans，2008，38(1)：133-148.

[8]LIZW，ZHOUMC.OnsiphoncomputationfordeadlockcontrolinaclassofPetrinets[J].IEEETransSyst，Man，Cybern，A：Syst，Humans，2008，38(3)：667-679.

[9]HOLLOWAY，KROGHLEBH.Onclosed-looplivenessofdiscrete-eventsystemsundermaximallypermissivecontrol[J].IEEETransactionsonAutomaticControl，1992，37(5)：692-697.

[10]LIZW，LIUGY，HANISCHMH.etal.DeadlockpreventionbasedonstructurereuseofPetrinetsupervisorsforflexiblemanufacturingsystems[J].IEEETrans，Syst，Man，Cybern，A：Syst，Humans，2012，42(1)：178-191.

[11]HUHS，ZHOUMC，LIZW.Livenessandratio-enforcingsupervisionofautomatedmanufacturingsystemsusingPetrinets[J].IEEETransSyst，Man，CybernA，Syst，Humans，2012，42(2)：392-403.

[12]JAVIERESPARZA，KEIJOHELJANKO.Unfoldings——Apartialorderapproachtomodelchecking[M].Springer，Berlin，2008.

[13]GIUAA，XIEXL.ControlofsafeordinaryPetrinetsusingunfolding[J].DiscreteEventDynamicSystems，2005，15(3)：349-373.

[14]CHENYF，LIZW，ZHOUMC.Mostpermissiveliveness-enforcingPetrinetsupervisorsforflexiblemanufacturingsystems[J].IntJProdRes，2012，50(22)：6357-6371.

[15]SREENIVASRS.Ontheexistenceofsupervisorypoliciesthatenforcelivenessinpartiallycontrolledfree-choicePetrinets[J].IEEETransactionsonAutomaticControl，2012，57(2)：435-449.

Controller Design for Safe Nets Based on Unfolding Graph

FANG Wei-bo，ZHAO Zhi-cheng

(School of Electronic Information Engineering，Taiyuan University of Science and Technology，

Taiyuan 030024，China)

Abstract：According to a special class of Petri net (PN)，PN unfolding-a partial-order method was used to deal with the problem about controller design for safe nets.The designed controller is maximally permissive and able to enforce the given specification.The definition about the set of control transitions was given，and an equivalent control structure of the reported controller was proposed，which was added to the unfolding net of the original one.It is easier to understand for engineers and can save the computational time on-line.

Key words：discrete event system，petri nets，safe nets，unfolding，controller