基于FA*-AC0 的无人机路径规划方法研究*

韩月明，刘铁林

（1.陆军工程大学石家庄校区，石家庄 050003；2.解放军66389 部队，石家庄 050081）

0 引言

当前，随着科技的发展，无人机凭借其机动性强、成本低、操作方便等特点，能完成目标侦察、精准打击、通信干扰、通信中继等多项任务，在军事领域获得广泛应用，无人机作战运用问题成为各军事强国的研究热点。其中，无人机路径规划技术作为无人机任务决策规划的核心模块，是体现其自主控制与智能化水平的关键，这无疑是无人机作战运用研究的重要方向。

无人机路径规划是根据已知的敌情和地形信息，从出发点到目标点，寻找一条满足无人机飞行性能约束的、生存概率最大、完成任务最佳、综合指标最优的飞行路线。无人机路径规划算法本质上是一个多约束的组合优化算法，主要衡量路径长度、路径光滑程度、路径安全性等性能指标。因此，更多的是考虑无人机自身约束条件，而无人机路径规划并非是简单地通过路径规划算法得到的结果，而是在该结果基础上，进一步考虑无人机作战任务约束，当多无人机路径规划时，还应考虑空间协同、时序协同等约束。因此，本文提出的无人机路径规划方法，主要研究了改进的组合优化算法，并将无人机任务考虑在内，使算法得以最终落地。

传统的路径规划算法主要有模拟退火算法、人工势场法、禁忌搜索算法等，智能优化算法有蚁群算法、遗传算法、粒子群算法、萤火虫算法等［1］。文献［2］将路径规划算法进行了分类，并对各算法的原理及适用条件加以阐述，未提及各自优势及不足；文献［3］通过修改距离启发函数，对蚁群算法进行改进，以提高搜索路径效率，但没有解决蚁群算法过于依赖人工参数选择的问题；文献［4］提出在斥力势场函数中引入相对距离，对原有方法进行改进，但未考虑实际场景中无人机的运行约束；文献［5］利用粒子群算法对蚁群算法的参数进行优化，引导粒子朝着评价指数高的方向收敛，缺点是收敛精度不高，且搜索范围有限；文献［6］提出了一种折射麻雀搜索算法，并在Wilcoxon 秩检验中证明了该算法具有较强的寻优能力，不足之处是算法较为繁琐，运行效率不高。

在上述研究中，有对路径规划算法的直接应用研究，也有针对传统算法进行改进优化。其中，蚁群算法（ant colony optimization，ACO）由于具有鲁棒性、易于实现、正反馈机制、易与其他算法结合等优势，运用最为广泛，但是它也存在着收敛性差、依赖参数选择、容易陷入局部优化等不足，不能适应越来越复杂的路径规划问题。因此，不管是算法的完善还是组合优化，都需要对蚁群算法进行进一步探索和研究。

相比其他算法，萤火虫算法（firefly algorithm，FA）可对ACO 有关核心参数进行优化，从而有效减少ACO 方法受到传统人工经验选择参数的主观影响。此外，考虑到FA 方法存在易于提前陷入局部最优的问题，因此，本文首先引入立方映射混沌算子，采用混沌法，既能保证群体多样性，又能有效防止算法早熟；其次，采用改进的萤火虫算法FA*与ACO 进行组合，得到优化后的核心参数用于路径搜索，并对比仿真条件下不同算法得到的路径规划结果，本文提出的组合优化算法表现出一定优越性；最后，在此算法基础上结合无人机作战任务，提出可用于实战的无人机路径规划方法。

1 基本算法描述

1.1 ACO 算法原理

蚁群算法作为一类启发式的仿生智能算法，主要模仿蚂蚁觅食途中持续释放特有的信息素行为机制，使得后续跟进的蚂蚁依据信息素浓度选择行进路径，经过不断反复循环后，使得更多的蚂蚁源源不断“行走”在相同路径上，从而产生最佳路径。该方法可用于解决无人机为完成目标搜索过程中的最优路径规划问题，算法的主要步骤为：

Step 1 构建工作空间。建立蚁群的搜索空间模型，可以看作许许多多的离散分布的空间点集合，以此成为蚁群算法中各类搜索节点的集聚；

Step 2 对算法参数进行初始化。赋值蚁群算法有关参数：蚂蚁数量、信息素启发值、适应度启发值、信息素衰减系数等［5，7］；

Step 3 路径搜索流程。在蚂蚁由当前点移动至下一点位时，会根据相关路径上信息素浓度值决定某一时刻移动方向。蚂蚁在某一时刻从某一地点选择下一地点的概率可用公式表示为：

