1.3　混杂动态系统

混杂动态系统是结合了实际系统中的两种类型变量（连续变量或称为模拟变量，离散变量或称为逻辑变量）的系统模型。连续变量由传统的微分或差分方程建模，离散变量则由自动机或Petri网等描述其逻辑变化关系，连续与离散动态过程相互耦合、交互影响，使得混杂变量（即连续变量和离散变量）的演化不仅受连续过程中模拟控制量的影响，而且受瞬时的离散事件的影响。

混杂系统的研究备受关注，已成为当前控制理论的主流和前沿研究方向，主要原因有：

（1）微处理控制器被广泛应用，如嵌入式系统。

（2）大多数物理过程都展现一些出离散动力学特性，如从突发故障、继电切换、碰撞、阀门、齿轮等现象到各种模态的转换。

（3）系统网络化的普遍存在，分布式大系统的逻辑协议连接等。

（4）控制理论本身的发展要求，如约束条件下的控制、变结构控制等。

混杂动态系统这一模型具有一定的广泛性和普适性。如柔性制造系统中半导体和集成电路生产线的生产控制与调度；工业过程中的化工、石化、冶金等连续流程工业的生产控制与调度；电力系统中的区域性供电网的调度与监控；智能交通系统中大城市交通系统的实时指挥和监控，空中交通管理等；通信网络和计算机网络等的管理；现代飞机、巡航导弹中基于计算机与其他复杂信息处理装置的决策操作和高精度控制；各类机器人系统、车辆控制系统；智能建筑中的温度控制等。

1.3.1　混杂系统稳定性分析及研究现状

周期线性微分自动机是一类特殊的混杂动态系统，其中，连续向量场为常向量，离散状态切换按照给定的次序周期变化。周期线性微分自动机的一个典型特例是切换服务系统。切换服务系统由一台服务器和n台缓冲器组成，缓冲器中的容量以某一定常速率变化，服务器按照一定的规则在各个缓冲器之间切换。近年来，这样的系统得到了相当程度的关注，被广泛应用于制造系统及计算机系统的调度和控制问题中。

当单位时间内被处理的任务数较大时，Perkins J R等提出离散任务流逼近连续流的研究方法，离散调度问题转化为连续系统切换的相关问题。针对单服务器多品种和多服务器网络问题及多种调度策略，证明了切换服务系统是最终有界的，并证明了它的Lagrange稳定性。Passion K M和Lu S H针对优先权调度策略，Burgess K L针对先到先服务策略和随机选择策略研究了切换服务系统的Lagrange稳定性，并给出了缓冲器容量的上界估计表达式。Chase C证明了在任意的调度策略下，不考虑切换等待时间的具有三个缓冲器的切换服务系统是周期稳定的，这是一种Lyapunov意义下的稳定性结果。杨根科等考虑切换等待时间的n个缓冲器切换服务系统，在优先权调度策略下，证明了任意轨道都将收敛到唯一的周期轨道，并给出了周期轨道表达式和收敛于周期轨道的速度估计。Li Z G通过使用混杂Petri网模型和构造李亚普诺夫函数，研究了包含一台服务器和三台缓冲器的切换服务系统在到达率相等情况下的一致渐进稳定性问题，但都未曾考虑系统的周期性。针对具有一台服务器和任意多台缓冲器的切换服务系统，Savkin A V提出在不要求到达率相等的假设下，按照周期顺序的“排空切换”策略，证明了该切换服务系统存在唯一的全局稳定的极限环，明确给出了这个极限环周期的计算公式。同时，提出在“服务器优先服务等待时间最长的缓冲器的排空切换”策略下，该系统的状态空间能被分成（n-1）！个无界区域，每个区域都是包含一条极限环的不变集。从其中任意区域出发的所有轨迹都收敛于这个区域包含的极限环，即这个极限环是稳定的。

在某种意义上，交叉口的车道可以看作缓冲器，而信号灯看作服务器，所以，交叉口的信号配时可以看做一种切换服务系统的切换规则问题。本书将现有的切换服务系统的理论应用于研究T形交叉口的信号配时问题，并进一步延拓理论，解决十字交叉口的信号配时问题。

切换系统是研究的最多最充分的一类混杂系统。切换系统的控制律设计是系统控制的一个基本任务，也是一项比较困难的工作，许多工具被用来研究这一问题。如公共Lyapunov函数方法、LaSalle不变原理的推广、多重Lyapunov函数方法、自适应控制律、基于观测器的镇定等。

