1. 引言
无人机(Unmanned Aerial Vehicle, UAV)是无人驾驶飞行器的简称。因其具有体积小、操作简单、生存能力强等优点，被广泛应用于军事、电力巡检、航空航天与科学研究等领域。在执行任务的过程中，无人机由于其特有的技术特点，可以搭载多种传感器设备，能够实时地监测当前的环境，确定自身所处的位置，实时地调整自身飞行姿态，规避各种障碍物，从而可以很好地完成既定的任务。在这个过程中，规划一条无碰撞、距离最短的路径是无人机能否顺利完成任务的前提和保障。在现实环境中，由于不确定的因素以及环境的可变性与动态性，无人机在执行飞行任务中会出现许多不可控的因素，因此，无人机路径规划算法的研究显得非常重要。
本文对目前主要使用的无人机路径规划算法进行综述，着重介绍了每种路径规划算法的基本原理、使用方法、代表性研究及其优缺点。同时，对后续的研究方向进行展望。
2. 无人机路径规划算法分类
Figure 1. Classification of UAV path planning algorithms
图1. 无人机路径规划算法分类
无人机路径规划是指在综合考虑能耗、威胁碰撞、路径长度等因素的基础上，规划出一条从出发点到达任务点且能耗最小的无碰撞路径。一条优秀的路径是无人机能否顺利完成任务的前提，而设计一条优秀路径最重要的部分就是路径规划算法的选取。优秀的路径规划算法不仅能够保证全局路径的最优性，还可以实时的躲过动态障碍物，从而提高无人机整体的飞行效率。目前，国内外学者对无人机路径规划算法进行了大量的研究，现阶段路径规划算法主要包括三类，一类是传统的无人机路径优化算法，如人工势场算法(APF) [1] [2] [3]、模糊逻辑算法 [4]、快速扩展随机树算法(RRT) [5] [6] [7] [8] 等；另一类是启发式无人机路径优化算法，如A*算法 [9] [10] [11] [12]、Dijkstra算法 [13] [14] [15]、模拟退火法 [16] [17] [18] 等；最后一类是目前最常用的群智能仿生路径优化算法，如遗传算法(GA) [19] [20] [21] [22]、蚁群算法(ACO) [23] [24] [25] [26]、粒子群算法(PSO) [27] [28] [29]、神经网络算法 [30] [31] [32] 等。具体分类如图1所示。
3. 传统路径规划优化算法
3.1. 人工势场算法
人工势场算法(APF)是类似于物理学中的一种引力场法，最早由Khatib提出。该方法的基本原理是将无人机在复杂环境中的运动抽象成在物理引力场中的运动，其中目标点对运动的无人机产生“引力”，可能的威胁物对运动的无人机产生“斥力”，最后通过求无人机所受合力来控制无人机的运动。一般来说该算法规划的路径比较好，但其也具有一定的局限性。具体表现在，当目标点附近存在威胁物时，威胁物离得越近，威胁物对无人机产生的“斥力”将远大于目标点对无人机产生的“引力”，从而在两种力的作用下，无人机将逐渐偏离目标点。因此，APF存在局部最优的问题，从而设计一种合适的人工势场成为了解决这个问题的关键。
针对传统人工势场法易陷入局部最优的问题，提出了许多解决方案。文献 [1] 中，韩尧等人提出了一种改进的APF，通过引入角度与速度调节因子，模拟真实的无人机飞行轨迹，然后又引入辅助避障力，有效地避开了局部最小值点。文献 [2] 提出一种用于三维环境下的多点势场路径规划算法，通过在APF的基础上引入定向搜索算法，轻松的克服了局部极限值问题。文献 [3] 中，邓叶等人通过在斥力势场函数中加入目标点与路径节点相对距离参数，同时引入了协调力，有效的解决了传统APF的局部极值问题。
3.2. 模糊逻辑算法
模糊逻辑法指对于不确定、未知的领域，模仿人脑的推理思维方式，进行模糊综合判断。对于无人机路径规划而言，模糊逻辑法的基本思想是在不清楚、不确定的环境里完成路径规划。该方法的优点是不需要提前构建模型，不依赖当前的环境信息，计算量小，鲁棒性好，但该方法在未知环境下运行时易出现局部死锁的问题，同时对于突发的威胁，不能做出及时的处理。目前，针对二维路径规划的研究，郭娜等人 [4] 提出了一种结合预测和模糊控制的局部路径规划方法。对于无人机三维路径规划的研究，国内外学者应用模糊逻辑算法相对较少。
3.3. 快速扩展随机树算法
快速扩展随机树算法是一种基于数据搜索的一种算法，简称RRT，基本原理是通过对组态空间选取采样点，然后逐步缩短随机采样点与搜索结构中结点之间的距离进行搜索，把搜索逐步导向空白区域，直到找到目标点。该算法可以非常有效的搜索三维空间，解决三维环境下路径规划问题。当然该算法也存在生成路径具有随机性、偏差性和收敛速度迟缓等问题。
针对RRT算法生成路径的随机性和偏差性，文献 [5] 中，周克强等人通过在RRT算法的基础上融入状态、时间、空间的思想，然后使用四元素法建立无人机的六自由度动力学模型，有效地解决了无人机动态路径重规划问题。针对路径规划算法中收敛速度迟缓的问题，文献 [6] 中，辛亭等人在RRT算法的基础上，引入一个方向参数，然后采用Dijkstr算法对产生的冗余节点进行处理，使得规划的路径成为无人机的可飞路径，有效的提高了收敛速度，并且也得到了近似的最优值。为了提高无人机路径规划算法的效率，文献 [7] 中，Aowabin Rahman等人在算法的起始点和目标点引入两棵随机树，提高了路径规划的速度。文献 [8] 中，李克玉等人提出了一种基于预规划路径优化RRT的算法。该算法首先在障碍物膨胀规则和相交规则下生成预规划路径，然后将预规划路径假设为由连续的质点组成，按一定的扩展树步长的比例从连续质点取点来确定搜索树的随机状态点，最后RRT算法在这些随机状态点的引导下进行搜索，生成避障规划路径。其改进的算法扩展了搜索的方向性，缩短了搜索时间，有效的提高了路径规划效率。
4. 启发式路径优化算法
4.1. A*算法
A* (A-Star)算法是一种信息搜索算法，也是静态路径中寻找最短路径最有效的搜索算法之一，被广泛应用二维环境路径寻优问题。该算法较好的结合了Dijkstra算法(广度优先)与贪心算法(深度优先)的优势，可以很好的解决全局路径规划问题。该算法的基本原理是通过定义一种特别的节点，然后从起点开始对所有节点进行位置评估，计算最小代价，并选取代价最小的节点进行继续搜索，直到找到目标点。这样不仅可以节省时间，还可以提高搜索效率，当然该算法还具有结构简单和收敛快等优点。但是当问题规模较大，环境复杂度较高时，该算法搜索效率较低，只可以生成一条路径。
针对复杂三维空间内无人机路径规划难的问题，文献 [9] 使用分层的思想对A*算法启发函数进行修改，并为相应的代价函数设置相应的权重，有效的提高了路径规划的效率。文献 [10] 中选择Dubins曲线作为A*算法的启发函数，有效的提高了路径的平滑性。文献 [11] 首先运用栅格法进行环境建模，然后利用IDA算法进行路径规划，最后对传统A*算法启发函数进行改进，提高了节点的搜索效率，并且结合双向搜索策略进一步降低了节点的搜索个数。文献 [12] 通过改变步长，设计变权值的路径评估函数，有效提升了路径的优化效果。
4.2. Dijkstra算法
Dijkstra算法是一种经典的路径规划算法，被广泛应用于二维环境的路径寻优中。它的基本原理是以起始点为中心，逐步向四周扩展，直到获得最短路径为止。该算法主要的优点是鲁棒性好，不存在局部最优的情况，一定可以找到最优路径。缺点是该算法需要遍历所有的节点，耗费时间比较长，效率比较低。
针对复杂环境下Dijkstra算法路径规划计算时间长的问题，王旭等人 [13] 通过使用蜂巢模型对地图进行建模，并在算法中引入一种模拟宣纸浸水模型，同时在搜索中引入地形影响参数，简化了运算模型，提高了路径规划效率。针对传统Dijkstra算法路径搜索范围大、效率低的问题，梁彧 [14] 提出一种改进Dijkstra算法，在原来算法的基础上于引入估计函数，对路径代价进行估计，缩短了响应时间，规划出了最短路径，同时也极大地提高了规划效率。李全勇等人 [15] 首先采用基于栅格图的拓扑地图建模方法，提高了路径平滑度，然后对时间权重进行优化，对传统算法中的权重因子进行优化，同时设计了弯道的时间权重函数。其改进的 Dijkstra 算法获得路径平滑度更好、时间权重更少、综合性能更好。
4.3. 模拟退火算法
模拟退火算法是一种基于固体退火的概率性算法。它的基本原理是通过给固体物质加热使其升温，温度升高后，固体内部分子运动加快，变成无序状态，然后通过外部操作使其均匀降温，固体内能减小，内部分子逐渐趋于有序状态。最后通过比较初始温度与结束温度，判断是否降到最低温度值，如果是，即可得到系统最低内能，也就是算法的最优解。该算法在实际应用中具有鲁棒性强、效率高和理论上全局最优的特点。目前已广泛应用于路径规划、车辆调度等方面。
文献 [16] 中，巩敦卫等人提出一种简单易行的模拟退火算法，通过引入脱障算子和一致寻优算子，前者采用维值定向扰动策略，使碰撞路段的两个端点以一定步长跳离障碍物，这既保证了路径的无碰性，又加快了寻优效率；后者对随机选取的若干个路径点进行变步长调整，使产生的可能解可以遍布整个解空间，提高了算法的全局寻优能力。文献 [17] 中，陶重犇等人通过三维栅格环境建模，验证了模拟退火算法的可行性，提高了路径规划的质量。针对无人机在丘陵山地区域工作效率低的问题，文献 [18] 范叶满等人根据无人机三维运动的受力分析提出了无人机三维运动的能效系数，设计了相应的模拟退火算法，完成了无人机在山地作业情况下能耗最优的作业路径规划。
5. 群智能仿生优化算法
5.1. 遗传算法
遗传算法(Genetic Algorithm, GA)是一种模仿自然界生物进化论的一种并行随机搜索算法，其中心思想是“优胜劣汰，适者生存”。它的主要原理是种群在进化过程中，对新产生的个体进行适应性筛选，适应性较差的个体被淘汰，适应性较好的个体被保留。这样反复操作，直到找到整个种群中最优的个体。该算法在应用上，由于其具有强大的全局搜索能力，被广泛应用于各种寻优问题中。但随着该算法被广泛应用，也暴露了一些问题，比如收敛速度慢、存在局部最优等问题。
在无人机路径规划的应用中中，文献 [19] 针对传统GA收敛速度慢的问题，提出了混合无重串选择算子、非对称映射交叉算子和启发式多次变异算子对传统GA进行改进，并采用三次B样条曲线进行路径平滑处理，提高了算法的收敛性和路径的平滑度。文献 [20] 针对GA早熟的问题，提出一种多频变异和交叉的思想，对种群初始化进行预处理，提高了算法的收敛速度。文献 [21] 通过在传统GA算法中增加删除节点的操作，避免了冗余路径点的出现。文献 [22] 通过建立无人机可飞行曲面，将实际飞行过程中的约束条件引入GA中，有效的提高了算法的搜索效率。
5.2. 蚁群算法
蚁群算法(Ant Colony Optimization, ACO)是一种模拟自然界中蚂蚁觅食行为的概率性算法，于1992年由Marco Dorigo博士提出。它的基本原理是蚂蚁在觅食的过程中，会在其经过的路径上释放一种信息素，而信息素的浓度与路径的长短成反比，信息素浓度越高路径越短。通常，蚂蚁会选择信息素浓度较高的路径，同时留下一定量的信息素，这样路径越短信息素浓度越高。最终，蚂蚁可以找到一条最短的觅食路径，即问题的最优解。该算法虽然具有强大的全局搜素能力，但是也存在耗时长与局部最优的问题。
ACO作为一种智能仿生算法，很好的被应用到路径规划方向。文献 [23] 通过构建分配不均的初始信息素，加入动态惩罚方法，降低了正反馈的作用，解决了局部死锁问题。文献 [24] 提出了多目标蚁群路径优化算法，通过改变启发信息，引入新的启发计算公式，适当缩小各可选路段的启发信息量，有效的加强了算法的搜索效率。文献 [25] 通过采用初始化信息素、引入权重因子和改进蚁群信息更新规则等方式，有效的提高了无人机路径的寻优效率。文献 [26] 针对传统无人机路径规划效率低与无法满足任务需求的特点，提出了一种改进的蚁群路径规划算法。首先，采用栅格法进行环境建模，其次，在路径搜索机制中引入一种双向搜索机制，最后，采取新的路径整合机制，避免了ACO过早陷入局部最优的问题，加快了寻优速度。
5.3. 粒子群算法
粒子群算法(Particle Swarm Optimization, PSO)是一种基于鸟群捕食行为的算法。它的基本原理指的是鸟群在寻找食物时，每只鸟在搜索食物的过程中都会相互间传递信息，以更新自己寻找食物的路径，以便自己找到最优的路径，同时他们也会将这个信息传递到整个鸟群，整个鸟群将会更新最优路径，这条最优路径也就是问题的最优解。
该算法操作简单、效率高、收敛速度快，被广泛应用于图像处理、函数优化和路径寻优等方向。但是对于需要跟踪动态极值的问题，PSO显示出了一些弊端，如解决问题效率低、存在局部最优等。在路径规划方面，文献 [27] 中为了保持粒子的多样性，引入元矩阵和交叉变异，并惯性调节参数，解决了PSO过早收敛的问题。文献 [28] 使用自适应原理调整学习参数，调节惯性权重和学习因子，有效改善了规划的路径。文献 [29] 中，王翼虎等人针对传统PSO在无人机路径规划方面易陷入局部最优的问题，提出使用细菌觅食算法的趋化操作和迁徙操作优化粒子群算法，并使用路径长度代价、障碍危险代价和航迹高程代价来构造适应度函数，有效的提高了寻优精度和稳定性。
5.4. 神经网络算法
神经网络是一种模拟生物神经网络结构和功能的一种数学模型，由大量的神经元连接构成。该算法通过模拟生物神经网络模型，进行自我学习与记忆，具有很好的寻优能力。当然该算法也有一定的缺陷，当面对复杂的问题时，神经网络算法往往比较耗时，最优性也无法得到保证。
在路径规划方面，文献 [30] 中，S. X. Yang等人首次将该算法应用到了路径规划方面，并实现了机器人的动态路径规划。文献 [31] 成功实现了神经网络算法对多无人机的路径规划。文献 [32] 中，徐卓通过波传的方式建立基于脉冲神经网络路径优化算法，实现了无人机在复杂威胁环境下的路径优化。
6. 存在的问题及后续展望
6.1. 存在的问题
目前，对于无人机路径规划的问题，国内外进行了大量的研究。但目前仍存在许多问题，主要包括环境建模问题、多无人机协同路径规划问题以及动态路径重规划问题等，具体分析如下：
1) 环境建模问题。路径规划过程中，现有的文献多是将无人机作为一个质点，任务空间多抽象为某种理想化、便于求解的模型，而没有考虑无人机的大小以及实际环境的复杂度，从而导致无人机在实际路径规划时效果比较差。
2) 多无人机协同路径规划问题。当前对于无人机路径规划算法研究，大部分集中于单无人机的研究，对于多无人机路径规划研究相对比较少。多无人机协同路径规划问题相较于单无人机路径规划问题，约束条件更多，协同性要求更高，计算更加复杂，实现更为困难。
3) 动态路径重规划问题。现有路径规划模型多假设目标状态和位置已知，然而，实际任务环境可能会存在许多不确定性，任务空间也更复杂，使得无人机在面对突发情况时路径动态重规划能力低、自适应性差。故有效地提高算法的动态适应性非常必要。
6.2. 后续展望
针对当前无人机路径规划存在的问题，未来应该从以下几方面进行研究改进。
1) 环境建模方面，应提高环境的复杂度与动态性，增加更多的飞行约束条件，同时将无人机自身的性能和特点等考虑在内，以便使仿真更加贴近实际。
2) 多无人机路径规划方面，应采用传统算法与群智能算法相结合的方式，提高多无人机路径规划的协同性。同时算法要更加关注多无人机整体和局部的关系、提高整体路径规划效率。
3) 动态路径规划方面，应提高环境的动态性，同时采用群智能融合算法，发扬每种算法的优点，规避单一算法的缺点，取长补短，从而达到更好的动态规划效果。
7. 结语
本文阐述了无人机路径规划算法的研究现状，并对当前路径规划算法的基本原理、优缺点以及后期可能的研究方向进行了分析。当前，单无人机静态路径规划算法已日趋成熟，但多无人机路径规划算法以及动态路径规划算法的研究还有很多问题，因此在接下来的工作中应着重进行这些方面的研究。
NOTES
*通讯作者。