張秀艷,鐘春富,賈建援

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

S3PR網(wǎng)的可達(dá)標(biāo)識(shí)集算法

張秀艷,鐘春富,賈建援

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

針對(duì)具有特定資源庫(kù)所的S3PR網(wǎng),提出了一種基于P不變式和嚴(yán)格極小信標(biāo)的計(jì)算可達(dá)標(biāo)識(shí)集的新方法.首先計(jì)算出由P不變式所確定的不變式標(biāo)識(shí)集,再通過(guò)分析嚴(yán)格極小信標(biāo)中相應(yīng)庫(kù)所的托肯數(shù)與其界的關(guān)系,提出判定標(biāo)識(shí)是否為偽標(biāo)識(shí)的判定定理,并基于判定定理有效求解偽標(biāo)識(shí)集,最終通過(guò)剔除不變式標(biāo)識(shí)集中的偽標(biāo)識(shí)來(lái)獲得可達(dá)標(biāo)識(shí)集.實(shí)驗(yàn)結(jié)果表明,采用所提的方法,可以快速有效地計(jì)算出S3PR網(wǎng)中的可達(dá)標(biāo)識(shí)集.

Petri網(wǎng);嚴(yán)格極小信標(biāo);P不變式;可達(dá)標(biāo)識(shí)集;死鎖控制

作為一種圖形化的數(shù)學(xué)建模工具,Petri網(wǎng)[1]以其能夠描述系統(tǒng)的并發(fā)和沖突行為,而廣泛應(yīng)用于柔性制造系統(tǒng)的死鎖分析和控制中[2-10].利用Petri網(wǎng)分析死鎖問(wèn)題,主要有兩種技術(shù):結(jié)構(gòu)分析[5-7]和可達(dá)圖分析[4].前一種通過(guò)添加控制庫(kù)所控制所有需控制的信標(biāo),計(jì)算簡(jiǎn)單,但會(huì)限制系統(tǒng)的行為,一般來(lái)講,所獲得的Petri網(wǎng)控制器是次優(yōu)的.而可達(dá)圖分析可以完全反應(yīng)系統(tǒng)的狀態(tài),通過(guò)添加控制庫(kù)所使事件與危險(xiǎn)狀態(tài)和死狀態(tài)分離,可以獲得最優(yōu)和最大行為許可的Petri網(wǎng)控制器.然而,隨著系統(tǒng)規(guī)模的增大,計(jì)算可達(dá)圖將會(huì)遇到狀態(tài)爆炸的問(wèn)題.因此,如何快速計(jì)算系統(tǒng)的可達(dá)標(biāo)識(shí)成為一個(gè)亟待解決的問(wèn)題.

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

1 基本定義

1.1 Petri網(wǎng)

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

Petri網(wǎng)N=(P,T,F,W)的標(biāo)識(shí)M是一個(gè)從P到N N的映射,其中,N N為非負(fù)整數(shù)集.令p∈P是N的庫(kù)所,稱M(p)為庫(kù)所p在標(biāo)識(shí)M下的托肯數(shù).稱為庫(kù)所子集S在N=(P,T,F,W)標(biāo)識(shí)M下的托肯數(shù)總和.(N,M0)稱為網(wǎng)系統(tǒng)或標(biāo)識(shí)網(wǎng),M0稱為N的初始標(biāo)識(shí).

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

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

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

令I(lǐng)為N的一個(gè)P不變式,M0是N的初始標(biāo)識(shí).則?M∈R(N,M0),ITM=ITM0.

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

1.2 S3PR網(wǎng)

定義1一個(gè)擁有資源的簡(jiǎn)單順序進(jìn)程系統(tǒng)(S3PR)N=(P0∪PA∪PR,T,F),由一系列共享資源的網(wǎng)復(fù)合而成,定義如下[2]:

(4)N′i是一個(gè)強(qiáng)連通的狀態(tài)機(jī),N′i=(PAi∪{},Ti,Fi)是將PRi中的庫(kù)所和相關(guān)弧從Ni中移除而獲得的網(wǎng).N′i的每一個(gè)回路都包含庫(kù)所.

(5)任意兩個(gè)網(wǎng)N′i,如果它們僅共享資源庫(kù)所,則它們是可復(fù)合的.

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

2 計(jì)算可達(dá)標(biāo)識(shí)集

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

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

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

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

定義4令X是一個(gè)矩陣,它的每一列對(duì)應(yīng)著S3PR網(wǎng)(N,M0)的一個(gè)極小P半流.稱由X確定的標(biāo)識(shí)集合,為N的不變式標(biāo)識(shí)集,其中,N NP是長(zhǎng)度為P的非負(fù)矢量.顯然,R(N,M0)?IX(N,M0).

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

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

定理1在S3PR網(wǎng)中,一個(gè)最大回路和一個(gè)嚴(yán)格極小信標(biāo)具有一一對(duì)應(yīng)關(guān)系,已知一個(gè)最大回路θ,與其相對(duì)應(yīng)的信標(biāo)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)是一個(gè)S3PR網(wǎng),N為由{}∪PAi∪Ti生成的子網(wǎng),RAi= {rp∈PR|p∈PAi},為PAi使用資源的集合.如果,且?r,r1∈PR(r≠r1),對(duì)于庫(kù)所p, p1∈PAi,q,q1∈PA,p,q∈H(r),p1,q1∈H(r1),且i≠j,有以下任意一種情況成立:p1＜Nip,且q＜Njq1;p＜Nip1,且q1＜Njq,則稱兩個(gè)子網(wǎng)Ni和Nj是反向的[9].

