改进蚁群算法的无人机航迹规划

王 瑶, 任安虎, 任洋洋

(西安工业大学电子信息工程学院,西安 710000)

0 引言

无人机航迹规划需要考虑多方面的因素,包括环境信息、任务目标等限制条件[1],以确保无人机能够高效地完成任务。这些因素之间相互作用,需要在规划过程中进行综合考虑和权衡,从而确定最优的航迹方案。目前,常见的航迹规划算法有粒子群算法[2]、遗传算法[3]、神经网络算法[4]、人工势场法[5]、蚁群算法[6]、A*算法[7]等。1991年,由DORIGO等[8]提出的蚁群算法相比于其他航迹规划算法,具备高效的全局搜索能力、良好的正向反馈机制、较强的鲁棒性以及实现简单[9]等优点。但是在进行航迹规划时该算法具有易陷入局部最优解、收敛速度较慢,容易造成航线质量差以及规划时间长等缺点。

针对蚁群算法的不足,研究者们进行了不同的改进。文献[10]融合改进人工势场法对模拟地图进行预搜索并引入重力势能模拟无人机的高空飞行,提出新的信息素挥发因子更新规则,提高了算法的随机性。但是由于引入预先探索和信息素浓度更新的策略,增加了搜索的时间成本,从而降低了算法的搜索效率。为了提高算法的搜索效率,文献[11]采用改进局部搜索策略的方法,调整初始信息素的因子,并在启发函数中引入路径偏移因子,从而增强了算法在全局搜索方面的能力。但航迹规划面对的环境具有复杂和多变的特征,在实际应用中,依靠单一算法很难达到预期的结果。文献[12]改进了蚁群算法中信息素的更新规则,并将其与遗传算法进行融合。融合方案获得的路径长度比遗传算法和蚁群算法的都要短。针对蚁群算法收敛性差的问题,文献[13]在传统蚁群算法的基础上引入了目标节点信息素的引导因子,以引导蚂蚁朝着目标节点进行搜索,从而降低搜索的盲目性。同时,还采用了再激励学习机制更新信息素,使得算法具有更快的收敛速度及更好的搜索效果。

从以上的改进可以看出,研究者们都致力于使算法具有更快的收敛速度,让无人机能够在最短的时间内到达目标位置。基于以上启发,本文提出一种改进的启发式蚁群算法,该算法在保留了传统蚁群算法的基本框架和优点下,通过进行初始信息素不均衡分配、优化状态转移规则以及动态调整信息素挥发系数,有效避免了蚁群算法易陷入局部最优及收敛速度慢等问题。

1 无人机航迹规划建模

1.1 二维环境建模

1.1.1 模型简化

航迹规划是为了确保无人机在执行任务时能够按照规定的路径安全、高效地飞行。在这个过程中,无人机应该是在三维环境中执行飞行任务,但是,当无人机在执行某些特定的任务时,不需要考虑高度的变化,只需保持在固定的飞行高度。因此,可以将航迹规划问题从三维空间转化为二维平面,以简化计算和优化航迹规划过程。本文对无人机在高速公路上穿越地形障碍,躲避禁飞区域进行航迹规划,将无人机的飞行环境做如下简化和假设[14]:1) 简化模型,将无人机简化为质点;2) 假设无人机在执行任务时,需要在规定的二维平面中保持固定的飞行高度和速度,并按照预设的航迹路线进行移动;3) 假设地形障碍,禁飞区域已知,在进行环境建模时用黑色代表地形障碍以及禁飞区。

1.1.2 建模

航迹规划中常见的二维环境建模方法有可视图法[15]、Voronoi图法[16]和栅格图法[17]。栅格图法与其他两种方法相比,在构建环境模型时方法简单且易于修改。此外,栅格法具有良好的适应性,并且易于计算机存储和处理。故本文采用栅格图法建立二维空间模型。

构建图1所示20×20的二维空间模型,0表示可通行的区域(即白色网格单元),1表示障碍物(即黑色网格单元)。

图1 二维空间模型

1.2 三维环境建模

