基于CPSO算法的海空跨域无人航行器集群协同作业路径规划

殷 翔，李培正，骆曹飞，马赛男，马 勇

（1.武汉理工大学航运学院，武汉 430063；2.内河航运技术湖北省重点实验室，武汉 430063；3.浙江嘉蓝海洋电子有限公司，舟山 316000）

1 引言

随着人工智能、信息技术的快速发展，无人航行器自主航行能力得到显著提升，能够完成如环境勘测、应急救援等任务，被广泛地应用到相关行业并发挥了重要作用。随着应用场景的多元化，单个无人航行器已不能满足复杂任务情形的需求，跨域无人航行器集群可协同完成复杂场景下的任务需求。

文献[1]基于人工势场法设计了无人机（Unmanned Aerial Vehicle,UAV）与目标的动态博弈关系，设计了一种群UAV 围捕方法。文献[2]提出一种融合粒子群（Particle Swarm Optimization,PSO）与改进蚁群算法的无人潜航器（Autonomous Underwater Vehicle,AUV）路径规划算法PSO-ACO，实现了AUV 的三维路径规划。文献[3]提出了一种新型的k度平滑的协同UAV协调路径规划方法。文献[4]为无人艇（Unmanned Surface Vehicle,USV）设计了基于非线性模型预测控制的轨迹跟踪控制器，实现了跟随者对领导者目标轨迹的实时估计。文献[5]提出了一种考虑避碰和同步打击时间的UAV 集群多目标同时打击协同优化方法。文献[6]为AUV 提出了一种基于Octree 模型和改进蚁群算法的路径规划方法。文献[7]为AUV 路径规划问题设计了一种基于四叉树的蚁群算法。文献[8]提出了一种基于PSO算法改进的蚁群优化算法，以寻找复杂海底环境中AUV 到达指定目的地的最优路径。文献[9]设计了一种无人船艇协商协议来实现群无人艇避碰。文献[10]提出了一种基于深度强化学习的无人船艇编队路径跟踪方法。文献[11]设计了一种UAV 和USV 协作清污协作系统。文献[12]采用有限角度的A*算法为USV 集群规划最优路径。文献[13]针对四旋翼水下航行器协同包围控制问题，设计了自适应反步法控制器和鲁棒反步法控制器分别处理航行器受到的未知常值干扰和时变干扰。文献[14]建立声学通信和定位系统来提升USV 和AUV 导航和控制性能。文献[15]设计了一种包括搜索阶段和航行阶段的分步动态目标追踪方法，并使用IPSO 算法来生成航行器路径。文献[16]利用可变柔性机械臂配合拦阻索的机构辅助实现在狭小空间和恶劣条件下对微小型固定翼无人机平台的自主释放与回收，形成了一种全新的跨域异构协作的实现方式。文献[17]设计了一种用于UAV-USV 集群的协作通信框架。文献[18]设计了一种分层着陆引导点生成算法，通过引导点序列实现了UAV 在USV 甲板上的稳定着陆。

分析可知，在同一类型无人航行器集群协同路径规划方面已取得了大量成果，但在无人机协同无人艇、无人艇协同无人潜航器等跨域集群无人航行器协同作业规划方面成果相对较少。文献[19]明确了跨域协同的基本内涵：在不同领域互补性地而不是简单叠加性运用多种能力，使各领域之间互补增效，从而在多领域建立优势，获得完成任务所需要的行动自由。不同的无人航行器集群，如UAV 集群、USV 集群、AUV 集群等，由于存在航行环境、结构性能、运动模型等差异，不同类型的无人航行器集群胜任的任务场景不尽相同。为此，在跨域协同路径规划中，需要为各类无人航行器集群设置独立的作业任务，从而多个领域互补增效，实现跨域无人航行器集群协同作业路径规划的有机耦合。

UAV 集群在空中航行，以其机动灵活、空间障碍物少、探测视野开阔等特点，可为USV 高效完成水面航行环境探测任务；AUV 在水下航行，隐蔽性强，但水下航行环境复杂，导致其环境探测效率较低，适合执行短距离水下目标探测任务；USV 在水面航行，具有小型轻量、操纵灵活、自主性强、无人驾驶等优点，在UAV 协同下水面航行环境情况相对更容易获得，可搭载AUV 等可承担较远距离的作业任务。

为应对复杂作业任务需求，需要为UAV、USV 和AUV 集群协同规划高质量的路径。为此，本文提出一种基于协同粒子群优化（Cooperative Particle Swarm Optimization,CPSO）的路径规划算法，以增进海空跨域无人航行器集群协同作业能力。

2 海空跨域无人航行器集群协同作业路径规划模型

2.1 海空跨域无人航行器集群协同系统描述

