多约束条件下无人艇和无人机集群协同航迹规划

侯岳奇，陶浩，龚俊斌，梁晓龙*，张诺

1 空军工程大学 空管领航学院，陕西 西安 710051

2 中国舰船研究设计中心，湖北 武汉 430064

3 中国人民解放军31005 部队，北京 100094

0 引 言

自美军2011 年提出空海一体战以来，随着多域战、多域作战等作战概念的递进演变，当前作战环境已不再局限于单一作战域，而是逐步向跨域协同、多域融合过渡[1]。在多域作战思想的引领下，结合无人作战的广阔前景，海上无人集群作战这一新兴作战概念应运而生。目前，海上无人集群在任务规划、航迹规划、环境感知和编队协同等方面的研究尚处于起步阶段，仍面临着诸多挑战[2]。

海上无人集群由无人艇（USV）和无人机（UAV）集群组成，综合考虑无人艇和无人机跨域特点的协同航迹规划是其中一项重要的关键技术。目前，大部分文献都是针对USV 或UAV 的航迹规划问题展开的研究。Niu 等[3]结合Voronoi 图和可视图的优点，采用Dijkstra 搜索算法求解了USV最短路径规划问题，在相同计算效率下能够得到比传统Voronoi 图方法更短的航行路径，但缺点是不能对具有非零区域的威胁区建模。Yang 等[4]将卫星热图像转换为二值图像，为航迹规划提供了环境信息，并在考虑USV 的转弯性能和环境约束的基础上，采用有限角度A*算法求解了USV的最短无碰撞路径。该方法的平均求解时间约为0.05 s，可作为实时航迹规划算法，但卫星图像的实时准确性难以保证。在USV 编队航迹规划方面，欧阳子路等[5]基于改进快速搜索随机数算法进行USV 编队路径规划，提出了一种非严格保形修正向量，能够在避开障碍物的情况下最大程度地保持队形稳定。Zhou 等[6]基于深度强化学习方法为USV 编队规划了可靠的避障路径，通过设计2 个奖励函数，对保持固定编队形状和灵活变化编队形状这2 种行为予以了训练学习，在障碍物杂乱的环境中，该方法的效果较好。相对USV，针对多UAV 航迹规划问题的研究起步则相对较早，目前，最新的研究主要集中在UAV 之间的协同上，例如，设计同时到达的航迹来提升协同攻击效果。Babel[7]针对多UAV 攻击多目标的航迹规划问题，提出了基于最短路径的同时到达优先算法，在考虑威胁和障碍的情况下，能够为多架UAV 规划满足时间约束的航迹。而在考虑跨域特点的协同航迹规划问题方面，相关研究则相对较少，Wu[8]针对无人潜航器和水空两栖无人机协同攻击目标航迹规划问题，对不同介质中的约束条件和优化指标进行建模，提出了水面搜索和水下攻击两阶段协同航迹规划方法，通过采用粒子群优化算法进行求解，实现了跨域协同攻击的效果。

由上述文献研究情况看，现有方法主要集中在解决同构平台的航迹规划方面，较少考虑跨域异构平台之间的耦合约束条件。USV 和UAV 集群协同航迹规划问题中需要考虑的耦合约束包括通信保持和到达时间约束。由于USV 与岸端指挥中心的直接通信距离和UAV 相比较短，所以通常需要通过UAV 来进行通信中继，以扩大其作战半径。因此，在USV 与UAV 协同航行的过程中，需要始终保持通信距离约束。此外，为了确保跨域集群到达作战区域时的整体协同性，USV 与UAV 的到达时间约束也需要重点考虑。

本文拟针对USV 和UAV 集群的协同航迹规划问题，在考虑威胁规避、机动特性和碰撞冲突约束的基础上，基于USV 和UAV 跨域通信的需求，进一步考虑通信保持约束，以使USV 和UAV集群在航行过程中能够始终保持通信连接。然后，设计航迹优化函数，将多约束条件转化为惩罚函数，并且采用自适应差分进化算法对优化问题进行求解。

1 协同航迹规划问题建模

1.1 问题描述

