无人机集群路径规划算法研究综述

刘君兰，张文博，姬红兵，朱明哲

（西安电子科技大学电子工程学院，陕西 西安 710071）

0 引言

无人机集群具有抗毁重构强、分布协同性高、军事经济效益显著等优势，能完成目标侦察、精准打击、通信干扰、通信中继等多项任务。因此，相关研究得到了各国的广泛关注。无人机集群控制技术主要包括编队控制、任务分配、路径规划、避碰避障等。其中，无人机集群路径规划是在满足一定约束条件下，规划出从起始点到目标点的路径，使得指定的性能指标最优。约束条件主要指环境约束、任务约束、空间协同约束、时序协同约束、无人机自身约束等。性能指标可以包括路径长度、路径光滑程度、路径安全性、任务完成时间等。无人机集群路径规划算法本质上是一个多约束的组合优化算法，主要包括传统的路径规划算法、智能优化算法和深度强化学习算法。本文首先梳理了传统路径规划算法，再着重探讨了深度强化学习算法在无人机集群路径规划上的应用，最后对无人机集群路径规划算法进行比较和总结。

1 传统路径规划算法

传统路径规划算法相对成熟，已经被广泛应用于单无人机寻路问题上。多无人机路径规划需要考虑各种协同约束以及路径交叉、飞行安全性问题。传统路径规划算法主要分为基于图搜索法、采样法和人工势场法。基于图搜索法对整个环境进行建模，再进行路径搜索，比较直观，易求出最短路径，适用于全局和连续区域内的路径规划，包括Dijkstra 算法、A*算法、D*算法等；人工势场法原理简单，易于实现，实时性好，局部寻路能力强，被广泛应用于智能优化算法和深度强化学习算法中，解决收敛慢问题；采样法通过采点构图来表示环境，再进行路径搜索，典型代表有快速扩展随机树算法（RRT）。

1.1 基于图搜索法

Dijkstra 算法的核心思想是贪心和广度优先搜索，以起始点为中心向四周扩散，以节点到起点的代价作为优先级选择下一路径点。这种算法能找到最优路径，但是花费时间长。

A*算法是Dijkstra 算法的改进算法，在Dijkstra 算法的基础上加了启发式搜索思想，在选择下一路径点时不仅考虑它到起点的代价还考虑了它到终点的代价。A*算法相较于Dijkstra 算法，能更快找到最短路径，原理简单易实现。然而，A*算法也存在规划路径不平滑问题，主要是由于搜索领域太小、路径转角太大导致，可增大搜索领域来改进。针对A*算法规划路径距离障碍物太近、路径安全性低问题，葛文雅等人提出了一种移动机器人路径规划安全A*算法，在启发式函数中增加了安全性评估函数，使得算法在选择下一路径点时会考虑距离障碍物的距离。

1.2 人工势场法

人工势场法（APF）将物理学中“势场”的概念引入无人机集群任务场景。核心思想是场景中的障碍物对无人机产生斥力，目标点对无人机产生引力，无人机在合力作用下运动。该算法实时性好,规划路径平滑，适用于局部路径规划。但是，由于无人机集群任务场景中元素复杂，合力为零的点较多，APF 易陷入局部最优,一种改进思路是设置虚拟障碍物或者虚拟目标点来摆脱局部最优点。对于APF 目标点不可达问题，可以通过设置最小吸引力大小、缩小无人机受斥力的方向范围、斥力随无人机靠近目标点而减小来改进。针对APF 应用在无人机集群任务场景中路径交叉问题，毛远航在文献[8]中为碰撞可能性高的无人机重新规划航点，来避免无人机发生碰撞。

1.3 采样法

前文提到的基于图搜索法、人工势场法，都需要对环境进行建模。在多维复杂空间，建模会花费大量时间和计算成本。采样法不需要对整个环境空间进行建模，以采样点重构环境，计算量相对较少。以RRT 算法为例，RRT 算法通过在空间随机采点来构建空间填充树，以树的躯干作为路径。然而，RRT 算法存在较大的随机性，收敛慢。郭枭鹏在文献[9]中将RRT 算法与人工势场法结合，利用RRT 随机采样特性帮助APF 跳出局部最优解。同时又通过APF 目标引力来引导随机树扩展，降低RRT 算法的随机性，使得寻路更具方向性。

2 智能优化算法

智能优化算法大多是通过模仿群体生物觅食、围捕行为等方式，来搜索空间最优解。算法能够解决高维复杂、多约束的优化问题。常见算法有遗传算法（GA）、蚁群算法（ACO）、粒子群算法（PSO）、蜂群算法、狼群算法等。

2.1 遗传算法

遗传算法是一种基于生物遗传进化过程的自适应方法，可以用来解决搜索和优化问题。算法的优势在于不受问题领域限制，具备快速启发式搜索的能力。劣势在于易早熟，易陷入局部最优解。改进方法有将GA 和传统路径规划算法结合，优化路径点；改进交叉算子或是变异算子；增加种群多样性等。吴振等人针对早熟问题，采用一种动态的适应度值标定法，以减小个体间适应度差值，防止进化初期某些超常个体占据整个种群导致早熟。周加权将模拟退火法与GA 结合，并对遗传过程中的交叉、变异进行调整，有效提升了GA 的全局搜索能力,克服了传统遗传算法陷入局部最优的问题。