Pettersson S等人针对切换仿射系统，通过求解LMIs问题得到Lyapunov函数的存在性，并进一步证明该系统的指数稳定性及鲁棒稳定性。Branicky M S等使用多Lyapunov函数工具分析切换系统的Lyapunov稳定性，使用迭代函数系统理论分析切换系统的Lagrange稳定性。LiZG等人针对矩阵测度的方法，利用“循环分析”的方法研究了一大类线性不确定切换系统的鲁棒稳定性问题，给出了其渐进稳定性的充分条件。Hespanha J P通过设计逻辑切换控制律实现了一类非完整积分器系统的镇定，保证了闭环系统的渐进稳定性。Pait F M等人应用循环切换策略研究了一类不确定系统的参数自适应控制。Narendra K S提出了多模型切换自适应控制的方法，改善了系统的瞬态性能。Beldiman O采用LMIs方法设计控制律以达到闭环系统镇定的目的。Hu B等人研究了含有两个线性子系统的切换系统的鲁棒镇定问题。在给定的切换规则下，Branicky M S和Johansson A M分别提出了多李雅普诺夫函数方法，研究切换系统的稳定性和控制律综合问题。以上都是关于连续时间切换系统，而Kim D K等研究了离散时间切换系统的鲁棒稳定性和控制综合问题。

这些都没有提及时滞系统的稳定性，而在各类工业系统中，时滞现象是极其普遍的。因此，本书研究了具有多胞型不确定性的时滞离散时间切换系统的稳定和镇定问题。

1.3.2　混杂系统可达性分析及研究现状

可达性问题的研究目的和意义在于混杂动态系统的模型检验，即：检验某个给定的性质（安全性、活性等）对于混杂动态系统是否是真的。可达性问题研究有很多方面，现阶段，主要研究的是混杂轨迹的可达集计算及其对偶问题。

（1）混杂轨迹的可达集计算：给定一个混杂自动机模型H=（Q，X，Inv，f，Init，E，G，R），计算任意一个初始状态（q0，x0）∈Init通过一系列离散转移和连续演化可以到达的所有状态的集合。

（2）可达集计算的对偶问题是：给定混杂状态空间的一个子集F⊆Q×X，计算通过一系列离散转移和连续演化可以达到一个状态（qf，xf）∈F的所有初始状态（q0，x0）∈Init的集合。

混杂系统可达性分析的难点在于连续部分，因此，大量工作针对连续系统展开。在可达性分析方法主要有两类。一类是近似方法，包括模型抽象化方法、区域近似表示和流管演化计算方法、生存能力理论等。另一类是分析方法，包括基于最优化的方法、栅栏凭证方法、多项式不变集表示方法和能控性分析方法等。

模型抽象化方法主要由计算机领域学者提出。所谓混杂系统的抽象化，就是通过对连续状态空间划分，用一个离散事件系统去近似混杂系统而将混杂系统的可达性问题转化为离散事件系统的可达性问题，进而利用离散事件系统已发展的各种有效检验方法进行分析。抽象化方法的关键问题包括：

（1）如何抽象化。

（2）抽象后的系统与原系统的关系，这里的关键问题是需要检验的性质是否保持。

（3）抽象系统的验证问题是否可有限步计算，即可判定性（Decidability）如何。

需要检验的性质可以用时间逻辑表示，而理论计算机科学中的“双向仿真”（Bisimulation）方法可以用来获得一个可达性等价的抽象化商系统。因此，许多学者研究了什么样的混杂系统可以得到基于双向仿真的有限的抽象化商系统。Alur R证明了配时自动机和初始化矩形自动机可以获得一个基于双向仿真的有限自动机抽象。Lafferriere G提出并证明了O最小混杂系统也有一个有限的双向仿真。Broucke M描述了一个一般的双向仿真的构造方法。Pappas G J讨论了线性混杂系统的双向仿真问题。Haghverdia E进一步系统地探讨了双向仿真问题等等。

