2.4 混成自动机

混成系统是一种既含有离散状态也含有连续状态的动态系统。混成自动机HA（Hybrid Automata）是描述混成系统的一种建模方法和技术，从离散和连续两个方面描述系统的变迁和演化。本节内容可参阅文献[4,13]。

2.4.1 混成系统

混成系统是一个动态系统，反映了连续（实值）状态和离散（有限值）状态之间的交互，以及状态随时间的演化。动态系统可以被外在输入激活，这些外在输入可能是控制信号（如驾驶员发给飞行器的起飞命令、驾驶员给汽车的制动命令、自主巡航命令或自动驾驶命令等），也可能是不可控制的干扰信号（如影响飞行器的风，影响汽车行驶的障碍物、影响汽车制动的路面等）。一些动态系统也可能需要有输出，这些输出可能是可测量的值（如飞行器高度和速度、汽车的速度等），也可能是系统的状态（如飞行器正常、汽车发动机正常等）。带有输入和输出的动态系统称为控制系统。

动态系统可以分成三类。

连续型 。状态在 n 维实数空间R ⁿ ( n ≥1)取值，用 x ∈R ⁿ 表示连续动态系统的状态，是 n 元向量。如：房间温度（1元向量）、汽车速度-加速度（2元向量）、飞机速度-仰角-空间位置（3元向量）等。

离散型 。状态在有一个有限集或可数集 Q ={ q ₁ , q ₂ ，…}中取值，其中 q _i 表示离散系统的状态。如：灯的开关状态∈{开，关}，高铁的运行状态∈{加速，减速，匀速}。

混成型 。由于系统既包含连续状态又包含离散状态，因此混成型动态系统的一部分状态在欧式空间R ⁿ 中取值，另一部分状态在一个有限集中取值。如：智能空调器、汽车自动换档器、高铁运行系统等智能系统。

智能空调系统是将房间温度保持在一个指定值的自动控制系统，这个系统由开关自动控制，无论空调处于开还是关状态，房间温度的变化都服从某个微分方程，如：d x /d t = -a ( x -30)，d x /d t = -bx 。其中 x 是房间温度； t 是时间； a 和 b 是系数，分别反映空调制热能力和房间保温能力。通过上述微分方程，可以求得温度与时间的显式函数关系： x = k _a e ^-at +30, x = k _b e ^-bt ，其中 k _a 和 k _b 是待确定的参数。

2.4.2 混成自动机的基本概念

使用混成自动机来建模混成系统，其节点由连续状态和离散状态组成，代表连续状态的变化，而边代表离散状态的转移。

定义2.5（混成自动机） 一个混成自动机 HA =( Q , X , F , Init , D , E , G , R )由8部分组成。

1. Q ={ q ₁ , q ₂ ,…}是离散状态集。

2. X =R ⁿ 是连续状态集，每个元素都是 n 维连续变量的向量， P ( X )是 X 的幂集，其元素是若干连续变量应满足的条件，这里条件可以是线性方程，也可以是微分方程。

3. F (·,·)： Q × X →R ⁿ 是向量场函数，为离散状态指定一组连续变量变化应服从的方程。

4. Init ⊆ Q × X 是初始状态集，( q , x )∈ Q × X 是 H 的状态。

5. D (·)： Q → P ( X )是域函数，为每个离散状态指定连续变量停留在这个离散状态应满足的条件（一般是线性条件），即定义了离散状态的连续变量域。

6. E ⊆ Q × Q 是边集，反映离散状态的转移。

7. G (·)： E → P ( X )是转移条件，为每一个边指定一组连续变量应满足的条件，可激活离散状态的转移。

8. R (·,·)： E × X → P ( X )是重置函数，为边上的连续变量向量赋值一组函数方程，从而重新赋值这些连续变量。

例2.14 制热空调系统

