EN中文

地球信息科学学报 >

2019 , Vol. 21 >Issue 4: 570 - 579

DOI: https://doi.org/10.12082/dqxxkx.2019.180392

论文

基于改进蚁群算法的无人机低空公共航路构建方法

  • 徐晨晨 , 1, 2, 3, 4 ,
  • 廖小罕 1, 3, 4 ,
  • 岳焕印 , 1, 3, 4, * ,
  • 鹿明 1, 3, 4 ,
  • 陈西旺 1, 3, 4
展开
  • 1. 中国科学院地理科学与资源研究所 资源环境与地理信息国家重点实验室,北京 100101
  • 2. 中国科学院大学,北京 100101
  • 3. 中国科学院无人机应用与管控研究中心,北京 100101
  • 4. 天津中科无人机应用研究院,天津 301800
*通讯作者：岳焕印（1975-）,男,河北石家庄人,博士,研究员,从事无人机航路规划、无人机遥感等研究。E-mail:

作者简介：徐晨晨（1991-）,女,安徽安庆人,博士生,从事无人机航路规划、无人机遥感等研究。E-mail:

收稿日期: 2018-08-20

  要求修回日期: 2019-03-04

  网络出版日期: 2019-04-24

基金资助

国家重点研发计划项目（2017YFB0503005）

国家自然科学基金项目（41771388）

收起

Construction of a UAV Low-altitude Public Air Route based on an Improved Ant Colony Algorithm

  • XU Chenchen , 1, 2, 3, 4 ,
  • LIAO Xiaohan 1, 3, 4 ,
  • YUE Huanyin , 1, 3, 4, * ,
  • LU Ming 1, 3, 4 ,
  • CHEN Xiwang 1, 3, 4
Expand
  • 1. Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, State Key Laboratory of Resources and Environmental Information System, Beijing 100101, China
  • 2. University of Chinese Academy of Sciences, Beijing 100101, China
  • 3. The Research Centre for UAV Application and Regulation, Chinese Academy of Sciences, Beijing 100101, China
  • 4. Institute of UAV application research, Tianjin and CAS, Tianjin 301800, China
*Corresponding author: YUE Huanyin, E-mail:

Received date: 2018-08-20

  Request revised date: 2019-03-04

  Online published: 2019-04-24

Supported by

National Key Research and Development Program of China, No.2017YFB0503005

National Natural Science Foundation of China, No.41771388

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

日益增加的无人机数量和飞手自由规划航线给航空安全带来极大隐患。构建一个安全、高效的航空飞行环境,可以为无人机活动设立隔离空域,并在隔离空域内规划无人机低空公共航路,以提高低空空域利用率,为无人机交通管理提供决策依据。本研究充分考虑无人机近地表飞行及其即时通讯等特点,以天津市为例,基于地理信息技术构建以多源地理空间数据为基础的无人机低空飞行环境,包括低空蜂窝网络环境、大气环境和政策空域环境等,并改进传统蚁群算法以搜索无人机最优路径,得到该区无人机低空公共航路网。研究结果表明,改进的蚁群算法大大提高了路径搜索效率,满足无人机航路规划的高时效性、动态更新等要求;并且天津市航路长度符合市场上现有的无人机最远航程要求,基本满足现有的无人机运输要求。本研究描述的无人机低空公共航路研究的核心算法和关键技术,可以为无人机管控系统提供核心技术支撑。

关键词： 无人机; 低空空域; 低空公共航路; 蚁群算法改进; 算法应用; 天津

本文引用格式

徐晨晨 , 廖小罕 , 岳焕印 , 鹿明 , 陈西旺 . 基于改进蚁群算法的无人机低空公共航路构建方法[J]. 地球信息科学学报, 2019 , 21(4) : 570 -579 . DOI: 10.12082/dqxxkx.2019.180392

Abstract

The ever-increasing numbers of UAVs and their free-flying route planning have brought great challenges to national aviation safety. In order to build a safe and efficient aviation flight environment, it is possible to establish an isolated airspace for the UAV activities, and also plan UAV low-altitude public air routes within it. If established, this would increase safe airspace utilization and provide a decision-basis for UAV traffic management. Taking full account of the geographic characteristics of near-surface flight and the near-instant messaging capabilities of UAVs, this study built a low-altitude flight environment for UAVs in Tianjin, China based on multi-source geospatial data using geographic information technologies, and constructed a low-altitude public air route network using an improved Ant Colony Optimization (ACO) algorithm. The study had five major components. Firstly, we developed a path-searching model by improving the traditional ACO algorithm from search space and local target selection. The improved algorithm can be used to search paths in eight directions along a line between the start and end points in order to shorten the search time, and the search radium was determined by an obstacles ratio. Then, local target selection was optimized by introducing evaluation function of A* algorithm and random roulette method. Secondly, we compared the calculating efficiency and path length between the traditional algorithm and the improved one, and found that the improved algorithm was three times more efficient and shorter than the traditional one. Thirdly, the low-altitude flight environment for UAVs included a cellular network, and climatological condition and airspace-policy can be taken into account. The cellular network environment was determined by the distribution of mobile communication base stations and signal attenuation principles. Climatological conditions included wind shear, thunderstorms, glaciation, and low-visibility weather events, and all of which have a significant impact on UAV flight safety. The airspace-policy factors included populated areas, key buildings, and civil airport clearances. Fourthly, we constructed a digital low-altitude airspace by establishing UAV flight principles within air routes and quantifying a grid cost for each kind of constraint. Lastly, the fifth component is verifying the outcomes’ reliability by comparing air-route length with the most realistic distance that the UAV currently exhibits. In summary, we found that the improved algorithm greatly shortened search time, and reduced path redundancy. The air-route lengths also comply with the farthest-distance requirement for UAVs currently on the markets. The study described basic ideas and key technologies of the UAV's low-altitude public air route research and can provide the core technical support for the UAV control systems.

