基于改进蚁群算法的无人机三维路径规划研究

温佳霖　梁丰　许雯

摘  要：针对传统蚁群算法（ACO）在无人机三维路径规划中存在的规划路径过长、容易陷入局部最优解和收敛速度慢等问题，提出基于改进蚁群算法的无人机三维路径规划。在传统蚁群算法启发函数中引入高度因子，使蚁群搜索具有方向性。同时将信息素更新系数、信息启发因子、期望启发因子改为根据迭代次数进行动态变化，增加全局搜索能力和跳出局部最优解的能力，加快收敛速度。通过栅格化的方法建立三维路径规划空间，经仿真实验验证了基于改进蚁群算法的无人机三维路径规划的有效性。

关键词：ACO算法；无人机；栅格化；三维路径

中图分类号：V279；V249；TP18 文献标识码：A 文章编号：2096-4706（2023）20-0084-05

Research on UAV 3D Path Planning Based on Improved Ant Colony Algorithm

WEN Jialin， LIANG Feng， XU Wen

（Zhejiang Wanli University， Ningbo  315100， China）

Abstract： Aiming at the problems of traditional ACO algorithm in UAV 3D path planning， such as long planning path， easy falling into local optimal solution， and slow convergence speed， UAV 3D path planning based on improved ant colony algorithm is proposed. This paper introduces a height factor into the heuristic function of traditional ant colony algorithm to make the ant colony search directional. At the same time， the pheromone update coefficient， information heuristic factor， and expected heuristic factor are changed to dynamically change based on the number of iterations， increasing the global search ability and the ability to jump out of local optimal solutions， and accelerating convergence speed. 3D path planning space is established using rasterization method， and the effectiveness of UAV 3D path planning based on improved ant colony algorithm is verified through simulation experiments.

Keywords： ACO algorithm; UAV; rasterization; 3D path

0  引  言

随着人工智能技术的飞速发展，无人机被广泛应用于民用领域（包括地理测绘、农业植保、集群表演等领域）。無人机三维路径规划是指在指定的三维区域内，规划一条使无人机快速安全到达目的地的三维最优路径。

目前，国内外学者在求解路径优化问题时常用的启发式算法有模拟退火算法[1]、蚁群算法[2]、A*算法[3]、遗传算法[4]、粒子群算法[5]等。一般的三维路径规划算法都存在计算过程复杂、无法大量存储信息、不能直接完成全局规划等问题。其中，A*算法的缺点是计算量随着维度的增加而急剧增大，粒子群算法、遗传算法和模拟退火算法只是准三维规划算法。

蚁群算法凭借其优良的适应性和鲁棒性，以及较易于与其他算法相互结合的特点而被广泛应用于无人机三维航迹规划中。同时，蚁群算法存在收敛速度慢、易陷入局部最优解、参数调节困难、规划路径过长的缺点。

基于传统蚁群算法的上述缺点，代婷婷[6]等提出增加最优路径上的信息素浓度，减小最差路径上的信息素浓度，从而提高了算法的收敛速度，但仍未解决易陷入死锁的问题。Sangeetha[7]等将增益算法加入传统蚁群算法中，发现这种做法可以有效地跳出局部最优，算法的收敛速度明显加快，但对于路径最优解的优化并不明显。熊自明[8]等引入偏航角对启发信息进行改进，使蚁群算法能够更加高效地搜索到最优航迹。刘蓉[9]等在蚁群算法中引入混沌机制优化信息素更新方法，将综合代价较小路径上的信息素浓度保留，提高了算法的迭代速度，避免在陷入局部最优的同时又不会错失最优解。张博[10]提出将信息素挥发因子改为高斯分布动态变化指数，以此调节挥发因子的范围。以上研究通过对蚁群算法的改进，解决了算法收敛速度慢的问题，但仍存在复杂环境中算法搜索效率低，容易陷入最优解以及最优路径过长的问题。

本文针对复杂的三维环境及蚁群算法的缺点，进一步对算法进行改进。在启发函数中引入高度因素和安全因素，提高寻找最优路径的能力，引导蚁群搜索方向。同时，提出根据迭代次数动态调整信息素更新系数、信息启发因子、期望启发因子的值，加快算法的收敛速度，提高全局搜索能力，增强算法跳出局部最优解的能力，减小规划路径的长度。最后，通过合理的仿真实验验证了改进遗传算法在无人机三维路径规划中的有效性。

1  三维空间抽象建模

在三维地图中建立抽象三维空间模型的方法如下：将三维地图左下角的顶点作为三维坐标原点A，建立三维空间坐标系A-XYZ，x轴为沿经度增加的方向，y轴为沿纬度增加的方向，z轴为垂直于海平面的方向。设定AB为最大长度，AA1为最大高度，AD为最大宽度。