某制热空调系统能够将房间温度保持在20℃，当室内温度低于19℃时空调启动“开”状态并对房间进行加温，此时室内温度变化服从微分方程：d x/ d t = -a ( x -30)。当室内温度上升到21℃时，空调启动“关”状态，此时室内温度变化服从微分方程：d x/ d t = -bx 。参数 a 反映了空调制热能力，参数 b 反映了房间保温能力。考虑到一些外在不确定因素，如温度检测的动态性，可能导致室内温度不在范围，因此再规定开状态和关状态内部约束条件，如：在关状态时室内温度大于等于18℃，而在开状态时室内温度小于等于22℃。

解：建立这个空调系统的混成自动机模型。

离散状态集 Q ={开，关}

连续状态集 X =R，连续变量 x ∈ X 是一维变量，代表房间的温度，是时间 t 的函数

向量场函数 F (·,·):{开，关}× X →R：

F （开， x ）=（d x/ d t = -a ( x -30)），空调启动，房间温度上升

F （关， x ）=（d x/ d t = -bx ），空调关闭，房间温度自行下降

初始状态集 Init ：{关}×{ x ∈R| x =<15}

域函数 D (·)： Q → P ( X )定义为：

D （开）={ x =<22}，规定在空调的开状态下房间温度不超过22℃

D （关）={ x >=18}，规定在空调的关状态下房间温度不低于18℃

边集 E ⊆ Q × Q ：

开→关：开状态到关状态有条边

关→开：关状态到开状态也有一条边

转移条件 G (·)： E → P ( X )：

G （开→关）={ x >=21}，从开状态转移到关状态的条件是房间温度大于等于21℃

G （关→开）={ x =<19}，从关状态转移到开状态的条件是房间温度小于等于19℃

重置函数 R (·,·)： E × X → P ( X )：

为每个边都指定了一个空集，即没有重置动作，在状态转移过程中房间温度变量 x 不进行重置，保留转移前的值

2.4.3 混成自动机图形化

同有限状态机一样，使用有向图表示混成自动机。

给定一个混成自动机 H =( Q , X , F , Init , D , E , G , R )，把 Q 中元素（状态）作为定向图的节点，把 E 作为有向图的边。

1.对每一个节点 q ∈ Q ，都关联一个连续状态集{ x ∈ X |( q , x )∈ Init }，一个向量场函数 F ( q ,·)：R ⁿ →R ⁿ （连续状态 x 应该服从的微分方程组）和一个域函数 D ( q )⊆R ⁿ （连续状态停留在这个节点的条件）。

2.对每一个起始于状态 q ∈ Q 终止于 q＇ ∈ Q 的有向边 q → q＇ ，都关联一个转移条件 G ( q → q＇ )⊆R ⁿ （规定了从离散状态 q 转移到离散状态 q＇ 的转移条件集），以及一个重置函数 R ( q → q＇ , x )：R ⁿ → P （R ⁿ ），重置语句用新值对连续状态变量进行重置。

例如：将例2.14图形化，结果见图2-22。

例2.14中，向量场函数 F (·,·)规定了空调温度连续变化应该服从微分方程。空调在开状态时，温度 x 按照 x = k _a e ^-at +30函数往30℃上升，而在关闭状态时，温度 x 按照 x = k _b e ^-bt 函数往0℃下降。

现在来分析一下，参数 k 、 a 与 b 对系统的影响。现在假设室温为15℃，则空调打开，将 x =15代入公式 x = k _a e ^-at +30求得 k _a =-15（因为时间 t =0）。假定经过时间 t 后房间温度上升到20℃，则参数 a =-1/ t ×ln（2/3），明显参数 a 的取值与时间有关。若在10个单位时间后房间温度上升到了20℃则得到 a =0.04。若在5个单位时间后房间温度上升到了20℃，则 a =0.08。现在考虑参数 b 。若开始时房间温度为21℃则结合时刻 t =0，可得参数 k _b =21。假设经过时间 t 房间温度下降到19℃，则有19=21e ^-bt ，求得 t =0.1/ b 。若要求房间温度从21℃下降到19℃花费5个单位时间，则得到参数 b =0.02。我们可以得到一组参数值( k _b , b )=（21,0.02）。

