基于改进蚁群算法的网格空间航迹规划

邱 诚，黄大庆，王浩雪，刘耀辉

（1.南京航空航天大学电子信息工程学院，江苏南京 210016；2.南京航空航天大学中小型无人机先进技术工信部重点实验室，江苏南京 210016）

近年来，各种无人机的使用、服务需求正在持续快速增长。在对抗新冠肺炎期间，无人机就被用于医疗物资投递、空中巡逻督查等方面。空间网格模型可用于实现无人机群飞行空间的数字表示、环境信息的预存储和空间属性的高效查询。无人机完成任务的前提是进行合理的航迹规划，在空间网格模型的基础上进行无人机的航迹规划更加符合信息化时代的需求[1]。

目前有多种算法被国内外学者用于无人机的最佳航迹求解，如文献[2]将启发算法与遗传算法结合，实现无人机路径的重规划；文献[3]用一种自适应粒子群优化算法进行路径规划；文献[4]基于人工势场，利用最优控制方法求解路径规划；文献[5]对蚁群算法进行改进，用来建立无人机低空航路网。其中，蚁群算法因为鲁棒性较强且具有正反馈机制，在无人机航迹规划的研究中受到广泛关注。在对蚁群算法的研究中，文献[6]进一步完善了算法的状态转移函数，并引入了信息素调节因子，以防止后期陷入局部最优；文献[7]在融合遗传算法的基础上改进信息素机制；文献[8]为克服蚁群算法在计算后期易陷入局部最优的问题，提出了混沌式搜索策略。但是，上述相关研究未考虑空域的实时性问题，在实际应用中，空域应当被赋予时间属性。

文中在传统飞行环境建模的基础上提出了新的蚁群算法改进策略，在搜索开始前通过信息素初始化规则，先初始化全局信息素，减少算法初期盲目搜索导致收敛速度慢的问题；通过部分次优解和最优解的交集对优质节点进行信息素强化，提升算法的全局寻优能力以及收敛速度；提出关联时间的空域网格化建模，使其更加符合实际需求。

1 空域网格化

1.1 空域网格化的基本概念及方法

空间地理剖分的思想早已有之，可追溯到夏商周时期出现的“井田制”，该土地管理制度根据道路、渠道将土地分隔成方块，体现了古老的空间剖分思想，是现代城市网格划分思想的鼻祖。人类对大区域空间的管理，习惯于网格式的“粒子化”分隔管理方式，各种典型的信息管理网格包括行政管理网格、环境监测管理网格、战场网格、有限元计算网格等。

基于空间信息剖分的思想，将空域进行网格化管理，划分成若干大小一致、相互链接的基本空域单元，建立空域四维时空框架。如图1-2 所示，每个网格单元G（Index,Time,Property）被用于组织空域中的各类数据，其中，Index 为网格单元空间编码，用于存储空间位置信息；Time 为时间戳；Property 为属性集合。空域网格化的核心是将物理的空域空间通过空间规则剖分后，利用矩阵空间管理空中交通的几何结构和空域结构，利用空域剖分建立唯一的全球地址码，以地址码作为主键索引各网格内的数据。

图1 空域四维时空框架的虚拟结构

目前有三类主要方法被用于构建全球平面网格，分别是经纬网格、正多面体网格和自适应网格。

1.2 GeoSOT网格

图2 空域网格划分核心内容

文中使用的网格化方法是一种空天地一体化的地球空间参考网格体系——全球经纬度剖分网格[9]（Geo-graphic coordinate Subdivision grid with One dimension integer coding on 2n-Tree,GeoSOT），该方法采用经纬度进行地球剖分，是经纬网格的一种。其设想的核心是对地球经纬度空间实行三次扩展（将地球及其邻近空间的经纬度范围扩展至512°×512°，将1°扩展为64＇，将1＇扩展为64″），将地球空间分割为一个个整度、整分、整秒的网格，最高一级包含整个地球空间，最小可以划分至厘米级，共32 级剖分，可根据实际需要选择合适的剖分层级进行研究。例如文献[10]针对战场空域表征需要，选取了最大512 km、最小128 m 共七级网格进行战场空域表征；文献[11]分析了GeoSOT 网格应用在无人机碰撞检测上的可行性，发现64 m 网格用于无人机碰撞检测的计算时间最少。

