基于改进精英蚁群算法的无人机三维航迹规划*

袁梦顺，陈 谋，邵书义，吴庆宪，闫 东

（南京航空航天大学自动化学院，南京 211106）

0 引言

随着无人机技术的进步，军用和民用无人机已被广泛应用以完成各种任务，其智能化是目前主要的发展方向之一。航迹规划是无人机智能化进程中的重要部分，也是智能控制与决策方向研究的热点。航迹规划首先需要满足约束条件，然后为无人机规划出符合需求的航迹。在航迹规划问题求解中，常用的搜索算法有A*算法、快速扩展随机树算法、群智能算法和人工势场法。

在航迹规划算法中，群智能算法全局搜索能力较强；人工势场法能够对搜索方向进行引导，且搜索出的航迹能够与障碍物保持安全距离。文献［4］提出了精英蚁群算法，算法中的信息素更新规则采用双精英蚂蚁策略，提升了算法的快速性。文献［5］研究了自适应蚁群算法，将蚂蚁搜索方式调整为局部搜索，减少了不必要节点的搜索。人工势场法在地图中设置障碍物斥力场和目标点引力场，文献［6］利用人工势场法能够为无人机规划出一条与障碍物保持安全距离的航迹。文献［7］提出了附加势场概念，避免了人工势场法陷入局部极值。

与二维航迹规划问题不同，三维航迹规划地图空间大、约束条件复杂，需在算法快速性和航迹代价之间作出取舍，以满足实际应用场景。解决三维航迹规划问题时，文献［8］中的群智能算法由于起始搜索阶段的随机性，搜索时间较长。文献［9］中的人工势场法核心为势场函数，需要合理转换后才能应用于三维栅格地图中。

基于以上研究，为了规划出一条安全、平滑且代价较小的航迹，本文提出了一种基于精英蚁群算法的改进算法，通过引入人工势场中的引力场与斥力场，蚂蚁的邻节点搜索限制，双精英蚂蚁策略，以及信息素扩散模型，加快算法的收敛速度。然后将混沌扰动添加到信息素更新规则中，增强算法的全局搜索能力。此外，为了处理规划出航迹转弯角较多的问题，引入视线算法以平滑航迹。仿真结果表明，本文算法规划出的航迹能够满足无人机飞行期望需求。

1 问题描述

无人机航迹规划首先需要满足基础地图、威胁区域和本身物理条件等限制，随后从起始点开始搜索，规划出可以到达目标点的可飞航迹。规划空间为三维栅格地图，每个栅格在算法中都是一个搜索节点，栅格中心为当前节点的坐标。因此，航迹规划问题可以描述为：在满足约束条件的前提下，从栅格地图节点集合中选择航迹节点，使无人机沿航迹节点飞行时与障碍物保持安全距离，且具有较小的航迹代价。图1 为二维栅格地图中的航迹规划示意图，图中黑色矩形为障碍物，蓝色圆形为威胁区域。

图1 航迹规划示意图

1.1 约束条件设置

在算法搜索过程中，蚂蚁选择的邻节点必须在无人机性能限制范围内，否则不考虑。设置约束条件可以省略不符合约束的邻节点，减少算法运行时间。对于无人机自身性能限制，参考文献［11］中的约束条件，本文主要考虑最大转弯角、最大爬升角、最小相对高度和最远航程约束。对于威胁区域，本文主要考虑导弹威胁区域和天气威胁区域，其中，天气威胁为雷暴和强风等。

1.2 航迹代价函数

在航迹规划中，航迹代价有多种计算公式本文采用的计算公式如下：

式中，表示航迹段的总数，L表示第段航迹的位置变化值，此项计算长度代价。G表示进入第段时转弯角度值，此项计算转弯代价。H表示第段的高度变化值，此项计算高度代价。、和分别为长度代价、转弯代价和高度代价的权重，能够对航迹搜索产生影响，各项权重的取值与实际飞行任务有关。

2 基于改进精英蚁群算法的三维航迹规划

2.1 改进精英蚁群算法基本原理