因此，当 a 和 b 取定值后，如 a =0.08和 b =0.02，空调器的效能以及房间保温能力就确定了，其图形化为图2-23。

2.4.4 混成系统的建模例子

例2.15 水缸系统

由两个水缸组成的水缸自动控制系统见图2-24，两个水缸中的水都以常速流出水缸，以常速通过一个软管流进水缸。在任何时刻水只能流进其中一个水缸，假定软管在两个水缸间瞬间转移，并保持两个水缸中的水在一定容量之上。

分析 ：设 x ₁ 和 x ₂ 分别表示第1水缸和第2水缸中水的容量， v ₁ 和 v ₂ 分别表示第1水缸和第2水缸2的出水（常）速度。设 w 表示水流进水缸系统的（常）速度，因此 w-v ₁ 和 w-v ₂ 分别是第1水缸和第2水缸的净（实际）进水速度，都是常数。往第2水缸注水时，要保持第1水缸水容量大于等于 r ₁ 和第2水缸水容量大于等于 r ₂ 。同样，往第1水缸注水时，要保持第2水缸水容量大于等于 r ₂ 和第1水缸水容量大于等于 r ₁ 。为了实现这个需求，需要一个控制系统在第1水缸的容量 x ₁ =< r ₁ 时自动调整软管使之往第1水缸注水，以及在第2水缸的容量 x ₂ =< r ₂ 时调整软管使之往第2水缸注水。

解：构建混成自动机模型。

离散状态集 Q ={ q ₁ , q ₂ }，其中 q ₁ 是第1水缸， q ₂ 是第2水缸

连续状态集 X =R ² ，连续变量 x 是二维向量( x ₁ , x ₂ )，其中 x ₁ 是第1水缸的水容量， x ₂ 是第2水缸的水容量，都是时间 t 的函数

向量场函数 F (·,·)：{ q ₁ , q ₂ }× X →R ² ：

F ( q ₁ x )=(d x ₁ /d t = w-v ₁ ，d x ₂ /d t = -v ₂ )，其中 w-v ₁ 是第1水缸的净进水速度， -v ₂ 是第2水缸的出水速度

F ( q ₂ ， x )=(d x ₁ / d t = -v ₁ ，d x ₂ /d t = w-v ₂ )，其中 -v ₁ 是第1水缸的出水速度， w-v ₂ 是第2水缸的净进水速度

初始状态集 Init ：{ q ₁ , q ₂ }×{ x ∈R ² | x ₁ >= r ₁ ∧ x ₂ >= r ₂ }：

初始时第1水缸和第2水缸容量分别大于等于 r ₁ 和 r ₂

域函数 D (·)： Q → P ( X )定义为：

D ( q ₁ )={ x ∈R ² | x ₂ >= r ₂ }，当第1水缸进水时保持第2水缸的容量大于等于 r ₂

D ( q ₂ )={ x ∈R ² | x ₁ >= r ₁ }，当第2水缸进水时保持第1水缸的容量大于等于 r ₁

边集 E ⊆ Q × Q ：{ q ₁ → q ₂ , q ₂ → q ₁ }，转移是在两个水缸间进行

转移条件 G (·)： E → P ( X )：

G ( q ₁ → q ₂ )={ x ∈R ² | x ₂ =< r ₂ }，在第1水缸进水时，只要第2水缸的容量小于等于 r ₂ ，自动机状态就转化到第2状态，即往第2水缸注水

G ( q ₂ → q ₁ )={ x ∈R ² | x ₁ =< r ₁ }，在第2水缸进水时，只要第1水缸的容量小于等于 r ₁ ，自动机状态就转化到第1状态，即往第1水缸注水

重置函数 R (·,·): E × X → P ( X )： R ( q ₁ → q ₂ ， x )= R ( q ₂ → q ₁ ， x )={ x := x }，状态改变时连续状态不改变，即保持水缸的当前容量

所得模型见图2-25。

2.4.5 混成自动机演化

混成自动机反映了动态系统随着时间变化的演化，下面考虑混成自动机状态（ q ( t )， x ( t )）的可能演化。

