S3PR網的可達標識集算法

張秀艷,鐘春富,賈建援

(西安電子科技大學機電工程學院,陜西西安 710071)

S3PR網的可達標識集算法

張秀艷,鐘春富,賈建援

(西安電子科技大學機電工程學院,陜西西安 710071)

針對具有特定資源庫所的S3PR網,提出了一種基于P不變式和嚴格極小信標的計算可達標識集的新方法.首先計算出由P不變式所確定的不變式標識集,再通過分析嚴格極小信標中相應庫所的托肯數與其界的關系,提出判定標識是否為偽標識的判定定理,并基于判定定理有效求解偽標識集,最終通過剔除不變式標識集中的偽標識來獲得可達標識集.實驗結果表明,采用所提的方法,可以快速有效地計算出S3PR網中的可達標識集.

Petri網;嚴格極小信標;P不變式;可達標識集;死鎖控制

作為一種圖形化的數學建模工具,Petri網[1]以其能夠描述系統的并發和沖突行為,而廣泛應用于柔性制造系統的死鎖分析和控制中[2-10].利用Petri網分析死鎖問題,主要有兩種技術:結構分析[5-7]和可達圖分析[4].前一種通過添加控制庫所控制所有需控制的信標,計算簡單,但會限制系統的行為,一般來講,所獲得的Petri網控制器是次優的.而可達圖分析可以完全反應系統的狀態,通過添加控制庫所使事件與危險狀態和死狀態分離,可以獲得最優和最大行為許可的Petri網控制器.然而,隨著系統規模的增大,計算可達圖將會遇到狀態爆炸的問題.因此,如何快速計算系統的可達標識成為一個亟待解決的問題.

在眾多Petri模型中,S3PR網[2]是學者們研究柔性制造系統死鎖問題時較常用的模型.針對S3PR網,文獻[11]提出了一種無需遍歷可達圖、計算可達標識數量的方法,但并未給出具體的可達標識集.筆者提出了一種基于P不變式和嚴格極小信標求解系統的可達標識集的方法.P不變式是Petri網的結構特性,反映了網結構與可達標識之間的關系.而信標也反映了網結構特性,一個未被標記的信標就不能再被標記.因此,信標與可達標識之間也存在著一定的聯系.筆者首先計算出由P不變式所確定的不變式標識集,其中必然包含不可達標識(偽標識).基于嚴格極小信標,提出判定標識是否為偽標識的充分必要條件.最終通過剔除不變式標識集中所有的偽標識來獲得可達標識集.

1 基本定義

1.1 Petri網

Petri網[2,8]是一個四元組,N=(P,T,F,W),其中,P和T是有限非空且不相交的集合,分別代表庫所和變遷的集合;稱F?(P×T)∪(T×P)為有向弧的集合;稱W:(P×T)∪(T×P)→N N為F中弧上的權值, N N={0,1,2,…}.若?(x,y)∈F,W(x,y)=1,則稱N=(P,T,F,W)為普通網;否則,稱為一般網.

Petri網N=(P,T,F,W)的標識M是一個從P到N N的映射,其中,N N為非負整數集.令p∈P是N的庫所,稱M(p)為庫所p在標識M下的托肯數.稱為庫所子集S在N=(P,T,F,W)標識M下的托肯數總和.(N,M0)稱為網系統或標識網,M0稱為N的初始標識.

令x∈P∪T是Petri網N=(P,T,F,W)的節點.x的前置集定義為·x={y∈P∪T|(y,x)∈F}, x的后置集定義為x·={y∈P∪T|(x,y)∈F}.相應地,令X?P∪T是節點的集合,X的前置集定義為X的后置集定義為