Key words： UAV; low-altitude airspace; low-altitude public air route; improvement of the ant colony algorithm; algorithm application; Tianjin City

1 引言

低空空域是重要的战略资源。近年来,中国民用无人机产业持续快速发展[1,2],2017年民用无人机产量达290万架[3],2020年产值将达到600亿元[4]。持续增加的无人机数量和高速发展的无人机产业和行业应用带来日益频繁的无人机低空飞行作业;但是无人机系统的操作人员水平参差不齐,培训体系和相关法律规范体系不健全,“黑飞”现象不断出现,严重扰乱了低空飞行秩序,对低空空域资源的科学管理和有效应用带来了巨大挑战,也给国家和民众安全带来了严重威胁。例如,2017年发生的无人机扰航事件多达80起[5],严重影响了民航飞行安全。低空安全问题已经成为亟待解决的难题。
为了加强低空安全,构建低空资源理论与技术保障体系,各国纷纷开展了前瞻性的探索研究。为了满足技术测试的场地和空域保障,并且避免对有人机和群众安全及隐私造成干扰,各国纷纷划设隔离通道作为无人机飞行测试场地,即“无人机交通管理走廊”。无人机交通管理走廊是一个集成了软硬件和人工智能技术的综合信息服务体系,旨在对低空无人机进行监视并提供气象情报服务,保障低空空域的健康运营环境。国外此类项目研究以非洲、美国和新加坡领先。2017年6月,非洲政府和联合国儿童基金会（UNICEF）在马拉维建立起了非洲第一条人道主义无人机走廊（Humanitarian UAV Testing Corridor）,长40 km,离地高度500 m[6];2017年9月,美国提出无人机交通管理走廊概念,计划将格里菲斯国际机场西部大部分乡村农田向西延伸80 km,在罗马市（Rome）和雪城（Syracuse）之间建立北美第一条无人机飞行走廊,配备雷达和地面传感器用来低空探测和追踪小型无人机,以保证走廊内无人机的安全间隔[7];2018年2月,新加坡空客公司联合新加坡民航管理局推出“Skyways”项目[8],旨在测试无人机在预先定义好的空中廊道中运输包裹的能力。国内还没有关于无人机交通管理走廊的系统研究,大部分研究注重于避障、导航和飞行控制等无人机飞行技术,只有部分学者提出无人机通道设计的规则和方法,如冯登超和袁晓辉[9]于2016年首次提出低空交通管理走廊技术的实施路线,并随之提出基于离散激光点云的空中走廊自动构建方案[10];白龙等[11]对城市区域的低空廊道划设提出了“高度-密度”和“隔离区”等规则和方法。
无人机交通管理走廊技术是一种旨在由“典型场景”到“广泛应用”的“自下而上”解决方法,在现有研究中,还有另外一种“自上而下”的顶层设计方法可解决无人机低空安全飞行问题,即构建无人机低空公共航路。无人机低空公共航路由廖小罕等[12]于2018年首次提出,是指在有人驾驶航空器最低飞行高度以上,预先规划具有一定宽度专供无人机飞行的公共空中通道;并且在2019年4月作为“中科天网”无人机综合管理云系统的组成部分得到中国民用航空局的认可[13]。低空通道的划设依赖于精准、全面的低空飞行环境和高效的路径搜索方法。无人机在低空飞行往往会穿越障碍物,因此,穿越不规则障碍空间的航路设计成为热点研究内容。
进行路径搜索的算法有很多,如A*算法[14]、遗传算法[15]、人工势场法[16]等。其中,蚁群算法[17,18]因其具有并行计算、鲁棒性强等优点,被广泛应用于求解复杂优化的问题,尤其是在离散优化问题方面。例如,林娜等[19]引入航路点的动态自适应选择策略和信息挥发因子动态自适应调整准则来解决收敛速度慢、易于陷入局部最优等问题;Talbi等[20]和Stützle等[21]使用禁忌搜索来改进蚂蚁的二次分配;曲小康等[22]改进了信息素更新机制,并融合了遗传算法增加了最优解的全局性,在此基础上快速有效地计算成本距离。但是,上述相关研究主要面向无人机的作业航路规划,范围小,多为单次航路规划,考虑的低空飞行环境要素有限且片面;而无人机低空公共航路涉及的规划空间广,在路径搜索过程需要考虑低空蜂窝网络环境和无人机空域政策环境,并且对路径搜索效率要求很高,故传统蚁群算法难以满足要求。
本文充分考虑了无人机航路规划的特点和要求,提出一种基于多源地理信息和改进蚁群算法的路径搜索方法：首先,获取所需规划区域的基础地理信息,如地形、低空气候、基站分布和政策限制区等,对其进行融合处理来模拟真实环境和飞行约束条件,构建低空栅格环境;然后,制定不同飞行约束条件下的无人机准入规则,计算每个网格的成本代价值;最后,对传统蚁群算法（Ant Colony Optimization Algorithm）进行改进,得到从起点到目标点的无人机航路,并与实际的无人机最远航程进行对比分析,从而保证规划结果的科学性和合理性。

