基于混合人工势场与蚁群算法的多飞行器冲突解脱方法*

管祥民 吕人力

(中国民航管理干部学院民航通用航空运行重点实验室1) 北京 100102)(浙江建德通用航空研究院2) 杭州 310025)

0 引 言

人工势场法在过去的20年间被广泛的运用于运动机器人导航，实时规避障碍物，其在线的避障有很强的鲁棒性，能够处理比较复杂的环境.然而，其运用在飞行器冲突探测和解脱方面并没有像机器人领域那么广泛，除了机器人领域比较活跃以外，另外一个可能的原因是飞行器运动模型的限制.Tomlin等[1]将该方法沿用到冲突解脱领域，基本思路是建立基于势力和涡流场(potential and vortex field methods)的运动规划来产生冲突解脱的机动策略.力场法用相对比较简单的力学方程，得到连续的冲突解脱路径，但是其隐含的一个假设是飞行器能够随着不断变化的力场进行连续的机动，或者飞行器的速度能够在很大的范围内变化，这和实际都是不符的.在转弯角度有限制的情况下，算法产生极端“不实际”的解.

在基于进化算法的冲突解脱方面，Durand等[2]利用遗产算法建立了一个简单的神经网络，在解决两机间的短期冲突能得到满意的结果，可靠性和计算效率都比较高.解决冲突解脱的神经网络可以通过遗传算法进行训练，不必知道初始最优解就可以得到适合的解脱路径，将遗传算法所得到的每一代结果代入神经网络中，使得神经网络的适应性得到提高.但是神经网络法对多于两架飞行器的冲突拓展十分困难.三机冲突比两机冲突的学习适应性差，而且在三机以上冲突的情景中，神经网络的规模呈指数级增加学习非常困难.文献[3]中基于遗传算法的冲突探测和解脱方法已经用于NASA Langley 研究中心的试验项目Airborne User Traffic Intent Information(AUTRII)，应用于飞行的爬升、转弯、下降阶段未来6～25 min内冲突预测和解脱.不仅可以用于飞行器之间冲突解脱，也可以用于危险区域(如SUA和雷雨云)的规避.由于在设计适应度函数的时候灵活性比较大，可以满足操作人员不同情况下的不同优化目标(最小时间延误，或者是最小航向角的改变等等)[4-9].

基于人工势场法等分布式方法,计算速度快，但可能会产生不切实际的解；基于进化算法等集中式方法可靠性高，但是计算量大，响应速度较慢，实时性差.本文结合人工势场法与蚁群算法的优点提出改进混合冲突解脱方法，利用人工势场法迅速得到近似可行的冲突解脱路径，然后将方案调整、编码得到“权威蚂蚁”，由“权威蚂蚁”衍生“权威蚁群”，利用“权威蚁群”始化信息素矩阵，基于蚁群算法，求得含有飞行规划约束的解脱方案.并通过与传统的人工势场法与蚁群算法进行比较，验证了改进算法在时效性和可行性上的优点.

1 混合人工势场与蚁群算法

1.1 利用人工势场法得到初始路径

将冲突解脱问题进行巧妙的转换，将目的地看作正电荷，所有飞机看作负电荷.这样，异种电荷互相吸引的作用保证了每架飞机会飞往目的地，而同种电荷互相排斥的作用则保证了不会发生飞行冲突.通过合理构造正负电荷的电场，将其化为物理学问题，对各飞机受力分析，确定运动轨迹,见图1.具体来说，假设有N架飞机，第i架飞机的位置为xi=(xi,yi).

图1 受力分析

为了确保飞机能飞往目的地，目的地xdi=(xdi,ydi)会激发引力场势场函数

(1)

目标点产生的引力

Fa(xi,xdi)=-Ua(xi,xdi)=-(xi-xdi)

(2)

为了避免和飞机j碰撞，飞机j会激发斥力场Ur(xi,xj),

(3)

式(3)为了保证遇到冲突时飞机都能向同一方向转弯，引入与斥力场相切的涡旋场

(4)

将上述三个力场叠加，就可以得到多机情况下动态的路劲规划方程：

