王晓江，陈俊硕

(1.中国飞行试验研究院，西安 710089；2.长安大学，西安 710064)

混杂系统优化建模与分析

王晓江1，陈俊硕2

(1.中国飞行试验研究院，西安 710089；2.长安大学，西安 710064)

针对组合混杂系统中由于不同工作模式数量随系统组成部分数以指数形式增长而导致系统更加复杂的问题，提出了一个基于超平面规划的模式枚举法.其根据组合离散混杂自动机之间的依赖关系和连接顺序依次进行，只枚举出组合系统的可行模式，去掉了由于离散混杂自动机之间交互和外部约束导致的不可行模式，降低了需要考虑的模式数量.基于混杂系统不同形式模型之间的等效性，可以在枚举同时将组合离散混杂自动机模型转换为能够进行离线最优控制的分段仿射模型.建立了二阶积分器的组合混杂模型，仿真结果表明了算法的可行性和有效性.

混杂系统；枚举算法；优化建模

混杂系统是一组相互交互数字有限状态机的集合，并且每个状态机都有一个模拟部分与之对应.目前对于混杂系统可以建立三种类型的模型，分别为离散自动机(Discrete Hybrid Automata, DHA)模型，混合逻辑动态(Mixed Logical Dynamical, MLD)模型和分段仿射(Piecewise Affine, PWA)模型[1].其中三种模型各有优点，DHA模型能够很容易用HYSDEL(Hybrid Systems Description Language, HYSDEL)语言描述，建模最简单也最方便[2-3].MLD模型比较适合计算量较小的混杂系统在线最优控制，一般都是由描述DHA模型的HYSDEL语言转换而来，也是目前应用最多的最优控制模型[4-5].而当推导离线最优控制率作为状态反馈控制率和设计混杂系统滚动时域观测器时[6]，则首先需要建立PWA模型，才能对系统进行分析计算，PWA模型适应于计算量较大，较复杂的混杂系统.

混杂系统也可是由几个混杂系统构成的组合混杂系统，其中不同工作模式的数量是以系统组成部分的指数形式增长，并且由于很多算法的时间和空间的复杂程度都是随着运行模式的数量增加而变得更加复杂，相应逻辑状态规模的暴增导致计算非常困难.在一些情况下，一个组合系统可以分解为一个可以在分层混杂系统[7]中被用到的分层结构，并且可以运用假设可靠的方法，将一个大问题化分成为几个小问题.但在更多情况下由于各个部分之间的交叉耦合太紧密，建立分层模型是根本不可能的.由于交叉耦合实质为一些有效约束，即使能够建立分层模型，也经常呈现出很多不可行的模式.所以通过显式计算和只考虑可行模式能够有效降低系统的复杂程度，本文提出了一个有效的枚举组合混杂系统可行模式的方法.

由于DHA中的阈值是由超平面定义的，所以枚举单个离散自动机的可行模式是很容易通过算法来计算超平面规划的单元来求解.由于这是一个计算机几何学中的典型的问题，可以用最优化和高效的算法.对于组合DHA系统，本文提出的算法可以根据组合DHA中的交互和依赖关系来枚举出一个组合混杂系统的可行模式.这个算法有两个特点，第一，为了枚举单个DHA的可行模式，用到了超平面规划中单元的概念和逆搜索方法，使得复杂程度与可能模式数量是比例关系而非指数关系.第二，当多个DHA组合成一个组合DHA时，模式枚举可以根据DHA的排列顺序的逐步进行计算.本文方法不同于蛮力法，不用将组合系统中每一个可能的模式都去讨论，因为组合DHA之间的交互及外部的约束的作用使得其中大部分模式是不可行的.

1 基于超平面规划的多面体分区

假设A为一组d维欧式空间内n个不同的超平面{Hi}i=1,…,n，其中每个超平面都是由一个线性等式Hi={x∈Rd|aiTx=bi}确定.如果A中没有互相平行的超平面并且空间中任意一点最多属于d个超平面，则称A中的超平面是一般位置超平面.

图1 二维空间内的4个超平面分布

图1中的超平面1、2、3、4为一般位置超平面，定义一个符号向量S表示为