针对海空跨域无人航行器集群协同作业路径规划问题，设计一个UAV 集群、USV 集群、AUV集群协同路径规划系统，在考虑避碰和转弯机动的基础上，区别不同UAV 集群的特性，给定不同无人航行器集群不同的航行任务，设计CPSO算法实现各无人航行器分步路径规划，最终来协同完成整体的目标追踪任务。整个系统运行过程为分步的三个阶段，每个阶段都对相应的跨域无人集群进行与之能力相适应的任务规划。第一阶段，UAV 集群起飞至航行高度，基于已知的航道信息，使用CPSO 算法规划UAV 集群路径，航行过程中使用传感器来沿途探测USV 航行区域障碍物，将障碍物的信息与已有的航道信息结合，生成完整的USV 通航环境图；第二阶段，利用完整的障碍物位置信息，通过CPSO 算法，规划USV集群的协同航行路径；第三阶段，USV 集群携带AUV 到达规划位置后，利用传感器探测水下航行环境，生成可用的水下航行环境图。AUV 集群结合航行环境图利用CPSO 算法规划集群协同水下路径，并从USV 处释放来追踪到目标位置。

海空跨域无人航行器集群的路径协同规划过程，实际上是分步的三次无人航行器集群协同路径规划过程，每个集群的航行都为下一个集群的规划提供关键的航行信息。每个集群的路径规划过程中，航行器的起始位置和终点位置已知，通过在两个已知信息点之间插入合适数量的路径点来形成一条完整的航行路径。航行场景的复杂程度决定了航行路径点的数量。

2.2 惩罚函数设计

在三个阶段的无人航行器集群路径规划的过程中，需要考虑航行中避碰因素、无人设备转弯性能因素[18]，同时协同航行的最终优化目标为整体航行时间最短。本文将障碍物碰撞约束、转弯性能约束、航行时间函数设计为惩罚函数。根据实际航行中无人航行器性能的差异，对不同的航行器设计不同的惩罚函数判断阈值和相关参数。为实现航线实际可行，将碰撞约束和转弯性能约束的惩罚函数设置较大的权重，使所有的规划航线不发生碰撞且同时满足无人航行设备转弯能力。

2.2.1 转弯惩罚函数

无人航行器在航行的过程中受到其结构和性能的约束，转弯过程的航迹通常较为平滑而且旋回半径有最小限制，因此需要加入独立的转弯性能的惩罚来使得每个航行器的航行轨迹实际可行。具体的设计方法为，每三个相邻且距离较近的航行路径点会形成一个转弯的夹角，而航行器的最小转弯半径需要小于规划路径的转弯夹角的最大内切圆半径，才能使得无人设备能够依照规划路径完成转向。

转弯惩罚函数的计算过程如下，三个相邻路径点构成的转弯夹角为：

取三个路径点的两段路径中最短的一段来设置内切圆，较短的路径为：

此时的最大内切圆半径计算为：

式中，α为每三个相邻路径点确定的路径夹角，l1是前两个路径点的距离，l2是后两个路径点的距离，l3是第一个和第三个路径点的距离，ρ是边l的最大内切圆半径，即极限转弯半径。

通过比较无人航行器的最小转弯半径和规划的转弯角的最大内切圆半径得到惩罚函数值tu为：

式中，无人航行器的最小转弯半径为R，且Pk–1，Pk，Pk–2为三个相邻的路径点，ρ≥R即表示规划的路径满足了航行设备的转弯性能约束。一段完整路径中每相邻三个路径点都需要进行转弯惩罚函数计算，从而得到完整路径的转弯惩罚函数值Atu为：

对于一条完整的路径若至少有一组惩罚函数取值为0，即发生过至少一次碰撞，则该路径的转弯惩罚函数值取0。

2.2.2 碰撞惩罚函数

海空跨域无人航行器集群规划航行的路径需要避免所有障碍物的碰撞。为简化避碰过程，将障碍物膨化为不同轴长的椭球。具体的碰撞惩罚设计方法为：首先根据航行器航行的高度，取得对应高度上障碍物切片信息，然后对于每两个相邻路径点构成的路径段都需要判断本路径段是否与障碍物切片相交。判断方法是计算路径线段上选取的样本点与障碍物切片圆心的距离，比较所有距离数值与障碍物切片半径的大小关系。

具体计算过程如下：

根据路径和障碍物的尺度确定航行器第k个路径线段的采样点数量n，生成采样点矩阵P：

第i个样本点与其对应的第j个障碍物切片圆心的距离为：

对于第i个样本点和第j个障碍物的碰撞惩罚数为：

航行器完整路径的碰撞惩罚函数值Acoll为：

2.2.3 时间惩罚函数