2 基于改进蚁群算法的路径搜索模型

2.1 空间划分与表示

首先对航路规划空间进行划分,构造路径搜索的最小单元。本文采用网格划分,航路由一系列相邻网格节点连接形成,每个航迹点的下一节点的搜索范围是以其为中心的8个相邻节点,如图1所示。
Fig. 1 Diagram of path search direction

图1 路径搜索方向示意

在蚁群算法中,航路的规划空间表现为各节点间的状态转移矩阵,作为判断从当前航点转移到下一相邻航点的依据,因此,研究需要构造状态转移矩阵,并计算各相邻节点间的转移概率。根据上述空间划分,设规划空间4个顶点坐标分别为（xmin, ymin）、（xmin, ymax）、（xmax, ymin）和（xmax, ymax）,设网格大小为a,则状态转矩阵行数和列数均为：
N = x max - x min a × y max - y min a （1）
坐标为（xi, yi）的网格在矩阵中的编号为：
P i = x i - x min a + 1 + y i - y min a × y max - y min a （2）
每个矩阵元素代表每个网格节点与其他网格节点间的通达关系,非0表示可达,0则代表不可达;根据无人机飞行空域环境对矩阵进行修正（若某网格节点相邻节点为“障碍物”,则它们之间不可达,矩阵元素值为0）,得到最终的状态转移矩阵。

2.2 算法改进

传统蚁群算法采用的是相邻栅格的搜索形式,用于大范围航路搜索存在局限性：① 搜索空间过大,易导致算法效率过低,收敛速度慢;② 搜索步长小,不适于长距离搜索;③ 没有方向启发搜索策略,易产生路径迂回冗余,搜索效率低。本文根据低空公共航路的特点引入以下2种机制对该算法进行改进。
（1） 可变搜索空间范围和局部搜索半径
传统蚁群算法中,随着搜索空间扩大,易出现“组合爆炸”问题,搜索效率随之快速降低。因此,合理控制搜索空间大小,既满足搜索空间内有最优路径解,又尽可能提升搜索效率是本文需要改进的问题之一。研究遵循“两点间直线距离最短”原则,以起、止航点间连线做可变距离的缓冲,形成搜索空间（图2）。缓冲距离从初始值逐渐增加,直至搜索空间内有最优航路解。同时,为了提高路径搜索效率,搜索过程中采用变长搜索,即根据局部搜索空间内障碍物的比例确定搜索步长。例如,当搜索空间内障碍物比例低于10%时,步长采用2个网格单元,如图2所示。
Fig. 2 Diagram of search space and variable search radius

图2 搜索空间和可变搜索半径示意

（2） 最优局部目标点选择
从当前航迹点转移到下一航迹点需要计算当前航迹点到所有相邻航迹点的转移概率,经典蚁群算法中计算公式如下：
P ij k t = τ ij α ( t ) η ij β ( t ) ∑ j ∈ allowe d k τ ij α ( t ) η ij β ( t ) j ∈ allowe d k 0 j ∉ allowe d k （3）
式中：allowedk表示蚂蚁可以到达的节点;α为信息素启发式因子,表示路径积累的信息素对路径选择的重要性程度;τij(t)表示航迹段ij的信息素浓度;β为期望启发因子,表示启发因素对路径选择的重要性程度,ηij(t)为启发函数,在经典蚁群算法中为节点i、j之间距离的倒数,易导致蚂蚁贪图当前最短路径而陷入局部最优。
本文参考A*算法中的估价函数[23],将当前节点与终止节点间联系引入启发函数,能有效解决局部最优问题,同时提高了算法效率。启发函数计算如下：
η ij t = 1 d ij 其他 1 - C × d Oj ¯ × d Oj ¯ + C × d Oj ¯ × d jE ¯ ρ < d Oi < d OE （4）
d Oj ¯ = d Oj ∑ j ∈ allowe d k ( d Oj + d jE ) （5）
d jE ¯ = d jE ∑ j ∈ allowe d k ( d Oj + d jE ) （6）
式中：dij表示当前节点i和下一节点j间距离; d Oj ¯ 、 d jE ¯ 别为归一化后的下一节点离起点和终点的距离; d Oj 为起始节点和下一节点j间距离; d OE 为起点和终点间距离;C和ρ为常数; C × d Oj ¯ 表示下一节点与终点间距离的权重;ρ表示开始引入方向信息的路径长度阈值,是为了避免蚂蚁在移动过程中过早受到方向信息影响而陷入局部最优,二者均在实际应用时确定数值;allowedk表示蚂蚁可以到达的节点。
此外,为了避免经典蚁群算法存在的过早收敛问题,本文采用随机轮盘赌法[24]对下一航迹点进行选择。随机轮盘赌算法是基于传统轮盘赌算法和贪婪算法的一种改良算法,既能够提高传统轮盘赌算法的收敛速度,又能够避免贪婪算法容易陷入局部最优值的缺陷。当随机数rand=0时,该算法等效于传统轮盘赌算法,能够避免局部最优值陷阱;而当rand=max（Pi）时,则该算法相当于贪婪算法,具有较快的收敛速度。
P i = P i P i ≥ rand 0 P i < rand （7）