式中，αβ 分别代表信息和期望启发因子；蚂蚁k 剩余节点集合用{allowed}表示；代表某一时刻t路径ij 间信息素浓度为启发函数；

Step 4 更新信息素。式（2）和式（3）分别代表局部和全局信息素的更新。在任意一只蚂蚁搜索路径完成后，路径上的局部信息素会得到更新，以此类推，路径上的所有信息素会在全部蚂蚁搜索路径完成后实现彻底更新。

式中，ξ 代表信息素衰减系数。

1.2 ACO 参数分析

1）信息启发式因素α 会在很大程度上影响蚂蚁选择路线的随机性，随着α 不断增大，蚁群在搜索过程中会被其主导，并且伴随随机性不断降低，算法也容易造成局部最优情况；与之相对应，当随机性持续提高，收敛速度会变慢。

2）期望启发式因子β 主要是在环境因素方面影响蚂蚁选择路径概率，当此数值变大后并居于主要地位时，会使得蚁群更加倾向于搜索下一节点位置，此时造成随机性降低，算法也相应陷入局部最优；当这个数值太小的时候，就会导致随机性变大、路径更难找到优值、蚁群收敛将明显变慢［8］。

3）信息素挥发系数ρ 主要是对算法收敛速度和全局搜索能力造成影响，数值越小，蚁群留下信息素浓度消散越慢，进而加强全局搜索能力，降低收敛速度；相反，数值越大，收敛速度加快，也容易限入局部最优。

1.3 FA 算法原理

传统的FA 主要受萤火虫个体吸引与移动的启发。主要原理是：每只萤火虫都是空间的独立点，萤火虫会在飞行过程中不断将发光弱的萤火虫吸引到自身旁边，从而实现一个地点的迭代，以寻找最佳的位置。应用到无人机路径规划中，即在多架无人机执行任务航行过程中，彼此通过信息交互，不断进行态势感知及位置共享，在规避障碍物及敌武器打击的前提下，获取较短路径到达目标位置的无人机通过机间信息发布与广播，使得临近无人机趋于选择相同路径，最终完成最优路径规划。随着战场环境及敌打击火力的变化，无人机在到达目标点位的中间路径在不断调整，即最优路径也在不断迭代和更新变化中，为简化模型，便于解决问题，本文假设无人机在静态障碍物下完成路径规划，不受外界因素的动态干扰。算法的主要步骤如下：

萤火虫的绝对亮度表示其所处位置为潜在的函数目标值，亮度高的萤火虫会吸引亮度低的萤火虫向自己移动，在栅格环境中，可认为从起点到终点移动的栅格数代表目标函数，其值越小，代表绝对亮度越大。将第i 只萤火虫的目标函数值定义为：

式中，t（i）表示第i 只萤火虫从起点到终点移动的栅格数。

绝对亮度公式可定义为：

式中，k 为亮度提取比例，设为常数。

萤火虫相对亮度公式定义为：

式中，β0为r=0 时的吸引力；γ 为光吸收系数；rij为Xi和Xj之间距离，定义为：

2 基于FA＊-ACO 算法的模型构建

2.1 改进的萤火虫算法FA＊

传统萤火虫算法会因为随机初始状态群体的分布不均匀，出现过早陷入局部最优的情况。因此，在对蚁群算法的参数选择进行优化前，先对FA 算法进行改进，主要是在依托原有算法基础上，通过引进立方映射混沌算子，得出全新的混沌萤火虫算法（FA*），在确保群体的多样性特征的同时，防止算法出现早熟。

本文采用立方映射初始化萤火虫种群，立方映射公式表示为：

Step 2 由式（10）进行G-1 次迭代，生成萤火虫位置；

Step 3 由式（11）映射到解搜索空间。

式中，Ud，Ld分别为搜索空间第n 维上界和下界；yid为第i 只萤火虫的第d 维；xid为第i 只萤火虫第d维坐标。

改进萤火虫算法实现过程［10］：

Step 1 设置目标函数f（i），初始化系统参数，设置萤火虫数量n，最大吸引度β0，最大迭代次数g，光吸引系数γ，随机步长因子α；

Step 2 萤火虫位置初始化，用立方映射；

Step 3 仔细比对萤光度，以萤光度最优的萤火虫为基准，更新萤火虫位置使得其移动至基准位置，得到整体优化值；

Step 4 在计算结果符合准确度要求或迭代数达到最大时，进入Step 5，反之，则将返回Step 3；

Step 5 算法终结，将整体的最优位置和个体最优位置输出全部完成。

2.2 基于FA＊-ACO 的模型构建

