（控制科学与工程专业论文）离散事件系统的禁止状态监控器设计.pdf

摘要 离散事件系统是由不规则时间间隔出现的事件序列驱动的一种动态系统。实 际的离散事件系统可能会演变到一些禁止状态，例如柔性制造系统中的死锁以及 工件碰撞、网络通信系统中的数据包丢失、自动导航车辆系统中的车辆碰撞等等。 禁止状态监控就是为系统设计状态反馈监控器以避免闭环系统进入禁止状态。 目前研究离散事件系统监控理论的数学工具主要有自动机、形式语言和p e t r i 网。鉴于p e t r i 网在系统状态表达和处理并发的优势，本论文以p e t r i 网为模型研 究控制规范为广义互斥约束f g m e c ) 的禁止状态监控问题。 事件全部可控的监控问题已经得到了有效解决，但是事件不可控情况下的监 控问题仍未得到有效的解决，目前的研究还只能处理几类特殊的监控问题。本论 文研究系统存在不可控事件的离散事件系统的监控问题，其主要研究工作概述如 下： 在第3 章，我们提出了基本广义互斥约束的概念，并针对控制规范为组基 本广义互斥约束的“逻辑与”或者“逻辑或”的监控问题，我们给出了监控器存在 的充要条件，并得到了最大允许监控器的综合方法，根据该方法设计的监控器具 有较高的计算效率，可以在多项式时间内完成在线计算。在此基础上，针对一组 g m e c 的“逻辑与”的监控问题，提出了基于约束转换的监控器综合方法。首先， 我们证明如果两组约束中的约束一一对应且等价，那么其中一组约束的“逻辑与” 和另一组约束的逻辑“与”等价，接着，在此基础上，通过约束转换，我们得到了 该组广义互斥约束的“逻辑与”的最大允许监控器。该方法将监控器综合问题简化 为约束转换问题，从而指明了有效解决一类监控问题的根本途径。 在第4 、5 、和6 章，我们首先分别定义了前向无同步前向无冲突网( 简称 f s f c f 网) 、前向无同步后向无冲突网简称( f s b c f 网) 和后向无同步网( 简称 j f 网) 。接着针对不可控影响子网分别为f s f c f 网、f s b c f 网和j f 网的一组 g m e c 的“逻辑与”的监控问题，基于本文提出的约束转换法给出了监控器的综 合方法，其中包括监控器存在的充要条件和最大允许监控器的算法。 针对事件图和状态机的g m e c ，在第7 章和第8 章我们分别给出了它们混合 型监控器的设计方法。在分析事件图和状态机的结构性质的基础上，分别设计了 状态使能观测器、路径观测器和库所观测器；最后根据观测器给出了计算最大允 许的状态反馈控制策略的算法。和现有的方法相比，我们的方法在适用范围上有 所缩小，但是无需对观测子网进行可达性分析，从而避免了指数级的计算复杂性， 设计的监控器可以在多项式时间内完成在线计算，计算效率更高。 摘要 对本文所提出的监控器综合方法，我们在理论证明的同时，还用较多的例子 予以说明和验证。 关键词：离散事件系统，p e t r i 网，监控，禁止状态，广义互斥约束，约束转换 a b s t r a c t ad i s c r e t ee v e n ts y s t e m ( d e s ) i 8 七h ed y n a m i c a ls y 8 t e mt h a te v o l v e sa c c o r d i n g t ot h ea b r u p to c c l l r r e n c eo fe v e n t s ，a tp o s s j b l yu n k n 0 w ni r r e g u l a rj n t e r v a l s a n a c t u a ld e sm a e n t e ri n t os o m ef o r b i d d e ns t a t e ss u c ha st h ec o l l i s i o n sb e t w e e n w o r k p i e c e sa n dt h ed e a d l o c k si nm a n u f a c t l l r i n gs y s t e m 8 ，t h e1 0 8 so fd a t ap a c l 【a g e s i nn e t w o r kc o m m u n i c a t i o ns y s t e m s jt h ec o i s i o n so f 、r e h i c l e 8i na u t o9 1 l i d e dv e h i c l e s y 8 t e m s t h ef o r b i d d e ns t a t ea v o i d a n c e8 u p e r v i 8 0 r yc o n t r o l i st os y n t h e 8 i z et h e s t a t ef e e d b a c ks u p e r v i s o rs u c ht h a tt h ec l o s e d l o o ps y s t e mn e v e rr e a e h e saf b r b i d d e n s t a 七e c u r r e n t l y ，t h em a i nr e s e 缸c ht o o l so ft h es u p e r v i 8 0 r yc o n t r o lo fd e s 缸ea u t o m a t a ，f o r m a ll a i l g u a g e sa n dp e t r in e t s i nt h i st h e s i 8 ，p e t r in e t 8 盯eu t m z e dt o s t u d yt h es u p e r v i s o r yp r o b l e m si nw h i c ht h e8 p e c i f i c a t i o ni sg e n e r 出i z e dm u t u a le x - c l u s i o nc o n s t r a i n t 8 ( g m e c ) i nc o n 8 i d e r a t i o no fi t sa d v a n t a g e so nr e p r e s e n t a t i o no f 8 y s t e 瑚s t a t ea n dc o n c u r r e n 四7t r e a t m e n t t h es u p e r 、r i 8 0 r yp r o b l e m si nw h i c ha l le v e n t 8a r ec o n t r 0 1 l a b l eh a v e b e e ns 0 1 v e d e 伍c i e n t l vb u tt h ec a s ew i t hp r e 8 e n c eo fu n c o n t r o l l a b l et r a n s i t i o n 8i ss t i l ln o tw e l l t r e a 七e d t h er e p o r t e d l e t h o d sc a no n l yb eu s e dt od e a lw i t h8 0 m es p e c i a ic l a s s e so f s u p e r v i 8 0 r yc o n t r 0 1p r o b l e m s t h e8 u p e r 订s o r yc o n t r 0 1o fd e s 耐t hu n c o n t r o l l a b l e t r a n s i t i o n si sa d d r e s 8 e di nt h i st h e s i sa 皿dt h em a i nc o 七r i b u t i o n sa r es u m m a r i z e d a 8f o u o w s ： i nt h et h i r dc h a p t e r ，t h ec o n c e p to fb a 8 i cg m e ci 8f i r s ti i l t r o d u c e d f b rt h e s u p e r v i s o r yc o n t r o lp r o b l e m sw i t ht h es p e c m c a t i o no ft h ec o n j u l l c t i o no ru 1 1 i o no f b a 8 i cg m e c ，t h ei l e c e s s 盯ya n ds 椭c i e n tc o n d i t i o no ft h ee x i s t e n c eo ft h es u p e r v i s o r i sp r e 8 e n t e d ，a n dt h em e t h o do f8 y n t h e s i z i n gt h em a x i m a u yp e r m i 8 s i v es u p e r v i s o r i sp r o p o s e d t h es y n t h e s i z e ds u p e w i s o ru s i n gt h ep r o p 0 8 e dm e t h o dh a sah i g h e r c o m p u t a t i o n a le m c i e n c ya n dt h eo n l i n ec o m p u t a t i o nc a nb ec o m p l e t e dw i t h i nt h e p o l y n o m i a lt i m e t h em e t h o do fs y n t h e s i z i n gs l l p e r v i s o rb a s e do nt h ec o n s t r a j n t t r a n s f o r m a t i o ni sp r o p o s e dt oe 1 1 f o r c et h es p e c m c a t i o no ft h ec o n j u n c t i o no fg m e c f i r 8 t l y ，i ti 8p r o v e dt h a tac o l l j u n c t i o no fg m e ci se q u i v 甜e n tt ot h eo t h e ri fa n y g m e ci nac o n j u n c t i o ni 8e q u i 、村e n tt o0 n eg m e ci nt h eo t h e ra n dv i c ev e r s a t h e n ，am a 村m a u yp e r m i 8 8 i v es u p e r v i s o ro fe n f o r c i n gt h ec o n j u n c t i o no fg m e ci s o b t a i n e db a s e do nt h ec o n s t r a i n tt r a n s f o r m a t i o n t h em e t h o dr e d u c e st h ed r o b l e m a b g t r a c t o fs u p e r v i s o r8 y n t h e s i si n t oap r o b l e mo fc o n s t r a i nt r a n s f o r m a t i o na n dp r e s e n t sa f u n d a m e n t a lm e a n s0 fe 伍c i e n t l ys 0 1 v i n gac l a s so f8 u p e r v i s o r yc o n t r o lp r o b l e m i nt h ef o u r t h ，f i r ha j l ds i ( t hc h a p t e r ，f o r w a r ds y n c h r o n i z a t i o n 锄df o r w a r d c o n 丑i c tf r e e ( f s f c f ) n e t s ，a n df o r w a r ds y n c l l r o l l i z a t i o na n db a c k w a r dc o n m c t f r e e ( f s b c f ) n e t s 盯e 矗r 8 t l yi n t r o d u c e d ，r e 8 p e c t i v e l 矿t h e n ，f o rac o n j u n c t i o no f g m e c sw h e r et h eu n c o n t r o i l a b l ei 丑u e n c es u b n e t sa r ef s f c fn e t s f s b c fn e t s a n dj fn e t 8 ，t h e8 u p e r v i 8 0 rs y n t h e 8 i sm e t h o d 8a r ep r o p o s e db a s e do nt h ec o n s t r a i n t t r a n 8 f o r m 8 t i o nm e t h o dp r o p o s e di nt h i 8t h e s i s ，i n c l u d i n gt h en e c e s 8 黜ya n ds u 伍一 c i e n tc o n d j t i o no ft h ee 妇s t e n c eo ft h es u p e r v i s o ra n dt h em g o r i t h mo fs y n t h e 8 i z i n g m a x i m m l yp e r m i s s i v e8 u p e r v i s o r i nt h es e v e n t ha n de i g h t hc h a p t e r ，t h em e t h o d 8o fs y n t h e 8 i z i n gc o m b i n e ds u p e r v i s o r 缸ep r o p o s e dt oe n f o r c eag m e co ns t a t em a c l l i n ea n dm a r k e d 盯a p h ， r e s p e c t i 忱1 y t b a 8 e do nt h ea n a l y s i so fs t r u c t u r ep r o p e r t i e so f8 t a t em a c h i n ea n d m a r k e dg r 印h ，t h es t a t ee n a b ko b s e r 、惯，t h ep a t ho b s e r v e r 锄dt h ep l a c eo b 8 e r v e r a r ec o n 8 t r u c t e d ，r e 8 p e c t i v e l h f i n a l i y ) t h ea l g o r i t h mo fc a k l l l a t i n gt h em a x i m a l l y p e r m i s s i v e8 t a t ef e e d b a c kc o n t r 0 1p o l i c yi 8g i v e n c o m p a r i n gw i t ht h er e p o r t e d m e t h o d s ，t h o u g ht h ep r o p o s e dm e t h o dl i m i t 8t h e 叩p l i c a t i o n8 c o p e ，j td o e sn o t n e e da n yr e a c h a b i l i t ya n 甜y s i 8a n dt h u sa v o i d 8e x p o n e n t i a lc o m p u t a t i o n 出c o m p l e ) 【i t y t h ed e 啦n e ds u p e r v i s o rh 8 8h i g h e rc o m p u t a t i o ne 伍c i e n c y8 u c ht h a ti ti s c 印a b l eo fc o m p l e t i n go i l l i n ec o m p u t a t i o nw i t h i np o l y n o m i a lt i m e t h ep r o p 0 8 e ds u p e r v i s o rs y n t h e s i sm e t h o d si nt h i st h e s i 8 盯en o to n l yp r o v e d i nt h e o r yb u t 血8 0v e r m e da n di 1 1 u 8 t r a t e db ym a n ye x a m p l e st h r o u 曲o u tt h et e x t k 叼、o r d s ：d i 8 c r e t ee v e n ts y 8 t e m s ，p e t r in e t s ，s u p e r v i s o r yc o n t r o l ，f o r b i d d e n s t a t e s ，g e n e r a l i z e dm u t u a le x c l u s i o nc o n s t r a j n t ，c o n s t r a i n t i y a n s f o r m a t i o n n 儿 p 丁 正 瓦 w c b d d d + 竹1 m 0 ，南) 虬 d d 石 d 嘉 ( ，m o ) ( 肛，m o ) m m w ， c 4 。k ， m ， c ， 4 ， 主要符号对照表 p e t r i 网 受控p e t r i 网 p e t r i 网的库所集 p e t r i 网的变迁集 p e t r i 网的可控变迁集 p e t r l 网的不可控变迁集 p e t r i 网库所和变迁或变迁和库所的二二元组集合 p e t r i 网库所和变迁或变迁和库所的二元组集合上的权值函数 p e t r i 网的控制库所集 p e t r i 网控制库所和可控变迁的二元组集合 p e t r i 网的关联矩阵 p e t r i 网的前置关联矩阵 p e t r i 网的后置关联矩阵 p e t r i 的标识 p e t r i 的初始标识 p e t r i 网上的一个广义互斥约束 p e t r i 网上的广义互斥约束对应的不可控影响子网 不可控影响予网的关联矩阵 不可控影响子网的前置关联矩阵 不可控影响子网网的后置关联矩阵 一个p e t r i 系统 一个受控p e t r i 系统 一个( 受控) p e t r i 系统的全部标识集 p e t r i 网上的一个广义互斥约束的禁止标识集 p e t r i 网上的一个广义互斥约束的合法标识集 p e t r i 网上的一个广义互斥约束的允许标识集 p e t r i 网上的一组广义互斥约束的交 p e t r i 网上厂的禁止标识集 p e t r i 网上厂的合法标识集 p e t r i 网上，的允许标识集 主要符号对照表 爿 m 爿 c 茁 一4 爿 p p p p e t r i 网上的一组广义互斥约束的或 p e t r i 网上彤的禁止标识集 p e t r i 网上z 的合法标识集 p e t r i 网上z 的允许标识集 一个库所 库所p 的全部输入变迁的集合 库所p 的全部输出变迁的集合 一个变迁 变迁的全部输入库所的集合 变迁t 的全部输出库所的集合 变迁t 的输入控制库所 受控p e t r i 网的一个控制 最小控制 最大控制 一个控制策略 受控p e t r i 网全部控制的集合 路径 环 路径丌的第一个节点 路径”的最后一个节点 一个变迁的多重集合( 变迁包) 一个变迁的多重集合对应的激发向量 一个变迁包的激发序列 一个变迁包的激发序列对应的激发向量 p e t r i 网从标识m 开始一步可达标识的集合 p e t r i 网从标识m 开始不可控可达标识的集合 受控p e t r i 网在控制策略u 下从标识m 开始不可控可达标识的集合 受控p e t r i 网从标识m 开始不可控可达标识的集合 整数的集合 d m 盯； 。r。；=u吖丌。h矿。亨盯孑晰州聃她 第一章绪论与综述 本章概述了离散事件系统监控理论研究的进展情况，并简要介绍了本论文的 研究思路和主要内容。 1 1 离散事件系统概述 在当今计算机科学和信息技术等一批高新技术发展的推动下，出现了一些高 度自动化、性能卓越的系统，例如排队系统、柔性制造系统、物流系统、自动导航 车辆系统、计算机操作系统、交通控制系统和网络数据交换系统等等，它们都属于 离散事件系统：随着未知的不规则时间间隔出现的事件演化的一类动态系统f 1 1 。 系统中的事件是用来描述系统行为的，包括排队系统中顾客到达和离开、柔性制 造系统中一道工序的开始与结束等等。离散事件系统的名称最早是由美国啥佛大 学的何毓奇教授提出来的f 2 1 。连续系统和离散事件系统的差别在于：前者是时间 推动的。其状态空间在时间维上是连续的；而后者是事件推动的，其状态点出现在 不规则间隔的时间点上。 基于离散事件系统广泛的工程背景和潜在的应用价值，目前众多的学者对该 系统的建模、设计、性能分析和控制综合进行了大量的研究，已经形成了一个研究 热点。为了实现离散事件系统的高度自动化和期望的各项性能指标，监控器综合 是个非常必要也是非常关键的问题。 离散事件的系统行为是它产生的事件序列( 事件串) ，事件序列清楚地描述离 散事件系统的演变过程。事件之间的逻辑关系能够揭示事件序列的规律：如果事 件a 和b 是因果关系，那么系统产生的任意事件串中a 总是先于b 出现；如果事 件a 和b 是并发关系，那么它们的出现没有必然的逻辑关系，例如售票系统中， 售票员和他( 她) 服务的顾客的行为是因果关系；而两个售票员行为之间是并发关 系。离散事件系统监控就是为了协调事件之间的逻辑关系，从而使得闭环系统的 事件序列满足一定要求，即达到相应的性能指标，例如稳定性( 安全) 、无阻塞、活 性和某系统参数的最优。 离散事件系统的控制区别于连续系统，但是它们之间也有着内在的联系。严 格地说，通常的系统一般既不是离散事件系统也不是连续系统，因为它既包含局 部时间驱动的连续变量又包含不规则时间间隔出现的事件。但是这样的系统可以 建模为由多个相互影响的连续予系统组成的系统，各子系统之间的关联从本质上 讲是逻辑( 因果) 关系，而这种逻辑关系可以描述为事件触发的条件。因此从全局 第一章绪论与综述 图1 1 复杂控制系统的框架结构 来看，任意复杂系统都可以抽象为一个离散事件系统。在实现一个系统的自动化 时，一个连续子系统需要一个局部控制器来实现它的各项性能指标，如稳定性、鲁 棒性等等；同时从全局出发的离散事件系统需要监控器来协调各子系统之间的关 系，从而使整个系统能够满足全局的性能指标，例如各子系统之间无冲突、全局最 优等等。图1 1 显示了这种复杂控制系统的框架结构。基于上述一般对象的控制系 统的构架，区别于连续系统上的控制器，我们一般将离散事件系统上的控制器称 为监控器，离散事件系统上的控制问题称为监控问题，设计监控器的过程称为监 控器综合。 在离散事件系统的理论研究中，出现了多种建模工具：排队论f 3 1 、摄动分析 法4 ，5 、随机p e t r i 网 6 、极大极小代数 7 、自动机与形式语言 8 和p e t r i 网 f 9 1 1 1 。自动机( 形式语言) 和p e t r i 网没有时间概念，它们着重于描述事件间的逻 辑关系，在离散事件系统监控理论的建模工具巾占主流地位。 离散事件系统监控理论起始于上世纪八十年代末r 眦a d g e 和w b n h a m 1 ，1 2 ，1 3 】的开创性的工作。在对象为有限状态机的前提下，他们利用形式语言给 出了禁止状态监控器综合的框架( r w 理论) ：设计一个监控器自动机，使得对象 自动机和监控器自动机同步生成的语言包含在规范语言内。禁止状态问题是指设 计监控器避免闭环系统进入给定禁止状态的集合。所谓禁止状态是不满足期望的 系统性能指标或不希望出现的状态，例如自动导航车辆系统中车辆的碰撞、制造 系统中系统阻塞或死锁、网络数据交换系统中数据包的丢失等等。学者们在解决 实际问题时，发现了其它多种控制规范：禁止字符串问题 1 4 - 1 6 】、死锁( 阻塞) 防 止问题【1 7 _ 2 1 】和活性保持问题 2 2 _ 2 6 卜基于状态空间的离散性，一般来说我们可 2 浙江大学博士学位论文 以把不满足给定性能指标( 控制规范) 的状态列为禁止状态，从而将该控制规范转 化为禁止状态问题，例如文献f 1 9 ，2 7 1 将一类死锁防止问题和活性保持问题转化为 禁止状态问题，文献1 4 ，2 8 ，2 9 1 将一类禁止字符串问题转化为禁止状态问题，因 此禁止状态问题是一类广泛的控制规范。 自动机包括图灵机( 0 型语言) 、线性有界自动机( 上下文无关语言) 、下推自 动机( 上下文有关语言) 和有限自动机( 正规语言) f 9 1 。其中图灵机的建模能力最 强，有限自动机的建模能力最弱。p e t r i 网的建模能力强于有限自动机。因为p e t r i 产生语言是正规语言的超集。一般来说，一种工具的建模自2 力越强，那么它带来的 计算复杂性也越高。 近年来，自动机的监控理论取得了丰富的成果8 ，这得益于r w 理论的诸多 优点：概念清晰、逻辑严谨和形式完美。然而自动机却难以克服“状态爆炸”问 题，即使在有限自动机上，监控问题的计算复杂性随着网的规模呈几何级数增长 3 0 】ah 0 1 l o w a y 和k r o 曲 3 1 】用一个实例详细分析了有限自动机上监控问题的计算 复杂性：在一个仅有五辆车辆组成的自动导航系统中，其有限自动机的模型的状 态就达数百万之巨，计算量之大难以实际应用。 相对于自动机，p e t r i 网更适合描述并发，而且在计算效率方面表现出了优越 的性能。g i u a 等f 1 5 ，3 2 指出：不象自动机用单个的库所来表示状态那样，p e t r i 网用库所集合来表示状态，这种结构化的状态表示方法能够更紧凑地描述状态空 间，即当系统的状态空间变得很大时，p e t r j 网本身仍然保持在很小的规模。另外 p e t r i 网图形化的描述方法，使得模型更为直观，更易于工程师掌握和理解，甚至 对于某些问题，一旦建立了它们的p e t r i 网模型，答案就显而易见了。p e t r i 网是一 个能够很好地平衡建模能力和计算复杂性的离散事件系统建模工具。 基于上述原因，在本论文中我们将以p e t r i 网为建模工具来研究禁止状态监控 理论。 1 2 离散事件系统禁止状态监控理论综述 对应一个禁止状态监控问题，p e t r i 网的状态空间可以分为不相交的两个集 合：合法标识集和禁止( 非法) 标识集。禁止状态监控的目的是：为p e t r i 网设计监 控器，利用监控器( 监控算法) 实时地禁止某些事件的激发从而避免系统到达禁止 状态。如果一个监控器能够使得系统永远不进入禁止状态，那么它是允许的。如果 个允许的监控器每次只禁止最少的变迁激发，那么它是最大允许( 最优) 的。在 禁止状态监控理论中，最核心的研究包括以下三个方面： 允许监控器存在性的问题 3 第一章绪论与综述 最大允许监控器存在性的问题； 允许监控器或最大允许监控器的设计方法。 g i u a 等f 3 3 提出了一类称为广义互斥约束的禁止状态控制规范，它要求网内 各库所包含托肯数的加权和不超过某一上界。广义互斥约束在某些文献中也称为 线性不等式约束，它是基于系统资源的有限性提出的，在系统上施加广义互斥约 束是为了避免资源有限导致的冲突。文献3 4 1 指出广义互斥约束无法表示全部的 禁止状态控制规范。但是广义互斥约束广泛的应用背景使得它一经提出就得到了 极大的关注，目前禁止状态问题的研究多以广义互斥约束为控制规范1 5 ，3 5 3 7 1 。 本文将集中研究广义巨斥约束的监控问题，为了叙述方便，下文提到的监控问题 默认为在p e t r i 网上实现广义互斥约束问题。 针对在变迁全部可控的p e t r i 网上实现广义互斥约束的“逻辑与”的控制问 题，g i u a 等 3 3 和n d i d o u 等 1 1 ，3 8 】利用库所不变量给出了一种结构性监控 器的综合方法，即在p e t r i 网内为每一个约束添加一个控制库所，使得该约束对应 的禁止库所( 权值非零的库所) 多重集合和控制库所组成一个库所不变量，从而使 得标识的加权和始终不超过该约束对应的上界。允许结构型监控器和最大允许结 构型监控器存在的条件是初始标识为合法标识。但是对于在变迁全部可控的p e t r i 网上实现广义互斥约束“逻辑或”的问题，允许的结构型监控器一般是不存在的。 实际的离散事件系统中存在不可控的事件，例如猫鼠迷宫中有的门无法关 闭【3 9 、自造系统机床发生故障 3 6 】等等，这些事件对应p e t r i 网内的不可控变迁。 不可控变迁的存在使得监控问题变得非常复杂。为了设计出高效的监控器，我 们有必要分析不可控变迁为监控问题带来高计算复杂性的原因。 当不可控变迁存在时，监控器仅仅避免系统进入非法( 禁止) 标识集是不够 的，因为系统可以从某些合法标识经过一系列不可控事件到达禁止标识。为了解 决这一问题，h o l l o w a y 和k r o 曲等 1 0 ，3 1 ，3 5 ，4 0 ，4 1 1 提出了基于状态反馈的监控 理论，其主要结论是： 定义了允许标识：如果系统无法从一个给定标识经过任意不可控事件序列到 达任意非法( 禁止) 标识，那么该标识称为允许标识； 当且仅当一个监控器能够使得系统仅在允许标识集内演变时，它是允许的； 允许的监控器存在的充分必要条件是：初始标识为允许标识。 一个允许的监控算法可以概括为： ( 1 ) 列举从当前标识m 一步可达的标识，所有这些标识组成集合r - ( m ) 4 浙江大学博士学位论文 ( 2 ) 对于r 1 ( m ) 的每一个标识，判定它是否为允许标识，并将r - 胁) 中所有非 允许标识组成标识集r ( m ) ( 3 ) 找到系统从m 到r a ( m ) 必须激发的可控变迁，并禁止这些变迁的激发。 显然，不可控变迁的存在使得监控算法增加了步骤2 ，而步骤2 的关键是找 到允许标识的判定方法，这实质上是p e t r i 网的可达性分析。然而p e t r i 网的可达 性分析非常复杂：l i p t o n 【4 2 】指出可达性分析的计算复杂性至少随着网的规模指 数级地增长。可达性分析问题是可判定的，但是目前还没有找到可行的方法f 4 3 。 由此可知，不可控变迁存在对监控器综合来说是一个极大的挑战，是离散事件系 统监控理论研究的难点，目前已经出现了多种监控器综合方法1 5 ，3 7 ，4 4 1 。 如前所述，解决存在不可控变迁的监控问题的关键是求得允许标识的判据， 根据求解允许标识判据的差别，我们把己报道的监控器综合方法分为三类：基于 关联矩阵的方法、基于可达图的方法和路径代数法。 关联矩阵包含了p e t r i 网的全部信息，关联矩阵也是可达性分析的有力工具， 因此利用关联矩阵来判断一个标识是否属于允许标识集是目前广泛应用的方法。 它的优点是：1 ) 其方法的适用范围较广；2 ) 基于矩阵的运算使得它能够处理大规 模的p e t r i 网。它的缺点是：1 ) 给出的监控器往往不是最优的；2 ) 很少能够给出允 许监控器和最大允许监控器的存在条件；3 ) 方法比较抽象。 l i 和w o n h a m 2 8 ，45 1 基于非并发假设给出了禁止状态监控器综合方法，他 们的方法同h o l l 嘞，和k r o g h 等人的方法实质上是一致的，但是他们详细 地分析了求解监控问题的计算复杂性，并给出了一套基于线性整数规划形式 统一的方法。他们指出判断一个标识是否为允许标识是一个比非线性整数规 划还要复杂的问题，但是当不可控子网为无环网时，该问题可以简化为线性 整数规划。针对不可控了网为无环网的监控问题，他们给出了基于关联矩阵 的线性整数规划监控器算法，由于在线求解线性整数规划是非多项式时间可 解的，这使得其难以应用于实时监控。为了得到有效的监控器算法，针对不 可控子网为1 型树状网或2 型树状网的监控问题，l i 和w j n h a m 得到了形 式为线性不等式的允许标识的判据，从而得到了多项式时间内可解的最大允 许的监控器算法。后来，l i 和w b n h m 4 6 1 基于并发的假设讨论了他们的监 控器综合方法。 m o o d y 等 3 6 ，4 7 5 0 】将结构型监控器综合方法推广到存在不可控变迁的问 题，提出了一个基于关联矩阵运算的约束转换方法，它可以将给定约束转换 为一个新的约束，而新的约束是允许标识的的充分条件，然后添加控制库所 5 第一章绪论与综述 使得p e t r i 网始终满足这一约束。需要指出的是，因为转换得到的约束不是 允许标识的必要条件，因此这种方法无法保证监控器的最大允许性。而且结 构型监控器无法实现广义互斥约束的“逻辑或”，因为利用控制库所实现约 束的“逻辑或”时必须更改p e t r i 网的运行规则。另外，结构型监控器综合理 论中还有很多问题等待解决，例如允许的结构型监控器的存在条件和最大允 许结构型监控器的存在条件，文献5 1 1 给出了不存在最大允许结构型监控器 的实例。b a s i l e 等| 5 1 ，5 2 1 进一步研究了约束转换方法，在提高算法效率上有 所贡献。 陈浩勋等【5 3 5 6 】给出了利用库所递减量设计监控器的方法，他们首先给出 了乖j 用关联矩阵求解库所递减量的方法，然后通过库所递减量给出允许标识 的判断条件，进而设计监控器。这种方法和m o o d y 的方法有相同的优点：允 许标识的判断条件是离线计算的，因而监控器算法的计算效率很高；但也有 类似的缺点：脓控器不是最大允许的，而且很难给出允许监控器的存在的条 件。 d a r o n d e 肌和ef 57 研究了活的事件图上的监控问题：他们指出在事件图 上可能无法设计结构型的监控器，即使能够设计结构型的监控器，其控制器 库所的数目随不可控予网的规模指数级地增长；他们给出了一种需要在线求 解整数规划的最大允许监控器算法，由于整数规划的高计算复杂性，使得这 种方法很难应用于实时监控。 基于可达图的监控器综合方法静优势在于：1 ) 设计方法和 淞，理论是一致 的；2 ) 其对应的控制规范不局限于广义互斥约束。其劣势是对象网必须是有界的， 即状态空间是有限的，另外只能用于小规模的p e t r i 网，因为网的状态空间随网的 规模指数级地增长。 g h 胡h i 等【5 8 ，5 9 介绍了一种利用状态可达图来设计监控器的方法，这种方 法的思想类似于f a v 理论：首先得到p e t r i 网的可达图，其次找到一个不存 在非允许标识的子图，再次通过求解整数规划给出监控器库所添加方法。该 方法存在下列问题：首先在某些情况下该方法无法给出允许的监控器，其次 其根据子图求解监控器库所的计算复杂性极高，只有在某些特殊情况下才能 简化为线性整数规划。 u z a m 等1 6 0 也利用可达图来设计监控器，与g h a 舶d 的方法的不同之处在 于他利用了p e t r i 网的简化技术，这使得最后生成的仅包含允许标识的子图 要小的多。 6 浙江大学博士学位论文 茹雨和吴维敏等3 4 ，6 1 1 提出了基于逆网的可达图的监控器综合方法，即通 过逆网上的可达图找到允许标识集。 我们最感兴趣的监控器综合方法是h o l l o w a y 和k r o 曲1 0 ，3 1 ，35 提出的路径 代数法，这种方法以图论为工具来研究网结构和可达性之间的关联( 规律) ，然后 根据这些规律来设计监控器。路径代数法相对基于关联矩阵和基于可达图的方法 有很多优点：1 ) 设计的监控器是依据网结构的，因此往往可以给出允许监控器和 最大允许监控器的存在的充要条件；2 ) 依据了受限p e t r i 网的性质，得到的允许标 识的判据一般非常简单；3 ) 以图论为工具，相对于基于关联矩阵的方法更为直观。 下面我们简单介绍一下近年来基于路径代数法的监控器综合研究工作： h o l l o w a y 和k r o 曲等f 1 0 ，3 1 ，3 5 研究了环状事件图上的控制规范为禁止条 件的控制问题。禁止条件是一类特殊的广义：巨斥约束，它要求每个库所的权 值为0 或1 ，约束的上限为1 。他们给出了形式为路径状态的逻辑运算表达式 的允许标识的判据，得到了最大允许监控器存在的充要条件，并给出了最大 允许监控器的设计方法。 h 0 1 l o w a y 等f 6 2 研究了包含事件图和状态机的一类p e t r i 网的禁止状态监控 问题，他们将网内的路径做了细致的划分，然后给出了路径集合上的代数系 统，并给出了允许标识的判断条件，并得到了最大允许监控器存在的充要条 件和最大允许监控器算法。由于他们针对的控制规范是满足前向路径等条件 限制的禁止条件，因此他们的方法的适用范围受到了较大的限制。 h 0 1 l o w a y 等 6 3 ，6 4 】利用路径代数法研究了p e t r i 网上一个库所的最大标识 的计算方法，该方法是对文献 6 2 】可达性分析的扩展，为研究禁止状态问题 打下了较好的理论基础。 b o e l 等 3 9 j 利用影响路径和影响域研究了状态机上的广义互斥约束的监控 问题，并利用影响域的状态给出了允许标识的判断条件，给出了最大允许监 控器的存在条件和最大允许监控器的算法。s t r e m e r s c hf 6 5 1 研究了在状态机 上限制每个库所标识的上界问题，虽然控制规范和文献3 9 不同，但是监控 器的设计方法和39 类似。 陈浩勋 5 5 利用不可控路径给出了影响不可控子网的定义，指出监控问题并 非总是和不可控予网的全部库所和变迁相关，并且证明监控问题仅和影响不 可控子网有关。由于影响不可控子网是不可控子网的子网，因此陈浩勋的结 论可以大大降低监控问题的计算复杂性，并拓宽了其它监控器综合方法的适 用范围。s t r e m e r 8 c h 等 6 6 ，6 7 】指出监控问题仅和对象网的某个子网有关，并 给出了该予网的理论上的定义，但是没有给出具体的生成算法。 7 第一章绪论与综述 b o e l 等f 6 8 研究了不可控影响予网为无环网的限制某个库所标识的上界的 控制问题，首先给出了利用关联矩阵生成不可控影响予网的代数方法，其次 给出了实现单个库所标识上界的最大允许监控器算法：1 ) 将无环网分解成序 状的层( 库所的集合) ；2 ) 定义了各层之间极小加的代数规则，并给出了单 个禁止库所不可控可达的最大标识的表达式；3 ) 利用该表达式设计最大允许 的监控器。 s t r e m e r s c h 和b o e l 【6 7 ，6 9 】继续研究了无环网上的监控问题，对文献【6 8 】的 方法进行了扩展，将控制规范从单禁止库所的约束推广到了广义互斥约束， 并讨论了通过改变p e t r i 网的变迁激发规则来解决约束的“逻辑或”的控制 问题，给出了允许标识的判断条件，给出了最大允许监控器存在的充要条件， 并给出了最大允许监控器的算法。 董利达等f 7 0 ，7 1 1 定义了序状p e t r i 网，给出了序状p e t r i 网的性质和可达性 分析方法，研究了影响不可控子网为序状p e t r i 网的监控问题，得到了允许 标识的判据，给出了最大允许监控器的存在条件，而且构造了最大允许监控 器算法。 我们可以看出，目前出现的各种基于路径代数法的监控器综合方法的适用范围都 是受限的，还有很多实际的监控问题有待解决。 从监控器的实现形式上，目前共有三种类型的监控器，它们是结构型监控器、 逻辑型监控器和混合型监控器7 1 1 ：结构型监控器3 3 ，5 0 ，7 2 是通过添加库所来 影响对象网的状态演变从而为对象施加控制的，它的理论依据是库所的容量有限 7 2 】。逻辑型监控器【1 0 ，3 7 ，3 9 是通过状态的函数为对象施加控制的：给定一个标 识，该函数给出要禁止的变迁。直观地讲，逻辑型监控器是通过施加外部的控制 动作来影响对象的状态演变的，因此逻辑型监控器更符合连续系统的控制器形式。 结构型监控器相对于逻辑型监控器有以下优势f 1 5 1 ：1 ) 控制动作的计算较快，因 为它无需在线计算；2 ) 对象和闭环系统可以用相同的p e t r i 网算法模拟：3 ) 闭环系 统是由标准的p e t r i 网规则组建的，便于利用p e t r i 网工具来研究闭环系统的性能， 如活性等。逻辑型监控器的优点是：只要存在允许监控器，就存在最大允许的逻辑 型监控器。但是在某些存在允许监控器的场合，不存在最大允许的结构型监控器。 吴维敏7 2 ，7 3 1 提出了一种混合型监控器，它首先设计观测子网，然后给出观测子 网的标识的函数，对应一个标识，该函数给出要禁止的变迁。由于监控器算法是基 于观测子网的状态的，因此在状态的提取上，它具有结构型监控器的优点；而