但双向仿真具有很大的局限性，一方面，即使某些简单类型的矩形自动机也可能没有有限双向仿真；另一方面，对于某些具体的验证问题，可以不需要如此严格的抽象化。因此，为达到验证目的采用更保守的抽象化方法是可行的。例如，Tanner H讨论了线性系统的“单向仿真”（Simulation）关系。Alur R等人提出了基于谓词抽象和反例验证的方法。Clarke E进一步给出了基于谓词抽象过程的细化方法。Girard A拓展单边和双边仿真到近似单边和双边仿真。Chutinan A则提出了一类新的基于区域边界的抽象化方法。Greenstreet M R则在抽象化时不是考虑连续状态空间划分，而是考虑连续对象的拓扑特征。沿着抽象化这一思路的研究工作仍然在不断深入，在此不一一列举。从总体上说，抽象化方法目前一般仅处理一些特殊类型的混杂系统，如配时自动机、矩形自动机、某些线性混杂系统等。

区域近似表示和流管演化计算方法主要由控制领域学者提出。这类方法主要考虑连续演化状态集合的近似表示和演化计算。基本思想是将连续系统从某个初始状态集合出发演化的状态流管按时间采样进行分段，从初始状态集合开始，选择适当的近似集合来表示每个流管段，并在一个采样周期内计算近似集合连续演化的可达集，如此迭代直到计算完所有流管段。这种方法有两个基本的问题：

（1）如何近似表示流管段。

（2）如何根据连续动力学规律对流管段的近似集合进行演化。流管段的近似表示和近似集合演化计算要考虑的因素有：

①储存的代价；

②集合并和交等运算的困难性；

③新的可达集计算的精巧性；

④对实际可达集近似的精度。

目前，根据连续动力学规律演化流管段主要近似方法有三种。

（1）超多面体近似及其各种改进。

Puri V讨论了超立方体近似，Dang T提出了多面体表面提升方法，Bournez O提出了正多面体近似方法，Chutinan A采用一般凸多面体近似，Stursberg O采用定向矩形包洛近似，Girard A提出了Zonotope近似，Greenstreet M R采用投影方法表示非凸多面体，PreuBig J结合连续向量场特征仅仅近似集合边界的演化。在这些近似方法中，一般多面体可以任意逼近凸集，但面和顶点数可能非常大。正多面体容易表示、面的个数随维数线性增长，但精确近似需要大量的小正多面体。Zonotope近似的主要优势在于：易于编码且在线性变换和Minkowski运算下是闭合的。

（2）超椭圆近似。

椭圆近似由Kurzhanskii提出。这一方法的主要问题是椭圆数量随维数平方增长。因此，当要求精确时需要用许多椭圆来近似，椭圆的交和并不是椭圆。

（3）水平集方法。

Mitchell I引入了基于求解Hamilton-Jacobi-Bellman方程的水平集（Level Set）方法。

在连续状态集合近似方法中，问题的关键是高维数、复杂非线性向量场等因素导致计算的复杂性和问题解决的难度。针对这些问题的可达性分析的改进工作仍然继续着。对于连续和混杂系统，近似方法与分析方法的结合应该更加具有优势。

1.3.3　混杂动态系统交通应用现状

目前，混杂动态系统在交通信号控制中的应用已取得了一些初步结果。

混杂动态系统的一种模型是混杂Petri网。Wang H首先建立了交叉口信号控制的配时Petri网模型，针对定时控制和全感应控制情况进行了研究和仿真。DiCesare F进一步将其拓展到交叉口信号网络的情况。Gallego J L采用Petri网模型考虑了交叉口三个安全性约束条件（灯色顺序与配时、冲突信号清理和驾驶员最大等待时间）。Farges J L提出随机Petri网的滤波方法并将其应用于交叉口排队长度估计。Wang J C使用随机配时Petri网对路段和交叉口建模，并进行了比较和性能分析。Cherif T、Tolba C等学者借助Petri网的分析工具研究了交通控制中的活性（liveness）及安全性（safety）。DiFebbraro A探讨了基于混杂Petri网的交通信号控制系统的模块化表示。List G F以一个八相位交叉口解释了Petri网模型的特点和优势。Fanti M P应用着色配时Petri网讨论了交叉口信号控制问题。在我国，王剑波提出了一种交通控制系统的分布式结构及控制策略，借助有色网建模技术对城市智能交通信号控制系统进行了建模分析。Zhang L G应用混杂Petri网建模交叉口，并采用二阶宏观仿真模型建模车辆运动研究了两个相邻交叉口的信号控制问题。叶剑虹等利用增广Petri网设计了一种交叉口实时交通信号控制系统。虽然，Petri网能很好地描述异步、并发等现象，但与连续动力学相结合构成混杂Petri网模型时，系统描述比较复杂，尤其系统优化方面的分析与算法还缺乏可用的结果。