kviFv(xi,xj))j=1，2，…，m，i≠j

(5)

斥力和涡旋力在[0,1]间取值，其大小可控制解脱路径的弧度.将牵引力归一化是为了使其和斥力、涡旋力的量级一致，这样其大小就和飞机到目的地的距离无关，仅指示去往目的地的方向.斥力系数kri、涡旋系数kvi用来控制斥力、涡旋力影响速度的权重.

图2 人工势场流程图

1.2 “权威”蚂蚁

势场法每步的航向由目的地的引力和其他飞机的斥力共同决定，这就使得其航向偏转在实数范围内取值；按照航向偏转只能取0°，±30°这三个离散的值.为了使人工势场的结果能顺利编码，有必要将人工势场的规划结果做适当的近似.事实上，只要确定了每架飞机解脱过程中每步的航向，解脱方案就唯一确定.如果飞机沿着之前的航向飞行与势场法要求的航向的偏差在容许误差(15°)内，则沿原航向飞行，反之做相应的调整.

近似后的航迹就可以按照之前约定的方式顺利编码，就可以得到“权威蚂蚁”的觅食路径.

1.3 “权威蚁群”

为了避免单次近似所带来的偶然误差，尽可能的全面地表征势场法得到的解脱轨迹，借鉴遗传算法基因变异的相关理论，由这只“权威蚂蚁”衍生“权威蚁群”.

假设“权威蚂蚁”的路径X=(x1,x2,…，xN*K)，xi∈{-1 1 0}，X的N×K个分量亦可看作该路径的基因.进行变异操作，随机选取其中若干分量，对每个分量，令其等概地向另外两种可取值变异.然后，对变异后产生的新个体进行安全性检验: 将变异后的x解码，检验其对应的解脱方案是否满足安全性要求.如果满足安全性要求(即没有飞行冲突)，就认为成功衍生了另一只“权威蚂蚁”.重复这样的操作，可以得到“权威蚁群”.

1.4 初始化信息素矩阵

每一只“权威蚂蚁”会根据解码后对应解脱方案的延误，在其路径上适当分泌信息素，而使路径上每一节点的信息素得到更新.更新方程为：τij(t+1)=(1-ρ)τij(t)+Q/S.

将“权威蚁群”的所有蚂蚁按上述方程更新它们经过的节点的信息素，就完成了初始化信息素矩阵的工作.

1.5 蚁群算法

利用蚁群算法解决冲突解脱问题，两个难点：①如何将冲突解脱方案映射为蚂蚁觅食路径，即编码问题；②定义怎样的路径为找到食物，即优化目标问题.鉴于此，下面将分三个部分阐述利用蚁群算法求解冲突解脱问题的流程.

1.5.1编码

为了在保证精度的情况下尽快获得计算结果，算法设定仿真步长为10 km，即每10 km更新一次航路点，这样，就可以将任意一架进入扇区的飞机的解脱过程离散化为K步.在每一步中，飞机保持一定的速度和航向，在进入每一步之前飞机的航向能做出调整，见图3.

考虑到民用飞机在巡航阶段正常飞行，一般没有大角度转弯或转向飞行.做出如下假设：飞机在解脱过程中只能选择三个飞行方向，即保持原有航向，左转30°，右转30°.这种假设除了简化搜索空间，还可以减少飞行员的反应时间，使其更好地执行冲突解脱方案.

综上，假设N架飞机在解脱过程中分为K步进行调整，将每步的调整方式用1(代表右转30°)，-1(左转30°)，0(保持原航向)编码，则每一种解脱方案被编码为一个N×K维的向量X=(x1,x2,…，xN*K)，xi∈{-1 1 0} (每k个分量对应一架飞机的解脱轨迹).

图3 离散化的解脱航迹

假设蚂蚁要穿越一个3×NK的迷宫，从第一列运动到最后一列觅食，每一列有三个节点供蚂蚁选择.这样，蚂蚁的每一条觅食路径就对应上文所述的编码向量，进而对应一个冲突解脱方案，至此我们完成了编码的工作，见图4.

图4 编码机制

1.5.2优化目标