采用FA* 优化ACO 的关键参数是FA*-ACO的核心思想，该方法将每只萤火虫初始位置对应设置为ACO 的一组重要参数，自主选择一组对应最优参数，进而将传统的经验选参方式进行优化改进。主要步骤：

Step 1 初始化萤火虫算法参数；

Step 2 明确单只萤火虫方位，即在对应的蚁群算法中相关参数；

Step 3 运行蚁群算法，计算出与当前萤火虫各自位置信息相对应的适应度函数值；

Step 4 运用适应度函数，以亮度信息为基础，更新每只萤火虫位置，直至到达更高亮度的个体所在位置；

Step 5 对是否达到终止条件进行判定（以停止更新萤火虫的亮度与位置为依据），并输出此时得到的与萤火虫位置相对应的最优参数；

Step 6 采用Step 5 获得的参数代入蚁群算法运行；

Step 7 最优值输出。

3 仿真实验与结果分析

为验证无人机在路径规划中运用本文提出算法的可行性和优越性，在同一场景下分别通过仿真实验运行传统蚁群算法、文献［3］中提出的改进蚁群算法、文献［5］中提出的粒子群- 蚁群算法以及本文提出的萤火虫-蚁群算法，并对所得结果进行对比分析。算法运行环境为：Windows7 64 bit；Matlab 2014。

3.1 环境建模

无人机运动环境模型一般采用栅格法建模。如图1 所示，建立栅格序号1～400、大小为20×20 的栅格图形，并按照自上而下、由左向右依次进行编号。假设白色方格表示无障碍，代表能够自由通行、黑色方格代表受到阻碍，无人机需绕过障碍物飞行。坐标以左下方为原点，从左到右为x 轴正方向，从下到上为轴正方向，每块栅格i 均对应着其在二维空间中的坐标（xi，yi），栅格坐标与序号的关系可表示为：

图1 栅格环境Fig.1 Grid Environment

式中，i 为栅格号；N 为栅格数，ceil 代表取整，mod代表取余。

3.2 算法参数设置

表1 FA 初始化参数Table 1 FA initialization parameters

表2 ACO 参数取值Table 2 ACO parameter values

表3 是引入改进萤火虫算法后得到的优化蚁群算法参数。

3.3 10×10 仿真环境

为增加对比性，分析本文算法有效性，分别做了以下几组的对比实验。假设4 种算法的迭代次数最多为80 次，蚁群数量最多为50 个。随机设置飞行空间内的障碍物分布，在相同栅格环境下，分别运行4 种算法处理无人机路径规划问题，得到各自最优路径如图2 所示（在本文仿真实验中定义的最优解为路径长度最短且转弯次数尽量少的路径），上述4 种算法均在实现对障碍物的有效规避基础上，抵达所设置的最终目标方位。

图2 10×10 仿真环境下4 种算法路径规划结果Fig.2 Path planning results of four kinds of algorithms in a 10×10 simulation environment

各算法的收敛曲线如图3 所示。算法分别从最优路径长度、迭代次数、运行时间上进行比较，如表4 所示。结果表明本文算法与其他算法相比全局搜索能力得到改进，收敛速度有所提高。

表4 10×10 仿真环境下结果对比Table 4 Comparison of results in a 10×10 simulation environment

图3 10×10 仿真环境下4 种算法收敛曲线Fig.3 Convergence curves of four kinds of algorithms in a 10×10 simulation environment

由图3 可知，文献［3，5］和本文所提算法在最优路径长度上，相比传统蚁群算法分别减少8.72%、10.21%和12.87%；在迭代次数上，文献［3，5］和本文所提算法相比传统蚁群算法分别减少18.18%、31.82%和45.45%；在运行时间上，文献［3，5］和本文所提算法相比传统蚁群算法分别减少5.36%、14.09%和28.47%。

传统蚁群算法在迭代第22 次时，得到的路径长度为23.546，在算法初期存在盲目搜索，收敛速度较慢，且陷入局部最优；文献［3］将算法引入改进距离启发因子后，收敛速度有所提升，在迭代第18次时得到的路径长度为21.492，跳出局部最优能力加强，但全局搜索能力不足；文献［5］对蚁群算法的参数进行了优化，相较传统蚁群算法和文献［3］所提算法，上下波动的幅度在随着迭代次数不断减小，说明粒子位置在不断接近群体最优，与传统蚁群算法相比跳出局部最优能力加强，但算法加快收敛的同时，对全局搜索能力减弱，在迭代第15 次时得到的路径长度为21.142；本文所提算法在萤火虫位置初始化的过程中采用混沌方式，有效保证了种群多样性，且收敛速度更快，算法平稳性更高，平均路径长度更短，在提高全局搜索能力和跳出局部最优解的能力更强，在迭代第12 次时，得到最短路径为20.516。