2.3 改进后的蚁群算法

改进后的蚁群算法具体步骤如图3所示。
（1）初始化搜索空间,根据障碍物比例确定搜索步长,并构建邻接矩阵;
（2）把第一代的蚂蚁m（m=1,2,…,N）放到初始位置,并把初始位置加入到每个蚂蚁的禁忌表;
（3）寻找下一步可以前往的节点,形成可选节点集LJD;
（4）计算启发函数Eta,此处融合了A*算法的估价函数,引入当前节点与终点间联系,以优化搜索;
（5）利用随机轮盘赌法选择下一个节点to_visit;
（6）更新蚂蚁所在位置节点和禁忌表;
（7）记录路径及其长度;
（8）重复步骤（2）-（7）,直至第一代的所有蚂蚁遍历完;
（9）更新信息素;
（10）重复步骤（2）-（9）,直至遍历所有代数;
（11）找到最优路径。
Fig. 3 Flowchart of the improved ACO algorithm

图3 改进后的蚁群算法流程

3 研究区概况与算法运用

3.1 研究区概况

天津市位于渤海湾经济圈中心,背靠东北,内连华北、西北地区,形成中国北方对内、对外开放两个扇面,经济地理位置十分优越。尤其是随着京津冀一体化进程,天津市的交通运输体系建设发展迅速,港口、铁路和公路运输上区域优势明显,已然成为中国北方乃至全国重要的交通枢纽之一。近些年随着无人机产业兴起和关键技术突破,无人机送货正逐渐成为一种新的运输方式,而天津市对于无人机产业发展的政策环境友好,具备良好的无人机临场飞行试验和空域条件,其无人机行业发展也在国内领先,因此本文以天津市为例进行无人机航路规划。
根据廖小罕等[12]对无人机低空公共航路的定义和四级架构划分（将航路划分为全国骨干、区域主干、支线和末端航路四个级别）,本文选择在天津市各区中心地带或交通枢纽附近建设各地支线航路无人机空港,进行支线航路规划。无人机空港所在地必须视域开阔、通信状况良好、无高层建筑或山体遮挡,以及不在政策限制区范围内[12]。据此原则,得到天津市无人机空港布局如图4所示。
Fig. 4 The drone-port layout and part of the grid cost of low-altitude airspace environment in Tianjin

图4 天津市无人机空港布局及其低空空域环境的部分网格成本代价示意（截至2018年）
注： 图b中数字代表网格的成本代价值。

3.2 算法应用

3.2.1 计算状态转移矩阵
状态转移矩阵元素值由每个网格节点的成本代价值确定,即每个网格节点内影响无人机安全飞行的因素加权值。影响无人机低空飞行的因素众多,主要包括地形、低空气候、政策规定的限制区和通信信号强度等。
（1）低空气候。影响较大的低空气候主要包括风切变、雷暴、积冰,以及雾、霾、沙尘暴等导致的低能见度事件等[25],风切变数据难以获取,本文用风速大于15 m/s的事件代替。各气象事件影响范围为事件观测台站1 km范围内的缓冲区。
（2）移动通信。随着无人机行业高速发展的同时,无人机通信链路呈现出与蜂窝移动通信技术紧密结合的发展趋势,形成“联网无人机”。根据《低空联网无人机安全飞行测试报告》[26],低空蜂窝网络初步满足无人机安全飞行需求。因此,可根据移动基站信号覆盖数据建立无人机的低空飞行通信环境。本文假设有人区信号覆盖良好,根据人口分布格网数据[27]和移动通信基站覆盖数据分析无人区移动信号覆盖情况。
（3）政策限定的无人机限制区。为了保障航空安全、国家安全和公众隐私,也为了规范无人机飞行,各地政府部门对无人机的活动范围进行了限定,规定了一系列无人机禁飞区、限飞区和危险区。本文主要考虑地市级以上的党政机关、火车站、客运站、港口码头、公安局和高层大厦等分布,采用缓冲保护区表示各限制区。其中,机场净空保护区根据《民用航空机场障碍物限制面保护范围数据》[28]采用多边形表示。
在构建天津市的无人机飞行低空空域环境时,本文假设支线航路宽度1 km。为简化计算,通信盲区、政策限制区以及地形数据等均转化为空域环境中的“障碍物”,网格成本代价均为1,在路径搜索中实行“禁止飞入”原则;大气环境为统计多发数据,因此在路径搜索时遵循“警告飞入”原则,网格成本代价值范围为0.2~0.8,离气候事件中心越近,其成本代价越大;其他区域均为路径搜索中的可飞区域,网格成本代价为0（表1）。本文假设无人机飞行高度为120 m,得到120 m处的低空空域环境及其部分网格成本代价如图4所示。
Tab. 1 The grid cost and access principle for each constraint