Pm= {x∈Rd|S(x)=m},该集合为超平面规划的一个单元，由于其为线性不等式定义的超平面，也可称之为一个多面体，其中m表示A中的第m个多面体(也可称之为单元).定义M(R)为空间中所有点所属的多面体或单元的集合，如图1所示M(R)包含10个多面体.定义“*”为单元的并集，如图1所示，m1=----和m2=+---，则m=*---就是等同于{m1,m2}表示为Pm1∪Pm2.当超平面不为一般位置超平面时，即R≠Rd需要定义其相应的多面体分区如下：

多面体的集合{Pm}满足

(i)∪m∈M(R)Pm=R(ii)Pi∩Pj=Ø,∀i,j∈M(R),i≠j

则称该多面体集合{Pm}为空间R的一个多面体分区.

2 离散线性混杂模型

2.1 离散混杂自动机

如图2所示，离散混杂自动机主要由描述混杂系统离散部分的离散有限状态机和描述连续部分的切换仿射系统组成.它们由事件发生器和模式选择器相连，事件发生器提取连续部分的输入ur(k)和状态xr(k)得到相应二进制开关信号δe(k)，开关量信号δe(k)和外部二进制输入的信号ub(k)共同触发有限状态机的状态xb(k).模式选择器结合所有的二进制变量信号(状态xb(k)，输入ub(k)和事件δe(k))来选择模式i(k)及相应的切换仿射系统连续动态.其中下标b表示二进制变量，r表示连续变量，下面详细定义4个部分.

图2 离散混杂自动机结构图

切换仿射系统(Switched Affine System, SAS)：是仿射系统的集合，由模式i(k)选择相应的动态

xr(k+1)=Ai(k)xr(k)+Bi(k)ur(k)+fi(k),

yr(k)=Ci(k)xr(k)+Di(k)ur(k)+gi(k).

(1)

其中:k∈N为离散化的时间常数，xr∈Xr是实际的状态，ur∈Ur为实际的外部输入，yr∈Yr是实际输出，Ai,Bi,fi,Ci,Di,gi为一系列相应维数的矩阵，模式i∈I表示一个选择仿射状态更新和输出函数的控制信号.

事件发生器(Event Generator, EG)：为依据仿射约束或阈值产生二进制的事件信号δe

δe(k)=fH(xr(k),ur(k)).

(2)

有限状态机(Finite State Machine, FSM)：是一个离散的动态过程，通过一个二进制的状态更新方程进行迭代更新

xb(k+1)=fB(xb(k),ub(k),δe(k)),

xb(k)=gB(xb(k),ub(k),δe(k)).

(3)

其中：xb,ub分别为二进制的状态和外部输入，yb为二进制的外部输出，δe为事件发生器输出的事件，fB，gB为确定的二元函数，例如

xb(k+1)=┐δe(k)∨(xb(k)∧ub(k)).

(4)

模式选择器(Mode Selector, MS): 其是通过方程fM结合二进制状态xb，二进制输入ub和事件δe，选择切换仿射系统的模式i(k)

i(k)=fM(xb(k),ub(k),δe(k)).

(5)

为当前模式，例如

(6)

其共有3个模式分别为[1;0]、[0;0]、[1;1]，只有当i(k-1) ≠i(k)时，模式才进行切换.有限状态机的一个确定的状态xb对应一个模式，但是事件δe对应的模式不只一个.

定理1 一个离散状态自动机如果在一个给定的初始状态x(0)∈X下，对于任何一个输入u(k)∈U其状态轨迹x(k)∈X和输出轨迹y(k)∈y都是唯一确定的，其中k∈N，则称该离散状态自动机在X，U，y上为适定的.

2.2 分段放射系统

分段仿射系统通过把状态空间分割成几个多面体，每个多面体对应一个仿射状态更新方程和一个输出方程

x(k+1)=Aj(k)x(k)+Bj(k)u(k)+fj(k),

y(k)=Cj(k)x(k)+Dj(k)u(k)+gj(k),

(7)

(7)