算法起始时，初始化蚁群数量和迭代次数，蚂蚁从起始点出发，按照轮盘赌规则选择下一节点，不断循环，直至搜索到终点为止。每有一只蚂蚁到达终点，根据式（1）计算航迹代价，随后对各节点的信息素浓度进行调整。完成一次迭代时，对当代蚁群中代价最小的两条航迹进行额外的信息素更新，即双精英蚂蚁策略，该策略可以避免蚁群算法过早收敛。

每次迭代完成后，信息素会同时发生扩散，即在航迹附近栅格扩散信息素，可以使算法更快地搜寻到期望航迹，算法在符合迭代终止条件后，用视线算法对航迹进行全局优化，使航迹更加平滑且代价更小，最后输出满意的航迹。

2.2 三维航迹规划算法具体设计

在应用三维栅格地图进行航迹规划时，邻节点搜索范围为周围的26 个栅格，通过数组索引加减即可访问邻节点。在此基础上，算法设计主要包括4个方面：启发函数、信息素更新、信息素扩散和航迹优化。

2.2.1 启发函数

传统蚁群算法在初始迭代时，蚂蚁搜索节点是随机选择下一节点，算法收敛速度较慢。在栅格地图中，算法搜索出的航迹可能会与障碍物边缘发生碰撞，本文引入人工势场法解决这些问题。

为了使算法快速规划出航迹，首先为目标点设置引力势场，节点的引力场值Att计算公式可表示为

为了使航迹与障碍物保持安全距离，为障碍物设置斥力势场。设障碍物对以其坐标为圆心，半径的球体区域产生斥力，则节点的斥力场值Rep计算公式如下：

综合引力场与斥力场，得到的启发式函数计算公式可描述为

图2 人工势场图

由图2 分析可知，节点在选择下一节点时，倾向于选择斥力场值和引力场值较大的节点，示意图中为斥力场值和引力场值都等于1 的节点。

2.2.2 信息素更新

信息素更新时，航迹节点的信息素会挥发一部分，则节点在（+1）时刻的信息素浓度计算公式为

式中，控制参量，仿真中取=4。

2.2.3 信息素扩散

图3 信息素扩散模型

2.2.4 航迹全局优化

算法中，蚂蚁搜索邻节点时，是以栅格为基础的，所以规划出的航迹中转弯角度为固定角度，且转弯较多，需进行全局优化。在全局优化中，主要运用三维栅格地图中的视线算法，视线算法在两点之间连接一条直线，直线经过的栅格无障碍物，则判定两点是可通视的。利用视线算法，当判断出两节点可通视，且省略两节点之间的多余节点后仍满足无人机约束条件，则将两节点直接相连。航迹优化如图4 所示，点虚线为原航迹，长划虚线为优化后的航迹。

图4 航迹全局优化

2.3 改进精英蚁群算法流程

基于改进精英蚁群算法的三维航迹规划步骤如下：

1）初始化地图、信息素浓度矩阵以及参数；2）对地图中的障碍物构造斥力场；3）将只蚂蚁置于起始点；4）每只蚂蚁通过状态转移策略选择下一节点。在邻节点集合中，蚂蚁会综合考虑引力场、斥力场和信息素浓度信息进行选择。其中，邻节点集合由符合约束条件的邻节点构成；5）所有蚂蚁是否完成搜索，若否，则返回到步骤4），若是，则执行下一步；6）根据蚂蚁搜索到的航迹对地图节点上的信息素浓度进行更新，更新规则中添加了混沌扰动；7）是否符合迭代终止条件，若否，则返回到步骤3），若是，则执行下一步；8）利用视线算法进行航迹全局优化，输出最终航迹。

算法具体流程图如图5 所示。

图5 算法具体流程图

3 仿真结果与分析

为验证算法的有效性，以Windows 10 为平台，Python3.6 语言为编程环境进行仿真，实验的硬件平台为：Intel Core i5 4210M 处理器，主频2.6 GHz，8 GB 内存。在相同硬件平台的条件下，用不同的地图对本文算法进行了验证。同时，为了进一步说明本文算法的作用，进行对比仿真，分析算法的优点和缺点。

3.1 算法仿真结果

