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

第 61 卷 第 10 期Vol.61 No.102023 年 10 月October 2023农业装备与车辆工程AGRICULTURAL EQUIPMENT&VEHICLE ENGINEERINGdoi:10.3969/j.issn.1673-3142.2023.10.019基于改进蚁群算法的无人机三维路径规划唐熙，王海宝，罗强（404120 重庆市 重庆三峡学院 智能山地农机技术研究中心）摘要 针对蚁群算法在解决三维航迹规划时运算时间长、局部最优等问题，利用蚁群算法研究无人机在三维环境下的航迹并进行优化。首先，在进行路径搜索时依据起点到终点的距离调整搜索窗口大小以减少算法运行的时间；其次在起始点和终点间可行区域内进行信息素初始化，加快算法的收敛速度；然后，根据无人机工作的最优高度范围改进启发式函数，结合精英蚂蚁信息素更新规则进行信息素更新；最后设置对比实验。结果表明，改进蚁群算法的运行时间更短，收敛速度和生成路径更短，能更好地解决无人机的三维路径规划问题。关键词 蚁群算法；三维模型；路径规划；无人机；启发式函数 中图分类号 V279+.2 文献标志码 A 文章编号 1673-3142(2023)09-0088-05引用格式：唐熙,王海宝,罗强.基于改进蚁群算法的无人机三维路径规划 J.农业装备与车辆工程,2023,61(10):88-92.UAV 3D path planning based on improved ant colony algorithmTANG Xi,WANG Haibao,LUO Qiang(Intelligent Mountain Agricultural Machinery Technology Research Center,Chongqing Three Gorges University,Chongqing 404120,China)Abstract In order to solve the problems of long operation time and local optimality of the ant colony algorithm in 3D trajectory planning,the UAV trajectory in 3D environment was studied and optimized by using the ant colony algorithm.Firstly,the search window size was adjusted according to the distance from the start point to the end point to reduce the running time of the algorithm.Secondly,the convergence speed of the algorithm was accelerated by initializing the pheromone in the feasible region between the start and end points.Then the heuristic function was improved according to the optimal altitude range of the UAVs work,and the pheromone update was performed in combination with the elite ant pheromone update rule.Finally,comparison experiments were set up,and the results showed that the improved ant colony algorithm had shorter running time,convergence speed and generation path,and could solve the UAV 3D path planning problem better.Key words ant colony algorithm;3D model;path planning;UAV;heuristic functions0 引言无人机的路径规划算法是实现无人机自主飞行的重要研究方向。与传统地面机器人相比，无人机在路径规划中不仅要考虑时间和动力学的约束，还要考虑地形可能导致的碰撞1。因此学者们提出了许多三维环境下的路径规划方法，如人工势场法2、萤火虫算法3、RRT 算法4等。蚁群算法是模拟蚂蚁觅食提出的一种算法，被广泛应用于解决旅行商问题5。Huang 等6考虑到无人机在路径规划时的静态威胁和动态威胁，在蚁群算法的基础上为障碍物添加排斥力场，并将斥力作为性能考察指标，改进后的算法能生成更加光滑的低成本路径；Zhang 等7利用插值法对地图进行栅格化处理，根据坡度阈值将三维地图转化为二维地图，利用并行技术加快蚁群算法；袁梦顺等8通过将人工势场法与状态转移策略进行融合，设置了双精英蚂蚁策略，提高了算法的全局搜索能力；刘雨青等9利用 Dijkstra 算法进行信息素初始化，根据不同路径点能量消耗的差异来改进启发式函数，并采用贝塞尔曲线进行平滑处理，规划出的路径较传统蚁群算法能耗比降低了 20%；王飞等10构造了新的启发函数，利用优质蚂蚁更新策略，自适应调整信息素挥发因子，比传统蚁群算法路径长度减少 10%，迭代次数减少了 40%左右，但是时间是传统蚁群算法的 2 倍。本文在现有蚁群算法的基础上以算法运行时间和最优路径长度为优化目标，采用改变搜索窗口大小的方式，根据无人机工作的最优高度范围改进收稿日期：2022-10-2589第 61 卷第 10 期启发式函数，通过 2 组实验对本文改进算法与蚁群算法、王飞等10的算法（下文称算法W）进行比较，并得出结论。1 三维模型建立1.1 三维环境建模首先以 A 为坐标原点建立一个 ABCD-EFGH三维空间坐标系，其中无人机横向移动的方向为 X轴，纵向移动的方向为Y轴，垂直移动方向为Z轴，沿 X 轴方向对 AE 进行 K 次等分，即可获得 K+1 个平面，如图 1 所示。利用地形高程信息中的横纵坐标与 XY 轴坐标对应，将高度信息存储在如式（1）所示矩阵 T 中，则地形高度的顶点在坐标系中可以用（X，Y，Tm，n）表示，连接相邻坐标即可表示整个地图的地形。TTTTTmnmn1111hgjgh=JLKKKKKKKNPOOOOOOO (1)1.2 搜索模式进行路径搜索时采取节点前进方式。无人机起飞点为 Us，目标点为 Ue，沿着 X 轴方向前进。从起始点所在平面 K1开始，探索在 K2平面可行区域内最优的下一节点位置，以此往复，总共探索K 个平面。无人机在一定时间内的最大横移和最大纵移动为 Ymax和 Zmax，则无人机的搜索范围为（2Ymax+1）（2Zmax+1）。搜索范围的大小对算法的运行时间有极大影响，减小搜索范围可以缩短蚁群算法运行时间，但搜索范围太小会导致蚁群算法陷入局部最优。传统蚁群算法搜索范围是一个固定值，缺乏灵活性，本文采用动态调整的方法。开始时，让无人机在一个较大的范围内搜索，在距离目标点一定范围内后，减小搜索范围（如图 2 所示），加快算法运行时间，使整体算法性能达到最优。1.3 距离计算公式在三维空间中，（xi，yi，zi）是蚂蚁当前的坐标，（xj，yj，zj）是下一点的坐标，（xe，ye，ze）为目标点的坐标。蚂蚁从当前点到下一点距离dxxyyzzijjijiji222=-+-+-_hih (2)蚂蚁从当前点到目标点距离dxxyyzzieeieiei222=-+-+-_hih (3)2 改进蚁群算法2.1 启发式函数改进启发式函数是蚁群算法的核心，设计一个符合当前模型的启发式函数能提高蚁群算法的效率。蚂蚁 m 从当前节点到下一个目标点会依据路径上的信息素值和启发式信息计算状态转移概率11，其表达式为 (4)式中：信息素启发因子；期望启发因子；ij启发式信息函数；ij信息素函数。启发式信息函数为 L Sijijijh=(5)LddMijijie=+(6)式中：M距离系数，用于调整距离在启发式函数中的权重。传统蚁群算法仅考虑与下一节点的距离，这样容易导致蚁群陷入局部最优。本文采用当前节点与下一节点和目标点的距离来引导蚂蚁选择距离目标点更近的下一节点，促使其向最优路径方向前进。无人机在空中飞行也会受到地形的影响，如低空突防12、植保作业13会跟随地形进行飞行。之前的三维蚁群算法只是将高度作为一个安全状态看待，无人机飞行高度大于地形高度即为安全，反图 1 三维模型Fig.1 Three-dimensional modelZYCBK1K2GKnKn+1FXEHKDA图 2 搜索模式Fig.2 Search modeK1ZYXYmax=1Ymax=2Kn+12唐熙 等：基于改进蚁群算法的无人机三维路径规划90农业装备与车辆工程 2023 年之为不可飞行区域。但是在无人机实际使用过程中，会存在一个最适工作高度，通过这一特性设置高度适应函数 Sij，让无人机在执行任务过程中在最适高度飞行，以保证无人机有更好的作业条件，具体表达式为SWWdTWWdTWFdTWdTF110minmaxmaxminmaxminminminijzizizizi211GGG=-Z (7)式中：Fmin安全状态下的最小离地高度；Wmax、Wmin无人机最适飞行高度的最大值和最小值；Ti当前位置的地形高度；dz飞行高度。2.2 初始信息素优化蚁群算法在初期的搜索是随机的，初始化的信息素值对其有很大的影响。普通蚁群算法初始化信息素值是开始时设置一个统一的值。统一的信息素值会影响算法的收敛速度，为解决这一问题，在沿起始点到目标点的直线距离范围内的空间设置初始有利区域，该区域中初始信息素值高于其他区域的信息素初始值，表达式为 (8)式中：0信息数初始值；dse起始点到终点的距离；Pdse上在无人机搜索范围内的点集合。沿初始点到目标点设置不均匀的信息素分布14，有利于引导蚂蚁朝着目标点的方向前进，加快收敛速度。2.3 精英蚁群信息素更新信息素更新包括信息素挥发和信息素增强。信息素挥发有利于探索未知区域，避免陷入局部最优，信息素增强是增加路径上的信息素值，加快收敛速度。当蚂蚁在完成节点间探索后，当前节点的信息素会按照设置的信息素衰减系数进行挥发，更新公式为1ijijxg x=-h (9)当蚂蚁完成一条路径的探索后会将本次路径长度与整个蚁群的最短路径进行比较，选出最短路径，在该路径上进行信息素增强，增大后续蚂蚁选择该路径的概率，采用蚁周模型更新信息素，更新公式为1ijijijxt xt xD=-+h (10)min length mNijxD=gh (11)式中：length(m)第 m 只蚂蚁经过的路径长度；信息素系数；N信息素常数。为防止信息素过小，收敛速度慢，信息素过大，陷入局部最优，限定,minmaxij!xxx6。2.4 改进算法流程算法实现步骤：（1）初始环境建模，设定起始点，目标点，设置蚁群数量，最大迭代次数等参数；（2）信息素的初始化，根据式（8）计算初始值，并进行不均匀的信息素分配；（3）蚁群探索。探索路径，根据状态转移概率式（4）求得下一节点，并按照式（9）进行挥发，直到探索完所有节点；（4）判断蚁群是否完成路径探索，是进行步骤 5，否返回步骤 3，直到蚁群完成探索；（5）对所有到达目标点的蚂蚁走过的路径进行信息素更新，并按照式（10）、式（11）增加最短路径各节点的信息素；（6）判断蚁群的迭代次数是否达到设定值，是进行步骤 7，否进行步骤 2，直到完成迭代；（7）输出最优路径长度，算法结束。3 仿真与分析算 法 运 行 环 境 为：处 理 器 为 AMD Ryzen 5800X，内存 16 GB，MATLAB R2021a，采用本文改进蚁群算法、算法 W 和传统蚁群算法进行对比实验，每种算法进行 20 次实验，随机抽取其中 5组作为最终结果，并选择出路径最短的一组对比其迭代次数。蚁群初始参数设置如表 1 所示。表 1 蚁群初始参数Tab.1 Initial parameters of ant colony参数数值最大迭代次数100蚁群数20信息素启发因子1期望启发式因子4挥发系数0.5信息素初始值1信息素衰减系数0.5距离系数203.1 实验 1随机生成一个 20 km20 km2 km 的栅格地图，设置起飞点为（1，11，3），目标点为（21，10，5）。传统蚁群算法、算法 W 和本文改进算法91第 61 卷第 10 期唐熙 等：基于改进蚁群算法的无人机三维路径规划的实验结果分别如图 3图 5 所示，3 种算法最优路径长度如图 6 所示。实验结果见表 2。由图 3图 5 和表 2 可知，本文的改进算法最优路径长度比蚁群算法减少了 19%，比算法 W 减少了 14%；运行时间比蚁群算法减少了 27%，比算法 W 减少了 52%。根据最适高度改进启发式函数后，改进算法寻找的路径更加跟随地形，不均匀的信息素分布加快了算法的收敛速度，在改进算法搜索窗口大小后，算法整体运行的时间也明显减小。表 2 仿真实验结果Tab.2 Simulation experiment results实验编号路径长度/km时间/s传统算法 W本文传统算法 W本文1125.4118.2103.51.893.021.422129.3121.5104.41.952.901.493125.1119.8101.62.202.951.414127.8118.5102.51.892.981.425125.3120.1101.61.882.911.41平均值126.6119.6102.71.962.951.433.2 实验 2为检验算法的通用性，验证其在更加复杂的环境下的性能，采用30 km30 km2 km的栅格地图，设置起飞点为（1，20，5），目标点为（31，19，5）。传统蚁群算法、算法 W 和本文改进算法的实验结果分别如图 7图 9 所示，3 种算法的路径长度与迭代次数对比如图 10 所示。实验结果见表 3。0 20 40 60 80 100 120迭代次数150145140135130125120115110105100路径长度传统蚁群算法 W文本改进算法图 6 最优路径长度迭代次数变化曲线Fig.6 Variation curve of iterations number of optimal path length2 0001 000020 15 10 5m5 10 15 20kmkm图 3 蚁群算法Fig.3 Ant colony algorithm2 0001 000020 15 10 5m5 10 15 20kmkm图 4 算法 WFig.4 Algorithm W图 5 本文改进算法Fig.5 Improved algorithm2 0001 000020 15 10 5m5 10 15 20kmkm图 7 蚁群算法Fig.7 Ant colony algorithm图 8 算法 WFig.8 Algorithm W图 9 本文改进算法Fig.9 Improved algorithm30 25 20 15 10 5 30 25 20 15 10 5 2 0001 0000mkmkm30 25 20 15 10 5 30 25 20 15 10 5 2 0001 0000mkmkm30 25 20 15 10 5 30 25 20 15 10 5 2 0001 0000mkmkm92农业装备与车辆工程 2023 年表 3 仿真实验结果Tab.3 Simulation experiment results实验编号路径长度/km时间/s传统算法 W本文传统算法 W本文1223.2216.0205.12.674.741.892225.2223.9200.62.764.781.843228.7218.6191.52.714.761.894227.5216.1197.02.744.821.925227.1213.2191.72.764.821.93平均值226.3217.6197.22.734.781.89结合图 7图 9 和表 3 可知，本文的改进算法得到的最优路径长度比蚁群算法减少了 13%，比算法 W 减少了 9%；运行时间比蚁群算法减少了31%，比算法W减少了60%。在更加复杂的环境中，本文改进算法依然可以找到最优路径，且所需时间大幅度减少。通过 2 个实验结果可知，改进后的算法在不同环境下都能搜索到最优路径，且所需时间大大减少，证明了改进算法的优越性和可行性。4 总结本文为解决蚁群算法在求解无人机路径规划问题中遇到的运行时间长、局部最优等问题，采用不均匀的初始化信息素，在蚁群搜索过程中改变搜索窗口大小,根据无人机工作的最优工作高度改进启发式函数，对达到目的地最短的蚂蚁进行信息素更新等方法对蚁群算法进行改进。通过 2组对比实验表明，改进后的蚁群算法比传统蚁群算法和算法W最优路径长度更短，运行时间更短。参考文献1 YU Z,SUN F C,LU X,et al.Overview of research on 3D path planning methods for rotor UAVC/2021 International Conference on Electronics,Circuits and Information Engineering(ECIE).Zhengzhou,China:IEEE,2021:368-371.2 邓叶,姜香菊.基于改进人工势场法的四旋翼无人机航迹规划算法 J.传感器与微系统,2021,40(7):130-133.3 UTKARSH GOEL,SHUBHAM VARSHNEY,ANSHUL JAIN,et al.Three dimensional path planning for UAVs in dynamic environment using glow-worm swarm optimizationJ.Procedia Computer Science,2018,133:230-239.4 GUO Y C,LIU X X,LIU X H,et al.FC-RRT*:an improved path planning algorithm for UAV in 3D complex environmentJ.ISPRS International Journal of Geo-Information,2022,11(2):112.5 张松灿,普杰信,司彦娜,等.蚁群算法在移动机器人路径规划中的应用综述 J.计算机工程与应用,2020,56(08):10-19.6 HUANG C X,LAN Y S,LIU Y C,et al.A new dynamic path planning approach for unmanned aerial vehiclesJ.Complexity,2018,2018:1-17.7 ZHANG M,JIANG Z W,WANG L H,et al.Research on parallel ant colony algorithm for 3D terrain path planningM/MOHAMED ALI M S,WAHID H,MOHD SUBHA N A,et al.Modeling,design and simulation of systems:Vol.751.Singapore:Springer Singapore,2017:74-82.8 袁梦顺,陈谋,邵书义,等.基于改进精英蚁群算法的无人机三维航迹规划 J.火力与指挥控制,2022,47(2):37-42.9 刘雨青,向军,曹守启.基于改进蚁群算法的水下自主航行机器人路径规划 J.计算机工程与科学,2022,44(3):536-544.10 王飞,江明.基于一种改进的蚁群算法的移动机器人三维路径规划研究 J.安徽工程大学学报,2019,34(03):43-48.11 李永胜,曲良东,李熹.自适应信息素更新蚁群算法求解 QoS组播路由 J.山东大学学报(工学版),2011,41(4):38-43.12 TISDALE J,KIM Z,HEDRICK J.Autonomous UAV path planning and estimationJ.IEEE Robotics&Automation Magazine,2009,16(2):35-42.13 王宇,陈海涛,李海川.基于引力搜索算法的植保无人机三维路径规划方法 J.农业机械学报,2018,49(02):28-33,21.14 LUO Q,WANG H B,ZHENG Y,et al.Research on path planning of mobile robot based on improved ant colony algorithmJ.Neural Computing and Applications,2020,32(6):1555-1566.作者简介 唐熙（1996-），硕士研究生，主要研究方向：智能算法研究。E-mail：tang_通信作者 罗强，副教授，硕士生导师，主要研究方向：智能机器人。E-mail：547953189 图 10 最优路径长度迭代次数变化曲线Fig.10 Variation curve of iteration number of optimal path length270 260250240230220210200190路径长度0 20 40 60 80 100 120迭代次数传统蚁群算法 W文本改进算法