（机械电子工程专业论文）柔性制造系统最大许可行为petri网控制器设计.pdf

摘要 摘要 柔性制造系统由计算机控制，利用有限的资源如机器人、缓冲器、机床等来加工 生产不同类型的工件。在柔性制造系统中，死锁是必须考虑和解决的问题。这是由于 死锁经常引起额外的损失甚至造成灾难性的后果。为了满足系统生产需要并能高效地 利用系统资源，必须设计一种高效的死锁控制策略来确保死锁不会发生。基于p e t r i 网 的死锁控制预防策略利用一种离线的控制机制，通过给系统添加约束的方式防止死锁 发生。该策略的优点是，一旦控制策略建立并应用于被控系统，死锁就不会发生。 通常评价一个p e t r i 网监督器的性能指标有三个：行为许可性、结构复杂性以及计 算复杂性。最大许可行为的监督器往往意味着系统资源可以被高效利用；结构简单的 监督器可以降低在控制策略实现阶段所需的软件和硬件费用；较低计算复杂度的控制 策略则意味着该策略可以应用于规模较大、比较复杂的系统。因此，许多研究者做了 大量工作以试图得到拥有最大许可行为的、简单监督器结构的以及较低计算复杂度的 控制器设计方法。 p e t r i 网的可达图分析对于死锁控制是一种非常重要的分析方法。由于要枚举部分 或者全部可达图而存在状态爆炸问题。基于该分析技术，往往可以得到具有较高许可 行为的次优或者最优监督器。本文立足于设计活性p e t r i 网监督器并兼顾考虑其行为许 可性、结构复杂性和计算复杂性，主要完成以下工作。 1 计算p e t r i 网的可达图往往引起状态爆炸问题。二值决策图( b d d ，b i n a r y d e c i s i o nd i a g r a m ) 能够用较小的数据结构表示较大的可达标识集合并对该集合进行高 效的运算。因此，二值决策图在一定程度上克服了状态爆炸问题。本文扩展二值决策 图的应用并提出多种算法使之应用于求解合法状态集合、首遇坏标识集合、合法状态 的最小覆盖集以及首遇坏标识的最小覆盖集。从而使本文的死锁预防策略更加高效。 2 基于结构分析，信标在死锁预防策略中是一种非常重要的概念。信标是库所的 集合并且一旦一个信标失去其所有托肯，它将永远被清空。一个极小信标不包含任何 其他信标。实际上，大部分基于信标的死锁控制策略只考虑极小信标。一个网的信标 ( 极小信标) 的数目与网的规模成指数关系。因此，计算所有的极小信标非常复杂。 本文提出一种利用二值决策图计算所有极小信标的方法。信标的特性可以用布尔函数 表示从而可以用布尔函数的真值来表示信标。然后用二值决策图来表示信标的布尔函 数。最后，一个网的所有信标都可以用二值决策图表示。利用二值决策图进行集合关 系运算从所有信标中计算出所有极小信标。试验结果验证了二值决策图计算所有信标 和极小信标的有效性和高效性。 3 提出一种通过整数线性规划设计柔性制造系统的最大许可行为的p e t r i 网活性监 督器方法。p e t r i 网的可达图可以分为两个区域：活区域和死区域。首遇坏标识处于死 区域并且是从活区域进入死区域首先遇到的标识。通过求解线性规划问题，使求得 i i d e s i g no fm a x i m a l l yp e r m i s s i v el i v e n e s s - e n f o r c i n gp e t r in e ts u p e r x r i s o r sf o rf m s 的p 不变式禁止一个首遇坏标识并保证所有的合法状态都可达。同时，提出一种向量 覆盖方法来减少需要考虑的合法状态和首遇坏标识的数目。向量覆盖使合法状态和首 遇坏标识减少到两个相对很小的集合，分别称作合法状态的最小覆盖集和首遇坏标识 的最小覆盖集。因此，设计控制库所时只需要考虑这两个较小的集合。对于选定的首 遇坏标识，提出进一步的向量覆盖方法，大大减小了合法状态最小覆盖集中需要考虑 的合法状态。从而使求解的整数线性规划问题具有较少的约束条件并能在短时间内求 解。 4 一些p e t r 网并不存在用控制库所表示的最大许可行为的监督器。对于这类网， 本文提出一种死锁预防算法来设计最好许可行为的监督器。所谓最好许可行为的监督 器就是能确保受控系统拥有最多合法状态。实际上，一些p e t r i 网不存在最大许可行为 活性监督器的原因是当某个首遇坏标识被禁止时，存在至少两个合法状态不能同时保 证其可达。也就是说，当设计一个p 不变式禁止某个首遇坏标识时，一些合法状态的 可达条件是相互矛盾的。因此，一个或者更多的合法标识必然被控制库所禁止。本文 通过设计一个整数线性规划问题并用其目标函数来保证最多的合法状态可达，从而得 到最好许可行为的控制器。 5 结构复杂性在最大许可行为控制器设计中也是一个很重要的评价标准。提出一 种监督器设计方法，使所得到的监督器在拥有最大许可行为的条件下所需要的控制 库所数目是较小的。最大许可行为可以通过设计整数线性规划( 记为m c p p ，m i n i m a l c o n t r o lp l a c ep r o b l e m ) 使得所求的控制库所能禁止首遇坏标识最小覆盖集中所有标识 并保证合法状态覆盖集中所有标识可达。在每个控制库所都可以构成一个p 半流的条 件下，线性规划的目标函数可以最小化控制库所的数目。因此，在每个控制库所都能 构成一个p 半流的条件下，得到的监督器拥有最小数目的控制库所并且是行为最大许 可的。 6 为了解决m c p p 的计算复杂度问题，并保证受控系统是行为最大许可的且拥有 较简单的控制结构，提出一种迭代的死锁预防策略以及一个改进的方法。在每一次迭 代中，通过一个整数线性规划设计一个p 不变式使得其禁止尽可能多的首遇坏标识。 求解该整数线性规划问题得到一个p 不变式以及一个控制库所。所有被该p 不变式禁止 的首遇坏标识都从首遇坏标识的最小集合中删除。此迭代过程一直进行直到首遇坏标 识最小集合为空时终止。最终求得一个拥有最大许可行为并拥有较少数目控制库所的 监督器。同时提出个改进的方法来减少该方法的计算时间。实际上，迭代步骤做了 如下修改。在每一次迭代，从首遇坏标识的最小集合中取出一个标识并设计一个p 不 变式来禁止所选择的首遇坏标识。p 不变式通过求解整数线性规划求得并使其保证合 法状态最小集中的所有状态可达。与此同时，目标函数保证该p 不变式可以禁止尽量 多的首遇坏标识。该改进版本的整数线性规划拥有较少的约束条件和变量。因此，跟 未改进版本的整数线性规划相比，其求解时间更短。 摘要 i i i 关键词：p e t r i 网，二值决策图，柔性制造系统，死锁预防，控制器，最大许可行为控制器 a b s t r a c t v a b s t r a c t f l e x i b l em a n u f a c t u r i n gs y s t e m s ( f m s ) a r ec o m p u t e r - c o n t r o l l e ds y s t e m st h a tc a l l m a n u f a c t u r ed i f f e r e n tk i n d so fp r o d u c t sw i t hal i m i t e dn u m b e ro fs h a r e dr e s o u r c e ss u c h a sr o b o t s ，b u f f e r s ，m a c h i n e s ，e t c i nf m s ，d e a d l o c k s 峨ah i g h l yu n d e s i r e ds i t u a t i o n ， w h i c ha l w a y sc a u s eu n n e c e s s a r yc o s ta n de v e nm a yl e a dt oc a t a s t r o p h i cr e s u l t si nt h e s e s 、，s t e m s i no r d e rt om e e tt h ep r o d u c t i o nr e q u i r e m e n t so fas y s t e ma n dm a k et h eb e s t u s eo ft h es y s t e mr e s o u r c e i s ，a ne f f e c t i v ed e a d l o c kc o n t r o lp o l i c ym u s tb ed e s i g n e da n d i m p l e m e n t e dt oe n s u r et h a td e a d l o c k sc a n n e v e ro c c u r b a s e do np e t r in e t s ，d e a d l o c k p r e v e n t i o nu s e sa no f f - l i n ec o m p u t a t i o nm e c h a n i s mt oi r e p o s ec o n s t r a i n t so nas y s t e m i no r d e rt op r e v e n ti tf r o mr e a c h i n gd e a d l o c ks t a t e s o n c ea c o n t r o lp o l i c yi se s t a b l i s h e d a n da p p l i e d ，d e a d l o c k sc a n n o to c c u ra n y m o r e g e n e r a l l y , t h e r ea r et h r e ev e r yi m p o r t a n tc r i t e r i ai ne v a l u a t i n gt h ep e r f o r m a n c eo f al i v e n e s s e n f o r c i n gs u p e r v i s o rf o ras y s t e mt ob ec o n t r o l l e d ：b e h a v i o r a lp e r m i s s i v e n e s s ， s t r u c t u r a lc o m p l e x i t ya n dc o m p u t a t i o n a lc o m p l e x i t y am a x i m a l l yp e r m i s s i v es u p e r v i - s o rh a st h eh i g h e s tp o t e n t i a lt ol e a dt oh i g hu t i l i z a t i o no fs y s t e mr e s o u r c e s ；as u p e r v i s o r w i t has m a l ln u m b e ro fc o n t r o lp l a c e sc a nd e c r e a s et h eh a r d w a r ea n d s o f t w a r ec o s t si n t h es t a g eo fc o n t r o lv a l i d a t i o na n di m p l e m e n t a t i o n ；ad e a d l o c kc o n t r o lp o l i c yw i t hl o w c o m p u 【t a t i o n a lc o m p l e x i t ym e a u st h a ti tc a nb ea p p l i e d t oc o m p l e xs y s t e m s t h u s ， m a n yr e s e a r c h e r st r yt h e i rb e s tt od e v e l o pd e a d l o c kp r e v e n t i o na l g o r i t h m st h a t c a n o b t a i nh v e n e s s e n f o r c i n gs u p e r v i s o r sw i t hm a x i m a lp e r m i s s i b i l i t y , as i m p l es u p e r v i s o r y s t r u c t u r e ，a n dl o wc o m p u t a t i o n a lc o m p l e x i t y r e a c h a b i l i t yg r a p ha n a l y s i si sa ni m p o r t a n tt e c h n i q u ef o rd e a d l o c kc o n t r o l ，w h i c h a l w a y ss u f f e r sf r o mas t a t ee x p l o s i o np r o b l e m s i n c ei tr e q u i r e sg e n e r a t i n ga l lo rap a r to f r e a c h a b l em a r k i n g s b a s e do nt h i st e c h n i q u e ，a l lo p t i m a lo rs u b o p t i m a ls u p e r v i s o rw i t h h i g hb e h a v i o r a lp e r m i s s i v e n e s sc a l la l w a y sb ea c h i e v e d t h i st h e s i sf o c u s e so nd e s i g n i n g l i v e n e s s - e n f o r c i n gp e t r in e ts u p e r v i s o r sf o rf m sb yc o n s i d e r i n g t h e i rb e h a v i o r a lp e r m i s - s i v e n e 8 8 ，s u p e r v i s o r ys t r u c t u r e ，a n dc o m p u t a t i o n a lc o m p l e x i t y t h ef o l l o w i n gr e s e a r c h c o n t r i b u t i o n sa r em a d ei nt h i st h e s i s 1 ar e a c h a b i l i t yg r a p ha l w a y ss u f f e r sf r o mt h es t a t ee x p l o s i o np r o b l e m b i n a r y d e c i s i o nd i a g r a m s ( b d d ) c a l lr e p r e s e n tl a r g es e t so fr e a c h a b l em a r k i n g sw i t hs m a l l s h a r e dd a t as t r u c t u r e sa n di m p l e m e n tt h ee f f i c i e n tm a n i p u l a t i o no nt h o s es e t s t h u s ， b d dc a nb eu s e dt or e p r e s e n tt h es t a t es p a c ei no r d e rt oo v e r c o m et h es t a t ee x p l o s i o n p r o b l e mt oac e r t a i ne x t e n t i n t h i st h e s i s ，w ee x t e n dt h ea p p l i c a t i o no fb d da n d p r o v i d ean u m b e ro fa l g o r i t h m st oc o m p u t et h el e g a lm a r k i n g s ，f i r s t - m e tb a dm a r k i n g s ( f b m ) ，t h em i n i m a lc o v e r i n gs e to fl e g a lm a r k i n g s ，a n dt h em i n i m a lc o v e r e ds e to f f b m w h i c hm a k e sm o r ee f f i c i e n tt h ep r o p o s e dd e a d l o c kp r e v e n t i o nm e t h o d s 2 b a s e do ns t r u c t u r a la n a l y s i s ，s i p h o n sp l a ya ni m p o r t a n tr o l ei nt h ed e v e l o p m e n t o fd e a d l o c kp r e v e n t i o np o l i c i e s as i p h o ni sas e to fp l a c e ss u c ht h a tt h ee x i s t e n c e o fa n y a r cf r o mat r a n s i t i o nt oap l a c ei nt h es i p h o ni m p l i e st h a tt h e r ei sa na r cf r o ma p l a c ei n t h es i p h o nt ot h et r a n s i t i o n t h u s ，o n c eas i p h o nl o s e sa l li t st o k e n s ，i tr e m a i n se m p t y o f t o k e n s am i n i m a ls i p h o ni st h eo n et h a td o e sn o ti n c l u d ea n y o t h e rs i p h o n8 sa p r o p e r s u b s e t i nf a c t m o s to ft h et h e o r e m sa b o u ts i p h o n sf o rl i v e n e s sa n a l y s i sa n dc o n t r o la r e r e l a t e dt om i n i m a ls i p h o n s t h en u m b e ro fs i p h o n s ( m i n i m a ls i p h o n s ) i nap e t r in e t i n c r e a s e se x p o n e n t i a l l yw i t hr e s p e c tt oi t ss i z e t h u s ，t h ec o m p u t a t i o no fa l lm i n i m a l s i p h o n si sc o m p u t a t i o n a l l ye x p e n s i v e t h i st h e s i sp r o p o s e sas y m b o l i cc o m p u t a t i o no f m i n i m a ls i p h o n sb yu s i n gb d d t h ep r o p e r t i e so fs i p h o n sc a n b er e p r e s e n t e db yb o o l e a n f u n c t i o n s t h u s ，s i p h o n sc a nb ei d e n t i f i e da st r u ev e r t i c e so fb o o l e a nf u n c t i o n s i nt h i s c a s e w eu s eb d dt or e p r e s e n tt h eb o o l e a nf u n c t i o n so fs i p h o n s a sar e s u l t ，a l ls i p h o n s o fap e t r in e ta r er e p r e s e n t e db yb d d t h e n ，w eu s ea b o o l e a nr e l a t i o nt oe x t r a c tt h e m i n i m a lo n e sf r o ma l ls i p h o n s e x p e r i m e n t a lr e s u l t ss h o wt h a tb d da r e e f f e c t i v ea n d e f f i c i e n tt oc o m p u t es i p h o n sa n dm i n i m a ls i p h o n s 3 t h ed e s i g no fam a x i m a l l yp e r m i s s i v el i v e n e s s e n f o r c i n gs u p e r v i s o rf o rf m s i sp r o p o s e db ys o l v i n gi n t e g e rl i n e a rp r o g r a m _ r u i n gp r o b l e m s ( i l p p s ) ar e a c h a b i l i t y g r a p hi sc l a s s i f i e di n t ot w oz o n e s ：l i v e - z o n e ( l z ) a n dd e a d l o c k - z o n e ( d z ) a nf b m i st h eo n ew i t h i nd z ，r e p r e s e n t i n gt h ev e r yf i r s te n t r yf r o ml zt od z b yu s i n ga n i n t e g e rl i n e a rp r o g r a m m i n ga p p r o a c h ，ap i n v a r i a n t ( p i ) i sd e s i g n e df o ra l lf b m s u c h t h a ti t i sp r e v e n t e df r o mb e i n gr e a c h e da n dn ol e g a lm a r k i n gi sf o r b i d d e n w ep r o p o s e av e c t o rc o v e r i n ga p p r o a c ht or e d u c et h es e t so fl e g a lm a r k i n g sa n df b m t ov e r ys m a l l s e t s ，n a m e l y ，t h em i n i m a lc o v e r i n gs e to fl e g a lm a r k i n g sa n dt h em i n i m a lc o v e r e d s e to f f b m t h u s ，w eo n l yc o n s i d e rt w os m a l ls e t so fl e g a lm a r k i n g sa n df b m t oo b t a i nt h e c o n t r o lp l a c e s v v h e na nf b mi ss e l e c t e da n da c o n t r o lp l a c ei sd e s i g n e dt of o r b i di t ，a f u r t h e rc o v e r i n ga p p r o a c hi sd e v e l o p e dt or e d u c et h es e to fl e g a lm a r k i n g st oa s m a l l e r o n e a sar e s u l t t h ei l p ph a sav e r ys m a l ln u m b e ro fi n e q u a l i t i e sa n dc a nb es o l v e di n as h o r tt i m e 4 t h e r ee x i s ts o m ep e t r in e tm o d e l st h a th a v en om a x i m a l l yp e r m i s s i v es u p e r v i s o r e x p r e s s e db ya s e to fc o n t r o lp l a c e s f o rs u c he a s e s ，w ep r o p o s eam e t h o dt oo b t a i na b e s tp e l m i s s i v ep e t r in e ts u p e r v i s o rs u c ht h a tt h em o s tl e g a lm a r k i n g sa r ek e p ti nt h e c o n t r o l l e ds y s t e m t h ef a c tt h a tn oo p t i m a lc o n t r o lp l a c ec a nb ed e s i g n e di s d u et o t h ep r e s e n c eo fa tl e a s tt w ol e g a lm a r k i n g st h a tc a n n o tb eg u a r a n t e e dt ob er e a c h a b l e b yf o r b i d d i n gap a r t i c u l a rf b m t h a ti s t os a y , w h e nap ii sd e s i g n e dt of o r b i da l l a b s t r a c tv i i f b m ，t h et e a c h a b i l i t yc o n d i t i o n so fs o m el e g a lm a r k i n g sh a v et ob ev i o l a t e d t h u s ，o n e o rm o r el e g a lm a r k i n g sm u s tb er e m o v e d t h i sp r o b l e mc a nb eh a n d l e db ys o l v i n ga n i l p pa n di t so b je c t i v ef u n c t i o ne n s n r e st h a tt h em o s tl e g a lm a r k i n g sa i ek e p ti nt h e c o n t r o l l e ds y s t e m 5 s t r u c t u r a lc o m p l e x i t yi sa l s oa ni m p o r t a n ti s s u ef o ram a x i m a l l yp e r m i s s i v e p e t r in e ts u p e r v i s o r ad e a d l o c kp r e v e n t i o np o l i c yf o rf m si sp r o p o s e d ，w h i c hc a n o b t a i nam a x i m a l l yp e r m i s s i v el i v e n e s s e n f o r c i n gp e t r in e ts u p e r v i s o rw h i l et h en u m b e r o fc o n t r o lp l a c e si sc o m p r e s s e d am a x i m a l l yp e r m i s s i v ec o n t r o lp u r p o s ec a nb ea c h i e v e d b yd e s i g n i n gc o n t r o lp l a c e ss u c ht h a ta l lm a r k i n g si nt h em i n i m a lc o v e r e ds e to ff b m a r ef o r b i d d e na n dn om a r k i n gi nt h em i n i m a lc o v e r i n gs e to fl e g a lm a r k i n g si sf o r b i d d e n a ni l p p ( n a m e l ym c p p ) i sd e s i g n e dt om i n i m i z et h en u m b e ro fc o n t r o lp l a c e su n d e r a na s s u m p t i o nt h a tac o n t r o lp l a c ei sa s s o c i a t e dw i t hap - s e m i f l o w t h er e s u l t i n gn e t h a st h em i n i m a ln u m b e ro fc o n t r o lp l a c e so nt h ep r e m i s et h a tt h ea s s u m p t i o nh o l d s ， a n dp o s s e s s e sa l lp e r m i s s i v es t a t e so fap l a n t 6 i no r d e rt oo v e r c o m et h ec o m p u t a t i o n a lc o m p l e x i t yp r o b l e mi nm c p pa n de n s u r e t h a tt h ec o n t r o l l e ds y s t e mi sm a x i m a l l yp e r m i s s i v ew i t has i m p l es t r u c t u r e ，w ed e v e l o p a ni t e r a t i v ed e a d l o c kp r e v e n t i o np o l i c ya n dam o d i f i e dv e r s i o n a te a c hi t e r a t i o n ，a m a x i m a l l yp e r m i s s i v ep ii sd e s i g n e dt of o r b i da sm a n yf b m a sp o s s i b l eb ys o l v i n ga n e ， i l p p a l lf b mt h a ta r ef o r b i d d e nb yt h ep ia r er e m o v e df r o mt h em i n i m a lc o v e r e d s e to ff b m t h i sp r o c e s si sc a r r i e do u tu n t i ln of b mi sl e f ti nt h em i n i m a lc o v e r e d s e t am a x i m a l l yp e r m i s s i v es u p e r v i s o rw i t has m a l ln u m b e ro fc o n t r o lp l a c e sc a n b ea c c o r d i n g l yo b t a i n e d w ea l s op r o v i d eam o d i f i e dv e r s i o no ft h ea b o v em e n t i o n e d m e t h o di no r d e rt of u r t h e rr e d u c et h ec o m p u t a t i o n a lt i m e i nf a c t ，w eo n l ym o d i f yt h e i t e r a t i o ns t e p sa sf o l l o w s a te a c hi t e r a t i o n a nf b mi ss i n g l e do u tf r o mt h em i n i m a l c o v e r e ds e to ff b ma n dap ii sd e s i g n e dt of o r b i dt h es e l e c t e df b m t h ep ii sc o m p u t e d b ys o l v i n ga ni l p ps u c ht h a tt h es e l e c t e df b m i sf o r b i d d e na n dn ol e g a lm a r k i n gi nt h e m i n i m a lc o v e r i n gs e to fl e g a lm a r k i n g si sf o r b i d d e n a tt h es a m et i m e ，w ea l s ou s ea n o b j e c t i v ef u n c t i o nt om a x i m i z et h en u m b e ro ff b mt h a ta r ef o r b i d d e nb yt h ep i t h e m o d i f i e dv e r s i o nh a sas m a l ln u m b e ro fc o n s t r a i n t sa n dv a r i a b l e s t h e r e f o r e ，c o m p a r e d w i t ht h ef o r m e r ，i tc a nb es o l v e di nas h o r t e rt i m ei ng e n e r a l k e y w o r d s ：p e t r in e t ，b i n a r yd e c i s i o nd i a g r a m ，f l e x i b l em a n u f a c t u r i n gs y s - t e r n ，d e a d l o c kp r e v e n t i o n ，s u p e r v i s o r ，m a x i m a l l yp e r m i s s i v es u p e r v i s o r s v m b o l s x i b = o ，1 】- r ( b ) i l 3 m a d 朋三 j f b m l j f b m m n 心 n l n f b m n n + n a n l n f b m n 艺 n f b m ( n ，m o ) 】 【】+ 【卅一 亿c p p o p a p r s y m b o l s as e tc a l l e dt h ec a r r i e r af u n c t i o n as e to f 礼v a r i a b l e sb o o l e a