为了保障飞行安全，任意时刻、任意两架飞机间的距离大约最小安全间距σ(20 km).对于离散化的冲突解脱过程，需要满足的约束条件为：|A′i-B′i|>σ，i=1,2,…,k(|A′i-B′i|表示第i步A、B两架飞机的直线距离).

那么，当蚂蚁路径所对应的解脱航迹满足上述安全性的要求时，就可以认为该蚂蚁找到了食物，从而会在该路径上分泌一定量的信息素来引导后续蚂蚁，否则，则认为该路径为无效路径，蚂蚁不会分泌信息素.

满足安全性的条件下，为了评价不同的解脱方案，定义飞机的延误Si.这里，假定每架飞机解脱过程飞行的距离和预设的飞行距离保持不变.具体来说，假定按照飞行计划，A飞机由A0飞往Ak是200 km的飞行距离，那么解脱方案也只规划200 km的飞行轨迹.为了规避冲突，A必须在飞行过程中进行航向的调整，这样飞行200 km后，A就不能到达Ak，而是落在了与其相近的A′k.将二者的距离定义为飞机在该种解脱方案下的延误：Si=|A′k-Ak|.为了顺利达到目的地，飞机要补偿飞行Si，显然，为了规避冲突而带来的额外运营成本、航班延误都和Si正相关，故而可以选择它作为评价解脱方案的指标.

定义解脱方案的延误S为所有飞机的延误的和，即S=∑Ni=1Si.S越小说明解脱方案越优秀，映射到蚁群算法中，可以认为该方案所对应的蚂蚁路径找到了更多的食物，从而会在该路径上分泌更多的信息素.

1.5.3迭代寻优

模拟蚂蚁自组织过程、程式化地迭代寻优，如下几个参数直接决定蚂蚁路径.

1) “迷宫”每个节点的信息素τijτij为第j列第i个节点的信息素.每当有成功觅食的蚂蚁经过该节点时，蚂蚁就会根据路径译码后对应的解脱方案的延误适当分泌信息素，而使该节点的信息素得到更新.更新方程为

τij(t+1)=(1-ρ)τij(t)+Q/S

(6)

式中：ρ为挥发系数，取值介于0到1，表征上一代蚂蚁留下的信息素的挥发速度；S为前文定义的解脱方案的延误.已分析过，S越小，解脱方案越优秀，故而要求蚂蚁分泌的信息素越多，二者存在负相关的关系.本文取反比来近似.Q为增益系数.将蚂蚁每次迭代分泌的信息素调整到合适的量级.

2) 蚂蚁的转移概率PijPij为蚂蚁第j步选择第i个节点的概率，设定蚂蚁选择每个节点的概率和该节点信息素的强度成正比，就有：Pij=τij/∑3i=1τij

经过“权威蚁群”初始化信息素后，第一代蚂蚁选择每一节点的概率和该节点信息素的强度成正比，即：Pij=τij/∑3i=1τij.由于“权威蚁群”根据人工势场法得到的解脱方案调整而来，利用其初始化信息素后能引导大量蚂蚁找到不发生冲突的安全路径，这样就避免了基本蚁群算法在初期没有信息素的指引，完全随机探测，得到大量无效路径的问题.

如前文所述，处于无效路径的蚂蚁不会分泌信息素，只有确保飞行安全的前提下，蚂蚁才会根据延误量在各自路径上适当分泌信息素，以此来引导后续蚂蚁，进而形成信息素的正反馈来加快解的收敛.利用“权威蚁群”初始化信息素保证了蚁群初期就能迅速搜索到安全路径，让其快速进入“正反馈”过程，这无疑会极大加快算法的收敛速度.

2 实验分析

2.1 场景描述

在经典对飞场景下，所有的飞飞行器均匀分布在同一个圆周上，该圆的半径为100 n mile，每架飞行器将沿着一条直线飞行.显然，如果没有进行冲突解脱调控，冲突将发生在圆周的中心点上.虽然这种极端情况似乎不太可能在现实中发生，但它可以洞察在极端情况下，算法在复杂的飞行器冲突解脱场景中处理问题的性能和效率.经典对飞场景见图5.