表1 各约束条件网格成本代价及飞行准入原则

类型 网格成本代价 遵循原则 限制高度/m
通信盲区 1 禁止飞入 120
政策限制区 1 禁止飞入 120
机场净空保护区 1 禁止飞入 120
地形 1 地形跟随 实际高度
低空气候 0.2~0.8 警告飞入 120
其他 0 可飞 0
每个网格的成本代价计算过程如式（8）所示。
w i = max ( w 通信 , w 限制区 , w 机场 , w 地形 , w 气候 ) （8）
3.2.2 算法改进前后性能对比分析
为了对比分析算法改进前后的性能,蚁群算法参数取值相同：蚁群数目为搜索空间网格数目的1.5倍,信息素挥发系数为0.1,信息素增强系数为100,信息素控制强度系数为2,启发式因子控制强度系数为5。本文选取宁河县-塘沽区、武清区-西青区和宁河县-津南区3条支线航路的搜索结果进行对比分析,200次迭代后的最终搜索路径结果如表2和图5。可以看出,传统蚁群算法得到的结果随机性较大,且很难得到最优路径;而改进后的算法通过缩减迭代次数达到快速收敛的效果,减少了迂回次数和冗余距离,大大提升了计算效率,同时得到的路径搜索结果接近最优路径,提升了路径的全局最优性。
Tab. 2 Comparison of performance before and after ACO algorithm improvement

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

支线航路 算法类型 格网搜索空间
大小/格网数量		 达到最优时迭代次数 搜索步长 搜索时长/s 路径网格成本代价 最短路径长度/步长 路径长度/步长 迂回次数
宁河县-塘沽区 改进后 14×51 8/200 2 130 0 54 64 1
改进前 14×51 120/200 1 205 0 54 75 5
武清区-西青区 改进后 26×60 10/200 2 332 3 93 93 0
改进前 26×60 75/200 1 452 0 81 105 10
宁河县-津南区 改进后 38×49 10/200 2 667 0 76 82 5
改进前 38×49 80/200 1 795 0 76 89 9
Fig. 5 Comparison of results before and after algorithm improvement

图5 算法改进结果对比

4 结果及分析

考虑到无人机飞行的动力学约束,研究采用四向搜索。基于栅格环境和改进蚁群算法进行路径搜索得到该区无人机低空支线航路网（图6）,表3和表4分别展示了各航段实际长度与航路网性能。
Fig. 6 Diagram of the layout of low-altitude feeder air routes in Tianjin

图6 天津市无人机低空支线航路分布示意

Tab. 3 Length for each UAV low-altitude public air route in Tianjin

表3 天津市各无人机低空公共路航段长度

序号 航段起点 起点经纬度 航段终点 终点经纬度 航段实际长度/km 直线距离/km
1 蓟县 (117°26' E,40°01' N) 宝坻区 (117°25' E,39°36' N) 56.58 45.54
2 蓟县 (117°26' E,40°01' N) 武清区 (116°58' E,39°34' N) 97.08 63.80
3 蓟县 (117°26' E,40°01' N) 宁河县 (117°39' E,39°23' N) 114.16 72.42
4 武清区 (116°58' E,39°34' N) 宝坻区 (117°25' E,39°36' N) 59.97 38.85
5 武清区 (116°58' E,39°34' N) 北辰区 (117°10' E,39°16' N) 64.68 38.28
6 武清区 (116°58' E,39°34' N) 西青区 (117°07' E,39°02' N) 91.67 60.66
7 宝坻区 (117°25' E,39°36' N) 宁河县 (117°39' E,39°23' N) 52.81 31.97
8 宝坻区 (117°25' E,39°36' N) 北辰区 (117°10' E,39°16' N) 67.84 43.02
9 宝坻区 (117°25' E,39°36' N) 塘沽区 (117°37' E,38°56' N) 102.01 75.45
10 宁河县 (117°39' E,39°23' N) 北辰区 (117°10' E,39°16' N) 72.61 43.47
11 宁河县 (117°39' E,39°23' N) 汉沽区 (117°51' E,39°15' N) 41.42 22.48
12 宁河县 (117°39' E,39°23' N) 塘沽区 (117°37' E,38°56' N) 63.52 48.90
13 宁河县 (117°39' E,39°23' N) 津南区 (117°23' E,38°58' N) 78.16 52.12
14 北辰区 (117°10' E,39°16' N) 西青区 (117°07' E,39°02' N) 42.05 26.05
15 西青区 (117°07' E,39°02' N) 静海县 (116°58' E,38°52' N) 31.30 22.91
16 西青区 (117°07' E,39°02' N) 津南区 (117°23' E,38°58' N) 32.80 24.64
17 汉沽区 (117°51' E,39°15' N) 塘沽区 (117°37' E,38°56' N) 60.39 39.74
18 津南区 (117°23' E,38°58' N) 大港区 (117°25' E,38°48' N) 26.91 17.94
19 静海县 (116°58' E,38°52' N) 大港区 (117°25' E,38°48' N) 45.00 39.63
20 塘沽区 (117°37' E,38°56' N) 大港区 (117°25' E,38°48' N) 36.51 23.94
合计 1237.48
Tab. 4 Values of assessment indexes for UAV air routes network in Tianjin