从初始状态( q ₀ , x ₀ )∈ Init 出发，连续状态 x 服从微分方程d x /d t = f _{q 0} （ q ₀ ， x ( t )）以及初始连续状态 x （0）= x ₀ ，离散状态 q ( t )保持初始离散状态 q ₀ 。

连续状态的演化重复进行，只要 x ( t )保持在域 D ( q )里。

-假设混成自动机进入离散状态 q ，时间为 t 时刻，则连续状态 x 的值为 x ( t )，且其演化服从微分方程d x /d t = f _q （ q ( t )， x ( t )），离散状态 q ( t )保持常状态 q ，即 q ( t )= q ；

-如果在时刻 t 的后续某个时间点 t′ ，连续状态 x 满足某个边( q , q′ )∈ E 的转移条件 G ( q → q′ )，则离散状态从 q 转移到离散状态 q′ ；连续状态 x ( t )从重置函数 R （ q → q′ ， x ( t )）∈R ⁿ 中获得新值，且其演化在离散状态 q′ 下服从微分方程d x /d t = f _q′ （ q′ ， x ( t )）；

-连续状态 x ( t )随着时间进行演化，触发离散状态的转移，在离散状态转移后，连续状态的演化重新开始，整个过程重复进行。

对所有离散状态 q ∈ Q ，域函数 D ( q )中的函数都是Lipschitz型连续函数。

最后，假定对于所有的边 e ∈ E ，边的转移条件 G ( e )≠∅（空集）；对于所有的连续状态 x ∈ G ( e )，连续状态 x 的重置函数 R ( e , x )≠∅。

注 ：在数学中，Lipschitz型连续函数是指满足Lipschitz连续条件的实值函数。Lipschitz连续条件以德国数学家鲁道夫·利普希茨命名，是一个比通常连续更强的条件。对于在实数集R的子集 D 上的函数 f ： D →R，若存在非负常数 k ，使得| f ( a ) -f ( b )|≤ k | a-b |，则称 f 满足Lipschitz连续条件，且称最小常数 k 为Lipschitz常数。绝对值函数 f ( x )=| x |是Lipschitz型连续函数，但不是可微函数。

为了描述混成自动机 H =( Q , X , F , Init , D , E , G , R )的具体演化，把时间集分化成连续区间，使得在连续区间能上能很好地体现连续状态的演化，同时又能区分离散状态的转移点。这样的时间区间集称为混成时间集。

定义2.6（混成时间集） 一个混成时间集是一个区间 T ={ I ₀ , I ₁ , I ₂ ,…, I _N }= ，它是有限集或者无穷集( N =∞)，使得对于所有的 i 都有 并且 = t _{i +1} ，若 N ≤∞则或者 或者 ）。

时间点 是离散状态转移的前一时刻， t _{i +1} 是离散状态转移后的那一时刻。为了时间点具有连续性，规定时间区间 I _i 的右端点 和时间区间 I _{i +1} 的左端点 t _{i +1} 重合。因此，这个时间点恰好是混成自动机离散状态转移发生时间点。这样我们假定离散状态的转移是瞬时发生的。注意可能会出现 ，即区间 I _i 是单点集{ t _i }的情况，示意图见图2-26。

例2.16 制热空调系统

以图2-23为例，描述空调系统混成自动机的演化过程。取空调加热方程为 x =-15e ^{-0.08 t} +30，房间降温方程为 x =21e ^{-0.02 t} ，房间初始温度为15℃。

解 ：开始时间区间 I ₀ ：空调处于开状态， t =0， x (0)=15，房间初始温度为15℃，经过6.4个单位时间后，房间温度上升到21℃，即 x (6.4)=21，空调进入关状态， I ₀ =[0,6.4]。

第二个时间区间 I ₁ ：空调处于关状态，房间温度从21℃下降到19℃需要5个单位时间，即 x (11.4)=19，空调进入开状态，得 I ₁ =[6.4,11.4]。