其中:x(k)，u(k)，y(k)分别表示在k时刻实际状态，输入和输出.Aj(k),Bj(k),Cj(k),Dj(k),fj(k),gj(k)分别为j(k)∈J时一定维数的常数矩阵和向量.本文用j(k)表示系统的一个模式，#J表示相应模式的代号，Pj(k)代表输入状态(X×U)空间中多面体集{Pj}j∈J.

定理2 假设∑PWA为如式(7)中所示的PWA模型，{Pj}是一个基于输入状态空间X×U的一个多面体分区，则∑PWA是适定的.

上述定理，相反的条件一般不成立，因为PWA系统可以是定义在重叠的多面体集上的.

3 枚举算法

根据上述两种模型的定义，本文给出了枚举出单个DHA的可行模式并将其转换为PWA模型的算法1，对于单一的DHA来说，在给定的二进制状态xb和输入ub，找到可行模式J∈I，多面体集{Pj}和相应的PWA动态{Sj}，这里Sj={Aj，Bj，fj，Cj，Dj，gj}，I为模式选择器的形象化.

算法1：

1)首先初始化j=0,J=Ø;

2)然后通过对集合M(R)中的每个多面体进行迭代，得到每个多面体Pj及其对应的事件发生器的信号δe;

3)进而由每个δe得到相应的模式选择器的模式值i(k);

4)最后由

上述算法枚举出给定输入ub和状态xb，单个DHA在该输入状态下对应的可行模式.如果二进制输入和状态的组合没有可行模式或者相应的状态空间为空集，该算法返回的多面体集合和动态集合都为空集.重复调用该算法就得到了在整个状态输入空间X×U上的PWA模型的集合，每个PWA模型对应一个可行的二进制输入和状态组合.如果对于给定的状态和输入，需要求得其对应的状态更新和输出，则该算法通过二分法查找选择相应的PWA模型是很有优势的，并且模型可以很容易的转换为一个定义在X×U上的PWA模型.

由上述定理1、2及多面体的定义可得，如果DHA∑是适定的，则所得的PWA模型也是适定的并且多面体集合{Pj}组成了一个X×U上的多面体分区.

但是在实际应用中，很多模型都是组合自动机，对于一个组合的DHA，包括s个DHA，每个定义为∑i,i∈{1,2,…,s}，其对应状态、输入和输出分别为xi∈Xi，ui∈Ui和yi∈Yi.Ii为每个DHA的可行模式集合，整个组合系统的外部输入为u，外部输出为y.则组合系统的实际和二进制状态空间集合为Xr=Xr1×Xr2…Xrs和Xb=Xb1×Xb2…Xbs，其中组合向量xr=[(xr1)T, (xr2)T…, (xrs)T]T，xb=[(xb1)T, (xb2)T…, (xbs)T]T，为按顺序排列的各个子系统的实数和二进制状态.这样可得组合系统的组合状态向量为x=[xr,xb]T.

各个子系统之间的联系可以用DHA之间的输出和输入的等式约束来表示.假设第i个DHA的输入为其他的DHA的输出和外部输入的线性组合如下所示

(8)

其中：Lmi和Li分别为相应维数的矩阵，其中Lmi为第m个DHA与第i个之间关系矩阵，其行数为第i个DHA的输入个数(包括二进制输入和实际连续输入)，列数为第m个DHA的输入的个数(同样也包括二进制输入和实际连续输入)，并且i，m∈{1,2,…,s}.由于组合是线性组合，并且表示的只是两个DHA之间的关系，单个DHA只能连接一个DHA的输出或者一个外部输入，这样矩阵[L1iL2i…LsiLi]的每行的和为1.

根据有向图的定义：一个有向图G是一个有序的二元组(V(G),A(G))其中集合V(G)是非空的顶点集，集合A(G)是一个V×V的子集，为带有方向的边的集合，称为弧集，A(G)中的元素称为有向边.

由上述定义可以直接运用到组合DHAs中通过定义DHA为相应的顶点，输出和输入的连接定义为边.这里的边可以表述为两个DHA之间的几种连接，其中组合系统连接方式的拓扑图可以用邻接矩阵来表示，并且该矩阵可以很简单的由连接方式得到.

