張 麗,趙良煦,王壽光,汪成英

(浙江工商大學信息與電子工程學院,浙江杭州 310018)

針對α網(wǎng)的最優(yōu)線性約束轉換方法

張 麗,趙良煦,王壽光,汪成英

(浙江工商大學信息與電子工程學院,浙江杭州 310018)

針對不可控影響子網(wǎng)為α網(wǎng)的一類Petri網(wǎng),提出了將給定的廣義互斥約束轉換成最優(yōu)允許線性約束的方法.該方法首先獲得了該網(wǎng)的不可控影響子網(wǎng);其次,提出了轉換后的禁止庫所集集合的求解算法;最后,根據(jù)禁止庫所集集合構造了“邏輯或”形式的最大允許線性約束.并且通過一個例子,說明了該方法的有效性.

Petri網(wǎng);離散事件系統(tǒng);禁止狀態(tài);不可控變遷

在離散事件系統(tǒng)中,監(jiān)控系統(tǒng)行為使其不進入禁止狀態(tài)并滿足系統(tǒng)的性能要求是極其重要的.但是如何控制系統(tǒng)行為,避免其進入禁止狀態(tài)是一個非常棘手的問題.此類控制問題可以用線性約束方法來表示.在基于Petri網(wǎng)的離散事件系統(tǒng)監(jiān)控器設計[1-14]中,線性約束轉換問題一直是研究的重點.當Petri網(wǎng)的所有變遷都可控時,可以直接設計最優(yōu)控制器[1].但當網(wǎng)中存在不可控變遷時,根據(jù)給定的線性約束限制系統(tǒng)的行為是不夠的.這是因為不可控變遷的實施會導致合法標識集的某些狀態(tài)演變成禁止狀態(tài),即不再滿足給定的約束,致使系統(tǒng)無法滿足性能要求.因此,需通過線性約束轉換方法得到最優(yōu)允許標識集,使得限制系統(tǒng)行為在允許標識集中,從而避免系統(tǒng)進入禁止狀態(tài).目前,如何通過線性約束轉換得到允許標識集仍是一大難題.

針對含有不可控變遷的Petri網(wǎng)的線性約束轉換研究,文獻[2-4]提出了基于關聯(lián)矩陣運算的線性約束轉換方法,但是轉換后的線性約束僅僅表示了允許標識集的一個子集,即無法保證監(jiān)控器的最大允許性.文獻[5-6]在Moody提出的算法上進一步研究了約束轉換方法且提高轉換效率,但是最終得到的約束仍不是最優(yōu)解.文獻[7]針對一類子網(wǎng)提出了將給定的線性約束轉換的允許線性約束的方法,但該方法計算效率不高.文獻[8]提出了自下而上的約束轉換的方法,該方法計算效率高,但是針對的是Petri網(wǎng)中不可控變遷只有1個輸入庫所的情況.對于不可控變遷有多個輸入庫所的情況,文獻[9]提出了用“邏輯或”形式的線性約束來表示允許標識集的算法,但是該方法得到的約束并不是最大允許.此外,文獻[9]沒有準確地定義允許標識集這個概念,因此,約束轉換問題仍然沒有得到解決.所以,文中針對一類網(wǎng)研究此類問題.

筆者主要針對Petri網(wǎng)的某一類子網(wǎng)的線性約束轉換問題進行深入研究,提出了求解最大允許線性約束的方法.該方法首先根據(jù)定義獲得不可控影響子網(wǎng);其次,提出了求解轉換后禁止庫所集集合的算法;最后,根據(jù)禁止庫所集集合構造了“邏輯或”形式的最大允許線性約束.筆者主要針對不可控變遷存在多個輸入庫所的Petri網(wǎng)的某一類子網(wǎng)來進行研究,提出了最優(yōu)線性約束轉換的算法,使得系統(tǒng)監(jiān)控達到了最優(yōu)控制.

1 基礎知識

1.1 Petri網(wǎng)

