（控制科学与工程专业论文）离散事件系统的混合监控理论.pdf

摘要 摘要 由于计算机科学及其应用的快速发展，研究者发现了一类与传统连续变量系统完全不 同的新的动态系统，被称为离散事件系统。离散事件系统的最大特点是系统状态的改变是 受事件而不是时间驱动的，属于一类人造系统。典型的离散事件系统包括了离散制造系 统( 尤其是柔性制造系统和计算机集成制造系统) 、通讯网络、交通控制系统、随机服务 系统和计算机操作系统等 离散事件系统的主要研究方向是性能分析和系统监控理论，而研究监控理论的数学工 具主要有自动机形式语言和p e t r i 网。这两者各有优劣势：自动机形式语言的离散事件系 统监控理论具有概念清晰、逻辑严谨和形式完美的优点，但是它却难以处理物理事件因素， 无法描述并发，以及会存在“状态爆炸”问题； 为有效的分析能力，但缺乏统一的理论体系， 而p e t r i 网则具有更为强大的建模能力和更 以及难以保证最后的闭环系统是最大允许控 制的本论文的研究内容从发挥两类工具的优点，克服其缺点为出发点，提出离散事件系 统的混合监控理论本论文的主要工作可以概括如下： 1 提出了基于约束转换的离散事件系统混合控制方法，这是对综合自动机和p n 的 离散事件系统混合控制方法的改进和完善，从而使之适用范围更为广阔 2 从提高计算效率和可表达性出发，首次提出了离散事件系统的混合分散控制针 对分散监控器会存在冲突这一问题，我们将r w 理论中的协调器概念引入到p n 中来加以解决，从而保证了最后的闭环系统仍然是无阻塞的。针对协调器的设计 和实现，我们同时提出了经验法和结构法两种方法 3 首次将控制流网( c f n ) 这一在自动机下，设计分散控制中的协调器结构方法运 用到p e t r i 网中，用来设计无死锁的混合控制方法这一方法充分利用了c f n 的 特性和优点，使得我们可以高效方便的判断系统是否存在死锁，同时针对存在的 死锁给出控制约束，最后形成最大允许的无死锁闭环系统 4 从形式语言的角度探讨了离散事件系统的分层控制，拓展了获取无阻塞分层控制 的判断方法；同时，利用一个经典的例子对分层控制在p e t r i 网模型下的应用进行 了尝试，取得了较好的结果；从而建立了完备的混合监控理论架构同时，探讨 了利用分层控制进行一类离散事件系统的调度控制，针对一个经典的例子，给出 i 浙江大学博士学位论文 了具体实现的算法和结果 5 最后讨论了离散事件系统混合监控理论的应用问题。首先，给出了本文所讨论的 混合控制方法的一个理论应用，即在离散事件系统的“或逻辑”这一非凸问题上面 的应用另外，详细给出了离散事件系统监控理论在交通路网控制这一具有实际 工程意义背景上的应用。 综上所述，本文在离散事件系统的混合监控理论上面做了大量工作，讨论和研究了包 括集中控制、分散控制和分层控制在内的不同控制方法，从而初步构建了一个较为完备的 理论架构另外，初步探讨了该理论在工程应用方面的可能性 关键词：离散事件系统；监控理论；混合方法；分散控制；分层控制；p e t r i 网 i i 摘要 a b s t r a c t d u et ot h er a p i dd e v e l o p m e n to fc o m p u t e rs c i e n c ea n di t se x t e n s i v ea p p l i c a t i o ni nm o d e r n s o c i e t y , s o m er e s e a r c h e r sf o u n dan e wt y p eo fd y n a m i cs y s t e mc a l l e dd i s c r e t ee v e n ts y s t e m s ( d e s ) ，w h i c hi s d i f f e r e n tf r o mc o n t i n u o u sv a r i a b l ed y n a m i cs y s t e m s t h ed o m i n a t i n g c h a r a c t e r i s t i co fd e si st h a ti t se v o l u t i o ni sn o td r i v e nb yt i m eb u tb ye v e n t s e s s e n t i a l l y , d e si s am a n m a d es y s t e m t y p i c a ld e si n c l u d ed i s c r e t em a n u f a c t u r i n gs y s t e m s ( e s p e c i a l l yf m sa n d c i m s ) ，c o m m u n i c a t i o nn e t w o r k s ，t r a f f i cc o n t r o ls y s t e m s ，r a n d o ms e r v i c es y s t e m sa n dc o m p u t e r o p e r a t i n gs y s t e m s ，a n ds oo n d e sr e s e a r c hm a i n l yc o n s i s t so fs y s t e mp e r f o r m a n c ea n a l y s i sa n ds u p e r v i s o r yc o n t r o l t h e o r y t h em a i nr e s e a r c ht o o l so fs u p e r v i s o r yc o n t r o lo fd e s a r ea u t o m a t a f o r m a ll a n g u a g ea n d p e t r in e t t h e s et w ot o o l sb o t hh a v ei t so w na d v a n t a g e sa n dd i s a d v a n t a g e s f o ra u t o m a t a f o r m a l l a n g u a g e ，i th a sc l e a rc o n c e p t i o n s ，p r e c i s el o g i ca n di n t a c tt h e o r e ms t r u c t u r a l ，b u ti ti sd i f f i c u l t t ot r e a tw i 廿lp h y s i c a le v e n t s ，c o n c u r r e n c ea n dt h es t a t ee x p l o s i o np r o b l e m f o rp e t r in e t ，i th a s m o r ep o w e r f u lm o d e l i n ga n da n a l y s i sa b i l i t y , b u ti ti sl a c k i n go fu n i f o r mt h e o r yf r a m e w o r ka n d d i f f i c u lt o g u a r a n t e e t h em a x i m a l l yp e r m i s s i v e n e s so ft h ec l o s e d l o o ps y s t e m s i nt h i s d i s s e r t a t i o n , w et r yt oc o m b i n et h e s et w ot o o l st og i v eo u tt h eh y b r i ds u p e r v i s o r yc o n t r o lo fd e s o u re f f o r t sc a nb ec a t a l o g e d 嬲f o l l o w s ： f i r s t l y , t h eh y b r i da p p r o a c h t o s u p e r v i s o r y c o n t r o lo fd e sb a s e do nc o n s t r a i n t s t r a n s f o r m a t i o ni si n t r o d u c e d o u ra p p r o a c he x t e n d st h eh y b r i da p p r o a c hw h i c hc o m b i n e st h ep n a n dr wt h e o r y , a n de n l a r g e st h ea p p l i c a t i o nr e g i o n s s e c o n d l y , i no r d e rt oh a v em o r ee f f i c i e n tc o m p u t a t i o na n dp o w e r f u le x p r e s s i o n , w eg i v et h e h y b r i dd e c e n t r a l i z e dc o n t r o lo fd e s a tt h ef i r s tt i m e t h ec o o r d i n a t o r , w h i c hi sa ne f f i c i e n tt o o l t os o l v et h eb l o c k i n gp r o b l e mb e t w e e nt h ed e c e n t r a l i z e ds u p e r v i s o r s ，i si n t r o d u c e di n t op e t r in e t t ok e e pt h ec l o s e l o o ps y s t e mt ob en o n - b l o c k i n g t w om e t h o d s ，t h ee x p e r i e n c ea n dt h es t r u c t u r e w a y , a r ea d d r e s s e dt od e s i g nt h ec o o r d i n a t o r t h i r d l y , t h ec o n t r o lf l o wn e t ( c f n ) ，w h i c hi san e wg r a p h i c a lm o d e lt h a tc a nh e l pt od o i i i 浙江大学博士学位论文 c o m p u t a t i o n a l l ye f f i c i e n tc o n t r o l l e rd e s i g nf o rd e s i nt h ef r a m e w o r ko fa u t o m a t a , i si n t r o d u c e d t ow o r kt o g e t h e rw i t hp nt o g e td e a l l o c k - f r e ec o n t r o lo fd e s w i t hf u l l ye x p l o i t i n gt h e c h a r a c t e r i s t i c sa n da d v a n t a g e so fc f n ，i ti su s e dt od e t e c tt h ed e a d l o c ki nt h es y s t e m ，a n dg i v e c o n s t r a i n t st o p r e v e n tt h e d e a d l o c ka n do b t a i nt h em a x i m a l l yp e r m i s s i v ed e a d l o c k f r e e c l o s e d l o o ps y s t e m s f o u t h l y , w ed i s c u s st h eh i e r a r c h i c a lc o n t r o lo fd e s i nt h ev i e wo ff o r m a ll a n g u a g e a n d t h e nw ea p p l yt h et h e o r yi n t op ns t r u c t u r e a l s ow ea p p l yt h eh i e r a r c h i c a lc o n t r o li nt h e s c h e d u l i n gc o n t r o lo fd e s a l lt h i se f f o r t sh e l pt oc o m p l e t et h eh y b r i ds u p e r v i s o r yc o n t r o l a r c h i t e c t u r e f i n a l l y , w ea d d r e s st h ea p p l i c a t i o n so f t h eh y b r i da p p r o a c ht os u p e r v i s o r yc o n t r o lo fd e s i n t h e o r ys i d e ，ah y b i r da p p r o a c ht o o r - l o g i c c o n t r o lo f d e si si n t r o d u c e d i ne n g i n e e r i n gs i d e , t h em o d e l i n ga n dc o n t r o lo fr o a d - n e ts y s t e mi sd i s c u s s e d t os l l m m a r i z ei naw o r d ，w em a d eag r e a te f f o r to nt h ed e v e l o p m e n to ft h eh y b r i d a p p r o a c ht os u p e r v i s o r yc o n t r o lo fd e s ，i n c l u d i n gc e n t r a l i z e dc o n t r o l ，d e c e n t r a l i z e dc o n t r o la n d h i e r a r c h i c a lc o n t r o l ，a n de l e m e n t a r i l yo b t a i nac o m p l e t ea r c h i t e c t u r eo fh y b r i ds u p e r v i s o r y c o n t r o lo fd e s i na d d i t i o n , t h ep o s s i b i l i t yo fa p p l y i n gt h eo b t a i n e dt h e o r yt oe n g i n e e r i n gi s d i s c u s s e d k e yw o r d s ：d i s c r e t ee v e n ts y s t e m s ；s u p e r v i s o r yc o n t r o l ；h y b r i da p p r o a c h ；d e c e n t r a l i z e d c o n t r o l ；h i e r a r c h i c a lc o n t r o l ；p e t r in e t i v 主要符号对照表 主要符号对照表 离散事件系统 连续变量系统 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 网的不客观变迁集 一个库所 v 吣 吣 | | | 一 删 似 | 耋 | 耋 删 册 研 p t r w m t l l p 浙江大学博士学位论文 v i 库所p 的输入变迁集合 库所p 的输出交迁集合 一个库所 库所t 的输入变迁集合 库所t 的输出变迁集合 表示一个离散事件系统的语言 l 的受控语言 l 的某个子语言 一个离散事件系统的自动化模型 有限字符集 包含空字符占的有限字符串集 空字符串 一个字符串 正数集 自然数集 空集 j p ， ， 广 l k e g z 占 s z n 矽 图表目录 图表目录 表1 1d e s 建模和分析的方法2 图3 1 一个简单的p e t r i 网系统1 9 图3 2 基于混合方法的离散事件系统监控。2 0 图3 3 闭环混合系统( p n 为受控对象，a u t o - n e t 为监控器) 2 6 图3 4 共享区域系统( p n 模型) 2 7 图3 5 仅考虑p a r i k h 向量的约束l 示意图2 8 图3 6 考虑全部向量的约束l 示意图2 9 图3 7 约束2 的示意图2 9 图3 8 约束3 和约束4 的示意图2 9 图3 9p 2 的等价自动机模型3 0 图4 1 一个简单的加工系统c f n 模型3 7 图4 2 一个柔性制造系统( f m s ) 4 0 图4 3 简化的柔性制造系统4 0 图4 4 加工机器m 1 的自动机模型4 l 图4 5 缓存器b 1 的自动机模型4 1 图4 6 原系统的p n 模型4 5 图4 7 带监控器和协调器的闭环系统模型4 5 图5 1 混合方法示意图4 9 图5 2 运输线系统。5 5 图5 3 运输线系统的p n 模型5 5 图5 4 运输线系统的p n 闭环系统5 6 图5 5 带不可控变迁的运输线p n 系统5 6 图5 6 无死锁带不可控变迁的运输线p n 闭环系统5 7 v i i 浙江大学博士学位论文 v i i i 图5 7 柔性制造系统的c f n 模型5 8 图5 8 柔性制造系统的p n 模型5 8 图5 9 带控制库所的闭环p n 柔性制造系统模型5 9 图6 1d e sg 6 2 图6 2 单层控制结构图6 3 图6 3 两层控制结构图一6 4 图6 4 运输线系统6 7 图6 5 运输线系统p n 模型6 7 图6 6 受控传输线系统的表达图6 8 图6 7 显性化后的传输线系统表达图6 8 图6 8 模块化的传输线系统表达图6 9 图6 9 传输线系统的上层p n 模型6 9 图6 1 0 未受控传输线系统的上层p n 模型6 9 图6 11 分层控制器设计图7 2 图6 1 2 哲学家就餐问题示例7 4 图7 1 一个简单的p n 系统8 0 图7 2 模型转化图示81 图7 3 带有监控器的闭环控制系统8 4 图7 4 实际路网示意图。8 5 图7 5 路网系统基本结构图8 6 图7 6 路网数据模型的组成。8 7 图7 7 路网模型图8 8 图7 8 路网的坐标图8 9 图7 9 仿真参数设置图。9 1 图7 1 0 路口转向禁止示例图9 2 图7 1 1 十字路口位置细分图9 3 图7 1 2 十字路口的交通灯模型9 4 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得澎姿盘茎或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： 签字日期：7 咿夕 年q 只| f l 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂 有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权迸望盘鲎可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期： 导师签名： 签字日期： 第一章绪论与综述 第一章绪论与综述 本章概述了离散事件动态系统( 简称离散事件系统) 理论，着重介绍基于自动机和 p e t r i 网的离散事件系统监控理论的研究内容和现状，同时也给出了本论文主要研究内容和 研究思路。 1 1 离散事件系统的基本概念 对于离散事件系统( d e s ：d i s c r e t e - e v e n ts y s t e m s ) 的研究最早可以追溯到对排队现 象和排队网络的研究从现今观点来看，排队论、网络分析、计划评审和调度排序等方法 所面对的研究对象都可归入d e s 的范畴但是，近年来d e s 所以受到人们的重视，并被 认为是系统与控制理论领域的一个前沿方向，一个重要的原因就是当今一大批高新技术发 展的需要和推动的结果 现今对离散事件系统研究的兴起出现在1 9 8 0 年前后那个时期，随着信息处理技术、 计算机技术和机器人技术等的发展和完善和广泛应用，在通信、制造、交通管理、军事指 挥等领域相继出现了一批反应技术发展的人造系统，其典型例子如柔性生产线或装配线、 大规模计算机和通信网络，空中或机场交通管理系统等等。 “离散事件系统”的称谓，首先是由哈佛大学何毓琦教授在1 9 8 0 年前后引入的，概指 上面提到的如柔性生产线或装配线、大规模计算机和通信网络、空中或机场交通管理系统 等一类人造系统，以区别已经广泛研究的连续变量动态系统。 构成离散事件系统的基本要素是离散事件。d e s 行为随时间的演化过程就是离散事件 复杂交互影响的结果粗略的说，离散事件是指d e s 中发生在离散时刻的事件所谓事 件则是使d e s 状态发生变动的一个行为或事情 和连续变量动态系统不同，d e s 中离散事件的发生时刻通常是异步的离散事件的发 生时刻，取决于这一时刻前系统行为的演化过程柔性生产线中的“工件到达机床”和“工 件加工完成”，通信网络中的“信号到达网络”和“信息传递结束”，就是离散事件的一些典型 例子 浙江大学博士学位论文 d e s 中的离散事件具有三个基本特点【1 4 2 】。一，离散事件是导致d e s 状态发生跃变 和触发新离散事件的唯一因素，即离散事件是驱动系统状态演化的基本因素；二，离散事 件的发生时刻是异步的和非约定的，即发生时刻由且只由系统的演化过程所决定；三，离 散事件是研究d e s 的主体，对d e s 的分析归结为确定离散事件交互影响所导致的系统状 态的演化过程，对d e s 的控制归结为禁止不期望事件的发生或者使事件按期望的时序发 生。 粗略地讲，d e s 是由离散事件驱动，并由离散事件按照一定的运行规则相互作用，来 导致状态演化的一类系统根据这个定义，我们知道d e s 有两个特点：第一，d e s 的系 统属性表现为是由离散事件驱动，而这正是其取名为离散事件系统的缘故；第二，d e s 的 人造属性表现为基于人为的运行规则，而这也是其能够覆盖一大批高科技中的人造系统的 原因所在 1 2 离散事件系统的建模和分析方法 和c v s ( 连续变量系统) 一样，在d e s 的研究中，建模问题具用同样的重要性。从 一般意义上说，模型是指反映系统主要行为特征的变量与系统结构参数间的一种关系模 型可以采用多种形式来进行表征，包括数学方程、映射、数据集合、曲线、图表、计算机 程序和语言描述等。基于系统的模型，可分析系统的行为性能及其与系统结构和参数的关 系，可进而研究系统的控制和优化。不管是对c v s 还是对d e s 的研究，目前主流的理论 和方法，几乎都是建立在系统模型的基础之上的 在d e s 中，常把d e s 的模型和分析区分为三个基本层次，即逻辑层次，代数层次和 统计性能层次 1 4 2 其各自采用的数学工具如下表所示。 2 表1 1d e s 建模和分析的方法 逻辑层次有限自动机形式语言方法、p e t r i 网分析方法 代数层次极大极小代数方法 性能层次排队网络方法、摄动分析方法、仿真方法 总体而言，现今对离散事件系统建模的研究，还远远不够成熟和完善。应当说，不管 第一章绪论与综述 是从形式的统一性，还是数学表达的简明性和计算分析的可行性，都远不如连续变量动态 系统的建模那样完美。更广义的说，由于d e s 属于人造系统的范畴，系统机制中可能会 同时并存多种交互作用，如事件间的交互作用，人与系统的交互作用、系统和环境的交互 作用等，系统各种关系中也可能会同时含有多种表达形式，如定量、定性和知识的形式等 因此，一个复杂的离散事件系统的建模，最终可能需要同时借助于运筹学，系统与控制理 论、人工智能与自然语言理解等多学科的方法的结合 1 3 1 1 。 就控制而言，离散事件系统的主要研究方向有两个：一是系统的工作性能分析，其主 要目标为在一定条件下优化系统的性能指标，使得系统能更加有效地提供服务，为改进现 有系统或者设计新系统提供理论依据 1 3 1 ；- - 是离散事件系统监控理论，其目的是通过外 部输入使系统按照人们预期的行为工作。为了区别连续系统上的控制器，离散事件系统上 的控制器称为监控器，离散事件系统的控制问题称为监控问题，监控器的设计过程称为监 控器综合。 离散事件系统的监控理论起始于上世纪8 0 年代r a m a d g e 和w o n h a m 的开创性工作 8 7 9 0 ，1 1 8 】。在对象为有限状态机( 自动机) 的前提下，他们利用形式语言自动机作为研 究工具，给出了禁止状态监控器综合的框架( 称为r w 理论) 该理论的基本原理是：设 计一个监控器自动机，使得监控器自动机和对象自动机同步生成的语言包含在规范语言 内。这一框架中，闭环系统由监控对象和监控器组成，这和现代控制理论非常类似 近些年来，由于r w 理论具有逻辑严谨、概念清晰和形式完美的优点，其发展迅速， 取得了非常丰富的成果但是形式语言自动机的方法具有其固有的局限性，主要是难以 处理物理事件因素，无法描述并发，以及会存在“状态爆炸”问题 为了克服上述的缺点，研究者引入了p e t r i 网来代替形式语言自动机来作为离散事件系 统的建模和研究工具。相对于自动机模型，p e t r i 暖 有如下的几个优点 2 3 ，3 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 网作为一种图形化建模工作，相比于语言和数学符号对系统的描述，更加直观易 懂，也更加容易被应用工程师掌握和理解 3 浙江大学博士学位论文 当然，自动机也有其独特的优点，比如能够保证整个系统是无阻塞( n o n b l o c k i n g ) ， 并且所获得的控制室最大允许的( 即最优的) 自动机和p e t r i 网两种方法都有各自无法取 代的优势，因此很多研究者认为未来的研究方向是将两种方法融合起来，充分发挥各自的 优势。本论文即是在这方面的一个尝试。 1 3 离散事件系统监控理论概述 离散事件系统监控理论所要研究的问题，概括的说就是设计一个控制器，使受控对象 的行为满足控制规范的要求根据控制规范其形式不同，目前的研究方向主要可以分为四 个方面： 禁止状态问题 1 9 ，3 1 ，5 4 ，5 5 ，8 0 ，1 0 7 】 禁止状态问题的控制规范是以禁止状态集或合法状态集的形式给出，要求所 有闭环系统的可达状态必须属于合法状态集，而不能有状态进入禁止状态集该 类问题一般采用状态反馈监控理论来进行分析，即控制策略( 监控器的综合) 是 基于离散事件系统当前的状态获得的 禁止字符串问题 2 3 ，4 8 ，1 0 1 】 字符串指的是事件发生的一组语言序列，相应的，该类问题的控制规范是以 合法语言集或者禁止语言集的形式给出，要求闭环系统的所有语言序列必须属于 合法语言集，而不能出现禁止语言集该类问题一般采用事件反馈监控理论进行 分析，即控制策略是基于离散事件系统已发生的事件序列来获得的 死锁防止问题 3 6 ，3 7 ，4 3 ，4 5 ，8 2 】 所谓出现死锁，指的是系统部分或者全部不能继续运行的状况( 即局部死锁 和全局死锁) ，这是系统不希望出现的运行状态，必须通过外部监控器来保证系 统不会进入这样的死锁状态。死锁防止的控制规范是根据系统的运行性质来设定 的，以保证系统的每一个可达状态都能进一步执行。 活性保持问题 2 7 ，3 1 ，3 2 ，4 5 ，9 5 ，9 6 ，9 9 ，1 0 0 】 所谓离散事件系统的活性，指的是闭关系统的每一个可达状态均能保证所有 事件可以进一步的被执行。没有死锁的系统一般情况下往往被称为活的系统，所 4 第一章绪论与综述 以活性保持和死锁防止是一对对偶问题。活性保持的控制规范也是根据系统的运 行性质来设定的 需要指出的是，虽然以上四类问题所给出的控制规范不相同，但是第三类死锁防 止问题和第四类活性保持问题，其本质上时一致的，而且他们都可以直接被转化成第 一类禁止状态f q 题进行解决 2 7 ，4 3 。同样的，状态反馈监控和事件反馈监控也是可以 实现相互转化的 1 4 基于自动机和形式语言的离散事件系统监控理论 基于形式语言自动机的离散事件系统监控理论，即r w 理论，经过多年的发展，已经 形成了非常严密的一个体系，主要包括了集中控制、分散控制和分层控制。 1 4 1 集中控制 所谓集中控制，指的是被控对象受控于一个单一的监控器的控制方法和结构这一方 法最早的研究工作由r a m a d g e 和w o n h a m 提出【8 7 。9 0 ，1 1 9 。在他们的方法中，重点研究 了基于可控性的最优无阻塞控制器的存在问题，以及控制器综合的多项式算法问题之后， 在上述工作的基础上，l i n 和w o n h a m 将部分可观性问题予以了研究。在可控性问题之上， 他们给出了可观性之下，存在监控器的充分必要条件 6 9 ，7 1 。 集中控制是离散事件系统监控理论的基础，之后的一系列研究都是这一控制的后续 但是，获得一个全局系统的完备控制逻辑往往是非常空难g o h a r i 和w o n h a m 已经证明， 随着被控对象模型的状态空间的增大，监控器的综合问题实质上是一个n p h a r df q 题【2 5 】。 所以对于大型d e s ，集中控制就变得十分困难，我们需要其他方法来获得合适的监控器 1 4 2 分散控制 在分散控制中，被控对象根据一定的法则，被分解成若干个模块，每一个模块由一个 本地监控器所控制，该本地监控器具有相应的部分可观性和控制权。有关这一方法的研究， 最初是由l i n 和w o n h a m 发起g 寸 6 8 ，7 2 这一方法的研究基于一个自然的假设，就是全局 的控制约束是由一系列本地约束所联合构成。研究者们同时考了对于本地时问具有完全可 观性和部分可观性的情况，给出了保证分散监控器存在的充分条件 3 ，1 1 0 。r u d i e 和 5 浙江大学博士学位论文 w o n h a m 进一步完善了这一方法，他们定义了共同可观性( e o o b s e r v a b i l i t y ) ，作为分散监 控器存在的充分必要条件 9 3 1 。y o o 和l a f o r t u n e 进一步拓展了共同可观性( c o o b s e r v a b l i l i t y ) 的概念，从而允许对共享事件进行各种各样的决策 1 2 4 - 1 2 6 。 最近，用可通信的监控器来实现分散控制引起了广泛的关注研究者希望通过这个 方法可以在共同可观性无法保证的情况下来协同解决可观性的协调。很多不同的用来实现 通信机制的模型陆续被介绍出来。w o n g 和v a l ls c h u p p e n 使用普通因果图来对分散监控器 之间的通讯渠道进行建模j i l l 。从而他们得到了对于存在不对称通信的两个分散控制器的 充分必要条件；在相同的设定下，同时获得了存在最小通信渠道的一个充分条件，但是如 何计算这样一个渠道仍然是一个开放问题。r i e k e r 和r u d i e 把这个问题放在基于逻辑模型 的认知架构下进行处理。他们给出了寻找最小通信渠道的一个贪婪算法 9 l 】。基于扩展的 轨迹模型，b a r r e t 和l a f o r t u n e 给出了一个所谓的“信息机构模式”( i n f o r m a t i o ns 咖c 嘶 f o r m a l i s m ) ，用来获得通信和控制间的依存关系 3 】对于监控器可以或不可以预测后续的 通信的两种情况，他们给出了是否存在分散监控器的充分必要条件另外，他们还提出当 无法预测后续通信的情况下，综合最小通信规则的一个算法。r u d i e ，l a f o r t u n e 和l i n 定 义了由一些函数组成的一种通信规则，这些函数连接了每一个可观字符串和相应的通信事 件子集 9 2 】。他们给出了在两个通信监控器情况下，寻找最小通信规则的指数复杂度的算 法。进一步，研究者们考虑到了无法忽略不计的通信滞后问题 1 0 6 】给出了有关可判定 性的结果，【8 6 恻给出了“滞后共同可观测性”的概念。 总的来说，分散控制是一个非常清晰的模块化控制，用以改进控制逻辑的可理解性和 降低运算复杂度。但是，这一控制方法也有其不足的地方：一是，该方法往往预先假设非 阻塞问题不用考虑；二是，该方法过于关注控制与观测性的折中协调，而不够关注如何设 计监控器综合的算法步骤。 1 4 3 分层控制 在分层控制中，被控对象受控于分层的分散监控器。这是控制体系一项非常具有创新 性的思想，它将分层的模型抽象技术引入到分散控制的结构中，从来获得了非常明显的计 算效率在这一体系的研究中，至关重要的非阻塞特质是核心问题之一 纯分层控制最初是由z h o n g 和w o n h a m 提出的，在他们的文献 1 2 9 】中给出了一个两 级的分层机构，其中高层的抽象模型是通过普通因果图集成的他们给出叫“层次一致性” 6 第一章绪论与综述 ( h i e r a r c h i c a lc o n s i s t e n c y ) 的核心条件，以保证高层监控器可以正确地应用到下层系统中 w o n g 和w o n h a m 拓展了这一方法和结果首先，层次一致性被基于控制结构( c o n t r o l s t r u c t u r e ) 这一新概念的“控制一致性”( c o n t r o lc o n s i s t e n c y ) 所代替；更为重要的，通过利 用因果图的可观性，他们获得了非阻塞性 1 1 3 在上述结果的驱动下，w o n g 和w o n h a m 进一步给出了分散控制的一个一般性的条件方法，这是一个简单但有效的分层结构。在正 常的综合分散监控器后，再加上一个协调器，作为高层监控器来解决潜在的存在在底层监 控器中的冲突。他们还给出了保证控制的最优性和无阻塞性的充分条件【1 1 4 。进一步，f e n g 和w o n h a m 通过将普通因果图替换为自然映射，特殊化了前面设计协调方式的方法，从而 使得这一方法更加具有实际性。同样的他们也给出了最优性和无阻塞性的充分条件，而且 进一步给出了由分层分散监控器和协调器组成的系统化的监控设计【1 6 。 另外，在文献 z 8 】中，h i l l 和t i b u r y 给出了一个递增的模块监控器的分层机构这一 方法的特别之处是，通过限制在分层机构中同一层次的监控器之间的共享事件，来获得全 局的非阻塞控制。s c h m i d t 等人考虑了高层监控器在低层的最优无阻塞应用 9 4 。他们找 到了充分结构条件，在这个条件中，一个特殊结构的下层监控器和其相应的高层结构，一 起保证了分层一致性和无阻塞性这些分层体系的结论被应用到分散的体系中，用来获得 分层分散最优无阻塞控制l e d u c 等人提出了一种基于界面的分层控制方法 4 9 ，5 0 。这个 方法将整个系统分割成高层的主子系统和下次子系统，以及他们中间的“请求”和“回复”通 信界面。 1 5 基于p e t r i 网的离散事件系统监控理论 基于p e t r i 网的离散事件系统监控理论相对上述基于自动机的，一般没有非常成熟的理 论体系。在这里我们可以基于其控制器的形武予以相对的划分和分析p e t r i的状态反馈 控制器，从形式来分，一共有三类：逻辑型监控器、结构型监控器和混合型监控器。已自 动机形式语言为工具得到的监控器，一般是逻辑型监控器；而i 麸p e t r i 为工具，得到的监 控器即可是逻辑型，也可以是结构型。 7 浙江大学博士学位论文 1 5 1 逻辑型监控器 所谓的逻辑型监控器，指的是控制律由一个逻辑函数来实现，下一步控制动作由逻辑 函数根据当前系统的状态或者已经产生的语言序列来决定。其方法主要有路径代数法和线 性代数法。 路径代数法首先是由h o l l o w a y 提出的 3 2 】。该方法以受控循环标识图( c o n t r o l l e d m a r k e dg r a p h ) 作为建模工具，来解决系统的禁止状态问题该方法的监控器本质是一个 逻辑运算器，它通过受控变迁进行控制，所以称之为逻辑型监控器这一方法定义了p e t r i 网中的路径，给出了路径集合上面的一种代数( a l g e b r a ) ，通过运算来得到禁止状态问题 的代数表达式。利用该表达式，能够判断系统何时进入禁止状态、何时需要进行控制，因 此不需要对整个状态空间进行搜索式算法在此基础上，l 汛g l l 对于境遇基于图论的路径 代数法进行了拓展 4 8 】。他改进了禁止状态问题的描述和反馈控制律的特性，而且有效的 减少了计算量，并进而提出了非确定性反馈控制律的概念 但是，路径代数法有其一定的局限性，即其控制对象必须是一类特殊结构的p e t r i l j 5 9 子 网虽然，很多研究者进行大量工作予以拓展，提高了该方法的适用区域，但是仍然无法 应用于广义p e t r i l 网中。而且，该方法没有考虑并发问题，这是非常大的一个缺憾 线性代数法，是由“和w o n h a m 提出的，这个方法利用的建模工具为向量离散事件系 统( v d e s ) ，该模型本质上等价于p e t r i 网 5 4 ，5 5 ，5 7 】( 这进一步说明可以将p e t r