定义：G为一个有s个顶点的图，每条边只对应一对顶点(没有平行边)，则图G邻接矩阵A=[aij]是一个s×s的0,1矩阵，如果有边直接从顶点i到顶点j则aij=1，否则aij=0.A中元素的排列顺序为{1,2,…,s}.

图3为由5个按顺序排列过的两输入两输出的DHA组合系统，其中∑1和∑4有外部输入，∑4和∑5有外部输出.

图3 组合DHA系统框图

其中∑3输入的邻接矩阵如下

与单个DHA类似，对于定义在X×U空间上的组合系统，通过对给定的二进制状态xb和外部输入ub来确定其可行模式集J⊆I1×I2×…×Is，多面体集合{Pj}j∈J和相应的PWA动态{Sj}j∈J.

首先，将邻接矩阵A通过矩阵变换转变为上三角形矩阵，这样就给组合DHA中每单个DHA编好了顺序，其中后面的DHA∑i的输入只取决于外部输入和前面∑j的输出(i>j).第一个DHA∑1，其输入向量仅是外部输入向量的子集(输入与其他的DHA无关).这里实际的状态和输入都是已知的，则可以用算法1来确定其模式J1，多面体集合(多面体分区){Pj}和相应的PWA动态{Sj}，其中j∈J1.这里的多面体是对Xr×Ur状态输入空间的分区.

由于每个模式j∈Jm和其对应的PWA动态Sj一起定义了其连接的后面的组合DHA的输入，所以首先我们需要将后面的DHA的输入通过用关于初始状态x和外部输入u的函数替换.如果邻接矩阵中ami=1，表示∑m的输出与∑i输入的相连i∈{m+1,…,s}，即ym=ui，则需把∑i的输入ui替换为Lmiym,j+Liu，其中ym,j=Cjx+Dju+gj.这里的Cj,Dj,gj是DHA∑m的PWA动态Sj中的元素，x和u为已知的状态和外部输入.其中j表示输入的方程只对应模式j∈Jm.替换以后就能保证后面的DHA∑m+1仅取决于组合状态和外部输入.

此后，对于一个给定的模式j∈Jm，随着m每增加1，算法2被再次调用，用后面的DHA∑m+i的超平面来将该模式下对应的多面体Pj分成由几个多面体组成的多面体集.所有剩下的模式j∈Jm再依次进行，当m达到最大值s时，当前DHA∑s对应的多面体集合加到前面的多面体集以后就构成了完整的定义在了整个状态输入空间组合DHA多面体集{Pj}j∈J和相应的PWA动态{Sj}j∈J.

概括上述方法，对于给定的二进制状态向量和外部输入向量，其中A已为上三角矩阵.

算法2：1)对于组合DHA系统，先对一个DHA∑m运用算法1，得到一个其最初的多面体集合P和PWA动态集S;

2)然后通过对其每个模式j下与后面DHA∑i,i∈{m+1,…,s}的连接方式，当有连接时用函数将后面DHA∑i的输入替换为DHA∑m的输出，重新运用算法1，对多面体进行进一步划分，得到新的多面体结合集Pnew和PWA动态集Snew，每次都将这些新的集合纳入到总的集合中，当每个模式都算完后就得到了该DHA∑m的多面体集{Pj}j∈Jm和PWA动态集{Sj}j∈Jm;

3)直到对最后一个DHA∑s运用过算法2以后，得到DHA∑s最终的多面体集{Pj}j∈Js和PWA动态集{Sj}j∈Js，将所有的单个DHA的多面体集和PWA动态集合并，得到最终的多面体集{Pj}j∈J和PWA动态集{Sj}j∈J;

对于图3中前两个连接系统如图4

图4 两个DHA组成的组合系统

DHA∑1和DHA∑2分别为：

其中