2 蚁群算法及改进策略

2.1 飞行环境模型建立

在传统的基于蚁群算法的无人机航迹规划研究中，通过建立栅格图的形式建立了无人机的航行环境模型[12-16]。如图3 所示，研究中往往简单地将黑色网格看作无法飞越的障碍网格，将白色网格看作可供航行的自由网格，从而忽略了低空环境随时间的变化，导致规划的路径不够科学、合理。

图3 飞行环境模型

基于空间信息剖分的思想，文中将飞行环境模型改进为关联了时间属性的网格化空域，选取GeoSOT中第16 级1 km×1 km 网格建立模型，每个网格除位置信息外，还对应一个时间信息，即若该网格存在障碍物，则网格关联一个障碍物存在的时间，在该时间范围外该网格依旧可以视为自由网格。

2.2 蚁群算法

蚁群算法(Ant Colony Optimization，ACO)的思想源自于蚁群觅食的过程。在觅食初期，所有蚂蚁均等概率地选定能够获取到食物的路线，信息素随着蚂蚁寻找的过程被释放在蚂蚁走过的路线上，该信息素可以指导后来的蚂蚁作出路线抉择，同时路线上的信息素含量也会随着时间衰减。同样时间内，相较于其他路径而言，较短路线上的信息素含量会累积得更高，而由于蚂蚁在路线选择中偏向于挑选信息素含量高的路线，基于正反馈作用，信息素含量较高的较短路线被更多的蚂蚁选择，其信息素含量也因此越来越高。由于信息素的挥发，较短路线上的信息素含量远高于其他路线时，所有蚂蚁倾向于选择该路径，认为该路径为最短路径。

2.2.1 状态转移函数

在蚁群算法中，蚁群根据状态转移函数选择下一个路径点，状态转移函数表示如下：

2.2.2 信息素更新机制

蚁群算法中的信息素更新机制如下：

式中，ρ为信息素蒸发系数；τij(t)为当前信息素含量；Δτij(t)为信息素增量计算如下：

2.3 改进策略

传统蚁群算法存在以下缺点：①蚁群在路径规划初期搜索存在盲目性，收敛速度慢，搜索时间长；②在某次迭代中，一只蚂蚁可能发现了最优解，但由于次优解路径上信息素已经积累较多，导致最优解与次优解之间信息素含量存在差距，算法无法收敛于最优解而陷于局部最优。

针对以上两个缺点，提出改进策略。首先，对于图3 已知起始点的环境模型，初始化全局信息素，加快算法初期搜索效率，更新规则为：

式中，MM 为栅格环境的列数；p为定值，为初始化信息素量；τij为由第i个栅格到第j个栅格之间的信息素量。

其次，提出改进的信息素更新机制，如下：

式中，Δτbetter(t)表示在此次迭代中所搜寻路线长度最短的五只蚂蚁在路径(i,j)上释放的额外信息素总量；为此次迭代中，搜寻路径最短的五只蚂蚁中第m只蚂蚁在路径(i,j)上释放的额外信息素量；为搜寻路径最短的第m只蚂蚁搜索到的路径长度；Lbest为当前历史最短路径长度；ω为一常数，用于控制次优解释放额外信息素量的大小。

改进的信息素更新机制将一代蚂蚁搜索路径长度排序，选出五只搜索的路径最短的蚂蚁，将其搜索到的路径与当前历史最优路径进行比较，对属于历史最优解和五个较优解交集的路径(i,j)进行信息素增强，强化优质路径上间的信息素量，加快算法收敛的同时提高蚂蚁的寻优能力[17]。

2.4 基于改进蚁群算法的航迹规划

利用改进的蚁群算法进行无人机航迹规划，具体步骤如下：

1）初始化算法各参数，初始化搜索空间，每个网格关联一个时间码；

2）对于已知起始点的环境模型，初始化全局信息素；

3）将所有蚂蚁置于初始位置，创建新的禁忌表Tabu，并将此时的位置加入禁忌表中；

4）更新蚂蚁在当前位置的可选节点集合，计算启发函数以及各节点转移概率；

5）蚂蚁根据轮盘赌的方式选择下一节点j，蚂蚁到达节点j后，更新禁忌表Tabu，将节点j加入禁忌表；

