针对α网的最优线性约束转换方法

张 丽,赵良煦,王寿光,汪成英

(浙江工商大学信息与电子工程学院,浙江杭州 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