一個普通Petri網(wǎng)N是一個四元組(P,T,F,m0),P和T分別稱為庫所和變遷的集合.P和T非空,有限且不相交.也就是說,P≠?,T≠?,P∩T=?.F?(P×T)∪(T×P)稱為流關系或是有向弧的集合.令x∈P∪T是Petri網(wǎng)N=(P,T,F)的節(jié)點.x的前置集x定義為x={y∈P∪T|(y,x)∈F},x的后置集x定義為x= {y∈P∪T|(x,y)∈F}.令X?P∪T是節(jié)點的集合,X的前置集定義為·X=的后置集定義為N的關聯(lián)矩陣N是一個以P×T為序標的整數(shù)矩陣.如果p是t的前置,則N(p,t)=-1;如果p是t的后置,則N(p,t)=1.則對于剩下的其他p和t,N(p,t)=0.庫所p對應的行向量稱為p的關聯(lián)向量,記做N(p,).變遷t對應的列向量稱為t的關聯(lián)向量,記做N(,t).

Petri網(wǎng)N=(P,T,F)的標識m是一個從P到N={0,1,2,…}的映射.(N,m0)稱為網(wǎng)系統(tǒng)或標識網(wǎng),m0稱為N的初始標識.一般地,用多集合符號p來表示m,其中,m(p)表示m中每一個庫所p中的托肯數(shù).稱t∈T在標識m下是使能的,當且僅當?p∈t,m(p)＞0,記為m[t〉.使能的變遷可以發(fā)射.變遷t發(fā)射后,網(wǎng)系統(tǒng)躍遷到另一個狀態(tài),產生一個新的標識m′,使得?p∈P,m′(p)=m(p)+N(p, t).在標識m下發(fā)射t到達標識m′,記為m[t〉m′.稱標識m′是從m1可達的,當且僅當存在一個變遷的發(fā)射序列γ=t1,t2,…,tn和標識m1,m2,…,mn,使得m1[t1〉m2[t2〉…mn[tn〉m′成立.在該網(wǎng)中,把從m0可達的所有標識的集合稱為(N,m0)的可達集,記為R(N,m0).

Petri網(wǎng)中,受外部控制器直接限制的變遷是可控變遷;否則,是不可控的.Tc(Tu)分別表示為可控(不可控)變遷的集合.滿足p=?的庫所稱為匯庫所,用ps表示.

Petri網(wǎng)的一條路就是它圖中的一條有向路,如果一條路上的所有變遷都是不可控的,則稱它為不可控路,一條從可控變遷t到庫所p的路,如果除t外,其他變遷都是不可控的,則稱它為內部不可控路.

1.2 線性約束

定義1廣義互斥約束(Generalized Mutual Exclusion Constraint,GMEC)是一個二元組(w,k),可表示為wm≤k,其中,w是一個從庫所集到非負整數(shù)集上的映射,即w:P→{0,1,2,…},同時也可看做是一個1×P的非負整數(shù)向量,即其第i維上的值wi等于w(pi);k∈N N.文中將廣義互斥約束簡稱為線性約束[3].

為了問題的簡化討論,以下給定的線性約束(w,k)形式都為m(ps)≤k.

定義2給定一個Petri網(wǎng)系統(tǒng)N=(P,T,F,m0)和一個廣義互斥約束(w,k),則禁止標識集Mw,k∶= {m∈M|wm＞k},合法標識集Lw,k∶={m∈R(N,m0)|wm≤k},允許標識集Aw,k∶={m∈R(N,m0)| Ru(m)?Lw,k,其中,Ru(m)表示只有不可控變遷發(fā)射下,從m可達的所有標識的集合.禁止庫所集Pf∶= {p∈Pw|w(p)≠0}[3].

定義3線性約束不等式集W∶={(w1,k),…,(wn,k)},n∈Z,“邏輯或”形式可表示為∨(W),即.其合法標識集允許標識集A∨(W)∶={m∈R(N,m0)|Ru(m)?

定義4給定一個Petri網(wǎng)系統(tǒng)N=(P,T,F,m0)和一個廣義互斥約束(w,k):m(ps)≤k,則該系統(tǒng)的不可控影響子網(wǎng)可表示為Nw∶=(Pw,Tw,Fw),其中,Pw是存在連向ps的不可控路徑的全部庫所的集合,Tw是包含在連向ps的不可控路徑內的全部變遷的集合,Fw=F ∩((Pw×Tw)∪(Tw×Pw))[7].

定義5一個無環(huán)普通Petri網(wǎng)N=(P,T,F)稱為是α網(wǎng),當且僅當滿足下列條件:網(wǎng)中有且僅有一個庫所沒有輸出變遷,即只有一個匯庫所.每個變遷有且只有1個輸出庫所.每個庫所最多只有1個輸出變遷[7].

2 線性約束轉換

2.1 可允許的約束條件

定義6當且僅當廣義互斥約束(w,k)中所有合法標識都是允許的,則該約束(w,k)是允許約束,即Lw,k?Aw,k[7].

定義7給定一個廣義互斥約束(w,k)和其允許標識集Aw,k,轉換后的“邏輯或”形式的約束∨(W)是最大允許約束,當且僅當L∨(W)=Aw,k.該轉換即為最優(yōu)轉換[9].

2.2 最優(yōu)約束轉換算法

這里主要針對不可控影響子網(wǎng)為α網(wǎng)的Petri網(wǎng)進行線性約束轉換討論.為了簡化討論,假定給定的線性約束(w,k)形式為m(ps)≤k.顯然,對于給定的線性約束,在不可控影響子網(wǎng)為α網(wǎng)的情況下,Nw中每個輸入庫所在其他庫所托肯數(shù)足夠多的情況下,經(jīng)過不可控變遷實施之后轉換的權值w(p)是一樣的,且都等于w(ps),文中假定w(ps)=1.

根據(jù)前面的定義及討論,提出了將初始線性約束轉換成“邏輯或”形式的最大允許線性約束的算法.

算法1線性約束轉換.

輸入:一個Petri網(wǎng)(N,m0),其中,N=(P,Tc∪Tu,F),初始線性約束(w,k):m(ps)≤k.

輸出:W∶={(w1,k),…,(wn,k)},其中,n∈Z.

根據(jù)定義2和4,得到不可控影響子網(wǎng)及禁止庫所集Pf0={ps}

Ω′∶={Pf0}; //Ω′表示轉換前的禁止庫所集集合

Ω∶=?; //Ω表示轉換后的禁止庫所集集合且初始為空

WHILEΩ′≠?DO //當Ω′不為空時,進行以下操作

FOR?Pf∈Ω′DO //對Ω′中任意禁止庫所集Pf

Ω′∶=Ω′Pf; //除去該禁止庫所集Pf

FOR?t∈·Pf-Pf·,t∈TuDO

FOR?p∈t DO

B∶=Pf∪{p}; //B表示禁止庫所集

IF·B-B·=?THEN

Ω∶=Ω∪{B}

ELSE

Ω′∶=Ω′∪{B}

END IF

END FOR

END FOR

END FOR

END WHILE

轉換得到Ω={Pf1,…,Pfn}

Ω中每個Pfi對應的約束(wi,k):

W∶={(w1,k),…,(wn,k)}.

2.3 實 例

例1已知一個Petri網(wǎng)N=(P,T,F)如圖1所示,P={p1-p7},Tu={t1-t3},給定初始約束條件是(w,k):m(p1)≤k.

圖1 含有不可控變遷的Petri網(wǎng)

根據(jù)算法1和圖1,初始時禁止庫所集集合Ω′={{p1}},Ω=?,由于Ω′≠?,所以對初始禁止庫所集Pf0={p1}進行轉換,經(jīng)過不可控變遷t1,Pf0轉換成了集合B1={p1,p2}與集合B2={p1,p3},因為·B1-B·1≠?,·B2-B2·≠?,所以Ω′={{p1,p2},{p1,p3}},Ω=?.繼續(xù)判斷得到的Ω′≠?,對Ω′中的禁止庫所集進行轉換.經(jīng)過不可控變遷t2,原先的B1轉變成了B3={p1,p2,p4}和B4={p1,p2,p5},B2轉變成了B5={p1,p3,p4}和B6={p1,p3,p5}.因為·B3-B3·≠?,·B4-B4·≠?,·B5-B5·=?,·B6-B6·=?,所以Ω′={{p1,p2,p4},{p1,p2,p5}},Ω={{p1,p3,p4},{p1,p3,p5}}.經(jīng)過判斷Ω′仍然不等于空集,繼續(xù)進行轉換.經(jīng)過不可控變遷t3,B3轉變成B7={p1,p2,p4,p6}和{p1,p2,p4,p7},B4轉變成B8={p1,p2,p5,p6}和{p1,p2,p5,p7}.而·B7-B7·=?,·B8-B8·=?,所以Ω′=?,Ω={{p1,p3,p4},{p1,p3,p5},{p1,p2,p4,p6},{p1,p2,p4,p7},{p1,p2,p5,p6},{p1,p2,p5,p7}}.此時,Ω′=?.轉換結束.

其禁止庫所集集合Ω′與Ω的轉變過程如下:

所以禁止庫所集集合Ω={Pf1,Pf2,Pf3,Pf4,Pf5,Pf6}={{p1,p3,p4},{p1,p3,p5},{p1,p2,p4,p6},{p1,p2,p4,p7},{p1,p2,p5,p6},{p1,p2,p5,p7}}.

因此,原始線性約束轉換成:

最終,轉換后的“邏輯或”形式的約束W={(w1,k),(w2,k),(w3,k),(w4,k),(w5,k),(w6,k)}.

定義8給定一個Petri網(wǎng)及線性約束(w,k),變遷t的權值定義為

定理1給定初始廣義約束(w,k),如果不可控影響子網(wǎng)為α網(wǎng),則根據(jù)算法1轉換后的“邏輯或”形式的線性約束W={(w1,k),…,(wn,k)}是最大允許的.

證明 根據(jù)定義7,轉換后的“邏輯或”形式的線性約束是最大允許的,當且僅當L∨(W)=Aw,k.因此,證明可從兩部分來進行,L∨(W)=A∨(W)和A∨(W)=Aw,k.假設tx為網(wǎng)中不可控變遷,tx≠?.

(1)L∨(W)=A∨(W).根據(jù)算法1,初始標識m經(jīng)過不可控變遷tx的實施,會產生最終的新的標識m′,滿足wm′≤k.根據(jù)α網(wǎng)的結構特性,顯而易見,此時不可控變遷tx的再次激發(fā),不會使wm′的值繼續(xù)增加,即wm′≤wm.也就是,(tx)≤0.由文獻[2]可知,對于?t∈Tu(t)≤0,則線性約束(w,k)是允許的.因此,轉換得到新的線性約束∨(W)都是允許約束,也就是約束中所有合法標識都是允許的,即L∨(W)?A∨(W).根據(jù)定義2和定義3,又得到A∨(W)?L∨(W),所以L∨(W)=A∨(W).

(2)Aw,k=A∨(W).首先,Aw,k?A∨(W),根據(jù)算法轉換,對于W中任意的線性約束(w′,k),都有w′≥w.因此,?(w′,k)∈W,?m,w′m≥wm.顯然,屬于A∨(W)的合法標識必然屬于Aw,k,故Aw,k?A∨(W).

其次,Aw,k?A∨(W).線性約束(w,k)中任一允許標識m經(jīng)過不可控變遷的實施,產生的最終標識的最大值定義為由于α網(wǎng)的結構特殊性很顯然,經(jīng)算法1進行約束轉換后的∨(W)中必定存在一條約束所以,f(m)≤wim.也就是說,線性約束(w,k)中的允許標識包含于“邏輯或”的約束∨(W)中.故Aw,k?A∨(W).

如上所述,最后得到L∨(W)=Aw,k,則轉換后的“邏輯或”形式的線性約束W={(w1,k),…,(wn,k)}是最大允許的.

因此,根據(jù)定理1得知,例1中的“邏輯或”形式的線性約束W={(w1,k),(w2,k),(w3,k),(w4,k),(w5,k),(w6,k)},是最大允許的.

3 結束語

在離散事件系統(tǒng)中,系統(tǒng)的監(jiān)控問題一直是研究的熱點.而線性不等式約束轉換問題仍是一大難題.針對不可控影響子網(wǎng)是α網(wǎng)的Petri網(wǎng),提出了將給定的原線性約束轉換為一組“邏輯或”形式的最大允許線性約束的算法.基于約束轉換的思想,含有不可控變遷的Petri網(wǎng)的監(jiān)控問題可以簡化為相當于變遷全部可控的Petri網(wǎng)的監(jiān)控問題,不可控變遷導致的復雜性由此降低,系統(tǒng)中的監(jiān)控問題得到了更好的控制.但文中研究的Petri網(wǎng)的較小子類,將線性約束轉換問題的研究推廣到更復雜的Petri網(wǎng)是今后研究的重點.

[1]Yamalidou E,Moody J O,Antsaklis P J,et al.Feedback Control of Petri Nets Based on Place Invariants[J]. Automatica,1996,32(1):15-28.

[2]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-467.

[3]Moody J O,Antsaklis P J.Supervisory Control of Discrete Event Systems Using Petri Nets[M].New Jersey:Kluwer Academic Publishers,1998.

[4]Moody J O,Antsaklis P J,Lemmon M.Feedback Petri Net Control Design in the Presence of Uncontrollable Transition [C]//Proceedings of the IEEE 34th Conference on Decision and Control.Piscataway:IEEE,1995:905-906.

[5]Basile F,Carbone C,Chiacchio P.Feedback Control Logic for Backward Conflict Free Choice Nets[J].IEEE Transactions on Automatic Control,2007,52(3):387-400.

[6]Basile F,Chiacchio P,Giua A.Suboptimal Supervisory Control of Petri Nets in Presence of Uncontrollable Transitions via Monitor Places[J].Automatica,2006,42(6):995-1004.

[7]Luo J L,Wu W M,Su H Y,et al.Supervisor Synthesis for Enforcing a Class of Generalized Mutual Exclusion Constraints on Petri Nets[J].IEEE Transactions on Systems,Man,and Cybernetics-Part A Systems and Humans, 2009,39(6):1237-1246.

[8]Wang S,Wang C,Zhou M.Design of Optimal Monitor-based Supervisors for a Class of Petri Nets with Uncontrollable Transitions[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2013,43(5):1248-1255.

[9]Luo J,Nonami K,Jin F.Maximally Permissive Supervisor Synthesis Based on a New Constraint Transformation Method[J].Automatica,2012,48(6):1097-1101.

[10]Luo J,Nonami K.Approach for Transforming on Linear Constraints on Petri Nets[J].IEEE Transactions on Automatic Control,2011,56(11):2751-2765.

[11]Wang S,Wang C,Yu Y.Comments on“Siphon-based Deadlock Prevention Policy for Flexible Manufacturing Systems”[J].IEEE Transactions on Systems,Man,and Cybernetics-Part A Systems and Humans,2011,41(2):338-340.

[12]Wang S,Wang C,Zhou M.Controllability Conditions of Resultant Siphons in a Class of Petri Nets[J]IEEE Transactions on Systems,Man,and Cybernetics-Part A Systems and Humans,2012,42(5):1206-1215.

[13]Basile F,Cordone R,Piroddi L.Compact Supervisors for General Constraint Enforcement in Petri Net Models with Uncontrollable Transitions[C]//European Control Conference.Piscataway:IEEE,2013:143-148.

[14]王安榮,李志武.基本信標計算的一種快速算法[J].西安電子科技大學學報,2008,35(4):632-638. Wang Anrong,Li Zhiwu.Effective Algorithm for Obtaining a Set of Elementary Siphons[J].Journal of Xidian University,2008,35(4):632-638.

(編輯:齊淑娟)

Optimal linear constraint transformation method forα-nets

ZHANG Li,ZHAO Liangxu,WANG Shouguang,WANG Chengying
(School of Information&Electronic Eng.,Zhejiang Gongshang Univ.,Hangzhou 310018,China)

For a class of Petri nets whose uncontrollable subnets areα-nets,this paper proposes a method to transform a given generalized mutual exclusion constraint into an optimal admissible one.Firstly,the uncontrollable subnets are obtained.Secondly,an algorithm for synthesizing the transformed sets of forbidden places is proposed.Lastly,according to the sets of forbidden places,the disjunction of admissible linear constraints which is maximally permissive is constructed.An example is provided to illustrate the efficiency of the proposed method.

Petri nets;discrete event systems;forbidden states;uncontrolled transitions

TP271+.8;TP301

A

1001-2400(2015)05-0183-05

2014-06-03< class="emphasis_bold">網(wǎng)絡出版時間:

時間:2014-12-23

浙江省杰出青年基金資助項目(LY15F030003,R14F020001);國家自然科學基金資助項目(61472361);浙江省科技計劃資助項目(2015C31064);浙江省新型網(wǎng)絡標準與應用技術重點實驗室資助項目(2013E10012)

張 麗(1989-),女,浙江工商大學碩士研究生,E-mail:wsg5000@hotmail.com.

趙良煦(1959-),男,副教授,E-mail:hzbz@zjgsu.edu.cn.

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

10.3969/j.issn.1001-2400.2015.05.030