在执行任务的初始阶段，USV 集群从岸端指定水域出航，UAV 集群则从指定起降场起飞，经过一段路径的机动航行后，安全到达各自的任务区域执行后续的巡逻、搜索、侦察、定位、跟踪和攻击等作战任务。所谓的USV/UAV 集群协同航迹规划问题，是指以USV/UAV 平台初始位置为起点，以指定任务区域的进入点为终点，在综合考虑威胁规避、机动特性、碰撞冲突、通信连接、到达时间等因素的基础上，形成航迹性能达到最优的集群航行路径，从而使集群平台能够安全、快速地到达任务区域。图1 所示为USV 和UAV集群协同航迹规划示意图。

1.2 场景建模

USV/UAV 集群的运动空间为海域和空域，其不仅需要将平台的运动空间限制在海域和空域的指定边界内，还要考虑规避其中存在的威胁和障碍。针对场景建模问题，需要建立统一的模型来描述环境空间，这是后续进行协同航迹规划的基础。

空域建模采用多边形和圆形电子地理围栏[9]来描述空域的边界和威胁信息。空域边界为空中禁出地理围栏，用于限定UAV 在指定的空域范围内航行，确保UAV 在执行任务过程中的安全。由于敌方威胁、恶劣天气等原因，空中还存在着禁止UAV 飞入的禁飞区，即空中禁入地理围栏。为减少油耗，UAV 在前往任务区域的过程中应避免高度机动，故通常采用平飞方式。本文假设UAV 在同一高度层飞行，将空域简化为指定高度的多边形和圆形区域。首先，定义一个多边形地理围栏，包含的属性和参数为：

式中： κ为地理围栏属性，当 κ=1时为禁出地理围栏，当 κ=0时 为禁入地理围栏；h为地理围栏高度；m≥3， 为多边形顶点个数；pi（i=1，2，··· ，m）为地理围栏顶点坐标。顶点坐标的排列通常为顺时针或逆时针方向，且根据需要具体确定。针对圆形区域，与式（2）的定义方式类似，其主要参数为圆心坐标和半径，顶点个数定义为m=1。 空域EA是由一个空中禁出地理围栏和多个空中禁入地理围栏共同组成的区域：

式中：BA0为空中禁出地理围栏；BA1,BA2,···，为空中禁入地理围栏。在实际应用中，地理围栏是对任务区边界、威胁区、障碍物等的统一表示，在设定地理围栏时，要对区域进行缩放，留出一定的冗余区域，用以确保航行安全。

海域通常依托电子海图[10]进行建模。常见的ShapeFile 格式电子海图包含了30 多个图层，有一些对任务用途不大的图层信息可无需考虑，只需要分析处理对任务、导航和控制有用的图层，包括海洋/陆地、障碍物、航道、区域界线、地貌等图层即可。二维海图是采用多边形来拟合海岸线、岛屿、半岛和滩涂的形状，相当于用多条相连的线段拟合边缘不规则的平面图形，这种处理与空域的建模方式相同。海岸线为海面禁出地理围栏，岛屿、半岛和通信浮标等威胁及障碍物则为海面禁入地理围栏。因此，海域ES也是由一个海面禁出地理围栏和多个海面禁入地理围栏共同组成的区域：

式中：BS0为海面禁出地理围栏；BS1,BS2,···，为海面禁入地理围栏。

电子海图中的集合轮廓信息十分准确，一个岛屿一般由上百条边构成，一条海岸线则多达几千甚至是上万条边。这些庞大的图形信息需要消耗大量的计算资源，会导致算法效率大大降低，且精确的海岸线和岛屿轮廓信息对航迹规划的意义并不大。因此，在实际应用时需要对电子海图进行预处理，对海岸线和岛屿边界进行粗粒度简化处理，尽可能生成边数少、几何关系简单的场景模型。

2 协同航迹问题优化求解

本节将以集群航行时间为指标建立航迹优化函数，并考虑地理围栏、转弯机动、碰撞冲突、通信连接等多种约束条件，以将协同航迹规划问题转化为带约束的优化问题。鉴于自适应差分进化（self-adaptive differential evolution，SaDE）算法在求解高维非线性优化问题上的优势，采用SaDE 算法对优化问题进行求解。

2.1 航迹优化函数