跨域无人航行器集群由于航行环境和性能的差异，实际航行速度有一定差异，这就导致最短的规划路径方案并不一定是最有效的方案。因此将航行时间最优而不是航行距离最优作为规划路径的评价指标。具体的设计方法是：对每个航行器的速度进行设置，根据规划的路径，计算每个航行器的航行时间，作为惩罚数值。

第i个航行器的近似航行距离为所有相邻的路径点的距离和，表示为如下：

则第i个航行器的航行时间为：

3 CPSO 协同作业路径规划算法

3.1 粒子群算法基本原理

粒子群优化算法是一种成熟的仿生算法，来源于对鸟类捕食过程的研究。粒子群算法采用群体进化的方法，需要建立N个维度的搜索区域，其中每个粒子都具有位置和速度两个矢量信息。在迭代过程中，会记录每个粒子的最佳位置和全局的最佳粒子位置，并共享信息到全局，根据每次迭代结果的共享信息来决定下一次迭代优化的方向。

具体的粒子群算法过程如下：

（1）首先建立维度M的初始粒子种群，为第i个粒子的当前位置信息矩阵；为第i个粒子进化速度矩阵。

（3）根据问题需求，确定适应度优劣评价标准，保存当前全局最优适应度的粒子位置和每个粒子最优适应度的位置，粒子个体最优历史确定如下式：

全局最优粒子确定如下式：

（4）根据已知的全局最优粒子和粒子个体最优历史，来确定粒子群的进化方向，具体进化方程包括速度更新和位置更新，速度更新方程如下式：

位置更新方程如下式：

式中，c1、c2为学习因子，用来分配全局最优粒子和粒子个体最优历史对于进化步长影响的权重；r1、r2为一对取值区间[0,1]的均匀分布随机数；Xbestij为第i个粒子个体最优历史的第j个数据值；Xallbestj为全局最优粒子的第j个数据值。

（5）重复步骤（2）～步骤（4），直到迭代次数达到预设代数，停止优化，输出当前全局最优粒子。

3.2 CPSO 算法和求解过程

粒子群优化算法具有较快的收敛速度，能高效处理简单的目标优化过程，广泛适用于不同领域的优化问题。但是随着优化目标的复杂度不断提高，普通的粒子群优化方法更加容易陷入局部最优解的情形。因此，本文使用协同粒子群优化方法，将复杂的优化目标分解为不同的粒子群的细化优化目标。协同粒子群算法基本思想为：建立一个有多个粒子种群的复合粒子群，每个独立粒子群代表了一个分解出来的细化优化目标，每个粒子群都具有M个维度，并在M个维度下进行优化，每一次的迭代优化，各个种群之间保持信息共享，直到达到整体的优化目标。

基于协同粒子群算法的求解过程如下：

（1）根据同类无人航行器的数量建立N个协同进化的粒子群，每个粒子群中包含M个粒子。建立每个粒子的位置矩阵和进化速度矩阵为第k个粒子群，第i个粒子的当前位置信息和当前进化速度。

（2）构造全局问题解C以及全局适应度函数：

式中，α、β、γ为不同惩罚函数的设计权重，权重的设计考虑到避碰和转弯约束的必要性，在平衡不同惩罚函数值量级的基础上，将α、β设计为较大权值，γ设计为较小权值。Atu、Acoll、γT分别为本文第二部分设计的惩罚函数。

（3）通过依次替换解中对应粒子群的粒子，搜索并保存每个粒子群的全局最优适应度的粒子位置和每个粒子最优适应度的位置。

第k个粒子群每个粒子个体最优历史确定如下：

第k个粒子群粒全局最优粒子确定如下：

（4）重复步骤（3），直到得到N个粒子群的所有粒子个体最优历史和全局最优粒子，全局问题解更新为：

然后通过式(17)、(18)对整个种群所有粒子的进化速度和当前位置进行更新迭代。

（5）重复步骤（3）～步骤（4），直到迭代次数达到预设代数，停止优化，输出并保存当前最优粒子群，即为此同类无人航行器最优路径规划方案。

（6）根据得到的同类航行器航行最优规划方案执行航行任务，并沿途更新其他集群航行器航行必要环境信息数据，完成之后，重复步骤（1）～步骤（6）来进行顺次的下一个同类无人航行器集群路径规划。直至3 次顺次的同类无人航行器路径规划完成后，得到并实现了最终的协同航行路径规划方案。

4 仿真结果及分析

4.1 海空跨域无人航行器集群参数设置

为了验证所提出的群无人航行器海空协同路径规划策略的有效性，本文建立了一个多障碍物的航行场景模型，并以其为任务区域进行模拟仿真实验。整个区域为一个水深100 m、空域高度100 m、长宽各为1000 m 的长方体区域。整个区域中，共设置大小、位置不同的11 个椭球形障碍物。