定義8令N=(P0∪PA∪PR,T,F)是一個(gè)S3PR網(wǎng),N為由}∪PAi∪Ti生成的子網(wǎng),RAi為PAi使用資源的集合.如果資源庫(kù)所r∈PR滿足:對(duì)于?i∈{1,2,…,k},?r∈PR,有且成立;對(duì)于?i,j∈{1,2,…,k},若RAi∩RA≠?,有j成立;在兩個(gè)反向的子網(wǎng)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為連續(xù)資源庫(kù)所,用PR表示連續(xù)資源庫(kù)所集合.

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

圖1 S3PR網(wǎng)(N,M)

推論1令N=(P0∪PA∪PR,T,F)為一個(gè)S3PR網(wǎng),S=SA∪SR,為一個(gè)嚴(yán)格極小信標(biāo),如果?r∈PR和r∈成立,則

定理2令N=(P0∪PA∪PR,T,F)是一個(gè)具有許可的初始標(biāo)識(shí)M0的S3PR網(wǎng),其中,?r∈PR,r∈.令S=SA∪SR是N的一個(gè)嚴(yán)格極小信標(biāo), IX(N,M0)是N的不變式標(biāo)識(shí)集.若對(duì)于M∈IX(N,M0),當(dāng)且僅當(dāng)M(SA)=成立,其中,bp是庫(kù)所p的界,則M是一個(gè)偽標(biāo)識(shí)[9].

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

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

引理3在S3PR網(wǎng)中,令r和r1為一個(gè)特殊資源對(duì),若S=SA∪SR,為一個(gè)嚴(yán)格極小信標(biāo),其中,SR={r,r1},則

圖2 S3PR網(wǎng)(N,M)

定理3令N=(P0∪PA∪PR,T,F)是一個(gè)具有許可的初始標(biāo)識(shí)M0的S3PR網(wǎng),其中,?r∈PR, r∈.令S=SA∪SR是N的一個(gè)嚴(yán)格極小信標(biāo),IX(N,M0)是N的不變式標(biāo)識(shí)集.若對(duì)于M∈IX(N, M0),當(dāng)且僅當(dāng)且M(H(r))=M0(r)成立,其中,r∈SR,H(r)∩SA=?,bp是庫(kù)所p的界,則M是一個(gè)偽標(biāo)識(shí).

證明 由引理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.根據(jù)托肯守恒定律,可得M(rp1)=0,且M(rp2)=0,即M(r)=0,且M(r1)=0.

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

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

定理4令N=(P0∪PA∪PR,T,F)是一個(gè)具有許可的初始標(biāo)識(shí)M0的S3PR網(wǎng),其中,?r∈PR, r∈∪.令S=SA∪SR是N的一個(gè)嚴(yán)格極小信標(biāo),IX(N,M0)是N的不變式標(biāo)識(shí)集.若對(duì)于M∈ IX(N,M0),當(dāng)且僅當(dāng)成立,其中,bp是庫(kù)所p的界;且M(H(r))=M0(r)成立,其中,r∈SR,H(r)∩SA=?,b p是庫(kù)所p的界;則M是一個(gè)偽標(biāo)識(shí).

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

定理4提出了一個(gè)具有特定類型的資源庫(kù)所的S3PR網(wǎng)中判別偽標(biāo)識(shí)的充分必要條件.因此,可通過(guò)剔除不變式標(biāo)識(shí)集中偽標(biāo)識(shí)的方法來(lái)獲得可達(dá)集.計(jì)算S3PR網(wǎng)可達(dá)集的算法如圖3所示.

3 實(shí)驗(yàn)結(jié)果

下面用一個(gè)柔性制造系統(tǒng)實(shí)例說(shuō)明通過(guò)該算法可以快速求得系統(tǒng)的可達(dá)集.圖2為該柔性制造系統(tǒng)的S3PR網(wǎng)模型(N,M0).

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

圖3 計(jì)算S3PR網(wǎng)可達(dá)集的算法流程圖

4 結(jié)束語(yǔ)

筆者提出了一種利用P不變式和嚴(yán)格極小信標(biāo)來(lái)計(jì)算可達(dá)集的方法.該方法適用于僅包含連續(xù)資源庫(kù)所和特殊資源對(duì)的S3PR網(wǎng).而文獻(xiàn)[9]的方法僅適用于只包含連續(xù)資源庫(kù)所的S3PR網(wǎng),該文擴(kuò)大了文獻(xiàn)[9]方法的適用范圍.由于文中方法只適用于具有特定的資源庫(kù)所的一類S3PR網(wǎng),把該方法應(yīng)用到更大類型的網(wǎng),將是以后研究的方向.

[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網(wǎng)事件分離狀態(tài)的BDD算法[J].西安電子科技大學(xué)學(xué)報(bào),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]李志武,周孟初.自動(dòng)制造系統(tǒng)建模、分析與死鎖控制[M].北京:科學(xué)出版社,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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-12-23

國(guó)家自然科學(xué)基金資助項(xiàng)目(51305325);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(XJS15039)

張秀艷(1981-),女,講師,西安電子科技大學(xué)博士研究生,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