航迹规划的主要目的是使跨域集群能够安全、快速地到达指定区域，评价航迹性能优劣的指标通常有航行距离、航行时间、航迹平滑度等。在航行距离方面，由于各平台的航行速度不同，故对航行距离进行优化不适用于性能有差异的异构平台。相比之下，航行时间的优化则更加符合航迹规划的目的，其优化的目标更加明确、具体。在航迹平滑度方面，从安全航行的角度来看，航迹的平滑程度只需满足平台转弯约束即可。航迹平滑度越好，平台转弯角度越小，航行时间越短，这与航行时间的优化目标是一致的。因此，选取航行时间这一优化指标即可满足航迹规划中快速到达指定区域的要求，而航行安全则通过设计约束条件来实现。本文从任务时效性需求出发，考虑到跨域无人集群的整体协同性，将选取集群平均航行时间为优化目标。平台Ui的航行路径长度为相邻路径点的距离之和，用D(Pi)表示：

式中， ‖·‖为 向量的欧氏范数。平台Ui的航行时间用T(Pi)表示：

式中，vi为 平台Ui的航行速度大小。为确保证跨域无人集群系统的整体协同性，提高执行后续任务的连贯性，通常需要各平台在尽可能短的时间内到达。因此，以平均航行时间为优化目标：

式中，P=(P1,P2,···,PN)，为所有航迹的集合。J(P)越小，则集群平均航行时间越短。

2.2 约束条件

在跨域协同航迹规划中，需要综合考虑的因素包括任务区域的威胁/障碍物分布、无人平台机动特性、集群各平台之间的避碰冲突以及通信保持。上述约束条件是影响航行安全的重要因素，必须将其作为航迹规划的硬性条件。本节将上述约束条件模型化为地理围栏约束、转弯机动约束、碰撞冲突约束和通信保持约束。

2.2.1 地理围栏约束

在执行任务过程中，各平台要始终保持在禁出地理围栏之内安全航行，同时，也要防止进入禁入地理围栏。针对圆形地理围栏，只需判断点与圆心的距离即可得到平台与地理围栏的位置关系。针对多边形地理围栏，可以采用现有的经典几何方法来判断平台Ui的 航迹Pi与地理围栏之间的关系[11]。这里不再赘述判断方法，只予以简单叙述。

当且仅当航迹Pi位于禁出地理围栏BS0内，并与禁入地理围栏 {BS1,BS2,···}不相交时，满足地理围栏约束，S1(Pi)=1；否则，不满足地理围栏约束，S1(Pi)=0。

2.2.2 转弯机动约束

图2 转弯过程中最大内切圆示意图Fig. 2 Diagram of maximum inscribed circle during turning

最大内切圆半径即极限转弯半径，若平台最小转弯半径大于该极限，则无法顺利完成转弯。假设平台的最小转弯半径为Rt，转弯约束可以表示为

2.2.3 碰撞冲突约束

USV/UAV 集群协同航迹规划问题需要同时考虑空间和时间的跨域协同关系，分别为集群协同关系在空间域和时间域上的体现。通过协调平台出发时间实现时间协同，并在此基础上考虑空间约束关系以进行碰撞冲突约束和通信保持约束的判断。对于协同航路规划问题，多平台之间极有可能发生碰撞冲突。碰撞冲突的研究对象是同构平台，即USV 与USV 之间以及UAV 与UAV 之间的碰撞冲突，必须确保同构平台之间的距离始终大于安全半径。但仅从航迹空间关系上无法判断是否存在冲突，需要从时空耦合的角度进行冲突检测。首先，确定时序关系，采用到达时间对齐、调整出发时间的方式来实现集群的同时到达。平 台Ui的 出 发 时 间ti为

然后，在时间统一的基础上进行空间冲突约束的判断。以时间间隔 ∆T进行离散化，得到一系列碰撞检测时序k∆T(k≥1)，其时序关系示意图如图3 所示。

图3 碰撞检测时序关系示意图Fig. 3 Time sequence diagram of collision detection

在碰撞检测时刻点k∆T，给定平台Ui的运动速度vi， 可以很容易推算得到Ui在k∆T时刻所处的位置，记为Pi[k]（其中，k为碰撞检测点序号）。对于同构平台Ui和Uj，相同序号碰撞检测点之间的相对距离应满足如下约束：

2.2.4 通信保持约束

USV/UAV 集群协同执行任务的能力是建立在可靠的通信网络上的，保持良好的通信连接是完成任务的前提条件，尤其是在复杂的条件下保持岸端、空中和海上的跨域联合通信。与同构集群不同，UAV 集群与USV 集群不仅要保持群内通信连接，跨域平台之间也要保持通信连接，即UAV 与USV 需要保持一定的空间关系以确保通信连接。