为了使研究结果更具有现实意义,不仅要在二维环境中对算法进行对比验证,还应该在三维环境中进行仿真实验。本文采用栅格化的方法对三维环境进行建模,首先将三维空间切片分层处理,然后再将每个切片划分为若干个栅格。这种栅格化方法可以提高路径规划的效率和精度,同时减少无人机的碰撞风险。

三维空间划分如图2所示。

图2 三维空间划分

首先建立三维直角坐标系O-XYZ。在三维直角坐标系中构造一个立体空间ABCD-EFGH,该立体空间的底面为ABCD,顶面为EFGH,表示无人机飞行的最高高度,其中,AB和AD的长度分别等于飞行空间的长度和宽度。将该立体空间沿着高度方向(Z轴)划分为l个切片平面,接着,将l个切片平面划分为m×n个栅格,从而将规划空间划分为n×m×l个栅格。

2 蚁群算法

2.1 转移概率公式

在蚁群算法模型中,蚂蚁根据状态转移公式选择下一个可行的节点,状态转移表示为

(1)

(2)

式中,dij为2个节点之间的欧氏距离。当距离越小时,启发函数所提供的信息越详尽丰富,即启发信息量越大。距离与启发信息量之间呈现反比例关系。

2.2 信息素更新规则

信息素更新规则表示为

(3)

(4)

式中:Q为信息素强度,是一个固定的常量,用于控制信息素增强的速度和程度;Lk为第k只蚂蚁在一次循环中走过的总路径长度。

3 改进蚁群算法

3.1 初始信息素浓度不均衡分配

在传统蚁群算法中,初始信息素分布通常是均匀的,这意味着所有路径上的信息素浓度都相等,这种情况下搜索初期所有路径的被选择概率相同,不利于算法搜索的多样性,而且存在一定盲目性。为了加快算法的寻优能力,本文采用有针对性的不均衡分配信息素的策略。利用A*算法快速的全局规划能力且便于和其他算法相结合的优势,首先利用A*算法规划出一条较优路径,使该条路径上的信息素浓度高于其他路径,避免初期搜索的盲目性。

3.2 状态转移规则的改进

无人机在飞行过程中,不仅要在最短时间内到达目的地,还要保证其飞行距离最短。在初始路径搜索阶段,每条路径上经过的蚂蚁数量较少,蚂蚁在选择下一节点时倾向于随机选择,为了防止蚂蚁在搜索过程中选择与目的地相反的方向从而影响算法的收敛速度,本文引入了一种启发式因子δij(t),即

(5)

式中,θ(0≤θ≤π)为目标的倾斜角度,表示蚂蚁从当前位置到下一节点与当前位置到目标点连线之间位移的夹角。改进后的状态转移概率表示为

(6)

式中,γ为启发式因子的重要程度。当θ较小时,δij(t)较大,状态转移概率就越大,蚂蚁选择该路径的概率就越大。

3.3 信息素挥发因子优化

传统蚁群算法在寻优过程中,其信息素挥发系数ρ通常是一个定值,但是蚁群算法的寻优过程是一个正反馈的循序渐进的过程,定量的挥发信息素满足不了这一动态过程的需求,而且蚁群算法本身容易陷入局部最优,因此,为了避免算法陷入局部最优的同时提高算法的收敛速度,本文引入高斯函数设计了一种信息素挥发系数的调整策略,表示为

(7)

(8)

式中:i为当前迭代次数;imax为最大迭代次数;ε>1,为信息素衰减系数。信息素挥发系数的调整策略是在搜索开始时具有较大的ρ,增加了算法的全局搜索能力,避免了算法过早陷入局部最优。随着迭代次数的增加,ρ在后期迅速下降,局部搜索能力变得更强,有助于蚂蚁找到最优路径。改进后的信息素挥发因子可以根据搜索进行的不同程度,动态地调整信息素挥发系数的大小,提高了算法的性能,增加了蚁群算法的鲁棒性。

3.4 算法步骤

改进蚁群算法的航迹规划步骤如下。

1) 环境建模。建立二维和三维环境模型,设置无人机的起始点和目标点。

2) 设定初始的蚂蚁系统和相关参数。设置蚂蚁数量m,确定信息素权重因子α,确定启发权重因子β,全局信息素挥发系数ρ以及信息素强度Q等相关参数。