所构造的三维路径规划空间如图1所示。沿着边AB对空间ABCD-A1B1C1D1进行等分，可以得到n + 1个平面Πi（i = 1，2，…，n），接着对这n + 1个平面沿着AD和AA1的方向分别进行m等分和l等分，结果如图2所示。由此得到（n + 1）×（m + 1）×（l + 1）个小正方体，即将三维空间离散化成一个三维点集合。

在算法中使用分层前进法和栅格平面法相结合的搜索方式。只允许蚂蚁在划分好的栅格间移动，且最大横向移动距离为Ly， max，最大纵向移动距离为Lz， max，以此确定蚁群搜索节点的范围。蚂蚁从起点S出发，前进到第二个平面时，在Ly， max×Lz， max的范围内寻找最优节点，直至到达终点E，如图3所示。

2  蚁群算法的改进

2.1  传统蚁群算法

蚁群算法是模拟蚁群在自然界中寻找食物时，会在它们经过的路径上释放一种名为信息素的激素，能让一定范围内的其他蚂蚁有所感知。当某条路径上经过的蚂蚁越来越多的时候，信息素的浓度会非常高，导致蚁群选择此路径的概率很高，据此提出了基于信息正反馈原理的蚁群算法。

蚁群算法解决优化问题的思路：用单个蚂蚁经过的路径表示优化问题的可行解，整个蚁群的全部经过路径构成优化问题的解空间。较短路径上蚂蚁释放的信息素更多，随着时间的推移，相对较短路径上累积的信息素浓度逐渐升高，从而选择该路径的蚂蚁数量也越来越多。最后，所有蚂蚁会在正反馈的作用下集中在最短的路径上，对应了待优化问题的最优解。

2.2  启发函数改进

启发函数的作用是引导蚂蚁选择最优路径，为了提高算法的效率，加入高度因素以引导蚂蚁的搜索方向。蚂蚁在搜索节点时应该避开障碍物，因此加入避障因素以避免无人机与障碍物相互碰撞。

2.2.1  高度因素

在启发函数中引入高度因素，通过高度因子加强对算法搜索方向的引导。本文将下一个搜索节点与目标点的高度差作为影响启发函数的因子，同时将距离目标点高度较近的节点作为较优选择点，使蚂蚁在高度的选择上也具有方向性。高度因子的计算式为：

2.2.2  避障因素

在三维环境中，会存在障碍物影响无人机路径的情况，为了使蚂蚁在寻找路径时避开障碍物，在启发函数中引入避障因子 。定义三维空间内某节点  的避障因子计算式为：

其中，Num表示此节点搜索区域内所有节点的数量，Unum表示搜索区域内不可达节点的数量。为三维空间模型中的所有节点定义安全值，当节点可达时，安全值赋1，当节点不可达时，安全值赋0。这样可以使蚂蚁在选择路径时有效地避开障碍物，但由于在选择下一个节点时需要对搜索区域内各个节点的安全值进行计算，这就增加了算法的复杂度。因此，需要在建模阶段提前计算好三维空间中各节点的安全值。

2.4  信息素浓度更新系数ρ的改进

在蚁群算法中，信息素浓度是影响蚂蚁搜索的重要因素，信息素位置设定以及更新方式对蚁群寻优具有重大意义。

在三维空间抽象建模中已经将整个搜索空间离散为一个个三维离散点，这些离散点就是蚁群算法进行搜索的节点。因此，针对搜索空间中所有离散点预先设置好一个信息素浓度值，将各离散点信息素浓度值的大小作为对蚂蚁的吸引程度，信息素浓度在每只蚂蚁经过后更新。

信息素全局更新是指在蚂蚁完成一条路径的搜索后，会以该路径长度作为影响值，从路径集合中选出最短的路径，并且增加最短路径中各个节点的信息素浓度。信息素浓度的更新规则如下：

其中，K表示常数，La表示第a只蚂蚁经过的路径长度，ρ表示信息素浓度的更新系数。

更新系数ρ是影响搜索路径上信息素浓度的重要因素之一，当ρ取值过大时，较优路径与其他路径上的信息素浓度有较大差距，缩小了蚁群的搜索范围，使蚁群快速聚集在较优路径上，但容易陷入局部最优。当ρ取值过小时，信息素衰减慢，路径上残留的信息素浓度大，扩大了蚁群的搜索范围，导致算法收敛速度慢。在算法初期搜索中，为较快得到较优解，ρ应取较大值；当算法处于停滞状态时，有可能陷入局部最优解，这时应该减小ρ值，扩大蚁群的搜索范围，便于跳出局部最优解。综合以上分析，ρ取值计算式为：