若?p∈·t,M(p)≥W(p,t),稱變遷t∈T在標識M下是使能的,記為M[t〉.變遷t發射后產生一個新的標識M′,使得?p∈P,M′(p)=M(p)-W(p,t)+W(t,p),記為M[t〉M′.當存在一個變遷發射序列σ=t0t1…tn和標識M1,M2…,Mn,使得M[t0〉M1[t1〉M2…Mn[tn〉M″成立時,則稱標識M″是從M可達的.從M0可達的所有標識的集合稱為(N,M0)的可達集,記為R(N,M0).

令N=(P,T,F,W)是一個Petri網.N的P向量I是映射I:P→Z Z,P向量是以P為序標的列向量, Z Z是整數的集合.稱P向量I是一個P不變式,當I≠0,且IT[N]=0T.若I中所有元素均為非負的,則稱I是一個P半流.

令I為N的一個P不變式,M0是N的初始標識.則?M∈R(N,M0),ITM=ITM0.

令N=(P,T,F,W)是一個Petri網.若·S?S·成立,則稱非空集合S?P為信標;若S不包含任何其他信標作為它的真子集,則稱信標S為極小的;若·S?S·成立,則稱極小信標S是嚴格的.

1.2 S3PR網

定義1一個擁有資源的簡單順序進程系統(S3PR)N=(P0∪PA∪PR,T,F),由一系列共享資源的網復合而成,定義如下[2]:

(4)N′i是一個強連通的狀態機,N′i=(PAi∪{},Ti,Fi)是將PRi中的庫所和相關弧從Ni中移除而獲得的網.N′i的每一個回路都包含庫所.

(5)任意兩個網N′i,如果它們僅共享資源庫所,則它們是可復合的.

(6)對于資源r∈PR,稱H(r)=¨r∩PA,為r的持有者的集合;對于工序庫所p∈PA,如果¨p∩PR= {rp},則稱rp為p持有或使用的資源.

2 計算可達標識集

定義2令N=(P0∪PA∪PR,T,F)是一個S3PR網,如果M0(p0)≥1,?p0∈P0;M0(p)=0,?p∈PA;M0(r)=1,?r∈PR,則稱初始標識M0為許可的初始標識.

定義3在一個具有許可的初始標識M0的S3PR網中,稱庫所p中的最大托肯數為庫所p的界,記為bp,且bp= max{M(p)|M∈R(N,M0)}[9].

引理1令N=(P0∪PA∪PR,T,F)是一個S3PR網,對于?r∈PR,i=1,2,…,k,只有H(r)∪{r}和PAi∪{pi0}構成極小P半流的支撐[7].

引理2令N=(P0∪PA∪PR,T,F)是一個具有許可的初始標識M0的S3PR網,則?p0∈P0,bp0= M0(p0);?r∈PR,br=M0(r);?p∈PA,bp=M0(rp)[9].

定義4令X是一個矩陣,它的每一列對應著S3PR網(N,M0)的一個極小P半流.稱由X確定的標識集合,為N的不變式標識集,其中,N NP是長度為P的非負矢量.顯然,R(N,M0)?IX(N,M0).

定義5稱不變式標識集中不屬于可達集的標識為偽標識.偽標識的集合記為S(N,M0),且S(N, M0)={M|M∈IX(N,M0)∧M?R(N,M0)}.

定義6令θ是S3PR網的一個有向回路,當θ中只有資源庫所和變遷時,稱回路θ為資源變遷回路(Resource Transition Circuit,RTC).R(θ)和T(θ)分別表示回路θ中的資源庫所集合和變遷集合.若回路θ滿足((p)T(θ))·=T(θ),則稱θ為最優回路(Prefect Resource Transition Circuit,PRTC)[5].令C(R)為包含資源庫所集合R的最優回路的集合,那么C(R)中必然存在一個最優回路是C(R)中所有回路的組合,即則稱θm為包含資源庫所集合R的最大回路(Maximum Perfect Resource Transition Circuit, MPRTC).顯然,C(R)中包含惟一一個最大回路.

定理1在S3PR網中,一個最大回路和一個嚴格極小信標具有一一對應關系,已知一個最大回路θ,與其相對應的信標S為[S]={p∈PA|p=(pt),t∈T(θ)},SR=R(θ),SA=H(SR)[S],S=SA∪SR[5].

定義7令N=(P0∪PA∪PR,T,F)是一個S3PR網,N為由{}∪PAi∪Ti生成的子網,RAi= {rp∈PR|p∈PAi},為PAi使用資源的集合.如果,且?r,r1∈PR(r≠r1),對于庫所p, p1∈PAi,q,q1∈PA,p,q∈H(r),p1,q1∈H(r1),且i≠j,有以下任意一種情況成立:p1＜Nip,且q＜Njq1;p＜Nip1,且q1＜Njq,則稱兩個子網Ni和Nj是反向的[9].

定義8令N=(P0∪PA∪PR,T,F)是一個S3PR網,N為由}∪PAi∪Ti生成的子網,RAi為PAi使用資源的集合.如果資源庫所r∈PR滿足:對于?i∈{1,2,…,k},?r∈PR,有且成立;對于?i,j∈{1,2,…,k},若RAi∩RA≠?,有j成立;在兩個反向的子網Ni和Nj中,若p,p1∈PAi,q,q1∈PA,p1∈¨p∩PAip,q∈H(r),p1,q1∈H(r1),r,r1∈PR且r≠r1,有q1∈q¨∩PAj成立,則稱r為連續資源庫所,用PR表示連續資源庫所集合.

例1圖1中,且?i∈{1,2},在兩個反向的子網N1和N2中,對于p2∈¨p3∩PA1,p3∈¨p4∩PA1,有p8∈p¨9∩PA2,p7∈∩PA2成立,則p9、p10和p11都為連續資源庫所.

圖1 S3PR網(N,M)

推論1令N=(P0∪PA∪PR,T,F)為一個S3PR網,S=SA∪SR,為一個嚴格極小信標,如果?r∈PR和r∈成立,則

定理2令N=(P0∪PA∪PR,T,F)是一個具有許可的初始標識M0的S3PR網,其中,?r∈PR,r∈.令S=SA∪SR是N的一個嚴格極小信標, IX(N,M0)是N的不變式標識集.若對于M∈IX(N,M0),當且僅當M(SA)=成立,其中,bp是庫所p的界,則M是一個偽標識[9].

定義9令N=(P0∪PA∪PR,T,F)為一個S3PR網,對于i∈{1,2,…,k},?r,r1∈PR,使得,且H(r)?PAi;H(r1)?PAi,且H(r1)=(¨H(r)∩H(r)¨)∩PAi成立,則稱r和r′為一個特殊資源對,用表示特殊資源對集合.

例2在圖2中,有,{p3,p5}?PA1,,{p4}? PA1,{p4}=(¨{p3,p5}∩{p3,p5}¨)∩PA1成立,則p12和p14為一個特殊資源對.同理,p13和p15為一個特殊資源對.

引理3在S3PR網中,令r和r1為一個特殊資源對,若S=SA∪SR,為一個嚴格極小信標,其中,SR={r,r1},則

圖2 S3PR網(N,M)

定理3令N=(P0∪PA∪PR,T,F)是一個具有許可的初始標識M0的S3PR網,其中,?r∈PR, r∈.令S=SA∪SR是N的一個嚴格極小信標,IX(N,M0)是N的不變式標識集.若對于M∈IX(N, M0),當且僅當且M(H(r))=M0(r)成立,其中,r∈SR,H(r)∩SA=?,bp是庫所p的界,則M是一個偽標識.

證明 由引理3可知,SR?.令SR={r,r1}.由于H(r)∩SA=?,由引理3可得令 t∈·r,t1∈r·,由定理1可知,H(r)={(p)t},SA={t(p)}.令H(r)={p1},SA={p2},則M(p1)= M0(r)=1,且M(p2)=M0(rp2)=M0(r1)=1.由定義2可知,M0(p1)=0,M0(p2)=0.根據托肯守恒定律,可得M(rp1)=0,且M(rp2)=0,即M(r)=0,且M(r1)=0.

(1)充分性.由反證法,假定標識M從M0可達.由引理3可知,p1∈,p2∈t·.則在N的可達圖中必然存在一個可達標識M′,使得M′[t〉M或M′[t1〉M.這就意味著在N的反網N′中,在標識M下,變遷t或t1必然使能,使得M[t〉M′或M[t1〉M′.在N中,有r∈t·,r1∈.這就意味著在N的反網N′中,r∈·t, r1∈·t1成立.由于M(r)=0,M(r1)=0,則在反網N′中,在標識M下,變遷t和t1都是非使能的,這與變遷t或t1必然使能相矛盾.因此,假設不成立,標識M是不可達的.

(2)必要性.由反證法,假定M是一個偽標識,且M(p1)+M(p2)≠M0(r)+M0(r1).而M(p1)≤M0(r),M(p2)≤M0(r1)成立.由充分性的證明,可得M是可達的,這與假設相矛盾.因此,假設不成立.若M是一個偽標識,則且M(H(r))=M0(r)成立.

定理4令N=(P0∪PA∪PR,T,F)是一個具有許可的初始標識M0的S3PR網,其中,?r∈PR, r∈∪.令S=SA∪SR是N的一個嚴格極小信標,IX(N,M0)是N的不變式標識集.若對于M∈ IX(N,M0),當且僅當成立,其中,bp是庫所p的界;且M(H(r))=M0(r)成立,其中,r∈SR,H(r)∩SA=?,b p是庫所p的界;則M是一個偽標識.

證明 由定理2和定理3可證得.

定理4提出了一個具有特定類型的資源庫所的S3PR網中判別偽標識的充分必要條件.因此,可通過剔除不變式標識集中偽標識的方法來獲得可達集.計算S3PR網可達集的算法如圖3所示.

3 實驗結果

下面用一個柔性制造系統實例說明通過該算法可以快速求得系統的可達集.圖2為該柔性制造系統的S3PR網模型(N,M0).

根據定義2,M0為許可的初始標識.根據定義8和定義9,p11∈,p12,p13,p14p15∈PΔR.因此滿足算法要求.根據引理1,求得N中有7個極小P半流,其各自的支撐分別如下:p8,p9,p10}.根據定義4,求得不變式標識集IX(N,M0),其中包含108個標識.根據定理1,可得N中有兩個嚴格極小信標:S1= {p5,p12,p14},S2={p7,p13,p15}.根據定理4,IX(N,M0)中的標識M滿足M(p4)=1,且M(p5)=1的是偽標識,或滿足M(p8)=1,且M(p7)=1的是偽標識.因此,求得偽標識集S(N, M0),其中包含33個標識.最終,通過剔除偽標識,可獲得可達集R(N,M0),其中包含75個標識.這一結果與用INA軟件計算的結果是一致的,表明該算法的可行性.

圖3 計算S3PR網可達集的算法流程圖

4 結束語

筆者提出了一種利用P不變式和嚴格極小信標來計算可達集的方法.該方法適用于僅包含連續資源庫所和特殊資源對的S3PR網.而文獻[9]的方法僅適用于只包含連續資源庫所的S3PR網,該文擴大了文獻[9]方法的適用范圍.由于文中方法只適用于具有特定的資源庫所的一類S3PR網,把該方法應用到更大類型的網,將是以后研究的方向.

[1]Murata T.Petri Nets:Properties,Analysis,and Applications[J].Proceedings of the IEEE,1989,77(4):541-580.

[2]Ezpeleta J,Colom J M,Martinez J.A Petri Net Based Dead Lock Prevention Policy for Flexible Manufacturing Systems [J].IEEE Transactions on Robotics and Automation,1995,11(2):173-184.

[3]陳玉峰,李志武.安全Petri網事件分離狀態的BDD算法[J].西安電子科技大學學報,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.

[4]Chen Y F,Li Z W,Barkaoui K.Maximally Permissive Liveness-enforcing Supervisor with Lowest Implementation Cost for Flexible Manufacturing Systems[J].Information Science,2014,256:74-90.

[5]Xing K Y,Zhou M C,Wang F,et al.Resource-transition Circuits and Siphons for Deadlock Control of Automated Manufacturing Systems[J].IEEE Transactions on Systems,Man,and Cybernetics,Part A:Systems and Humans, 2011,41(1):74-84.

[6]Liu D,Li Z W,Zhou M C.A Parameterized Liveness and Ratio-enforcing Supervisor for a Class of Generalized Petri Nets[J].Automatica,2013,49(11):3167-3179.

[7]Li Z W,Zhou M C.Control of Elementary and Dependent Siphons in Petri Nets and Their Application[J].IEEE Transactions on Systems,Man,and Cybernetics,Part A:Systems and Humans,2008,38(1):133-148.

[8]李志武,周孟初.自動制造系統建模、分析與死鎖控制[M].北京:科學出版社,2009.

[9]Zhang X Y,Li Z W,Zhong C F,et al.Reachability Analysis of a Class of Petri Nets Using Place Invariants and Siphons [J].Maejo International Journal of Science and Technology,2013,7(2):278-290.

[10]Wu N Q,Zhou M C.Avoiding Deadlock and Reducing Starvation and Blocking in Automated Manufacturing Systems [J].IEEE Transactions on Robotics and Automation,2001,17(5):658-669.

[11]Chao D Y.Recursive Solution of Number of Reachable States of a Simple Subclass of FMS[J].International Journal of Systems Science,2014,45(3):702-710.

(編輯:齊淑娟)

Method to compute the reachability set of S3PR

ZHANG Xiuyan,ZHONG Chunfu,JIA Jianyuan
(School of Mechano-electronic Engineering,Xidian Univ.,Xi’an 710071,China)

This paper proposes a novel approach to computing the reachability set by using place invariants and strict minimal siphons for S3PR with specific resource places.First,the set of invariant markings is enumerated.Then a necessary and sufficient condition is developed to decide whether a marking is spurious by analyzing the relationship between the number of tokens in the corresponding places of any strict minimal siphon and their bounds.In addition,the spurious markings are calculated.Finally,the reachability set of the net is generated by removing all the spurious markings from the set of invariant markings.Experimental results show the efficiency of the proposed method.

Petri nets;strict minimal siphons;place invariants;reachability set;deadlock control

TP271+8

A

1001-2400(2015)05-0105-05

2014-04-29< class="emphasis_bold">網絡出版時間:

時間:2014-12-23

國家自然科學基金資助項目(51305325);中央高?；究蒲袠I務費專項資金資助項目(XJS15039)

張秀艷(1981-),女,講師,西安電子科技大學博士研究生,E-mail:xiuyan0224@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.018.html

10.3969/j.issn.1001-2400.2015.05.018