2.3 基于SaDE 算法的优化求解

考虑到上述多约束条件，跨域无人集群协同航迹规划问题可以转化为如下优化问题：

式中，P∗是使J(P)取值最小的最优航迹集合。所谓约束条件，是指所有平台的航迹必须同时满足地理围栏约束、转弯机动约束、碰撞冲突约束和通信保持约束。为便于优化求解，将约束条件转化为惩罚函数，得到如下优化问题：

式中，M为惩罚因子，取值为较大的正数。

当所有约束条件均满足时，惩罚项取值为0；当所有约束条件均不满足时，惩罚项的惩罚力度最大，取值为 4MN；当存在部分航迹不满足约束条件时，该项的取值为M的整数倍，其取值大小与不满足约束条件的个数有关。上述设计的优势在于，使航迹代价函数保持了一定的梯度，在优化过程中，满足约束条件个数较多的个体更容易被保留，进而逐渐产生符合约束条件的可行解。惩罚因子M应尽量大于J(P)的估算值，以保证惩罚项在寻优过程中的有效性。

由于平台数量和路径点个数较多，故该优化问题属于高维非线性优化问题。考虑到SaDE 算法在求解高维非线性优化问题上的优势[12]，这里采用该算法进行求解。差分进化算法是一种基于群体智能理论的随机启发式搜索算法，其通过群体内个体间的合作与竞争进行寻优。同时，该算法特有的记忆能力还使其可以动态跟踪当前的搜索情况，便于调整搜索策略，因此具有较强的鲁棒性和全局寻优能力。采用SaDE 算法求解上述航迹规划问题的算法步骤如下。

步骤1：路径编码。SaDE 算法采用的是实数编码形式，一个个体对应一个解，每个个体由若干实数位组成，每一位表示一个变量。首先，给定平台数量和中间路径点个数，确定编码的长度。平台Ui的 中间路径点个数为ni，在给定高度的情况下，中间路径点为二维变量，则平台Ui的中间路径变量个数为 2ni。编码总长度D为UAV 和USV 路径变量个数的总和：

该公式中的第1 项为NA架UAV 的路径变量总数，第2 项为NS艘USV 的路径变量总数。编码方式如图4 所示。

图4 SaDE 算法实数编码方式Fig. 4 Real number coding of SaDE algorithm

步骤2：产生初始种群，将进化代数初始化为1。根据地理围栏信息，确定路径点的规划空间，进而确定每个变量的上界和下界。设定种群规模为NP，随机生成NP个满足上、下界约束的初始个体。

步骤3：计算适应度函数。按照步骤1 中的编码方法，逆向操作解码以得到各个平台的航迹信息集合P，然后代入航迹代价函数中，计算每个个体的适应度函数值。

步骤4：进化操作。根据进化代数自适应调整变异算子，对种群进行变异操作和交叉操作，对边界条件进行处理以得到临时种群。对临时种群和原始种群中对应的个体，进行“一对一”的选择操作，选出优胜个体进化为新种群。

步骤5：终止优化。判断是否满足终止条件或达到最大进化代数，若是，则进化终止，否则，进化代数+1，返回步骤3。

在协同航迹规划优化过程中，随机生成的初始航迹通常不满足约束条件，在惩罚项的影响下适应度函数值较高。在优化初期，主要是寻找满足约束条件的“可行航迹”，需要设置较大的变异算子，提高种群的多样性，并寻找到尽可能多的“可行航迹”，防止“早熟”现象。而在优化后期，则主要是在“可行航迹”集中寻找最优航迹，需要设置较小的变异算子，提高全局最优解的精度。因此，采用具有自适应变异算子的SaDE 算法，自适应变异算子F设计如下：

式中：F0为常数变异算子；Gm为最大进化代数；G为当前进化代数； λ 为随G自适应变化的参数。在SaDE 算法中，变异算子决定了个体变异的幅值大小，决定了随机变异的精细程度。在进化初期，自适应变异算子为 2F0，保持了个体的多样性。随着不断的进化，变异算子逐步降低至F0，以保留优良航迹，提高搜索到全局最优航迹的概率。

3 仿真分析

