改进蚁群算法的无人机三维路径规划_孔维立.pdf

引用格式:孔维立，王峰，周平华，等 改进蚁群算法的无人机三维路径规划J 电光与控制，2023,30(3):63-69 KONG W L,WANG F,ZHOU PH,et al Three-dimensional path planning of UAVs based on improved ant colony algorithm J Electronics Optics Control,2023,30(3):63-69改进蚁群算法的无人机三维路径规划孔维立a，王峰a，周平华a，王鹤峰b(太原理工大学，a 信息与计算机学院，山西 晋中030000;b 机械与运载工程学院，太原030000)摘要:针对蚁群算法在无人机三维路径规划问题中存在收敛速度慢和容易陷入局部最优的问题，提出了一种融合改进人工势场的蚁群算法。构造重力势能场，将改进人工势场的合力作为系数对预搜索可行区域内的信息素进行初始化，提出一种随机性信息素挥发因子更新机制，改进蚁群算法的启发函数和信息素更新规则，引入重力势能来模拟无人机高空飞行，并将其应用于信息素的更新。最后设置两组对比实验对比 4 种算法。结果表明，所提算法有效地解决了蚁群算法存在的问题，提高了算法搜索路径的效率和能力，能在不同的环境下最快地收敛到最优值，证明了该算法的适应性和有效性。关键词:无人机;三维环境;改进蚁群算法;启发函数;信息素更新规则中图分类号:TP242文献标志码:Adoi:10 3969/j issn 1671 637X 2023 03 012Three-Dimensional Path Planning of UAVs Based onImproved Ant Colony AlgorithmKONG Weilia,WANG Fenga,ZHOU Pinghuaa,WANG Hefengb(Taiyuan University of Technology,a School of Information and Computer,Jinzhong 030000;b School of Mechanical and Transportation Engineering,Taiyuan 030000,China)Abstract:Aiming at the problems of slow convergence and easy to fall into local optimum in three-dimensional path planning of Unmanned Aerial Vehicles(UAVs),this paper propeses an ant colonyalgorithm with improved artificial potential field,constructs a gravitational potential field,and initializespheromones in the preliminary searchable area with the resultant force of improved artificial potential field asa coefficient A random pheromone volatilization factor updating mechanism is proposed,which improves theheuristic function and pheromone updating rules of ant colony algorithm,introduces gravitational potentialenergy to simulate UAV flying at high altitude,and applies it to pheromone updating Finally,two groupsof comparative experiments are set up to compare the four algorithms The comparison results show that theimproved algorithm can effectively solve the problems existing in the ant colony algorithm,improve theefficiency and ability of the algorithm to search the path,and converge to the optimal value in differentenvironments,which proves the adaptability and effectiveness of the algorithmKey words:UAV;3D environment;improved ant colony algorithm;heuristic function;pheromoneupdate rule0引言随着科学技术的进步，无人机已经广泛应用于军事、工业以及生活等多个领域，路径规划1 2 是无人机执行任务的重要部分。三维路径规划3 是指在一个三维环境中让目标在指定的区域内找到一条距离短、耗能少的安全路径，使无人机可以高效地完成任务。路收稿日期:2022-02-16修回日期:2022-05-16作者简介:孔维立(1997)，男，山西运城人，硕士生。径规划问题的解决是无人机高效、准确、安全完成任务的重要保证，具有广阔的应用前景和研究意义。目前，针对无人机路径规划的问题，国内外学者已经进行了广泛的研究，如今已存在算法主要有遗传算法4、A*算法5、粒子群优化算法6、狼群算法7 和蚁群算法8 等。遗传算法是依据生物进化论提出的算法，搜索能力强，个体的选择随机，但编程复杂，比较依赖初始种群的优劣;A*算法吸取了 Dijkstra 算法9 和贪婪最佳优先搜索算法的优势，但如果存在多个最小第 30 卷第 3 期2023 年 3 月电光与控制Electronics Optics ControlVol 30No 3Mar 2023值，算法将无法保证最后结果为最优。粒子群优化算法是通过种群中个体之间相互合作交流信息的算法，该算法易于实现并且需要调节的参数较少，但是遇到离散化的问题不能达到很好的效果。狼群算法是依据灰狼群抓捕猎物的行为启发而提出的算法，该算法收敛性能强、参数少、容易实现，但搜索能力较弱。蚁群算法是受蚁群觅食行为启发而提出的仿生学算法，该算法采用分布式搜索，算法效率较高，并且易于和其他算法相结合，但是会过早地陷入局部最优，收敛速度较慢。为解决这些问题，文献 10 结合粒子群算法，先通过粒子群算法预搜索路径对信息素进行初始化，之后通过改进蚁群算法进行全局路径搜索，提高搜索能力，使算法收敛加快并且得到了更好的路径，但结果得到的路径拐点比较多;文献 11 将蚁群算法和粒子群算法相融合，将两种算法同时进行演化，得到更优的路径，但算法在理想的环境下进行，适用范围窄;文献 12 改进了全局搜索策略，在启发函数中加入路径偏移系数，降低了搜索复杂空间的难度，提高了算法效率，但其在多算法应用方面需要改进;文献 13 提出自适应调整信息素挥发因子规则，并且引入优质蚂蚁更新策略，但是在动态避障方面有所欠缺;文献 14提出了一种精英扩散蚁群算法，采用精英策略改进信息素浓度公式，加强优质个体对种群的影响以加快算法收敛，但对无人机路径规划选择的空间有所影响;文献 15 引入目标点距离影响因子，改进斥力场函数，同时引入信息素调节系数来降低信息素的干扰，有利于移动机器人快速搜索出最优路径。虽然很多改进算法在路径规划上取得了很好的成效，但是蚁群算法仍存在需要改进的问题。本文针对这些问题，引入了改进的人工势能法，提出一种信息素挥发因子更新机制，设计了新的构造函数，最后通过两组实验，用本文改进蚁群算法与蚁群算法、狼群算法和文献 13 算法进行对比。结果表明，本文算法可以适应不同的环境，且能很快地收敛到最短的路径。1环境建模环境建模是本文仿真实验的基础，仿真无人机飞行应先对其飞行环境进行建模。常用的方法有栅格法16、自由空间法、可视图法等。本文利用栅格法来为无人机的飞行环境建立模型，具体的三维模型如图1 所示。首先以 O 为顶点构造 ABCO A1B1C1O1三维空间，其中，x 轴为无人机横向移动的方向，y 轴为无人机纵向移动的方向，z 轴为垂直于水平面的方向。建立好三维空间后，沿着 y 轴方向对 OO1边进行 S 等分，过一个等分点做一个平行于 AOA1O1的平面，最后可以得到S+1 个平面。之后再利用栅格法对每一个平面进行划分，沿着 x 轴方向对 OA 边进行 m等分，沿着 y 轴 OF边进行 n等分，最后每一个平面可以划分为 m n个栅格，这样就可以得到每一个离散点的坐标值，将这些点集合设为 P。空间中每一个点都有相对应的两个坐标值:等分点序号坐标和空间内具体位置坐标。通过这两个坐标，空间中的任意一个节点都可以用数学方法表示出来，用于后续的仿真与实验。图 1三维模型空间Fig 13D model space2改进蚁群算法2 1初始化信息素由于初始化信息素时，三维空间中的所有节点信息素均相同，会使得蚂蚁在迭代过程中遍历所有点的概率相同，使蚂蚁毫无目标地对地图所有节点进行搜索，大大降低了搜索路径的效率，导致收敛速度变慢，甚至搜索出糟糕的路径。因此本文引入人工势能法，并对其进行改进，通过引入 3 个虚拟势力场对信息素浓度进行初始化。将目标点和障碍物假设为虚拟引力场与虚拟斥力场，对无人机产生引力和斥力;再假设一个虚拟重力势场，使无人机受重力影响。改进后的人工势能法可以很好地适用于模拟无人机飞行状况，使蚂蚁在搜索路径时受到引力、斥力与重力的影响，使其在 3 个力的引导下对目标进行搜索，增强了局部搜索能力。无人机虚拟力场下的受力如图 2 所示。图 2无人机受力图Fig 2UAV force diagram本文通过预搜索，先利用人工势能法融合蚁群算46第 30 卷电光与控制孔维立等:改进蚁群算法的无人机三维路径规划法进行一次迭代，让蚂蚁先对可行区域进行搜索，之后利用人工势能法的合力作为系数，对蚂蚁预搜索得到的可行路径进行信息素浓度增强，作为后续蚂蚁寻找路径的先验知识，其他区域均为初始化信息素基数。这样会使后续蚂蚁依靠先验知识，更倾向于对信息素浓度增强后的路径进行搜索，摒弃了无用的节点，使得蚂蚁在局部搜索时有更高的效率。引力势场函数 Uatt定义为Uatt=12kdD，S(1)式中:k 为引力场尺度系数;dD，S为无人机与目标点之间的距离。无人机所受的引力 Fatt定义为Fatt=grad(Uatt)=kdD，S。(2)斥力势场函数 Urep定义为Urep=12(1L1L0)2LL00L L0(3)式中:为斥力场尺度系数;L 当前节点和斥力场之间的距离;L0为斥力场的最大作用距离。当无人机超出最大作用距离时，无人机将不受斥力影响。无人机所受的斥力 Frep定义为Frep=grad(Urep)=1L1L()021L2LL00L L0。(4)重力势场函数 Ugra定义为Ugra=12gh(5)式中:g 为重力加速度;h 为无人机距地面高度。无人机所受的重力 Fgra定义为Fgra=grad(Ugra)=gh。(6)目标节点所受合力为Fall=Fatt+Frep+Fgra=(1L1L0)21L2 kdD，S ghLL00L L0。(7)将无人机所受的合力作为系数对信息素进行初始化，即x=(1+Fall)0 xR0其他。(8)式中:R 为预搜索可行区域;0为初始化信息素浓度基数，本文所有节点的初始化信息素浓度基数为 1。由于加入预搜索，会使蚂蚁寻找路径之前进行一次迭代，增加了算法的时间复杂度，预搜索的时间复杂度为T(n1)=O(nm2)(9)式中:n