仿真中，单个栅格长度、宽度和高度均为100 m。首先在规格为64×64×64 的栅格地图1 中，使用本文算法进行航迹搜索。在地图1 中，山峰1 顶点为（2.05 km，1.85 km，1.15 km），山峰2 顶点为（4.25 km，2.05 km，1.55 km），山峰3 顶点为（3.55 km，4.05 km，2.05 km）。设定无人机的起始点为（0.15 km，0.15 km，0.25 km），目标点为（6.25 km，6.05 km，1.45 km）。规划出的航迹如图6 所示，其中黑色线段表示规划出的无人机航迹。

图6 地图1 规划航迹

在增加威胁区域后的栅格地图2 中，使用本文算法进行航迹搜索。球体威胁区域为导弹威胁，球体威胁区域1 中心为（1.05 km，0.85 km，0.35 km），半径为0.3 km；球体威胁区域2 中心为（1.05 km，3.05 km，0.55 km），半径为0.5 km；球体威胁区域3中心为（3.25 km，0.65 m，0.55 km），半径为0.5 km；球体威胁区域4 中心为（3.25 km，3.35 m，0.85 km），半径为0.3 km。圆柱体威胁区域为天气威胁，圆柱体威胁区域1 平面中心坐标为（4.95 km，5.05 km），半径为0.5 km，高度为2 km，圆柱体威胁区域2 平面中心坐标为（0.95 km，5.35 km），半径为0.5 km，高度为1.5 km。搜索起始点和目标点与之前相同，规划出的航迹如图7 所示。

图7 地图2 规划航迹

改进精英蚁群算法在不同地图中，规划出航迹的各项指标如表1 所示。

从不同地图的可视化结果来看，在图6 中，本文算法规划出的航迹与障碍物能够保持安全距离，且航迹较为平滑。在添加了威胁区域后，图7 中的航迹能够规避威胁区域，航迹较图6 有改变，但是航迹仍旧平滑安全。由表1 中的数据可知，相同规格地图，当地形复杂时，航迹代价和搜索时间都会略有增加。通过不同地图的仿真，在一定时间内均能规划出符合要求的航迹，所以本文算法能够有效解决无人机的航迹规划问题。

表1 不同地图航迹数据

3.2 对比仿真结果

在上述规格为64×64×64 的栅格地图2 中，搜索起始点和目标点与之前相同，用基础蚁群算法、文献［13］中的改进蚁群算法和本文算法进行对比仿真。文献［13］算法规划出的航迹如图8 所示。

图8 文献［13］算法规划航迹

不同算法规划出航迹的各项指标如表2 所示。

表2 不同算法航迹数据

将图8 与本文算法规划的航迹图比较，本文算法规划出的航迹比较平滑，转弯角较少，符合无人机约束条件，效果较好。分析表2 数据可知，基础蚁群算法表现较差，算法搜索时间较长，航迹节点数较多，航迹长度较长。因为基础蚁群算法航迹节点之间必须是相邻栅格，所以航迹节点数众多，且算法中没有对目标点的启发函数，所以搜索时间较长。文献［13］算法搜索时间较短，航迹节点数较多，航迹长度略短，因为算法仅添加了启发函数。本文算法航迹代价最小，航迹节点数明显减少，且搜索时间最短。算法的提升在于以下方面，首先将人工势场法与启发函数结合，添加到转态转移策略中，提升了算法快速性；其次通过双精英策略和信息素扩散，进一步减少搜索时间；同时在信息素更新中加入混沌扰动，增强全局搜索能力；最后利用视线算法进行中间节点的省略，减少了航迹节点数，且降低了航迹代价。

4 结论

本文提出了一种以精英蚁群算法为基础改进的算法，设置斥力场使无人机与障碍物保持安全距离，设置引力场使算法快速规划出期望航迹。在细节方面，设计了算法的启发函数、邻节点搜索、信息素更新、信息素扩散和视线算法。将完成设计的算法应用到三维栅格地图中，最终规划出满意航迹。随后与其他蚁群算法规划出的航迹进行对比，本文算法规划速度较快，航迹平滑，航迹代价小且航迹安全。本文提出的算法为三维静态环境中的航迹规划算法，能够为无人机规划出符合需求的航迹，后续将调整算法中的参数，从而减少算法的运行时间。