2.2 蚁群算法

蚁群算法是一种随机搜索算法，核心思想是利用蚁群的信息素，通过正反馈的方式寻求问题的最优解。针对ACO 自身收敛慢、易陷入局部最优解问题，陈侠等人引入自适应参数和双向搜索机制，得到了理想的航迹。蚁群改进算法在无人机集群优化方面应用较多。苏菲等人对ACO 引入协同策略，使得算法能用于多种协同约束条件下多机航迹规划。针对无人机集群路径规划中路径交叉问题，宋霏羽等人进行了交叉检测与消除，提出的改进ACO 能增加解的多样性，跳出局部最优。苏梅梅等人改进ACO的信息素更新机制，增加了无人机数量约束，解决了无人机集群执行任务时路径交叉、资源分配不均匀等问题。

2.3 粒子群算法

粒子群算法在1995 年被提出，源于对鸟群捕食行为的研究。核心思想是群体中每个粒子共享自己找到的极值，获得整个粒子群的最值，然后对每个粒子进行调整，最终找到全局最优解。PSO 算法的主要优势在于简单、易实现、收敛快、可调参数少。

在相对较复杂的环境中，PSO 算法容易陷入局部最优，针对这一问题可通过调整PSO 的参数，如惯性权重，加速因子等来解决。谢勇宏等人采用线性递减的惯性权重方式，来均衡不同迭代时期粒子的全局搜索与局部搜索能力，在速度更新公式中加入加速度量，帮助粒子跳出局部最优。万路萍在文献[19]中采用非线性递减惯性权重，保证在算法迭代后期仍能保持良好的寻优能力；在粒子陷入局部最优时，也会在速度上给予一些扰动，让粒子跳出局部最优。也有一些结合其他算法的改进PSO，付兴武等人将天牛须搜索算法与PSO 结合，利用天牛个体对环境具有独立判断能力来克服PSO 中粒子完全受群体最优影响，最终改进算法在三维路径规划上效果更优。针对无人机路径规划中方案单一问题，苏子美等人结合基于集的粒子群优化（S-PSO）和综合学习粒子群优化（CLPSO），对速度更新公式进行改进，增加了最优解的多样性。

3 深度强化学习算法

深度强化学习算法主要分为基于值函数的算法、基于策略函数的算法和结合两者优势的Actor-Critic 架构算法。基于值函数的算法拥有拟合动作价值函数的网络，代表算法有DQN、Rainbow 等。基于策略函数的算法有拟合动作空间的概率分布函数的策略网络，代表算法有PG、TRPO 等。结合两家之长的Actor-Critic架构算法既有评价动作好坏的Critic 网络，也有选择动作的Actor网络。其代表算法有A3C、DDPG 等。

传统方法大多分开处理无人机集群路径规划及任务分配问题，忽视了两者之间的耦合关系。强化学习算法更多的是以任务为导向，以奖励函数为指引，在满足各种约束条件的前提下，完成任务分配、路径规划、避碰避障。目前应用较多的是DQN 及其改进算法、DDPG 算法及其改进算法。针对稀疏奖励，张仕充在文献[24]中提出了APF-DQN 模型，在奖励函数中设置人工势场分量，保证在未到达目标点时，也有一定的引导性奖励。对于训练样本奖励低导致收敛慢问题，王军等人将HER 与DQN 相结合来增加经验池样本有效性，从而提高收敛速度。张瀚等人结合人工势场法来干预DDPG 算法的动作选择，最终提升了路径平滑度，缩短了路径长度。于盛在文献[27]中利用MADDPG 解决了多无人机二维空间的多目标路径规划问题，在设置奖励函数时充分考虑到了避碰、避障、趋向目标这三点。

强化学习试错-学习机制可能导致训练初期盲目性问题，研究者通过引入迁移学习的相关知识来帮助强化学习适应更复杂的任务场景。迁移学习主要包括基于实例的迁移、基于特征的迁移和基于共享参数的迁移。其中基于共享参数的迁移最为常用，可以将二维环境训练出来的模型参数映射到三维环境的模型中作为初始参数，也可以将静态环境训练出来的模型参数作为动态环境下模型的初始参数。胡晓东等人将静态环境下训练的深度神经网络权重作为动态环境下深度神经网络的初始权重，最终成功缩短了训练收敛时间。

4 无人机集群路径规划算法比较

无人机集群路径规划不仅需要考虑复杂未知环境、无人机自身性能约束，还要考虑无人机之间的时间协同和空间协同约束。传统路径规划算法、智能优化算法和深度强化学习算法在路径规划上有各自的优势和劣势以及适用的场景，如表1 所示。

表1 无人机集群路径规划算法

5 结束语

无人机集群的应用场景较为复杂，传统的路径规划算法很难规划路径或者规划路径所花时间较长。智能优化算法和深度强化学习算法在复杂环境下更具优势，能实现真正的群体智能，但是智能优化算法存在易陷入局部最优，深度强化学习算法存在稀疏奖励等缺陷，需要结合其他算法来改善，所以在无人机集群在路径规划上应考虑各种算法相结合的混合算法。■