1. 引言
路径规划是指在给定的地图或空间环境中，通过对目标点和障碍物之间的关系进行建模，寻找从起点到终点的最优路径。而路径规划算法则是指解决路径规划问题所采用的计算方法和技术。路径规划算法广泛应用于自动化、机器人、航空航天、交通运输等领域，在无人驾驶、智能导航等实际应用中具有重要意义。同时，路径规划算法也是计算几何、优化算法、人工智能等不同领域交叉的产物。尽管路径规划算法在实际应用中取得了很大的成功，但由于各种复杂因素的影响，如车辆间的交互、环境变化等等，目前广泛使用的算法仍面临着诸多挑战。因此，研究者们需要对已有算法进行优化和改进，使之在更复杂的环境中具备更强的适应性和鲁棒性。本文综述了基于图搜索、基于采样、智能仿生等不同方法的无人机路径规划算法，并介绍了各种算法的优缺点，并对无人机路径规划未来的发展做出了展望。
2. 算法分类
无人机路径规划算法可以分为基于图搜索、基于采样、智能仿生算法等不同方法。如图1所示。
Figure 1. Classification of path planning algorithms
图1. 路径规划算法分类图
3. 传统路径规划算法
传统路径规划算法是指通过搜索、数学建模和其他基础知识来完成路径计算。与现代神经网络、深度学习等新兴领域的算法不同，这些传统算法主要关注问题的数学描述和寻找正确的决策过程。
3.1. 基于图搜索的路径规划算法
基于图搜索的路径规划算法是将无人机环境抽象成一个有向或无向图，然后使用搜索算法搜索最优路径。常见的搜索算法包括A*算法、Dijkstra算法等。这些算法都可以应用于无人机路径规划，且路径精度较高，但是它们却受状态空间大小以及维度的限制，当搜索状态空间过大或遇到高维状态空间时往往会遇到维数灾难等问题。
两种基础的基于图搜索的算法是深度优先搜索(DFS)和广度优先搜索(BFS)。
深度优先搜索(DFS)的基本思想是，从图上任意一个节点开始，沿着其中一条路径继续走到底，直至无法再向下，然后回溯到上一个节点，选择其它一条路径向下搜索，直到所有节点都被访问过为止。它具有内存消耗小、对于寻找任意一条路径具有优势的特点，但容易陷入死循环或者搜到非最短路径。
广度优先搜索(BFS)的基本思想是，从图的初始节点开始，依次遍历该节点的相邻节点(也称为邻居节点)，然后再依次遍历这些相邻节点的未被访问的邻居节点，直到所有节点都被访问过为止。BFS可以用于寻找最短路径问题，因为它首先访问距离起点更近的节点，而且检查每个节点的最早访问时间，确保对每个节点的最短路径进行了计算，而不是仅查找第一个达到目标的路径，但其空间复杂度较高。无人机的航拍视角存在一定的局限性。无人机通常以俯视视角拍摄地面目标，图像中多为小目标。小目标像素值低，特征单一，可利用信息少，给目标检测任务带来了一定的难度。常规目标检测算法的卷积神经网络中单层特征图表征能力有限，难以应对图像中复杂的小目标，导致检测效果较差。针对无人机航拍图像小目标检测性能差的问题，需要重新设计优化网络结构，提高网络的特征提取能力，增强算法的鲁棒性。
3.1.1. Dijkstra算法
Dijkstra算法最早发表于1959年，由荷兰计算机科学家狄克斯特拉提出 [1] 。广度优先搜索可以从起点开始向着离其最近的节点进行探索，而Dijkstra算法则是以当前已经找到的最短路径为基础，逐步更新到达其他节点需要的最短路径。可以说，Dijkstra算法是广度优先搜索的一种改进算法，因为它增加了对路径权重的考虑。对于无权图，每条边的权重都为1或者0时，Dijkstra算法实质上就退化成了广度优先搜索。Dijkstra算法的核心思想是上文提到的广度优先搜索与贪心策略的结合，它解决了带权图的单源最短路径问题，使用贪心策略选取当前最小的路径并扩展到连通分量的下一个点，直到所有节点都被遍历。这里要注意，它只适用于权值非负且没有负权回路的图，因为这样可以保证每条路径的权重总和都是唯一确定的。
Dijkstra算法常用于路由算法、地理信息系统(GIS)、GPS导航、互联网中的链路状态路由协议(如OSPF和IS-IS)等领域。但是，Dijkstra算法在实现过程中需要维护一个优先队列，并不断拓展到达起点的最短路径。因此，当顶点数量非常大时，执行时间和空间占用比较高。针对这一问题鲍培明 [2] 对算法进行了改进，在算法运行中他只考虑最短路径附近的顶点，而不对离最短路径较远的顶点进行处理，随着顶点的数量减少，算法的速度也就得到了提高。巩慧 [3] 等通过几何拓扑学的方法对运行轨迹进行了平滑处理，解决了算法路径转折点过多的问题。王超 [4] 等将红外技术与Dijkstra算法进行融合，显著增强了无人机的避障能力，这也正符合无人机路径规划未来加强多领域融合的趋势。
3.1.2. A*算法
A*算法是在1968年由Peter E. Hart、Nils John Nilsson、Bertram Raphael等人提出的 [5] 。A*算法是一种启发式搜索算法，用于解决加权有向图中的单源最短路径问题。它是在Dijkstra算法的基础上，通过引入启发函数为搜索提供辅助信息，在备选路径中选择更有可能到达目标节点的路径，以便快速找到最短路径。该算法基本思路是以起始节点为根节点，从起点节点开始搜索，将搜索范围分层，每次扩展离终点估计距离最近的节点作为当前节点，并按照启发函数进行排序。一直搜索到终点节点被访问或者开放列表为空为止。其中，启发函数是预测节点到终点的代价，常用的启发函数包括曼哈顿距离、欧几里得距离和切比雪夫距离等。如果没有考虑到目标节点，则A*算法就变成了Dijkstra算法；如果只考虑到目标节点而不计较路径到当前节点的代价，则A*算法会退化成启发式广度优先搜索。
A*算法在实际应用中，可能需要处理大量的节点，要存储和更新起始节点到当前节点的最小代价以及启发式函数估计值等信息。这些节点的存储和查找成本会相对较高，尤其是在面临高维度和复杂环境时，可能会造成缓慢的执行效率与较长的搜索时间。吴鹏 [6] 等针对这些问题对传统A*算法进行了改进，他运用双向搜索的方法，使正向搜索与反向搜索同时进行，从而让目标节点在中间区域相遇，大大减少了运行时间。王小红 [7] 等先将传统的8邻域扩展到24邻域；再将启发函数进行多种的融合，而不是采样单一的欧几里得距离或曼哈顿距离，去除了不必要的转折点和节点，这使得路径轨迹更加平滑。龚云鑫 [8] 等给出了凸角点和邻居关系的定义，用凸角点作为节点、邻居关系作为节点扩展到目标点的依据。这种方法降低了对无用节点的访问次数，有效提高了搜索效率和避障能力。
3.2. 基于采样的路径规划算法
与基于搜索的算法不同，基于采样的路径规划算法不需要对配置空间和边界进行构建。这种方法通常是指从给定的起点和终点，通过对自由空间进行采样或生成随机点的方式，依次确定可达的连接关系，从而生成一条符合约束条件的最优路径。基于采样的路径规划算法有PRM算法、RRT算法等。这些方法能有着较好的可扩展性和鲁棒性，但是其准确性受采样密度的影响，提高采样密度可以是最优路径更加精准，但同时也会增加算法的运行时间。
3.2.1. PRM算法
PRM (Probabilistic Roadmap)算法是一种常用于路径规划的基于采样的方法，又被叫做概率路线图，可以求解非闭合环境下的路径规划问题。它由Kavraki [9] 等人在1996年提出，现已被广泛应用于机器人运动规划、自主驾驶汽车、物料搬运等领域。
PRM算法的主要优点是可扩展性好、对复杂环境具有良好的适应性和处理能力强。缺点是需要大量随机采样来填充搜索空间，因此其计算效率相对较低。此外，由于需要手动调整参数来确保算法的有效性，并且通常情况下无法识别速度变化的区域或处于高风险位置的路径，导致其路径规划质量较差。
邹善席 [10] 等通过随机节点生成函数在自由空间生成随机节点，取代落在障碍物中的节点，在采样节点数目不变的情况下，提高自由空间中的节点数目，配合改进的节点增强法，提高了节点的利用率，降低了路径中节点数目。程谦 [11] 等通过改变改变采样点之间的距离，使不合理的路径减少，大大提高了算法的效率。薛阳 [12] 等将原先的最近邻搜索算法替换为了局部敏感哈希算法，加快了无向路线图的形成速度，减少了算法运行时间。
3.2.2. RRT算法
RRT (Rapidly-Exploring Random Tree)算法是一种在随机采样空间中快速探索建立搜索树的路径规划算法，又叫做快速扩展随机树算法。它可以求解非闭合环境下的路径规划问题，是在1998年由Steven M. LaValle和James J. Kuffner Jr. [13] 提出的。它与PRM算法相同，都是在采样空间中选择节点并使其与多个其他节点连接以构建通向目标状态的搜索图，但是PRM倾向于预先生成可行路径，然后使用搜索算法查找最短路径；而RRT则是基于原始方法迭代扩展树结构，直到找到通往目标状态的有效路径为止，这使得其速度较快，并且能够处理复杂的动态环境。
由于RRT算法的搜索空间是根据随机采样点建立的，因此生成的路径通常不够平滑，更不会对最优路径进行明确的引导，路径的质量在一定程度上受到起始和目标状态之间距离、采样大小和分辨率等因素的影响。S.Karaman和E.Frazzoli [14] 对RRT算法进行了改进，在2011年提出了RRT*算法，它主要改进点是增强搜索图的质量并实现去除不同向树中的冗余路径。与RRT相比，RRT*更关注路径质量，并优化了基础算法，解决了由于点密度不均、采样随机性导致路径不够平滑和存在偏移等问题。侯宇翔 [15] 等通过单元分解的方法将地形图分为可行区域和障碍区域，将随机采样点只选择在相邻的区域，最后再对最终路线进行优化，这样做既缩短了时间又减小了路径长度，从而使算法得到优化。
3.3. 人工势场算法
人工势场算法(Artificial Potential Field, APF)，是一种常见的路径规划算法。于1986年由Khatib [16] 提出。该算法通过在环境中设定虚拟的“势场”来引导无人机沿特定路径移动，其核心思想是将所有障碍物看作各自产生的斥力场，将目标节点和终点看作为有引力的点，运用电荷间的静电力原理模拟带电粒子在势场中的运动轨迹，从而实现避开障碍物、找到最短路径的目标。该算法对大量数据和复杂环境下的应用有着较高的计算效率。与其他规划方法相比，它不需要预先进行图像分割或构造地图，只需考虑目前存在的空间障碍即可。由于其高效性，在实时操作的多次迭代中，人工势场算法可以提供快速、实时的部署方案，适用于需要快速决策并立即执行的自主移动机器人领域。但是由于避障势能效果的限制，人工势场算法会导致出现局部最优解而没有全局最优解。
为有效对人工势场算法存在的问题进行改进优化，众学者提出了很多解决方法。何炳坤 [17] 等通过采用虚拟目标点技术解决了传统人工势场算法的局部最小值问题。李钧泽 [18] 等通过对引力和斥力的改进，成功解决了与远目标端障碍物碰撞和无法到达目标点的问题。同时，引入临时障碍物有效地解决了局部极小值问题。
4. 智能仿生算法
智能仿生算法是近年来被广泛研究的一种无人机路径规划方法。这种方法利用人工智能技术，如神经网络、遗传算法、粒子群算法、蚁群算法、狼群算法和蜂群算法等，来搜索最优路径。这种方法具有一定的鲁棒性和自适应性，但是算法执行效率较低，需要大量的训练数据和计算资源。
4.1. 神经网络算法
神经网络算法是一类基于人工神经网络的机器学习算法 [19] ，其核心思想是将许多简单的神经元连接起来形成具有各种复杂行为的神经网络，并通过调整它们之间的权重和偏置值，使得该网络能够自动拟合数据并完成相关任务。
陈秋莲 [20] 等利用神经网络对障碍环境进行统一建模，实现对障碍的快速探测；利用三次样条曲线对路径进行光滑处理，降低粒子编码维数，从而在保证轨迹准确性的前提下，保证轨迹的精确性，并防止陷入局部极值，从而加快算法的收敛性。
4.2. 遗传算法
遗传算法(Genetic Algorithm, GA)是一种基于自然选择和遗传变异原理的优化算法 [21] 。遗传算法的原理是基于达尔文进化论和自然选择的思想。在解决路径规划问题时其基本原理为：1) 个体编码：在遗传算法中，每个解决方案都被表示为一个染色体，并通过二进制编码进行高效存储和操作。例如，在路径规划问题中，每一个直线段可以通过将其起点、终点及路径中的其他关键点进行编码而表示。2) 初始种群的生成：在算法开始之前，需要初始化一个包含各个染色体的种群。通常需要根据路径规划问题的要求，随机生成多组不同的染色体，并称之为初始种群。3) 适应度函数：用于衡量一个染色体对问题的解决质量。对于路径规划问题，适应度函数通常被定义为机器人从起点到终点的距离(或时间)等评估指标，使得距离较短(或时间较短)的染色体具有更高的适应度。4) 选择操作：选择操作通过保留当前最优的染色体和淘汰掉最劣的染色体来确保下一代中的优秀基因得以传承，经过多次操作可以逐步淘汰不好的染色体，直至最终得到满足要求的较优解。5) 交叉与变异：在选择操作之后，通过染色体的交叉和变异来产生新的染色体，即生成下一代。交叉操作将两个染色体的部分基因相互交换，而变异则通过改变随机基因的值来引入多样性。6) 终止条件的判断：在算法运行过程中，需要根据具体实验进行多轮迭代，即反复执行选择、交叉和变异等步骤。如达到预设的目标或者到达演化次数的要求，可以结束迭代并输出当前的最佳路径信息。
通过上述步骤，遗传算法能够随着迭代次数的增加，逐渐寻找出更加适应和接近问题的解决方案，进而获得可行的路径规划策略。但是遗传算法需要通过多次迭代来寻求优解，对计算资源和时间要求比较高。因此，运行时间较长，往往需要耗费大量的时间和计算资源。且由于遗传算法中的操作为随机性质，可能会导致算法收敛到局部最优解而不是全局最优解，特别是在处理复杂问题时。汤云峰 [22] 等通过在适应度函数中加入惩罚函数并引入精英保留机制(保留每次迭代中的最优个体)的方式提高了摆脱局部最优路径的能力。白云飞 [23] 等则通过将两交换启发交叉算子替换为三交换启发交叉算子的方法减小了运行时间并解决了易陷入局部最优的问题。
4.3. 蚁群算法
蚁群算法(Ant Colony Optimization, ACO)是一种基于模拟蚂蚁觅食行为的优化算法，在组合优化问题中得到了广泛应用。它最初是由意大利学者Marco Dorigo [24] 和Andrea Colorni在1992年提出的。其核心思想是从三个方面来模拟蚂蚁觅食行为，即信息素、启发式信息以及蚂蚁的行动规则。信息素是指蚂蚁在路径上释放的一种化学物质，具有引导其他蚂蚁寻找食物的作用，启发式信息则是通过预测下一步可能到达的位置进行局部搜索，而蚂蚁的行动规则则是按照信息素浓度进行选择。
蚁群算法具有强大的全局搜索能力，它通过信息素的引导和搜索策略的设计，可以进行全局搜索，从而找到问题的全局最优解或者近似最优解。但是也容易陷入局部最优点而无法跳出，尤其在问题的解空间极小或者存在突出的山峰时，更加容易产生此类问题。江明 [25] 等对蚁群算法进行了改进，他调整了初始时信息素的浓度，提高了前期的搜索效率，由于传统蚁群算法中信息素的初始浓度分配是均匀的，所以可能会出现搜索方向与目标点方向相反的情况，从而导致费时且不优。他还加入了避障策略与自适应调整挥发系数，有效地提高了算法的全局搜索能力。Cheng [26] 等人将标准的蚁群算法与模拟退火算法结合起来改进了更新信息素的方法。在高温阶段，增加蚁群算法的搜索空间，防止陷入局部最优；在低温阶段，搜索的多样性和收敛速度之间取得了更好的平衡。Chen [27] 等则是通过在启发式函数中引入A*估值函数的思想用于解决算法容易陷入局部最优、路径过长、转弯过多等问题的。
4.4. 人工蜂群算法
人工蜂群算法(Artificial Bee Colony Algorithm, ABC)是一种启发式优化算法，由Karaboga [28] 小组在2005年提出用于解决优化代数问题。它模拟了蜜蜂觅食和群体行为的过程。ABC算法主要包含三类蜜蜂：雇佣蜜蜂、侦查蜜蜂和观察蜜蜂。每个雇佣蜜蜂负责搜索一个花粉位置，并将该位置信息告知其它雇佣蜜蜂。每个侦查蜜蜂负责在搜索空间中随机选择一个未被探索的位置进行搜索。若该侦查蜜蜂搜索到更优秀的位置，则该侦查蜜蜂“申报”该位置，以便让雇佣蜜蜂去搜索。而观察蜜蜂则负责从已经发现的最优位置中选出一个最优秀的位置。
人工蜂群算法具有全局搜索能力强、鲁棒性高的特点，与其他启发式算法相比，人工蜂群算法还具有快速的收敛速度，可以在较短时间内找到满意的解。但是ABC算法在某些情况下，ABC算法可能会太快地陷入局部最小值，导致搜索停滞不前。且算法中的蜜蜂个体之间需要频繁通信以交流信息，这可能会导致算法的运行效率不如其他算法。李保胜 [29] 等针对该问题对人工蜂群算法进行了优化，首先通过佳点集的方法生成第一代蜜源位置，保证了蜜源信息的多样性和均匀性；然后在采蜂搜索机制中引入自适应动态调整因子，增强了算法前期的全局优化能力和后期的局部搜索能力；最后采用大步长搜索机制增强侦察蜂的优化效果。这使得算法的精度和运行效率都得到了显著的提高。朱金磊 [30] 等将开采次数作为信息交互因子加入到选择概率中来提高选中潜在较优解的概率，结合余弦函数变化特点，对选中的个体进行全局最优个体引导下的自适应局部开发，提升局部开发精度。
5. 无人机路径规划所面临的挑战与未来发展方向
5.1. 面临的挑战
1) 动态环境：无人机常常需要在不断变化的环境中进行飞行，例如城市或其他复杂地形、有可能出现新的障碍物，或者传感器数据突然失效，导致无法准确预测和规划无人机的路径，需要重新计算。这种动态环境很可能会对无人机路径规划造成很大的干扰。
2) 建模要求高：在考虑背景噪声、气象条件、无人机姿态等因素时，无人机执行的任务不可避免地带有一定的不确定性。因此，需要建立可靠的模型和算法来优化无人机路径规划，提高路径规划的准确性和可靠性。无人机的自主飞行和路径规划需要高精度的控制系统和传感器支持，同时需要考虑无人机模型和物理特性等因素。
3) 安全问题：随着无人机应用领域的拓展和无人机数量的增加，无人机与人类、其他飞行物体之间的安全问题变得越来越重要。尤其是在共享空域中，如何引导和规划一组无人机在特定时间和位置执行任务，需要更为精细和考虑到安全因素。
5.2. 未来发展方向
1) 加强多领域融合：无人机路径规划需要与人工智能和大数据等领域进行深度融合，发掘更多的数据和模型来提升路径规划算法的准确性和效率。
2) 无人机路径规划需要加强对无人机模型和环境的感知和理解，例如结合计算机视觉、激光雷达、摄像头、雷达等传感器进行三维环境感知和建模，为路径规划提供更准确的数据支持。
3) 发展动态路径规划技术：未来的无人机飞行任务往往会涉及到动态变化的环境因素，如强风、突发事件等。为了更好地适应这种情况，无人机路径规划技术需要向动态路径规划方向发展，自主调整飞行速度和航线，以更好地应对意外事件。
4) 推进多无人机协同路径规划技术的发展：深入探索无人机间的协调问题，并针对不同任务场景研究相应的协同路径规划方法。例如，在消防救援等场景中，需要多架无人机进行协作作业，此时需要研究用于多台无人机协调路径并及时避免碰撞的算法。
6. 总结
无人机路径规划是无人机应用领域中的一个重要问题，对于无人机的自主飞行和任务执行具有重要意义。无人机路径规划算法的选择和优化需要根据具体应用场景和任务需求进行综合考虑。未来，随着无人机技术的不断发展和应用场景的不断扩展，无人机路径规划也将面临更加复杂和挑战性的问题。因此，我们需要不断探索新的算法和技术，加强对无人机模型和环境的感知和理解，优化无人机的控制系统和传感器等硬件设备，为无人机的自主飞行和任务执行提供更加可靠和智能的支持。
NOTES
*通讯作者。