馬子玥,童 音
(西安電子科技大學(xué) 機(jī)電工程學(xué)院,陜西 西安 710071)
?
采用基本標(biāo)識圖的Petri網(wǎng)控制策略
馬子玥,童 音
(西安電子科技大學(xué) 機(jī)電工程學(xué)院,陜西 西安 710071)
提出了一種基于基本標(biāo)識圖的Petri網(wǎng)的在線監(jiān)督控制策略.首先根據(jù)原Petri網(wǎng)的初始標(biāo)識與變遷的可控性,建立基本標(biāo)識圖,通過求解整數(shù)規(guī)劃將其中節(jié)點(diǎn)標(biāo)記為合法或弱非法標(biāo)識.之后基于標(biāo)記的基本標(biāo)識圖對Petri網(wǎng)中的可控變遷進(jìn)行在線控制,從而防止系統(tǒng)到達(dá)非法標(biāo)識.該控制策略能夠避免可達(dá)圖的窮舉計(jì)算,具有良好的效率.
Petri網(wǎng);監(jiān)督控制;基本標(biāo)識
由文獻(xiàn)[1]提出的監(jiān)督控制理論是離散事件系統(tǒng)建模與控制的重要方法.在監(jiān)督控制理論中,其控制器的設(shè)計(jì)目標(biāo)為防止系統(tǒng)進(jìn)入某些非法狀態(tài).早期監(jiān)督控制理論主要針對自動機(jī)模型.在自動機(jī)模型中進(jìn)行控制相對較為簡單,可通過迭代算法將由不可控事件指向非法狀態(tài)的狀態(tài)標(biāo)記為弱非法狀態(tài),最后在迭代完成之后刪除所有的非法狀態(tài)和弱非法狀態(tài)就得到了所期望的閉環(huán)控制系統(tǒng).
Petri網(wǎng)是一類廣泛使用的離散事件系統(tǒng)模型,具有良好的建模能力.由于Petri網(wǎng)的演化狀態(tài)是由網(wǎng)結(jié)構(gòu)和標(biāo)識共同表示,從而避免了狀態(tài)爆炸問題[2-16].然而,Petri網(wǎng)中的監(jiān)督控制問題更為復(fù)雜,因?yàn)橹赶蚍欠?biāo)識的變遷在其他正常情況下可能仍然在使用,因此不能通過簡單的刪除變遷來實(shí)現(xiàn)控制目的.對于某些特殊問題可以采用信標(biāo)分析[2-5]、求解許可集合[6-10]、子網(wǎng)特征分析[11]以及筆者之前工作中提出的拓展廣義互斥約束控制器[12]來解決,但是對于一般性問題沒有很好的解決方案.通常情況下基于區(qū)域理論的控制策略[13-14]需要列舉Petri網(wǎng)系統(tǒng)的所有可達(dá)狀態(tài),因此不可避免地遇到狀態(tài)爆炸問題.
在解決Petri網(wǎng)系統(tǒng)的診斷問題過程中,文獻(xiàn)[15-16]中提出了構(gòu)建基本標(biāo)識圖和壓縮一致標(biāo)識來提升診斷效率的策略.這一策略將系統(tǒng)的可達(dá)狀態(tài)用一組稱作基本標(biāo)識的狀態(tài)來進(jìn)行表示.筆者提出了一種基于基本標(biāo)識圖的Petri網(wǎng)在線控制策略,通過構(gòu)建基本標(biāo)識圖來對系統(tǒng)的狀態(tài)數(shù)進(jìn)行壓縮,在此基礎(chǔ)上通過求解線性規(guī)劃將基本標(biāo)識劃分為許可基本標(biāo)識與非許可基本標(biāo)識,從而實(shí)現(xiàn)控制目標(biāo).
一個Petri網(wǎng)N可由四元組N=(P, T, Cpre, Cpost)表示,其中P與T分別是m個庫所與n個變遷的集合,Cpre與Cpost分別為維度為 m× n、元素為非負(fù)整數(shù)的矩陣,分別稱為N的輸入矩陣與輸出矩陣.矩陣 C= Cpost- Cpre,是一個以 P× T為序標(biāo)的整數(shù)矩陣,稱為關(guān)聯(lián)矩陣.變遷t的輸入庫所的集合記為·t= {p∈ P| Cpre(p, t)> 0},輸出庫所集合記為 t·= {p∈ P| Cpost(p, t)> 0}.
Petri網(wǎng)N=(P, T, Cpre, Cpost)的標(biāo)識M是一個m維非負(fù)整數(shù)列向量.N, M0稱為初始化的網(wǎng)系統(tǒng),M0稱為N的初始標(biāo)識.變遷t在標(biāo)識M下是使能的若 M≥ Cpre(·, t),記作 M[t.若變遷t在M下使能,t的發(fā)射將會使得系統(tǒng)到達(dá)新的標(biāo)識 M′= M+ C(·, t)= M+ Cpost(·, t)- Cpre(·, t),記作 M[tM′.若從M開始 M[t1M1[t2M2…[tnMn成立,則稱標(biāo)識Mn從標(biāo)識M可達(dá),記作 M[σMn,σ= t1t2…tn.所有從M可達(dá)的標(biāo)識記為R(N, M).初始化的網(wǎng)系統(tǒng)N, M0的可達(dá)集合記為R(N, M0).
Petri網(wǎng)中的變遷集合T可以劃分為可控變遷集合Tc與不可控變遷集合Tu,其中的元素個數(shù)分別記為nc與nu.換言之,一個不可控變遷 tu∈ Tu在M下使能時,tu總是可以發(fā)射而不能由外部控制器阻止.
廣義互斥約束(Generalized Mutual Exclusion Constraint,GMEC)是一個二元組(w, k),其中w是m維整數(shù)列向量,k為整數(shù).它定義了一組集合 S(w, k)= {M| wT·M≤ k}.拓展的廣義互斥約束是一個二元組(W, k),其中W是 m×r 維整數(shù)矩陣,k為r維整數(shù)列向量.其定義了一組集合 S(W, k)= {M| WT·M≤ k}.

定義2 給定標(biāo)識M和可控變遷t,其解釋向量幾何Y(M,t)定義為nc維向量的集合[15]:
Y(M, t)=yσ|σ∈Σ(M, t) .
定義3 給定標(biāo)識M和可控變遷t,其最小解釋向量集合Ymin(M,t)定義為Y(M, t)中最小元素組成的集合[15].
最小解釋向量的物理含義為: 在標(biāo)識M1下,若通過發(fā)射不可控制變遷到達(dá)某個標(biāo)識M2且可控變遷t在M2下使能,那么所發(fā)射的不可控變遷序列σ所對應(yīng)的發(fā)射向量yσ必然不小于Ymin(M1, t)中的任意元素.
假設(shè)1 系統(tǒng)中的所有庫所與不可控變遷不構(gòu)成環(huán).
系統(tǒng)中不包括不可控環(huán)路這一假設(shè)具有現(xiàn)實(shí)意義.若現(xiàn)實(shí)系統(tǒng)中有不可控制的環(huán)路存在,則一旦環(huán)路使能,會不可控制地消耗或產(chǎn)出資源(取決于環(huán)路增益的正負(fù)性),這樣的系統(tǒng)通常是不穩(wěn)定的.
在滿足上述假設(shè)的情況下,給定Petri網(wǎng)N、可控/不可控變遷集合Tc/Tu以及標(biāo)識M,最小解釋向量集合Ymin(M, t)可以通過針對關(guān)聯(lián)矩陣變換的操作實(shí)現(xiàn)[15].為簡化問題,考慮不可控子網(wǎng)中不包含逆向沖突結(jié)構(gòu),在該情況下任意Ymin(M, t)只包含惟一元素[15].
定理1 當(dāng)滿足假設(shè)1時,對任意yσ∈Ymin(M1,t),必然存在至少一個對應(yīng)的發(fā)射序列σ滿足 M1[σM2[t.
證明 因?yàn)椴豢煽刈冞w組成的子網(wǎng)是無環(huán)的,若存在yσ≥0滿足狀態(tài)方程 M1+ C y≥ 0,則必然存在某個對應(yīng)的發(fā)射序列σ在M下是使能的.
在此基礎(chǔ)上通過下述算法生成其基本標(biāo)識圖.
算法1 基本標(biāo)識圖的生成.
輸出: 基本標(biāo)識圖B=(V, E).
步驟1 令V={(M0, 0)},其中0為標(biāo)記位.
步驟2 若V中存在標(biāo)記位為0的元素(M, 0),則:





步驟3 刪除每個頂點(diǎn)的標(biāo)記位.
結(jié)束: 輸出B=(V, E).
定義5 給定Petri網(wǎng)N、可控/不可控變遷集合Tc/Tu,標(biāo)識M的不可控標(biāo)識集合定義為
Ru(M)=M′|M[t1t2…tsM′, t1, t2, …, ts∈Tu.
證明 由基本標(biāo)識圖的構(gòu)造過程可知,y1是M0下t1的最小解釋向量.根據(jù)定理1,存在相應(yīng)的發(fā)射序列σ1滿足 M0[σ1M1.同理,可推知對陳述中的任意Mi都存在相應(yīng)的發(fā)射序列σi滿足 Mi[σi+1Mi+1.因此,Ms是可達(dá)的,故Ru(Ms)中的標(biāo)識均可達(dá).

M0[σ1t1M1[σ2t2M2…Ms-1[σstsMs[σs+1M .



對于實(shí)際物理系統(tǒng),某些狀態(tài)是不希望到達(dá)的(例如緩存溢出或死鎖等狀態(tài)).這些狀態(tài)對應(yīng)于Petri網(wǎng)模型中的某些標(biāo)識,被稱為非法標(biāo)識.考慮非法標(biāo)識由一組拓展的廣義互斥約束(W, k)表示,即非法標(biāo)識集合F定義為 F= {M| WT·M≤ k}.
定義6 若M∈F,則M被稱為非法標(biāo)識.若Ru(M)∩ F ≠ ?,則M被稱為弱非法標(biāo)識.
根據(jù)定義,非法標(biāo)識同時也是弱非法標(biāo)識.若系統(tǒng)處于某個弱非法標(biāo)識,則存在某個由不可控制變遷組成的發(fā)射序列使得系統(tǒng)到達(dá)非法標(biāo)識.由于這一發(fā)射序列是不可阻止的,因此防止系統(tǒng)進(jìn)入非法標(biāo)識集合F控制的目標(biāo)是防止系統(tǒng)到達(dá)某個弱非法標(biāo)識.
證明 若M是非法標(biāo)識,則根據(jù)定理3,基本標(biāo)識圖B中必然存在路徑 M0- (y1, t1)- M1- (y2, t2)- …- (ys, ts)- Ms,M∈ Ru(Ms).根據(jù)定義6,Ms是弱非法標(biāo)識.
證明 用反證法.假設(shè)B中存在路徑M0-(y1, t1)-M1-(y2, t2)-…-(ys, ts)-Ms且Ms是非法標(biāo)識.根據(jù)定理2,存在發(fā)射序列σ滿足 M0[σMs且 σTc= t1t2…ts.因?yàn)镸s是弱非法標(biāo)識,存在非法標(biāo)識 M∈ Ru(Ms),因此 Ms[σ′M,σ σ′ 是一個發(fā)射序列滿足 M0[σ σ′M 且t1t2…ts,與題設(shè)矛盾.因此Ms一定不是非法標(biāo)識.
定理6 一個基本標(biāo)識M是弱非法標(biāo)識當(dāng)且僅當(dāng)以下整數(shù)規(guī)劃問題存在可行解:
基于以上分析,以下的算法2可實(shí)現(xiàn)對系統(tǒng)的在線控制.
算法2 在線控制策略設(shè)計(jì).
輸出: 在線控制許可集合Cpermit.
步驟1 判斷M0是否是弱非法標(biāo)識.若M0是弱非法標(biāo)識,則退出.
步驟2 計(jì)算基本標(biāo)識圖B=(V, E),并標(biāo)記其中的弱非法標(biāo)識頂點(diǎn).
步驟3 令當(dāng)前基本標(biāo)識Mc=M0.
步驟4 令Cpermit=Tc.
步驟5 對所有可控變遷t∈Tc,檢查二元組(Mc, t):
若B中存在M滿足Mc-(·, t)-M且M是弱非法標(biāo)識,則令Cpermit:=Cpermit{t}.
步驟6 輸出控制策略Cpermit并等待; //Cpermit集合中的變遷為允許發(fā)射的變遷.
步驟7 當(dāng)觀察到某一可控變遷t發(fā)生時,更新當(dāng)前基本標(biāo)識Mc:=Mc+C y+C(·, t),其中 Ymin(M, t)= {y}.
步驟8 返回步驟4.
算法2運(yùn)行時首先通過求解定理6中的整數(shù)規(guī)劃問題判斷初始標(biāo)識M0是否為弱非法標(biāo)識.若M0為弱非法標(biāo)識,則不存在可行的控制策略,算法中止.步驟2建立基本標(biāo)識圖并通過求解定理6中的整數(shù)規(guī)劃問題,找出V中的弱非法標(biāo)識頂點(diǎn).之后控制器在線依次檢查每個可控變遷t發(fā)射后的情況.若B中存在M滿足 M0- (y1, t1)- M1且M1是弱非法節(jié)點(diǎn),而且允許t1發(fā)射,則系統(tǒng)可能到達(dá)M1這一弱非法標(biāo)識,從而進(jìn)一步到達(dá)某一非法狀態(tài)F.因此,從Cpermit中刪除t1,表明在初始狀態(tài)下通過外部控制器阻止t1發(fā)射(無論t1是否使能).反之,若經(jīng)t1到達(dá)的M1為合法標(biāo)識,則說明允許t1發(fā)射后系統(tǒng)無論如何經(jīng)過不可控制的變遷序列均不會到達(dá)非法標(biāo)識,故在Cpermit中保留t1.對所有變遷進(jìn)行檢查后系統(tǒng)輸出當(dāng)前的控制策略Cpermit,并停留在步驟6等待.每當(dāng)控制器監(jiān)測到某個可控變遷t發(fā)射的時候,步驟7對系統(tǒng)當(dāng)前狀態(tài)進(jìn)行更新,之后重新執(zhí)行步驟4~6,更新當(dāng)前的控制策略.

圖1 包含3條生產(chǎn)線的自動制造系統(tǒng)
考慮圖1中包含3條生產(chǎn)線的自動制造系統(tǒng).p1代表Idle庫所,其中生產(chǎn)線Ⅰ為 p2t3p3t4p4負(fù)責(zé)生產(chǎn)半成品A.另兩條生產(chǎn)線Ⅱ: p5t4p6t5p7t6p8和生產(chǎn)線Ⅲ: p5t7p9t7p10t9p11生成半成品B,并與生產(chǎn)線Ⅰ的半成品A進(jìn)行組裝后得到產(chǎn)品進(jìn)入庫房.系統(tǒng)中可控變遷集合為{t1, t4, t7, t10, t11},其余為不可控變遷.假設(shè)系統(tǒng)的容量為r,即系統(tǒng)的初始標(biāo)識 M0= rp1.

圖2 圖1中Petri網(wǎng)的基本標(biāo)識圖B(局部)
考慮系統(tǒng)容量r為4的情況,即系統(tǒng)的初始標(biāo)識M0=4p1.由于系統(tǒng)容量限制,庫所p8中的零件數(shù)應(yīng)不超過2,即合法標(biāo)識M滿足 M(p8)≤ 2.因此,非法標(biāo)識集合F由拓展的廣義互斥約束表示為 M(p8)≥ 3.該系統(tǒng)具有 5 423 個可達(dá)狀態(tài),在此基礎(chǔ)上基于區(qū)域理論的控制器設(shè)計(jì)策略需要多次求解包含超過 50 000 個線性約束的整數(shù)規(guī)劃問題.因此,筆者采用上面提出的算法設(shè)計(jì)在線控制器.算法1構(gòu)造的基本標(biāo)識圖僅含117個基本標(biāo)識頂點(diǎn),通過求解定理6中的整數(shù)規(guī)劃(僅包含12個變量,36個約束條件)判定其中111個為合法基本標(biāo)識,6個為弱非法基本標(biāo)識.最終算法1得到一個包含117個狀態(tài)的在線控制器,其部分列于圖2.在初始狀態(tài) M0= 4p1下,由于不存在可控變遷指向弱非法基本標(biāo)識,系統(tǒng)對可控變遷的發(fā)射不進(jìn)行任何限制,即此時的控制策略 Cpermit= {t1, t4, t7, t10, t11}.當(dāng)系統(tǒng)發(fā)射t1后,系統(tǒng)狀態(tài)遷移至基本標(biāo)識 M1= 3p1+ p2+ p5,同時輸出當(dāng)前控制策略 Cpermit= {t1, t4, t7, t10, t11}.以此類推,當(dāng)控制器檢測到系統(tǒng)發(fā)射了 t1t1t4t4t1t1t4后(灰色路徑)到達(dá)基本標(biāo)識 M7= 4p2+ p5+ 3p6,而在該狀態(tài)下變遷t4指向弱非法基本標(biāo)識 M8= 4p2+ 4p6.因此,此時控制器的控制策略為阻止t4,即 Cpermit= {t1, t7, t10, t11},從而防止系統(tǒng)經(jīng)不可控變遷的發(fā)射而到達(dá)非法標(biāo)識.
最后,不同系統(tǒng)容量下的可達(dá)圖分析控制策略與基本標(biāo)識圖控制器設(shè)計(jì)策略的對比數(shù)據(jù)列于表1(測試均采用Matlab工具包).從表1可以發(fā)現(xiàn),當(dāng)系統(tǒng)容量增加時,其可達(dá)標(biāo)識數(shù)呈指數(shù)增長,使得基于可達(dá)圖的控制器設(shè)計(jì)策略代價很高.當(dāng)系統(tǒng)容量 r>8 時,可達(dá)圖的計(jì)算時間已經(jīng)超過 1 h (可達(dá)圖包含超過106個可達(dá)標(biāo)識),意味著基于可達(dá)圖的區(qū)域分析策略已經(jīng)不可行了.相反可以發(fā)現(xiàn),系統(tǒng)的基本標(biāo)識數(shù)增長緩慢,且遠(yuǎn)遠(yuǎn)小于其可達(dá)標(biāo)識數(shù).計(jì)算基本標(biāo)識圖的時間僅需計(jì)算可達(dá)圖的1%,其中求解整數(shù)規(guī)劃的計(jì)算量占總計(jì)算量約5%.因此基于基本標(biāo)識圖的控制策略可以有效地對系統(tǒng)進(jìn)行控制.

表1 不同系統(tǒng)容量下的可達(dá)圖RG與基本標(biāo)識圖B的規(guī)模
針對包含不可控變遷的Petri網(wǎng)系統(tǒng),筆者提出了一種基于基本標(biāo)識圖的在線控制策略.通過構(gòu)建基本標(biāo)識圖來對系統(tǒng)的狀態(tài)數(shù)進(jìn)行壓縮,在此基礎(chǔ)上通過求解整數(shù)規(guī)劃將基本標(biāo)識圖的頂點(diǎn)劃分為合法基本標(biāo)識和弱非法基本標(biāo)識,在線控制器與系統(tǒng)并行運(yùn)行,實(shí)時跟蹤可控變遷的發(fā)射,并阻止系統(tǒng)到達(dá)基本標(biāo)識圖中的弱非法基本標(biāo)識狀態(tài).筆者提出的控制算法與傳統(tǒng)的基于可達(dá)圖的控制器設(shè)計(jì)算法相比,由于避免了可達(dá)圖的窮舉,計(jì)算量大大減少,具有較高的效率.
[1] RAMADGE P J G, WONHAM W M. The Control of Discrete Event Systems [J]. Proceedings of IEEE, 1989, 77(1): 81-98.
[2]LI Z W, ZHOU M C. Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems[J]. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 2004, 34(1): 38-51.
[3]LI Z W, ZHOU M C, WU N Q. A Survey and Comparison of Petri Net-based Deadlock Prevention Policies for Flexible Manufacturing Systems [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2008, 38(2): 173-188.
[4]LI Z W, WU N Q, ZHOU M C. Deadlock Control of Automated Manufacturing Systems Based on Petri Nets—a Literature Review [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2012, 42(4): 437-462.
[5]張秀艷, 鐘春富, 賈建援. S3PR網(wǎng)的可達(dá)標(biāo)識集算法[J]. 西安電子科技大學(xué)學(xué)報, 2015, 42(5): 105-109.
ZHANG Xiuyan, ZHONG Chunfu, JIA Jianyuan. Method to Compute the Reachability Set of S3PR [J]. Journal of Xidian University, 2015, 42(5): 105-109.
[6]GIUA A, DICESARE F, SILVA M. Generalized Mutual Exclusion Constraints on Nets with Uncontrollable Transitions [C]//Conference Proceedings-IEEE International Conference on Systems, Man and Cybernetics. Piscataway: IEEE, 1992: 974-979.
[7]MOODY J O, ANTSAKLIS P J. Petri Net Supervisors for DES with Uncontrollable and Unobservable Transitions [J]. IEEE Transactions on Automatic Control, 2000, 45(3): 462-476.
[8]BASILE F, CORDONE R, PIRODDI L. A Branch and Bound Approach for the Design of Decentralized Supervisors in Petri Net Models [J]. Automatica, 2015, 52(2): 322-333.
[9]LUO J L, SHAO H, NONAMI K, et al. Maximally Permissive Supervisor Synthesis Based on a New Constraint Transformation Method [J]. Automatica, 2012, 48(6):1097-1101.
[10]MA Z Y, LI Z W, GIUA A. Comments on “Maximally Permissive Supervisor Synthesis Based on a New Constraint Transformation Method” [J]. Automatica, 2015, 51(1): 131-134.
[11]陳曉亮, 蔣忠遠(yuǎn), 葉劍虹. 工作流網(wǎng)的混或檢測和預(yù)防策略 [J]. 西安電子科技大學(xué)學(xué)報, 2015, 42(2): 77-83.
CHEN Xiaoliang, JIANG Zhongyuan, YE Jianhong. Confusion Detection and Prevention Policies for Workflow Nets [J]. Journal of Xidian University, 2015, 42(2): 77-83.
[12]MA Z Y, LI Z W, GIUA A. Design of Optimal Petri Net Controllers for Disjunctive Generalized Mutual Exclusion Constraints [J]. IEEE Transactions on Automatic Control, 2015, 60(7): 1774-1785.
[13]GHAFFARI A, REZG N, XIE X L. Design of a Live and Maximally Permissive Petri Net Controller Using the Theory of Regions [J]. IEEE Transactions on Robotics and Automation, 2003, 19(1): 137-142.
[14]陳玉峰, 李志武. 安全Petri網(wǎng)事件分離狀態(tài)的BDD算法 [J]. 西安電子科技大學(xué)學(xué)報, 2010, 37(1): 119-124.
CHEN Yufeng, LI Zhiwu. Computation of Marking/Transition Separation Instances for Safe Petri Nets Using BDD [J]. Journal of Xidian University, 2010, 37(1): 119-124.
[15]CABASINO M P, GIUA A, SEATZU C. Fault Detection for Discrete Event Systems Using Petri Nets with Unobservable Transitions [J]. Automatica, 2010, 46(9): 1531-1539.
[16]CABASINO M P, HADJICOSTIS C N, SEATZU C. Probabilistic Marking Estimation in Labeled Petri Nets [J]. IEEE Transactions on Automatic Control, 2015, 60(2): 528-533.
(編輯:郭 華)
Supervisor synthesis in Petri nets based on basis marking graphs
MAZiyue,TONGYin
(School of Mechano-electronic Engineering, Xidian Univ., Xi’an 710071, China)
This paper proposes a method to design an online controller based on basis marking graphs for Petri nets. According to the initial marking and the controllability of transitions, a basis marking graph is first computed whose nodes are marked as legal or weakly illegal by solving integer programming problems. Based on the marked basis reachability graph, an online transition disabling rule is computed on-time to prevent the system from reaching illegal markings by firing uncontrollable transitions. This control strategy has a high efficiency since the full enumeration of the reachability graph is avoided.
Petri net; supervisory control; basis marking
2015-11-05
時間:2016-04-01
國家自然科學(xué)基金資助項(xiàng)目(61374068, 61472295)
馬子玥(1984-),男,博士,E-mail:maziyue@gmail.com.
http://www.cnki.net/kcms/detail/61.1076.tn.20160401.1622.024.html
10.3969/j.issn.1001-2400.2016.06.012
TP271+8
A
1001-2400(2016)06-0068-06