为了对比在复杂环境下4 种算法的差异，本文设置30×30 的仿真环境进行路径规划仿真实验。4种仿真算法的路径规划结果如下页图4 所示，通过对比分析发现，就路径平滑度和路径长度而言，传统蚁群算法得出的结果不够理想，过早陷入局部最优解，文献［3，5］规划的路径起伏较大，中间出现多个折点，按此路径规划结果用于无人机实际飞行中，不仅使整体路径变长，且中间需进行多次转向偏移，无人机需要不时调整航向角和转弯角，这给无人机的飞行性能和安全控制带来较大挑战，不利于无人机高效、平稳完成作战任务。相比之下，本文提出的FA*-ACO 算法所规划的路径长度最短，且在偏差度上更小、路径平滑度更好，减少了许多波峰波谷、转折转弯，更加利于无人机在航行过程中的航向控制与安全稳定。上述算法的全部收敛曲线分别拟合成趋势曲线，如图5 所示。

图4 30×30 仿真环境下4 种算法路径规划结果Fig.4 Path planning results of four kinds of algorithms in a 30×30 simulation environment

图5 30×30 仿真环境下4 种算法收敛曲线Fig.5 Convergence curves of four kinds of algorithms in a 30×30 simulation environment

由图5 可以看出，在复杂环境下，本文改进算法搜索到的路径相比于其他3 种算法搜索到的路径较优，且收敛速度较快。由表5 可以看出，传统蚁群算法用了49 次迭代收敛到52.289，不足之处在于收敛速度较慢，易陷入局部最优，在多次迭代后趋于稳定的最优路径长度仍然要长于其他算法。文献［3］用了38 次迭代收敛到54.973，得到的最优路径稍短，收敛性也有所提高，但未能跳出局部最优解，且这种情况在复杂环境下表现得更明显；文献［5］用了32 次迭代收敛到52.156，使蚁群算法在初期较易落入局部极值且后期收敛速度缓慢的问题得到了改善，但本文改进的FA*-ACO 算法只用了26 次迭代便收敛于最优路径49.127，较文献［5］而言，本文算法在最优路径和迭代次数上分别减少了5.8%和18.75%，在算法运行时间上，本文算法与传统蚁群算法相比表现出明显优越性，稍微优于文献［3］和文献［5］。综上，本文算法可以提高收敛速度，而且在改善解的质量方面也取得了较好的效果，提高了在全局搜索空间的遍历性和收敛速率，避免陷入局部最优解，但本文算法在收敛后期出现了在最优值附近短暂震荡的情况，说明该方法在解决复杂环境下的路径规划问题时的求解效率和求解精度还有进一步优化的空间。

表5 30×30 仿真环境下结果对比Table 5 Comparison of results in a 30×30 simulation environment

4 基于任务的无人机路径规划调整策略

本文在研究路径规划算法中定义的最优解为路径长度最短，转弯次数最少的路径。实际作战中，不论是单架无人机独立完成任务，还是多架无人机协同作战，在无人机规划路径的选择上，仅靠优化算法获取的最短路径并非是实际上的最优解，即并不一定是能达到作战最佳效费比的最终选择。这是因为在作战过程中，指挥者不仅要考虑无人机完成任务的路径最短，以降低油耗和缩短任务时间，更重要的是要结合战场态势信息，把握好无人机进入战场的时机，尤其是多无人机路径规划中，首要考虑各无人机所需完成任务的紧急程度，力求既满足团队协同高效的要求，又使整体生存概率最高。此外，当无人机数量较多且面临复杂环境的时候，对于编队中的无人机个体来说，有可能规划出数条相同或交叉的路径，且有相同的时间要求，为避免发生碰撞，结合无人机执行任务的重要程度、时间约束等设置“通行规则”，如表6 所示，用以解决可能产生的碰撞冲突问题，弥补算法的不足。在此之前，先按照每架无人机执行任务的紧要程度以及时间约束条件进行编号，任务越紧急则序号越靠前。

表6 多无人机路径通行规则Table 6 Path passage rules of multiple UAVs

5 结论

本文对改进后的萤火虫算法和蚁群算法进行组合优化，目的是让组合算法的搜索性能有所提升，并进一步应用于无人机路径规划和寻优，避免蚁群算法中过于依赖参数选择和萤火虫算法易早熟的问题，实验结果对所提算法的可行性和优越性进行了验证。在下步工作中，还需要进一步改进组合算法的求解效率和精度，同时考虑三维环境下动态障碍因素影响等问题。