图5 经典对飞场景示意图

2.2 评价指标

实验将采用四个主要指标来评估飞行器冲突解脱方案的质量即：冲突概率，计算时间，可行性，以及系统效率.

冲突概率是评价飞行器冲突解脱方案系统安全性的一个重要指标，为

(7)

式中：Cj为第j个飞行器的冲突数；n为飞行器的总数.

考虑到飞行器在高速飞行时需要实时解决飞行冲突，以确保飞行安全.有效缩短计算时间是不同的算法需要解决的重要问题.

引入参数算法的平均计算负荷，可表示为

(8)

式中：m为实验重复次数；Tj为第j次实验所需要的时间.

在某些飞行器冲突解脱方案中，有些方案的航向改变量可能太大，超出了飞行器机械性能可以实施的范围，记为一次不可行点.

可行性可以表示为

F=∑ni=1fi

(9)

式中：fi为第i架飞行器在飞行器冲突解脱方案不可行点的数量；F为用来评估一个飞行器冲突解脱方案可行性的参数.

系统效率为

(10)

式中：Si为第i个飞行器延误；Sdi为第i个飞行器的预设步长.显然，当所有的飞行器沿预定的航迹飞行时，SE=1；当涉及的参与冲突飞行器的数量增加时，SE将会相应减少.

2.3 经典对飞场景下解脱方案对比

由于所有的飞行器都会在同一时间通过圆的中心，每架飞行器必须改变它的航迹，以避免冲突.

在经典对飞场景中，改进算法与其他方法的性能参数对比见表1.由表1可知，改进后的算法的优越性随着飞行器数量的增长得到更好地体现.尽管改进后算法的性能参数并不是都是最好的，但他们与最好的性能差别并不是特别大.在实际情况下，改进算法的每一个解都是可行的，符合实际工程应用的要求，即获得“不是最好的，但最有效的”解决方案.

表1 经典场景下人工势场法、蚁群算法的和改进算法性能参数对比

注：CL-计算时间；F-可行性；SE-系统效率；CP-冲突概率.

在经典对飞场景下，比较三种算法的计算时间、可行性、系统效率和冲突概率的对比图见图6.

图6 三种算法在经典对飞场景下的对比

由图6a)可知，当飞行器架数超过12架后，蚁群优化算法的计算时间已经超过60 s，不符合冲突解脱实时性的要求.虽然人工势场法的计算时间略小于改进算法，但两者算法计算时间相差不大，都符合冲突解脱时的实时性需求.

由图6b)可知，人工势场法不符合可行性要求.在改进算法中，飞行器只能选择三个飞行方向，即保持原来的方向不变，左转30°或右转30°.这个假设可以保证确改进算法得到的飞行器冲突解脱方案是可行的.此外，该假设不仅减少了搜索空间，也减少飞行员所需的反应时间，使飞行器冲突解脱方案的更容易实施.

由图6c)可知，改进算法的系统效率明显高于基本的蚁群优化算法，但略低于人工势场法.由图6d)可知，蚁群优化算法的冲突概率远高于人工势场法和改进算法.

人工势场法在计算时间较短、系统效率和冲突的概率较低，但算法的可行性欠佳不能应用于实际场景.蚁群优化算法的性能也不理想.改进后的算法在所有四个指标(即计算时间、可行性、系统效率和冲突概率)上均符合实际场景的需求，并有着较好的速度与效率.

3 结束语

基于人工势场法等分布式方法虽然计算速度快，但可能会产生不切实际的解；基于进化算法等集中式方法可靠性高，但是计算量大，响应速度较慢，实时性差.本文结合人工势场法与蚁群算法的优点提出改进混合冲突解脱方法，利用人工势场法迅速得到近似可行的冲突解脱路径，将方案调整、编码得到“权威蚂蚁”，由“权威蚂蚁”衍生“权威蚁群”，利用“权威蚁群”始化信息素矩阵，基于蚁群算法，求得含有飞行规划约束的解脱方案.并通过与传统的人工势场法与蚁群算法进行比较，验证了改进算法在时效性和可行性上的优点.