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

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

方偉波，趙志誠

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

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

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

收稿日期：2015-03-18

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

中圖分類號：TP301文獻(xiàn)標(biāo)志碼：A

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

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

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

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

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

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

1.1Petri網(wǎng)

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

定義1：Petri網(wǎng)

一個(gè)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?相應(yīng)的稱為變遷t的輸出庫所集合，?p={t/(t,p)∈F}稱為庫所p的輸入變遷集合，p?為庫所p的輸出變遷集合。

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

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

定義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是一個(gè)配置，如果:

(1)若t∈C，t′

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

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

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

(1)將PN中的每一個(gè)初始標(biāo)識所在的庫所復(fù)制到事件網(wǎng)中；

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

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

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

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

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

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

定義4：截止變遷

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

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

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

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

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

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

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

假設(shè)禁止?fàn)顟B(tài)滿足可達(dá)性要求，即：如果標(biāo)識M∈F，若M→M′，即標(biāo)識M′是從標(biāo)識M可達(dá)的，則M′∈F.

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

定義5：控制變遷集

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

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

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

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

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

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

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

圖2　圖1的控制策略

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

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

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

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

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

3結(jié)論

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

參考文獻(xiàn)：

[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