表4 天津市无人机航网络评价指标数值

指标 作用 公式 参数说明 计算值
网络连接度 衡量航路网的成熟度,连接度越高,网络越成熟 J=2MN N为航路网中的节点数量,Mi为第i节点邻接的边数,M为网络总边数 3.64
非直线系数 两点间航路距离与其直线距离的比值,越接近1连接越便捷 R=∑i=1N∑j=1NLij∑i=1N∑j=1NSij Lij表示节点ij间航段实际长度,Sij表示节点ij间直线距离 1.49
从安全性角度,研究得到的航路分布均匀,避开了通信盲区和恶劣气象事件频发区,保障了无人机的安全飞行;避开了政策限制区和机场净空区,保障了国家空域安全和人民群众安全。从经济性角度,该网络的非直线系数为1.49,表示无人机交通比较便捷;网络连接度为3.64,表示网络成熟度较高;航路网的总长度为1237.48 km,每条航路的长度均在120 km以内,符合市场上现有的大部分Ⅲ、Ⅳ类（7 kg≤ 起飞全重 ≤150 kg）固定翼油动无人机的最远航程要求（图7）。据统计,“雷鸟无人机”当前最远航程120 km,巡航时速120 km/h,载重65 kg,汽油动力,假设采用该机型作为运输无人机,则1 h就可以覆盖全天津市,在现有的地面交通基础上大大提升了运输能力。
Fig. 7 Chart of the farthest distance for Ⅲ and Ⅳ UAVs

图7 Ⅲ、Ⅳ类无人机最远航程统计
注：数据来源于无人机遥感系统信息库[29]。

5 结论与讨论

5.1 结论

划定无人机专用航路可以维护和规范低空空中交通管理,提高低空空域资源的利用率,并保证航空和公共安全,因此,本文根据无人机低空航路的特点,对传统蚁群算法进行改进,构建了天津市的无人机低空支线航路网,通过实例验证得到如下结论：
（1） 研究基于传统的蚁群算法,压缩了蚂蚁在路径寻优过程中的搜索空间,使其接近于包含最短路径的格网集合,并根据空间障碍物比例确定路径搜索步长,大大缩短了路径寻优过程;此外,为了解决传统蚁群算法中易产生路径迂回等问题,研究引入了终点目标的方向信息,提高了终点对于路径寻优的引导作用。与传统蚁群算法相比,改进后的蚁群算法能够在比较少的迭代次数下快速收敛,大大缩减了路径寻优时间;同时,改进后算法产生的路径冗余较少,接近最短路径,提升了路径的全局最优性。
（2） 研究在收集了天津市近地表基础地理数据的基础上,利用GIS制图和栅格成本距离计算等技术构建了无人机低空飞行栅格环境,并采用改进的蚁群算法得到无人机空港之间的最优航路,进而得到该区支线航路分布结果。经统计,各支线航路长度均在120 km以内,基本符合当前无人机最远航程技术要求;形成的航路网络非直线系数为1.49,表示可以进行便捷的无人机交通;网络连接度为3.64,体现了较高的成熟度,能形成低空无人机快速运输体系。按照当前无人机技术趋势,通过计算,研究得到的天津市无人机支线航路网络交通体系能够在1 h内服务全区,既便捷又高效。随着无人机数量的剧增、应用的多样化及其避障、导航和通讯技术的不断突破,无人机低空交通运输体系必然发展起来,其低空属性决定了其可以弥补现有交通体系中低空领域的空白,可以与地面交通、航空交通构成立体化的地面-低空-高空交通网络体系,能够大大提升交通运输能力。
本文的研究方法和进一步深化的成果可作为全国低空航路网构建的工作基础,促进和规范未来无人机大范围商业化应用、为全国和地区的无人机飞行监管提供相关技术支撑,为已有的无人机云管理系统提供公共航路支持。

5.2 讨论

本文针对无人机的飞行特点和相关空域政策,提出了无人机低空公共航路的构建方法,并改进传统蚁群算法,大大提升了路径搜索效率,能快速生成最优航路。然而,本文仅是全国无人机低空公共航路构建的前期工作,还存在如下不足：
（1） 低空飞行环境构建。首先是低空飞行环境要素的选择,本文考虑了当下低空蜂窝网络、气候和空域政策限制区环境,严格来讲,影响无人机飞行的因素远不止这些,还应包括其他人口稠密区、电磁干扰和防空导弹危险区等,但受限于真实数据的获取,本文暂未研究上述要素。随着5G时代的到来,5G蜂窝网络能在增强现有水平区域覆盖能力的同时,大幅增加垂直空间的容量和覆盖,通过灵活的波束扫描和波束分层满足多样化的场景覆盖要求[30],为无人机低空飞行构建低时延、高可靠、高性能的广覆盖低空网络,从而提供更高的飞行自由度和更广阔的有效空域。因此,在后续研究中,会持续更新和完善基础数据、动态调整5G覆盖下的蜂窝网络环境,形成较为全面和精准的航路规划数据库。其次,本文研究特定高度上的航路搜索,而各自然或人工约束条件的空间范围应是随高度变化的,因此后续会深入研究各约束条件的空间模型,形成无人机飞行的三维真实低空环境。最后,本文尚未考虑低空飞行环境随时间的变化,尤其是空域政策的更新,易导致航路穿越临时禁区。因此,在后续研究中考虑引入动态数字空域环境的概念,引入时间维度,构建四维低空数字飞行环境,使在此基础上规划的无人机低空公共航路更科学、合理。
（2） 航路结果验证。本研究仅是将航路实际长度与市场现有无人机最远航程统计结果进行对比分析,距离实际应用差距还很大,后续会进行无人机的仿真飞行试验和实际飞行验证,确保航路的合理性、高可靠性和实际应用能力。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
廖小罕,周成虎,苏奋振,等.无人机遥感众创时代[J].地球信息科学学报,2016,18(11):1439-1447.