状态x1∈X=[0,8]，外部输入u1∈U=[0,6]，外部输出为y2，由图4可见，u2=y1，由于已经按照连接顺序排列过，邻接矩阵已经为上三角矩阵.先通过算法1来获得DHA∑1的超平面分布，其包含2个超平面，{[x1, u1]T∈X×U | x1=3}和{[x1, u1]T∈X×U | x1=6}.然后通过枚举超平面中的单元法，将整个状态输入X×U空间分成了3个多面体分区{Pj}, j∈J1={1, 2, 3}，如图5(A)所示其中还有每个多面体所对应的超平面规划的标示符号，同时相应的PWA动态输出函数为Si, i∈{1,2,3}如图5(C)所示.

4 仿真结果

为了验证算法的有效性，对于式(9)所示二阶积分器，对其进行优化建模分析，首先将其视为两个一阶积分器的串联，这样其就是两个DHA组成的组合DHA

(9)

通过取采样时间T=1s进行线性化，将其转化为离散模型得到离散的状态空间表示方式为

(10)

图5 组合系统的多面体分区和PWA动态输出函数

并且在状态约束x∈[-2, 2]，输入约束u∈[-2, 2]时，可得到其状态空间的多面体分区如下，其中黑色线段表示闭环预测控制在各个多面体区间的运行轨迹.如图6所示在给定初始状态和输入时，通过组合PWA模型预测下一步输出y从而得到最优的输入u使y能够快速达到期望值1，其中输入状态空间由在初始模式5最终到达模式1.

图6 对上述混杂模型进行预测控制，得到相应的输入和输出曲线及工作模式轨迹

5 结 语

本文对引入图论的概念对组合混杂系统的DHA进行PWA模型转换给出了相应的算法，其不仅能枚举出所有的可行模式并且随之能判断组合系统是否适定，由于其对已经处理过的超平面有保存功能，大大减少了离散计算的时间.最后通过对串联积分器的建模和控制，仿真结果表明所设计算法能够有效的将其转化为PWA模型并且枚举出其可行的模式，对给定参考值的输入控制输入能使输出很好的达到参考值.

[1] HEEMELS W P M H, SCHUTTER B D, BEMPORAD A. On the equivalence of classes of hybrid dynamical models[C]// Orlando: Conference on Decision and Control, 2001. 364-369.

[2] 张 悦, 王东风, 韩 璞, 等. 一类混杂系统的推广自动机模型及其仿真[J]. 系统仿真学报, 2007, 19(15): 3546-3549.

[3] 李继方, 汤天浩, 姚 刚. 共直流母线交流传动节能系统的混杂系统建模与分析[J]. 电工技术学报, 2011, 26(7): 181-187.

[4] 李 凌, 袁德成, 井元伟. 模拟移动床过程的混杂系统建模方法[J]. 控制与决策, 2013, 28(2): 299-302.

[5] 李 宁, 李颖晖, 朱喜华. 新型容错逆变器的混杂系统建模与故障诊断[J]. 电机与控制学报, 2012, 16(9): 53-58.

[6] 孙云平, 刘 赟, 李俊民. 一类二阶时变非线性系统的混合自适应重复学习控制[J]. 西安电子科技大学学报, 2006, 33(3): 495-499.

[7] 仝庆贻, 颜钢锋. 混杂系统及其在电力系统中的应用[J]. 电力系统及其自动化学报, 2003, 15(2): 14-18.

Study on optimization modeling and analysis of hybrid system

WANG Xiao-jiang1, CHEN Jun-shuo2

(1.Chinese Flight Test Institute, Xi’an 710089, China; 2. Chang’an University, Xi’an 710064, China)

Compositional hybrid systems are very complex, as the number of different operational modes depends exponentially on the number of component systems. Enumerative algorithm was proposed, which was based on hyperplane arrangements. The sequential enumeration greatly reduced the number of modes considered by pruning unnecessary modes from the resulting system. Based on the equivalence of discrete hybrid automatas and piecewise affine systems, an algorithm was presented, which enumerated the modes of a composition of discrete hybrid automatas and transforms it into an equivalent piecewise affine representation. Second-order integrator was presented illustrating the algorithm and showing its feasibility and effectiveness.

hybrid system; enumerative algorithm; optimization modeling

2016-08-15.

王晓江(1985-)，男，硕士，工程师，研究方向：飞机性能试飞.

N945.12

A

1672-0946(2017)02-0202-06