針對α網的最優線性約束轉換方法

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

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

針對α網的最優線性約束轉換方法

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

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

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

Petri網;離散事件系統;禁止狀態;不可控變遷

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

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

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

1 基礎知識

1.1 Petri網

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

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

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

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

1.2 線性約束

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

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

定義2給定一個Petri網系統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)表示只有不可控變遷發射下,從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網系統N=(P,T,F,m0)和一個廣義互斥約束(w,k):m(ps)≤k,則該系統的不可控影響子網可表示為Nw∶=(Pw,Tw,Fw),其中,Pw是存在連向ps的不可控路徑的全部庫所的集合,Tw是包含在連向ps的不可控路徑內的全部變遷的集合,Fw=F ∩((Pw×Tw)∪(Tw×Pw))[7].

定義5一個無環普通Petri網N=(P,T,F)稱為是α網,當且僅當滿足下列條件:網中有且僅有一個庫所沒有輸出變遷,即只有一個匯庫所.每個變遷有且只有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.該轉換即為最優轉換[9].

2.2 最優約束轉換算法

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

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

算法1線性約束轉換.

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

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

根據定義2和4,得到不可控影響子網及禁止庫所集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網N=(P,T,F)如圖1所示,P={p1-p7},Tu={t1-t3},給定初始約束條件是(w,k):m(p1)≤k.

圖1 含有不可控變遷的Petri網

根據算法1和圖1,初始時禁止庫所集集合Ω′={{p1}},Ω=?,由于Ω′≠?,所以對初始禁止庫所集Pf0={p1}進行轉換,經過不可控變遷t1,Pf0轉換成了集合B1={p1,p2}與集合B2={p1,p3},因為·B1-B·1≠?,·B2-B2·≠?,所以Ω′={{p1,p2},{p1,p3}},Ω=?.繼續判斷得到的Ω′≠?,對Ω′中的禁止庫所集進行轉換.經過不可控變遷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}}.經過判斷Ω′仍然不等于空集,繼續進行轉換.經過不可控變遷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,k),變遷t的權值定義為

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

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

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

(2)Aw,k=A∨(W).首先,Aw,k?A∨(W),根據算法轉換,對于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經過不可控變遷的實施,產生的最終標識的最大值定義為由于α網的結構特殊性很顯然,經算法1進行約束轉換后的∨(W)中必定存在一條約束所以,f(m)≤wim.也就是說,線性約束(w,k)中的允許標識包含于“邏輯或”的約束∨(W)中.故Aw,k?A∨(W).

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

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

3 結束語

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

[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">網絡出版時間:

時間:2014-12-23

浙江省杰出青年基金資助項目(LY15F030003,R14F020001);國家自然科學基金資助項目(61472361);浙江省科技計劃資助項目(2015C31064);浙江省新型網絡標準與應用技術重點實驗室資助項目(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