[Liao X H, Zhou C H, Su F Z.et al.The mass innovation era of UAV remote sensing[J]. Journal of Geo-information Science, 2016,18(11):1439-1447. ]

[2]
王万国,田兵,刘越,等.基于RCNN的无人机巡检图像电力小部件识别研究[J].地球信息科学学报,2017,19(2):256-263.

[Wang W G, Tian B, Liu Y, et al.Study on the electrical devices detection in UAV images based on region based convolutional neural networks[J]. Journal of Geo-information Science, 2017,19(2):256-263. ]

[3]
国统计局.中华人民共和国2017年国民经济和社会发展统计公报. 2018-02-28. [EB/OL] .

[National Bureau of Statistics. Statistical communique of the People's Republic of China on 2017 national economic and social development [EB/OL]. ]

[4]
中华人民共和国工业和信息化部.工业和信息化部关于促进和规范民用无人机制造业发展的指导意见.2017. [EB/OL]. 2017-12-22.

[Ministry of Industry and Information Technology of the People's Republic of China.Guiding opinions of the Ministry of Industry and Information Technology on promoting and regulating the development of civil UAV manufacturing[EB/OL]. ]

[5]
中国民用航空局. 2017年中国民用无人机驾驶航空器运行管理年报[R].北京:2018-03-22.

[Civil Aviation Administration of China (CAAC). Unmanned aircraft operation management of CAAC annual report 2017[R]. Beijing: 2018-03-22. ]

[6]
Unicefstories. Africa's first humanitarian drone testing corridor launched in Malawi by government and UNICEF.2017[EB/OL]. .

[7]
Handler C H. New York state creates nation's first air corridor for Unmanned Aerial Vehicles.2018.[EB/OL].

[8]
Zazulia N. Airbus testing unmanned package delivery in Singapore.2018[EB/OL]. .

[9]
冯登超,袁晓辉.低空安全走廊及应急管理可视化研究进展[J].电子测量与仪器学报,2016,30(4):493-505.低空飞行安全环境是低空空域管理的重要研究内容,低空安全走廊及应急管理的可视化研究可以用于飞行器在低空空域的飞行安全保障及对地面人群和建筑物的保护等方面。综合阐述了近年来低空安全走廊及应急管理可视化的研究进展。首先总结了国内外低空空域的飞行安全事故和现状。然后从三维低空安全走廊构建、动态信息交互机制及安全应急管理策略、低空起降阶段安全监管可视化三个方面介绍了低空安全走廊及应急管理可视化的研究进展,阐述了应用于低空安全走廊及应急管理可视化方面的相关技术,并对低空安全走廊及应急管理可视化的发展趋势进行了展望。对相关领域研究者开展研究具有一定的参考和指导价值。

DOI

[Deng D C, Yuan X H.Advancement of safety corridor and emergency management visualization in low altitude airspace[J]. Journal of Electronic Measurement and Instrumentation, 2016,30(4):493-505. ]

[10]
Yuan X H, Feng D C, Zuo Z J.Automatic construction of aerial corridor from discrete LiDAR point cloud[M]//Hassanien A E, Elhoseny M, Kacprzyk [J]. Quantum computing: An environment for intelligent large scale real application. Springer, Cham, 2018:449-465.

[11]
白龙,路紫,杜欣儒,等.城市区域(超)低空空域无人机活动通道划设规则与方法[J].地球科学进展,2016,31(11):1197-1204.

[Bai L, Lu Z, Du X R.Rules and methods of UAV activities' aerial lanes design for (ultra) low airspace in regional areas[J]. Advances in Earth Science, 2016,31(11):1197-1204. ]

[12]
廖小罕,徐晨晨,岳焕印.基于地理信息的无人机低空公共航路[J].无人机,2018(2):45-49.

[Liao X H, Xu C C, Yue H Y.Research on UAV low-altitude public air route planning based on geographic information[J]. Unmanned Vehicles, 2018(2):45-49. ]

[13]
中国科学院地理科学与资源研究所. “中科天网”无人机综合管理云系统正式获得中国民用航空局批准运行.2019-04-17[EB/OL].

[Institute of Geographic Science and Natural Resources Research, Chinese Academy of Science.The Integrated Management Cloud System for UAVs (named “Zhongke Skynet”) was officially empowered for trial operation by the Civil Aviation Administration of China (CAAC). 2019-04-17 [EB/OL]..]

[14]
Zammit C, Van Kampen E J. "Comparison between A* and RRT Algorithms for UAV Path Planning"[C].2018AIAA Guidance, Navigation, and Control Conference, AIAA SciTech Forum, Kissimmee, Florida, USA, 1846.

[15]
Silva Arantes J, Silva Arantes M, Motta Toledo C F, et al. Heuristic and genetic algorithm approaches for UAV path planning under critical situation[J].International Journal on Artificial Intelligence Tools, 2017,26(01):1-30.

[16]
Chen Y, Luo G, Mei Y, et al.UAV path planning using artificial potential field method updated by optimal control theory[J]. International [J].urnal of Systems Science, 2016,47(6):1407-1420.

[17]
Dorigo M.Optimization, learning and natural algorithms[D]. Italian: Politecnico di Milano, 1992.

[18]
Dorigo M, Maniezzo V, Colorni A.Ant system: An autocatalytic optimizing process[R]. Dipartimento di Elettronica e Informazion. Milano, Italy.Technical Report, 1991.

[19]
林娜,刘二超.基于改进蚁群算法的无人机动态航路规划[J].计算机测量与控制,2016,24(3):149-153.

[Lin N, Liu E C.UAV route planning in dynamic environment based on modified ant colony optimization[J]. Computer Measurement & Control, 2016,24(3):149-153. ]

[20]
Talbi E G, Roux O, Fonlupt C.Parallel ant colonies for the quadratic assignment problem[J]. Future Generation Computer Systems, 2001,17(4):441-449.

[21]
Stützle T, Hoosb H H.MAX-MIN ant system[J]. Future Genetic Computer System, 2000,8(16):889-914.

[22]
曲小康,芮小平,韩莹,等.栅格成本距离计算的改进蚁群方法[J].地球信息科学学报,2016,18(8):1052-1059.<p>栅格数据模型是地理信息科学领域的主要数据模型,成本距离分析是其重要的应用方向之一。但当栅格数据量较大时,传统的Dijkstra求解效率较低,因此本文提出了一种用改进蚁群算法来求解栅格成本距离的方法。首先,构建了适合人工智能算法的栅格数据模型及编码方法;然后,在此基础上初始化蚁群,采用状态概率选择机制计算相邻栅格单元之间距离成本,以及距离成本路径方向选择,同时利用改进的信息素更新机制加强蚁群之间信息交流,加快算法收敛速度;最后,引入了遗传算法的选择、交叉和变异等算子优化生产的成本距离的解,增加解的全局性。本文以北极地区的海冰密集度栅格数据为基础,求解北极地区适合航行路线的成本距离。实验表明,结合了蚁群算法和遗传算法优势的改进蚁群算法,能够快速有效地求解出基于栅格数据的成本距离。</p>

DOI

[Qu X K, Rui X P, Han Y, et al.A method of computing raster cost distance based on the improved ant colony algorithm[J]. Journal of Geo-information Science, 2016,18(8):1052-1059. ]

[23]
AlShawi I S, Yan L, Pan W, et al. Lifetime enhancement in wireless sensor networks using fuzzy approach and A-star algorithm[C]. IET conference on wireless sensor systemsLondon,UK, 2012.

[24]
赵峰,杨春曦,陈飞,等.自适应搜索半径蚁群动态路径规划算法[J].计算机工程与应用,2018,54(19):56-87.

[Zhao F, Yang C X, Chen F, et al.Self-adjust searching radius dynamic planning algorithm based on ant colony algorithm[J]. Computer Engineering and Applications, 2018,54(19):56-87. ]

[25]
国家气象中心.中国地面累年值月值数据集(1981-2010年).[EB/OL]..

[National Meteorological Information Center. Dataset of monthly surface observation values in individual years (1981-2010) in China. ]

[26]
中国民用航空局.低空联网无人机安全飞行测试报告. 2018-02-06[EB/OL]

[Civil Aviation Administration of China (CAAC). Safety flight test report of low-altitude networked UAVs. 2018-02-06[EB/OL].]

[27]
资源环境数据云平台.中国人口空间分布公里网格数据集.[EB/OL].. DOI:10.12078/2017121101.

[Resources and Environment Data Cloud Platform, Gridded dataset of Chinese population spatial distribution at 1kilometer resolution. [EB/OL].DOI:10.12078/2017121101]

[28]
中国民用航空局.关于公布民用机场障碍物限制面范围的公告.2017-05-17[EB/OL].

[Civil Aviation Administration of ChinaAnnouncement on the restricted area of obstacles in civil airports. 2017-05-17[EB/OL]. ]

[29]
中华人民共和国科学技术部国家遥感中心.无人机遥感系统信息库[EB/OL]. 2019. .

[National Remote Sensing Center of China. Information base of uav remote sensing system[EB/OL].2019.]

[30]
王文杰. 5G技术的发展与运用[J].现代工业经济和信息化,2018(5):82-83.21世纪是科技快速发展的时期,通讯技术也在不断变革,人们对通讯的需求也日益增长,通讯的5G时代即将来临。首先对5G技术的发展路径、技术特点与未来的应用领域进行研究,然后探讨5G的商业化和工业化价值,5G技术将会带动一系列高新技术领域的发展。

DOI

[Wang W J.Discussion on the development and application of 5G technology[J]. Modern Industrial Economy and Informationization, 2018(5):82-83. ]

Options
文章导航

/

〈 〉