海空跨域无人航行器集群中包含 3 类无人航行器集群，每个集群根据任务需求来设置航行器数量；本文协同集群设计为：UAV 集群共两台，记为a1、a2；USV 集群共4 台，记为s1、s2、s3、s4；AUV 集群共两台，记为u1、u2。具体每台航行器的参数和状态设置如表1、表2所示。

表1 UAV 和AUV 基础参数Table 1 General parameters of UAV and AUV

表2 USV 基础参数Table 2 Basic parameters of USV

4.2 协同作业路径规划仿真

CPSO 算法需要预设最大迭代次数，迭代次数的设置不仅会影响优化过程探索全局解的能力，也会影响仿真规划的效率。较低次数的迭代虽然能快速得到可行解，但是收敛过早，对全局最优解的发现能力较差；较高次数的迭代虽然能够得到全局最优解，但是探索过程缓慢，效率低下。本文选择使用线性递减的惯性因子，来保证算法前期全局寻优能力强，后期局部寻优能力强。

仿真模拟过程中，进行多次仿真模拟过程，对比不同仿真迭代次数下算法的有效性。每次仿真实验预设不同的最大迭代次数，包括：10 次、30 次、50 次、100 次、200 次、500 次、800 次、1000 次、2000 次最大迭代数。得到的适应度测试结果见表3、图1、图2。同时，展示了10次、100 次、800 次的仿真规划方案，如图3～图5所示。

图1 不同迭代次数下的最优适应度值折线图Fig.1 Line diagram of optimal fitness value under different iterations

图2 整体最优适应度值折线图Fig.2 Line diagram of the overall optimal fitness values

图5 最大迭代次数为800 次的协同路径Fig.5 Collaborative path graph with maximum number of iterations of 800

表3 不同迭代数下适应度Table 3 Adaptation table under different iterations

由仿真结果可以看出：

（1）如图3所示，在本次仿真场景实验的条件下，10 次迭代优化就可以得到可行的协同作业路径规划方案。但是由于迭代次数较小对于全局解的探索能力较小，导致此时的协同作业规划方案适应度较差，虽然完全满足了避碰约束，但仅部分满足了转弯的约束，同时航行路径有往复，耗费了较多的航行时间。

图3 最大迭代次数为10 次的协同路径Fig.3 Collaborative path graph with maximum number of iterations of 10

（2）如图4所示，在100 次的最大迭代次数的条件下可以得到较优的协同作业路径规划方案，尤其是UAV 和USV 集群协同航行路径，完全满足了转弯和避碰的约束要求，同时航迹平滑没有往复。此时的UAV 集群和USV 集群的协同适应度迭代结果也达到最优水平，如图1所示。但是由于AUV 集群的规划路径区别于其他集群，需要考虑到航行深度的变化，导致路径规划更加复杂。从而，AUV 集群的规划路径依然有急转弯、往复的现象。相应的AUV 集群的协同适应度迭代结果（见图1）并未达到最优水平。

图4 最大迭代次数为100 次的协同路径Fig.4 Collaborative path graph with maximum number of iterations of 100

（3）如图5所示，在最大迭代次数设置为800次的条件下，得到了全局最优的协同作业路径规划方案。UAV 集群、USV 集群和AUV 集群均得到了最优的协同路径，即完全满足了转弯、避碰的约束条件，同时航迹线十分平滑。此时，如表3、图1、图2所示，各跨域无人集群的协同适应度和全局适应度均达到了最优水平。

仿真结果表明，在UAV 集群和USV 集群的协同作业路径规划过程中，能在50～100 次的最大迭代次数下较为稳定地收敛到最小适应度值，即得到这两个跨域协同集群作业方案的全局最优解；而AUV 集群的协同作业路径规划过程，需要500～800 次的迭代次数来收敛到较为稳定的最小适应度值。如图5所示的仿真结果，充分地体现出了本算法对于解决海空跨域无人航行器集群在复杂水域环境下协同作业以追踪水下目标问题的优越性和有效性。

5 结论

本文面向海空跨域无人航行器集群协同作业任务提出了一种基于CPSO 的路径规划算法。在CPSO 算法设计过程中，将无人航行器转弯性能、航行时效和避碰等约束条件以惩罚函数形式体现出来，建立全局的适应度优化函数实现非线性迭代求解，为各个无人航行器建立独立的粒子群来优化，并行处理同类航行器的优化过程，共享优化信息，减少了迭代次数，提升了协同作业路径规划的效率。仿真结果表明，CPSO 算法为UAV、USV、AUV 无人航行器集群规划了有效协同作业路径，实现了水下目标的有效跟踪。