6）判断蚂蚁是否到达目标点E，若是，则停止搜索，迭代结束；否则，转到步骤4），直到到达目标点E；

7）当全部蚂蚁都抵达了目标点E 后，迭代结束，记录每代中每只蚂蚁经过的路线以及长度，并记录在此次迭代中所找到的路径总长度较短的前五只蚂蚁的序号，对这五只蚂蚁经过的路线与当前长度最短的路线取交集，进行信息素更新；

8）确定当前迭代次数是否已到达最大值，如果是，则输出为最佳路径；否则，转到步骤3）继续迭代。

3 仿真结果分析

文中所使用的仿真平台是Matlab2014a，硬件工作环境：CPU 参数为Intel Core i7-6700HQ 2.60 GHz，内存8.00 GB。规划范围为20 km×20 km 的二维空域平面空间，仿真的关键参数设置如表1 所示。

表1 仿真参数设置

3.1 栅格环境建模下仿真

为了对改进前后算法的性能做合理的对比分析，对改进前后算法取相同参数。传统蚁群算法最优航迹及改进蚁群算法最优航迹分别如图4 和图5所示，对比两图可知，改进后的蚁群算法所得最优航迹明显较传统蚁群算法平滑。

图4 传统蚁群算法最优航迹

图5 改进蚁群算法最优航迹

传统蚁群算法收敛曲线及改进蚁群算法收敛曲线分别如图6 和图7 所示，结合实验数据可知，传统蚁群算法规划的最短路径长度为34.041 6 km，在迭代第43 次达到最优，而最后却收敛于次优解；改进蚁群算法规划的最短路径长度为31.556 3 km，在迭代第31 次达到最优且收敛。传统蚁群算法并不能收敛到最优解，主要是因为当蚂蚁发现了最优解时，由于在次优解上的信息素积累已经较多，使得蚂蚁在一次迭代中，从最优路径上释放的信息素对后来的蚂蚁无法产生足够的诱导影响，从而使得计算陷于局部最优，改进的蚁群算法基本解决了这个问题。

图6 传统蚁群算法收敛曲线

图7 改进蚁群算法收敛曲线

对改进前后的算法分别进行10 次重复实验，所得数据如表2 所示。

表2 改进前后蚁群算法对比

由表2 可知，文中所给出的改进蚁群算法比起传统蚁群算法更具优势，平均路径长度缩短了6.5%，且所寻得的最优路径显著优于传统蚁群算法所寻得的最优路径，平均迭代次数降低了41%。对比两种算法的结果显示，文中给出的改进蚁群算法不但收敛速度快而且所寻路径也更优，从而证明了算法的可行性。

3.2 关联时间的网格化环境建模下仿真

设无人机飞行速度为30 km/h，预计11:15从起始点飞往目标点，关联时间的网格模型如图8 所示。箭头所指部分为临时禁空区，空域禁用时间为10:00-11:30。采用改进的蚁群算法进行航迹规划，起始点坐标(0,20)，目标点坐标(20,0)，关联时间的网格化环境下得到的最优路径如图9 所示。由图8 可知，所规划路径穿过了临时禁飞区，这是因为在此次路径规划中，当路径搜索至该临时禁空区时，空域已变为可通行状态，无人机可选择该区域里的节点作为航迹规划的节点。图8所示的最优路径长度为28.041 6 km，对比3.1 节中的最优路径长度，明显得到了一条更优路径，并且也在一定程度节约了空域资源。

图8 关联时间的网格模型

图9 关联时间的网格化环境下的最优路径

4 结论

无人机行业的快速发展离不开空间信息科学的进步，数字地球的概念为无人机在低空安全、合理地飞行创造了条件。文中采用了空域网格化方式，对传统蚁群算法加以改良，改进蚁群算法可获得更快的收敛速度并且具有更强的全局寻优能力，更容易取得最优解且得到的路径长度更短。将飞行环境网格化并为每个网格赋予时间属性，更加符合实际需求，发展动态数字空域将是当下和未来的研究重点。

文中旨在说明对空域进行网格化处理以及在算法中赋予其时间属性的重要性以及对传统蚁群算法用于航迹规划中存在的缺点进行改进，故仅在二维环境下进行仿真，后续研究应当建立三维场景进行仿真。