其中，c表示最优解连续未进化的循环次数，cmax表示常数，ρmin表示ρ的最小取值，限制ρ的最小取值是为了避免ρ过小导致算法性能下降。

2.5  改进蚁群算法步骤

1）建立栅格地图模型，设置蚁群算法的迭代次数、蚂蚁个数、信息素更新系数、信息启发因子、期望启发因子、信息素强度等初始参数。

2）构建解空间。

3）将蚁群放置在起点开始寻找节点。

4）蚁群根据启发函数搜索下一个节点并选择转移节点。

5）对比更新路径。

6）全局信息素更新。

7）判断是否达到最大迭代次数，若达到最大迭代次数则完成路径规划，输出最优路径。反之，则返回步骤4）。

本文最终的算法流程如图4所示。

3  仿真结果与分析

在MATLAB R2020a环境下，搭建无人机三维路径规划仿真环境，在大小为21 km×21 km×2 km的三维空间，设定某些高度的地形为无人机前往目标点的障碍物。规定x轴、y轴方向每个节点的间隔为1 km，z轴方向每个节点的间隔为200 m。路径规划出发点坐标为（1，10，4），目标点为（21，8，6）。设置最大迭代次数N = 300，信息素更新系数ρ = 0.8、ρmin = 0.2、cmax = 10、K = 100，最大横向移动距离Ly， max = 2 km，最大縱向移动距离Lz， max = 2 km。根据上述参数进行三维路径规划仿真。

如圖5所示为传统蚁群算法路径规划图，其中显示的规划路径节点较为分散，且航迹不够平滑。如图6所示为改进蚁群算法的路径规划图，其中显示的规划路径航迹平滑。证明改进的蚁群算法能寻找到更安全、更平滑的路径。图7、图8分别为普通蚁群算法和改进蚁群算法的最佳适应度变化曲线。从图中可以看出，改进后的算法收敛迅速且降低了适应度值（即路径长度），同时能够及时跳出局部最优解，找到更优解，有效解决了传统蚁群算法规划路径过长、容易陷入局部最优解和收敛速度慢的问题。

4  结  论

针对传统蚁群算法中常见的收敛速度慢、较容易陷入局部最优解、参数调节困难、规划路径过长等缺点，本文对三维空间环境下无人机的路径规划问题进行了优化研究。在传统蚁群算法的基础上，通过增加高度因素，使改进蚁群算法中的蚁群搜索更具方向性。对信息素更新系数进行动态调节，有助于蚁群选择出更优的路径。仿真实验结果表明，本文所提出的改进蚁群算法三维路径规划效果较优，路径长度明显缩短，较好地验证了改进蚁群算法在该问题中的有效性及实用性。

参考文献：

[1] 禹建丽，程思雅，孙增圻，等.一种移动机器人三维路径规划优化算法 [J].中南大学学报：自然科学版，2009，40（2）：471-477.

[2] 孔维立，王峰，周平华，等.改进蚁群算法的无人机三维路径规划 [J].电光与控制，2023，30（3）：63-69.

[3] 支琛博，张爱军，杜新阳，等.改进A*算法的移动机器人全局路径规划研究 [J].计算机仿真，2023，40（2）：486-491.

[4] 吕倩，孙宪坤，熊玉洁.改进遗传算法的无人机路径规划 [J].导航定位学报，2020，8（5）：42-48.

[5] 辛守庭，赵冠宇，王晓光，等.基于改进粒子群算法的旋翼无人机三维航迹规划 [J].飞行力学，2022，40（5）：47-52+73.

[6] 代婷婷，朱桂玲，胡晓飞.改进蚁群算法及其应用 [J].洛阳理工学院学报：自然科学版，2021，31（3）：80-84.

[7] SANGEETHA V，RAVICHANDRAN K S，SHEKHAR S，et al. An Intelligent Gain-based Ant Colony Optimisation Method for Path Planning of Unmanned Ground Vehicles [J].Defence Science Journal，2019，69（2）：167-172.

[8] 熊自明，万刚，吴本材.基于改进蚁群算法的无人机低空突防三维航迹规划 [J].电光与控制，2011，18（12）：44-48.

[9] 刘蓉，杨帆，张衡.基于改进混沌蚁群算法的无人机航路规划 [J].指挥信息系统与技术，2018，9（6）：41-48.

[10] 张博.基于改进蚁群算法的无人机航迹规划研究 [D].西安：西安科技大学，2020.

作者简介：温佳霖（1998—），男，汉族，江西赣州人，硕士研究生在读，研究方向：物流信息技术应用。

收稿日期：2023-04-11