第三个时间区间 I ₂ ：空调处于开状态，此时加热方程的参数 k =11，空调服从温度方程 x =-11e ^{-0.08 t} +30，从19℃加热到21℃，需要2.5个单位时间，得 I ₂ =[11.4,13.9]，空调进入关状态。

第四个时间区间 I ₃ ：空调处于关状态，房间温度从21℃下降到19℃，需要5个单位时间，即 I ₃ =[13.9,18.9]，空调进入开状态。

第五个时间区间 I ₄ ：空调处于开状态，空调温度变化服从温度方程 x =-11e ^{-0.08 t} +30，从19℃加热到21℃，需要2.5个单位时间，即 I ₄ =[18.9,21.4]，空调进入关状态。

这样一直重复下去，直到空调关机为止。

根据上述演化，我们得到 I ₀ =[0,6.4]， I ₁ =[6.4,11.4]， I ₂ =[11.4,13.9]， I ₃ =[13.9,18.9]， I ₄ =[18.9,21.4]。

空调系统混成自动机的演化过程示意图见图2-27。

例2.17 水缸系统

设例2.15中第1水缸和第2水缸中水的容量都是1，两个水缸的水流（常）速度为1/2，即 v ₁ = v ₂ =1/2，水流进水缸的（常）速度为3/4，即 w =3/4，因此，第1水缸和第2水缸的进水速度都是常速度3/4-1/2=1/4，再设 r ₁ = r ₂ =0。

解 ：初始状态是 q = q ₁ , x ₁ =0， x ₂ =1。即第1水缸无水，第2水缸满缸，因此初始状态往第1水缸注水。第2水缸是满缸代表 x ₂ =1，且出水速度 v ₂ =1/2，所以水缸流干需要2个单位时间，第2水缸流干后系统自动往第2水缸注水，此时第1水缸的水容量 x ₁ =1/4×2=1/2，即半缸水，时间区间 I ₀ =[0,2]。

系统状态为 q = q ₂ , x ₁ =1/2， x ₂ =0。系统往第2水缸注水，第1水缸出水速度 v ₁ =1/2，而 x ₁ =1/2，因此经过1个单位时间后，第1水缸流干，系统转向往第1水缸注水，此时第2水缸的水容量 x ₂ =1×1/4=1/4，时间区间 I ₁ =[2,3]。

系统状态为 q = q ₁ , x ₁ =0， x ₂ =1/4，系统往第1水缸注水。由于此时第2水缸只有1/4水容量，出水速度 v ₂ =1/2，因此经过0.5个单位时间后，第2水缸流干，系统转向往第2水缸注水，此时第1水缸的水容量 x ₁ =1/4×0.5=1/8，时间区间 I ₂ =[3,3.5]。

系统状态为 q = q ₂ , x ₁ =1/8， x ₂ =0，系统往第2水缸注水。由于第1水缸只有1/8水容量，出水速度 v ₁ =1/2，因此经过0.25个单位时间，第1水缸流干，系统转向往第1水缸注水，此时第2水缸的水容量 x ₂ =1/4×0.25=1/16，时间区间 I ₄ =[3.5,3.75]。

系统状态为 q = q ₁ , x ₁ =0， x ₂ =1/16，系统往第1水缸注水。第2水缸水容量 x ₂ =1/16，出水速度 v ₂ =1/2，因此经过0.125个单位时间，第2水缸流干，系统转向往第2水缸注水，此时第1水缸的水容量 x ₁ =1/4×0.125=1/32，时间区间 I ₄ =[3.75,3.825]。

系统状态为 q = q ₂ , x ₁ =1/32， x ₂ =0，系统往第2水缸注水。第1水缸经过1/16个单位时间后无水，系统转向往第1水缸注水，此时第2水缸的水容量 x ₂ =1/4×1/16=1/64，时间区间 I ₅ =[3.825,3.888]。

得到混成时间集 I ={[0,2]，[2,3]，[3,3.5]，[3.5,3.75]，[3.75,3.825]，[3.825,3.888]}，两个水缸水容量演化过程见图2-28。