基于改进蚁群算法的网格空间航迹规划_邱诚.pdf

电子设计工程Electronic Design Engineering第31卷Vol.31第4期No.42023年2月Feb.2023收稿日期：2021-11-22稿件编号：202111146作者简介：邱 诚（1997），男，福建福州人，硕士研究生。研究方向：数字空域、无人机航路规划。近年来，各种无人机的使用、服务需求正在持续快速增长。在对抗新冠肺炎期间，无人机就被用于医疗物资投递、空中巡逻督查等方面。空间网格模型可用于实现无人机群飞行空间的数字表示、环境信息的预存储和空间属性的高效查询。无人机完成任务的前提是进行合理的航迹规划，在空间网格模型的基础上进行无人机的航迹规划更加符合信息化时代的需求1。目前有多种算法被国内外学者用于无人机的最佳航迹求解，如文献2将启发算法与遗传算法结合，实现无人机路径的重规划；文献3用一种自适应粒子群优化算法进行路径规划；文献4基于人工势场，利用最优控制方法求解路径规划；文献5对蚁群算基于改进蚁群算法的网格空间航迹规划邱 诚1，黄大庆2，王浩雪1，刘耀辉1（1.南京航空航天大学 电子信息工程学院，江苏 南京 210016；2.南京航空航天大学 中小型无人机先进技术工信部重点实验室，江苏 南京 210016）摘要：随着信息技术的不断进步，建设数字地球已成为当下热点。为了使无人机领域的发展与信息技术的进步相结合，文中对空域的网格化及数字化进行了研究，将网格化思想应用于无人机航迹规划，对传统蚁群算法进行了改进，提出初始化全局信息素规则，并通过增加次优解和最优解交集的信息素浓度，强化优质路径的上信息素的引导作用。仿真结果表明，文中给出的改进蚁群算法与按照传统蚁群算法进行的航迹规划相比，平均路径长度减少 6.5%，平均迭代次数降低了41%。结合仿真实例，证明了网格化的空域关联时间属性的重要性。关键词：空域网格化；空域数字化；无人机；航迹规划；改进蚁群算法中图分类号：TN964.3文献标识码：A文章编号：1674-6236（2023）04-0137-06DOI：10.14022/j.issn1674-6236.2023.04.029Track planning in grid space based on improved ant colony algorithmQIU Cheng1，HUANG Daqing2，WANG Haoxue1，LIU Yaohui1（1.College of Electronic and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China；2.Ministerial Key Laboratory of Unmanned Aerial Vehicle Technology，NanjingUniversity of Aeronautics and Astronautics，Nanjing 210016，China）Abstract:With the continuous progress of information technology，building a digital earth has become ahot issue.In order to combine the development of UAV field with the progress of information technology，this paper studies the gridding and digitization of airspace，applies the gridding idea to UAV trackplanning，improves the traditional ant colony algorithm，proposes to initialize the global pheromone rule，and increases the pheromone concentration of the intersection of suboptimal solution and optimalsolution，strengthen the guiding role of pheromone on highquality path.The simulation results show thatcompared with the traditional ant colony algorithm，the average path length is reduced by 6.5%and theaverage number of iterations is reduced by 41%.A simulation example is given to illustrate the importanceof grid spatial correlation time attribute.Keywords:spatial grid；airspace digitization；UAV；track planning；improved ant colony algorithm-137电子设计工程 2023年第4期法进行改进，用来建立无人机低空航路网。其中，蚁群算法因为鲁棒性较强且具有正反馈机制，在无人机航迹规划的研究中受到广泛关注。在对蚁群算法的研究中，文献6进一步完善了算法的状态转移函数，并引入了信息素调节因子，以防止后期陷入局部最优；文献7在融合遗传算法的基础上改进信息素机制；文献8为克服蚁群算法在计算后期易陷入局部最优的问题，提出了混沌式搜索策略。但是，上述相关研究未考虑空域的实时性问题，在实际应用中，空域应当被赋予时间属性。文中在传统飞行环境建模的基础上提出了新的蚁群算法改进策略，在搜索开始前通过信息素初始化规则，先初始化全局信息素，减少算法初期盲目搜索导致收敛速度慢的问题；通过部分次优解和最优解的交集对优质节点进行信息素强化，提升算法的全局寻优能力以及收敛速度；提出关联时间的空域网格化建模，使其更加符合实际需求。1空域网格化1.1空域网格化的基本概念及方法空间地理剖分的思想早已有之，可追溯到夏商周时期出现的“井田制”，该土地管理制度根据道路、渠道将土地分隔成方块，体现了古老的空间剖分思想，是现代城市网格划分思想的鼻祖。人类对大区域空间的管理，习惯于网格式的“粒子化”分隔管理方式，各种典型的信息管理网格包括行政管理网格、环境监测管理网格、战场网格、有限元计算网格等。基于空间信息剖分的思想，将空域进行网格化管理，划分成若干大小一致、相互链接的基本空域单元，建立空域四维时空框架。如图 1-2所示，每个网格单元 G（Index,Time,Property）被用于组织空域中的各类数据，其中，Index为网格单元空间编码，用于存储空间位置信息；Time为时间戳；Property为属性集合。空域网格化的核心是将物理的空域空间通过空间规则剖分后，利用矩阵空间管理空中交通的几何结构和空域结构，利用空域剖分建立唯一的全球地址码，以地址码作为主键索引各网格内的数据。目前有三类主要方法被用于构建全球平面网格，分别是经纬网格、正多面体网格和自适应网格。1.2GeoSOT网格文中使用的网格化方法是一种空天地一体化的地球空间参考网格体系全球经纬度剖分网格9（Geo-graphic coordinate Subdivision grid with Onedimension integer coding on 2n-Tree,GeoSOT），该方法采用经纬度进行地球剖分，是经纬网格的一种。其设想的核心是对地球经纬度空间实行三次扩展（将地球及其邻近空间的经纬度范围扩展至 512512，将 1扩展为 64，将 1扩展为 64），将地球空间分割为一个个整度、整分、整秒的网格，最高一级包含整个地球空间，最小可以划分至厘米级，共 32 级剖分，可根据实际需要选择合适的剖分层级进行研究。例如文献10针对战场空域表征需要，选取了最大 512 km、最小 128 m 共七级网格进行战场空域表征；文献11分析了 GeoSOT网格应用在无人机碰撞检测上的可行性，发现 64 m网格用于无人机碰撞检测的计算时间最少。2蚁群算法及改进策略2.1飞行环境模型建立在传统的基于蚁群算法的无人机航迹规划研究中，通过建立栅格图的形式建立了无人机的航行环境模型12-16。如图 3所示，研究中往往简单地将黑色网格看作无法飞越的障碍网格，将白色网格看作可供航行的自由网格，从而忽略了低空环境随时间的变化，导致规划的路径不够科学、合理。图1空域四维时空框架的虚拟结构图2空域网格划分核心内容-138图3飞行环境模型基于空间信息剖分的思想，文中将飞行环境模型改进为关联了时间属性的网格化空域，选取GeoSOT中第 16级 1 km1 km 网格建立模型，每个网格除位置信息外，还对应一个时间信息，即若该网格存在障碍物，则网格关联一个障碍物存在的时间，在该时间范围外该网格依旧可以视为自由网格。2.2蚁群算法蚁群算法(Ant Colony Optimization，ACO)的思想源自于蚁群觅食的过程。在觅食初期，所有蚂蚁均等概率地选定能够获取到食物的路线，信息素随着蚂蚁寻找的过程被释放在蚂蚁走过的路线上，该信息素可以指导后来的蚂蚁作出路线抉择，同时路线上的信息素含量也会随着时间衰减。同样时间内，相较于其他路径而言，较短路线上的信息素含量会累积得更高，而由于蚂蚁在路线选择中偏向于挑选信息素含量高的路线，基于正反馈作用，信息素含量较高的较短路线被更多的蚂蚁选择，其信息素含量也因此越来越高。由于信息素的挥发，较短路线上的信息素含量远高于其他路线时，所有蚂蚁倾向于选择该路径，认为该路径为最短路径。2.2.1状态转移函数在蚁群算法中，蚁群根据状态转移函数选择下一个路径点，状态转移函数表示如下：Pkij(t)=ij(t)ij(t)sallowedkis(t)is(t),jallowedk0,其他（1）式中，Pkij(t)为蚂蚁在节点 i选择节点 j作为下一节点的转移概率；t表示当前的迭代次数；ij(t)为当前信息素浓度；s表示所有可选节点集合allowedk中的元素；是信息素启发因子，表示信息素的重要性程度，越大，表示信息素浓度在蚂蚁节点的选择中越关键；是距离启发因子，表示距离的重要性程度，越大，则蚂蚁更偏向于选取离目标点较近的节点；2.2.2信息素更新机制蚁群算法中的信息素更新机制如下：ij(t+1)=(1-)ij(t)+ij(t),01（2）式中，为信息素蒸发系数；ij(t)为当前信息素含量；ij(t)为信息素增量计算如下：ij(t)=k=1nkij(t)（3）kij(t)=QLk,蚂蚁经过路径lij0,其他（4）式中，kij(t)为第 k 只蚂蚁在路径(i,j)上产生的信息素量；Q 为信息素强度；Lk为第 k只蚂蚁在此次搜索中得到的路线总长度。2.3改进策略传统蚁群算法存在以下缺点：蚁群在路径规划初期搜索存在盲目性，收敛速度慢，搜索时间长；在某次迭代中，一只蚂蚁可能发现了最优解，但由于次优解路径上信息素已经积累较多，导致最优解与次优解之间信息素含量存在差距，算法无法收敛于最优解而陷于局部最优。针对以上两个缺点，提出改进策略。首先，对于图 3已知起始点的环境模型，初始化全局信息素，加快算法初期搜索效率，更新规则为：ij=p,j=i-1j=i-MM-1 j=i-MM1.25p,j=i+MM-1j=i-MM+11.5p,j=i+1j=i+MM j=i+MM+10,其他（5）式中，MM为栅格环境的列数；p为定值，为初始化信息素量；ij为由第 i个栅格到第 j个栅格之间的信息素量。其次，提出改进的信息素更新机制，如下：ij(t)=k=1nkij(t)+better(t)（6）better(t)=m=15mbetter(t)（7）mbe