为了验证所提协同航迹规划方法的有效性，本文采用1.2 节中建立的场景模型，以某湖试验场为任务区域进行模拟仿真验证。空域高度设置为500 m，空中禁出地理围栏为海域上方的矩形空域，并随机设置2 个空中禁入地理围栏和3 个海面禁入地理围栏。假设UAV 在指定区域起飞至指定高度，将完成起飞后的坐标点设为UAV的起点，USV 以岸端布放位置为起点。

仿真中，设置跨域集群平台数量为7，记为U1,U2,···,U7， 其中3 架UAV 记为U1∼U3，4 艘USV记为U4∼U7，UAV 和USV 的初始状态信息分别如表1 和表2 所示。各同构平台之间的安全半径均为100 m。UAV 之间的最大通信距离为12 km，UAV 与USV 之间的最大通信距离为10 km，USV 之间的最大通信距离为5 km。

表1 无人机初始状态信息Table 1 Initial status information of UAV

表2 无人艇初始状态信息Table 2 Initial status information of USV

根据平台数量及其中间路径点个数，可以得到SaDE 算法实数编码变量长度为20。在SaDE算法中，设置种群中个体数量为 200，最大进化代数为 500， 常数变异因子F0=0.3， 交叉因子为 0.1。其他参数取值为：惩罚因子M=103，离散时间间隔∆T=5 s。仿真结果如图5～图9 所示。

图5 示出了仿真场景下空中和海面禁入、禁出地理围栏，并给出了USV/UAV 集群的航迹规划结果。UAV 在高度为500 m 的空域中运动，USV在海面上航行，航迹起点均位于靠近左侧岸端的位置，航迹终点分布于右侧远端的任务区域。图5中，黑色虚线为空中和海面禁出地理围栏，所有航迹均保持在禁出地理围栏以内；红色和蓝色实线分别为空中、海面禁入地理围栏，为尽可能节省航行时间，部分航迹与禁入地理围栏距离较近，甚至出现了与地理围栏几乎“相切”的现象。这不会影响到航行的安全性，因为在设计地理围栏时已留有一定的冗余距离。仿真结果验证了前文所设计地理围栏约束的有效性。

图5 无人艇与无人机集群航迹规划结果Fig. 5 Results of path planning of USV and UAV swarms

航迹优化函数随迭代次数的变化曲线如图6所示。在优化初期，由于惩罚函数的作用，函数值较高，此时产生的解均不满足约束条件。从第1代迭代至第100 代，主要是寻找符合约束条件的可行解，此时函数值逐渐降低至1 000 以下，所产生的解满足约束条件，验证了前文设计的惩罚函数的合理性。从100 代以后，主要是寻找使优化函数值最小的解，最后到第500 代时适应度函数值收敛至565.8，也即USV/UAV 集群的平均航行时间为568.5 s。

图6 航迹优化函数值优化过程Fig. 6 Optimization process of path optimization function

图7 USV/UAV 集群平台航行时序关系图Fig. 7 Navigation sequence diagram of USV/UAV swarms

为了验证碰撞冲突约束和通信保持约束的有效性，图8～图9 给出了USV/UAV 集群平台间的实时距离变化情况。本节设定的安全半径均为100 m，因此安全距离为200 m。由图中可以看到，平台间的距离始终大于安全距离，验证了碰撞冲突约束的有效性。

图9 给出了3 组平台间的最大距离及其上限值，其中实线为平台间的实时最大距离，虚线为最大通信距离。从图中可以看到，所有平台的实时距离均小于最大通信距离，保证了USV/UAV集群的通信连接，验证了前文所提通信保持约束的有效性。

图8 平台间最小距离随时间变化的曲线Fig. 8 Variation curves of minimum distance between platforms with time

图9 平台间最大距离随时间变化的曲线Fig. 9 Variation curves of maximum distance between platforms with time

4 结 语

本文提出了基于自适应差分进化算法的USV 和UAV 集群协同航迹规划方法，实现了多约束条件下的协同航迹规划，并能够在障碍环境中实现集群安全航行和通信保持，具有一定的应用价值。通过地理围栏和时序检测方法，将障碍规避、平台防撞和通信保持问题建模为多个约束条件，并通过罚函数法将航迹规划问题转化为了无约束的优化问题。采用SaDE 算法进行了优化求解，其优势在于能够保持搜索初期的多样性和后期的精确性，保证最优航迹的求解，但随着路径点个数的增加，求解时间会不断增大。受求解时效性的限制，所提方法只能应用于离线航迹规划，后续将针对实时在线规划展开更深入的研究。