3) 利用A*算法规划出一条较优路径,使得初始的信息素分布不均匀。

4) 将m只蚂蚁放在起始位置上,开始进行路径搜索。

5) 选择下一个节点。根据式(2)计算启发式信息量,根据式(6)计算转移概率,选择下一个可行的节点。

6) 当所有蚂蚁完成一次迭代之后,根据式(7)调整信息素挥发系数,然后根据式(3)更新信息素含量,否则返回执行步骤5)。

7) 判断是否满足收敛条件,如果满足,则退出并输出最终结果,否则返回执行步骤3)。

4 仿真实验与结果分析

4.1 实验环境

本仿真实验运行在一台搭载有Intel Core i7-6600U处理器、主频为2.60 GHz、内存为8.00 GiB的计算机上。

4.2 参数设置

为保证仿真结果的准确性,参与对比的算法均在相同的参数下进行仿真测试,初始参数值设置如表1所示。

表1 参数设置

4.3 仿真实验结果分析

为了验证本文改进蚁群算法在无人机航迹规划问题中的可行性,本文分别在二维环境和三维环境下对传统蚁群算法、本文算法、传统A*算法、文献[7]算法进行仿真实验来评估改进蚁群算法的性能。

4.3.1 二维环境仿真实验分析

二维环境下仿真结果如图3所示。

图3 二维环境下仿真结果

对于二维环境模型,4种算法的性能评估如表2所示。

表2 4种算法性能评估(二维环境)

上述实验是在障碍物较多的20×20的栅格地图中进行的。从图3(a)和图3(b)可以看出,传统蚁群算法的收敛过程不稳定,所规划的航迹出现了较多的转弯和拐点,导致无人机频繁地变更方向,增加了油耗和飞行时间,从而影响飞行效率;另外,拐点的出现也表明当全局搜索空间增大时,传统蚁群算法的性能容易受到局部最优解的影响。

从图3(c)和图3(d)可以看出,改进后的蚁群算法可以减少航迹上的拐点和转弯,使得飞行路线更加顺畅和自然;而且本文算法在第12代就收敛得到最优解,相比于传统蚁群算法能够快速地向最优解靠近,算法的收敛速度得到了提升。从表2的仿真结果数据可以看出,本文算法航迹长度较传统蚁群算法缩短了12.05%,较传统A*算法缩短了9.29%,较文献[7]算法缩短了3.64%;同时,与其他3种算法相比本文算法的拐点数目相对较少,得到的航迹更平滑。综上所述,本文所提算法有效提升了航迹规划的效果。

4.3.2 三维环境仿真实验分析

无人机的初始位置坐标为(1 km,1 km,1 m),终点位置坐标为(100 km,100 km,60 m)。三维环境下仿真结果如图4所示。

图4 三维环境下的仿真结果

对于三维环境模型,4种算法的性能评估如表3所示。

表3 4种算法性能评估(三维环境)

从图4(b)和图4(d)可以看出,在三维空间环境模型中,传统蚁群算法在第36代左右得到最优解,而本文算法在第4代就收敛得到最优解,收敛速度提升了88.89%。从表3的数据可以看到,本文算法航迹长度比传统蚁群算法缩短了6.42%,比传统A*算法缩短了6.16%,比文献[7]算法缩短了1.39%。由此可知,本文所提的改进算法可以有效提高蚁群算法的性能,在保证快速收敛的前提下,算法的搜索能力以及寻找最优解的能力都得到提升,有效解决了其他算法收敛速度慢、易陷入局部最优的问题。

5 结束语

基于传统蚁群算法提出一种改进的蚁群算法,旨在解决传统蚁群算法容易受限于局部最优、收敛速度缓慢等问题。通过对初始信息素进行不均衡分配、状态转移规则以及信息素挥发因子的优化,进行二维环境和三维环境的仿真实验,实验结果表明,改进后的算法在搜索过程中能够克服传统蚁群算法在局部最优解附近停滞的问题,能够更加全面地搜索解空间,具有更快的收敛速度,可以有效避免算法陷入局部最优。本文的研究主要是在静态环境下进行的,在接下来的工作中可以将优化算法拓展应用到动态环境中。