混杂动态系统的另一种典型模型是将有限自动机与连续动态系统结合构成的混杂自动机。这种模型能以一种相对简单的方式同时对交通系统中的模拟量（密度、速度、排队长度等）和离散事件变量（管理决策、自然事件、突发事故、车辆的到达和离开，信号切换等）进行建模。基于这种模型的控制策略与算法能很好地满足上述交通控制系统的未来发展趋势，是一种新的很有前途的交通信号控制方法。混杂自动机理论在自动公路的研究中已取得很好的成果，但在交通信号控制方面的研究还处于起步阶段。JiaL首先提出了交叉口信号控制的混杂自动机模型。ZhaoX H也独立提出了基于混杂自动机的单交叉口信号优化控制，以及两个交叉口之间的协作控制。

1.3.4　CheckMate仿真工具介绍

目前已有众多的仿真工具用于混杂系统的仿真、验证。OmSim混杂系统仿真环境，所用的面向对象语言Mola可用于连续时间和离散事件动态系统的建模。SHIFT是描述混杂自动机动态网络的编程语言，其中的元件模型在系统演化过程中可随时创立、互连与消亡，适用于智能高速公路等复杂的应用场合。Taylor发展Matlab工具箱用于混杂系统的建模与仿真，在Matlab5.1版中首次加入的Stateflow软件包，利用有限状态机仿真离散事件系统，并通过Simulink可以实现和连续系统进行混杂仿真，可作为混杂系统仿真平台。

混杂系统的形式验证工具大致可分为两类：以HyTech、Kronos和UPPAAL为代表的模型检查方法和Step为代表的定理证明。它们的共同目标是：给定系统描述，确定系统是否满足特定的性质。HyTech作为分析混杂系统的形式验证工具，能够计算出线性混杂系统满足时要求的条件，通过检查符号化的模型的准确性来实现。进行逻辑控制程序的形式验证时可直接利用HyTech软件。Kronos和UPPAAL是检验配时自动机的工具，可用来对通信协议进行验证。针对具有复杂连续动态系统的验证问题，Dortmund研制了VERDICT软件包。另外，模型检验工具SMV虽然不能用于具有时间约束的系统，但其基于有序二进制决策图的搜索算法对计时验证有一定借鉴意义。

本书采用Carnegie Mellon大学电气与计算机工程系开发设计的CheckMate3.6混杂系统工具箱在Matlab环境下对交叉口混杂自动机模型进行仿真研究。CheckMate3.6能够用于对阀值事件驱动的混杂系统（threshold-event-driven hybrid system）进行建模。一个阀值事件驱动的混杂系统（TEDHS）由三个子系统构成，即切换连续系统、阀值事件发生器和有限状态自动机，如图1-6所示。

CheckMate3.6仿真系统中，TEDHS模型由三个主要模块组成，如图1-7所示。切换连续系统模块定义在不同的离散状态下系统的连续动态行为，能够定义线性或非线性动态方程；多面体阀值判定模块为不同离散状态之间的切换定义转移条件，该模块在仿真系统中产生事件，驱动各个离散状态之间的切换；有限状态自动机模块定义一个由事件驱动的有限状态转移系统的离散状态及各个离散状态之间的切换序列。

切换连续系统模块中包含所有离散状态下的连续动态方程，该模块的输入u由有限自动机模块的输出q提供，模块的输出x为混杂系统的连续变量。验证过程中，根据有限自动机模块输出的离散状态选择相应的连续动态方程。连续动态方程由用户编写的m函数提供。切换连续系统模块支持三种连续状态，即时钟状态，方程为，c为常数；线性状态，方程为；以及非线性状态，方程为。对于不同的连续动态方程，验证工具自动调用相应的流管道计算程序，三种连续状态方程的流管道计算方法不同。

多面体阈值事件模块代表一个连续状态区域：Cx≤d，其中C，d为常矩阵。模块的输入x为切换连续系统模块的输出，模块的输出为一个布尔逻辑值，该布尔逻辑值判断连续状态变量x是否在此连续状态区域中，若在区域中，则布尔逻辑值为1，否则为0。

有限自动机模块采用Matlab工具箱中给以如下限制的有限状态流（Stateflow）模块：

（1）每个事件输入都为多面体阈值事件输出的布尔逻辑值。

（2）每个数据输入必须是切换连续系统或多面体阈值事件输出的逻辑函数。

（3）只有一个离散值输出函数。