2. 北京航空航天大学 无人驾驶飞行器设计研究所, 北京 100191
2. Research Institute of Unmanned Aerial Vehicle, Beijing University of Aeronautics and Astronautics, Beijing 100191, China
2008-05-12中国汶川发生了里氏8.0级的地震,带来了巨大的人员伤亡和经济损失,尽管及时抢修了道路,但是地面救援仍然无法在第一时间到达核心灾区.无人机的低成本特点以及三维飞行能力,使其在空中救援方面优于地面救援[1],无人机按照规划的最优路径飞行能够在最短的时间到达救援区域,许多学者在这方面展开了研究.
为了最大限度地发挥飞行优势,面向救援任务的无人机航路规划集中在三维空间,因此传统的二维航路规划方法比如人工势场法[2]、RRT(Rapidly exploring Random Tree)法[3]等受到限制.三维救援搜索中,应用最广泛的一类方法是A*方法.通过与局部算法的组合,A*还能完成未知环境下的三维航路搜索[4, 5].但是A*方法只能保证距离上的最短,无法兼顾其他性能指标,因此多目标优化方法逐渐引起学者们的兴趣.利用蚁群方法能够找到最优的三维航路并具有鲁棒性,但是受地形建模的方式影响很大[6].根据经验定义搜索域,通过改进编码方式和算法结构,Sullivan等实现了遗传方法的多目标同时优化[7].粒子群算法计算速度快,通过对粒子的改进能够具备一定鲁棒性,并成功规划出适于可变形机器人的光滑航路[8].为降低大尺度规划空间的算法时空开销,房建成等建立了基于MDP(Markov Decision Processes)的全局路径规划模型,并将其拓展到三维规划中,但是仿真地形较为简单[9].
尽管在无人机三维航路规划方面的研究取得了很大进展,但是必须要面对的问题是:算法的优越性如何使其在实际的应用中发挥真实作用.该问题的解决涉及两个方面:首先,算法在设计阶段应该考虑无人机物理约束[10],否则无人机无法按照规划出的航路进行飞行,航路规划就失去了本来的意义.其次,算法的应用不能仅停留在虚拟地形的仿真阶段,要使其能够真实地作用于实际的数字地图,将无人机导引至救援区域.
针对救援任务中无人机的三维航路规划问题,本文提出了一种适合三维真实地形的无人机航路规划方法.该方法在满足无人机约束的前提下,进行数字地图的预处理,完成均匀网格划分,并设计了地形数据的数据结构,最后提出改进的蚁群算法进行三维航路规划,得到适合无人机飞行的最优航路.
1 数字地图的预处理能够处理真实的地形数据,可以提高航路规划算法的实用性.地形数据首先需要进行预处理,包括数字地图获取、地形信息截取、高程信息提取和生成xyz坐标序列4个阶段.
救援区域的经纬度坐标和海拔高程数据可以从各国官方数据库下载.需要注意的是,官方提供的下载数据精度不会很高,并且一般为较大的地形块数据,如果直接对地形块进行操作,会产生许多冗余信息,也会降低预处理的速度.因此需要针对感兴趣的地形部分进行截取,之后提取高程信息数据,这部分操作可以通过编程实现也可以利用Google Earth和Global Mapper等商业软件完成,最后导出由x、y、z组成的三维坐标序列形式的文本文件.
2 满足无人机约束的均匀化网格地形建模 2.1 无人机约束的处理无人机的机动性直接受爬升角、爬升高度、转弯角等多种因素的影响[11],而这种飞行能力对于航路的可行性是很强的约束.在复杂地形环境建模时,通过充分考虑无人机的物理约束,能够避免航路的后处理和二次平滑.
在后续的航路规划过程中,采用蚁群算法进行问题的求解,因此飞行环境建模采用网格式建模方法.首先,三维网格地形的垂向高度需要小于最大爬升高度,爬升角与转弯角相似,分别属于垂向和水平面内的角度机动约束.以水平面内的转弯角为例,当无人机定速飞行时,给定最大过载,能够确定其最小转弯半径,并且满足:
式中:nmax为最大过载;Rmin为最小转弯半径;V为无人机速度；g为重力加速度.根据式(1)进一步求得转弯时的角速度:
则单位时间t内的转弯角为ωt,根据式(1)和式(2)建立二维水平面内满足无人机约束的栅格地形模型如图 1所示.
|
| 图 1 基于无人机约束的二维栅格模型示意图 Fig. 1 Schematic diagram of two-dimensional grid model based on UAV constraints |
经过数字地图预处理后的三维坐标序列能够准确描述地形信息,但直接采用坐标序列进行航路规划会增加计算量,因此需要剔除冗余信息,降低数据点的密度.虽然变精度的栅格能够更好地描述环境和提高算法效率,但是实现起来却十分复杂,目前的航路规划方法主要以均匀网格数据表示地形.均匀化过程是对三维坐标序列的等间隔取点,如果没有数据点则要通过其邻域内的点进行曲线拟合完成,并且均匀化后的栅格地形要保证栅格密度满足2.1节的无人机约束要求.
2.3 满足航路计算的地形数据结构设计设地形的x和y方向分别有网格点P个和Q个,网格点间距分别为Δx和Δy.用L代表地形x方向的长度,W代表地形y方向的长度,则有
设H为地形高度表,用H(zi,zj)表示网格(zi,zj)处的垂向高度,其中zi=1,2，…，P,zj=1,2，…，Q.三维网格地形如图 2所示,图中α为垂向爬升角,θ为水平面内的转弯角.设无人机当前所在的网格点为O,则根据无人机约束,下一时刻的可行网格点为A、B、C、D和O′.
|
| 图 2 基于无人机约束的三维地形网格模型示意图 Fig. 2 Schematic diagram of three-dimensional terrain grid model based on UAV constraints |
根据图 2,可以得到如下结论:
Δz为垂向网格点间距.结合前文的定义可知:Δx=OO′,Δy=O′B=O′D,Δz=O′A=O′C.根据无人机约束设计的地形数据结构,可以确保在此基础上规划出的航路对于无人机是可行的.
3 改进的三维蚁群航路规划方法在寻找食物源时,作为蚂蚁能在其走过的路径上释放一种蚂蚁特有的化学物质——生物信息激素,经过众多蚂蚁的协同搜寻过后,几乎所有的蚂蚁都会走最短的那一条路径[12].蚁群算法的研究内容很多,其基本原理描述可以参考文献[13].下面主要介绍对蚁群算法的主要改进内容.
3.1 性能优化指标设计性能优化指标,代表着航路的搜索趋势,或者说最终搜索出的较优/最优航路将具备的特征.设一条航路由N条航路段和N+1个航路点组成,第i和第i+1个航路点组成的航路段,由li表示,则代价指标定义为
式中:Di为当前航路点偏离起始点与目标点连线的距离,即航向偏离代价,此代价一般对应燃油代价,偏离越大,航路越长;Hi为UAV经过航路点时的飞行高度,由于地形是离散的,因此采用该航路点的高度Hi代表该航段li的飞行高度;Fi为地面信息的离散值惩罚,当Fi值越大,说明地形越复杂,高低起伏变化越大,不适合UAV进行地形跟随/回避飞行;Ti为网格点的危险系数,如果网格点距离该点地势的海拔高度越小,Ti越大;Si为安全距离指标,Si的值与无人机和障碍之间的距离成反比:Si=c/dmini,其中c为比例系数,dmini为li上每一点到障碍距离的最小值;wd、wh、wr、wt、ws分别是Di、Hi、Fi、Ti、Si的加权系数.
3.2 路径交叉方法路径交叉适用于两条航路存在共同航路点时的情况,如图 3所示.设a1和a2属于当前全局最优航路,a3和a4属于本次搜索的局部最优航路.从两条航路中随机选取某一交叉航路点,使用路径交叉方法,生成两条新的航路,它们分别为a1、a4与a3、a2.
|
| 图 3 航路交叉示意图 Fig. 3 Schematic diagram of path crossing |
将两条新生成航路的代价与前次全局最优航路比较,如果新生成航路较优,则替换原全局最优航路,否则不变.航路交叉方法的思想,是将遗传算法中的交叉操作[14]引入蚁群算法,这种做法可以有效地增加解空间的多样性,避免局部极小,并在很大程度上加快了蚁群算法的收敛速度.
3.3 网格搜索代替航路点搜索本文所采用的地形是大比例尺的复杂真实地形环境,航路计算时需要存储的栅格点数量巨大,因此存在组合爆炸问题[15].针对这种情况,把地图中相邻的小栅格合并成大的栅格,以栅格为单位代替航路点记录环境信息.使用栅格作为搜索单位,在计算航路代价时必须考虑拐角代价的计算问题,如图 4所示.
|
| 图 4 栅格转移示意图 Fig. 4 Schematic diagram of grid transforming |
平行的两个栅格之间形成的航路带代价值可以直接由栅格上的代价函数相加得到,即J(a11→a12)=Ja11+Ja12.当两个栅格不平行时,会出现拐角栅格转移的情况.针对图 4,当UAV从栅格c12飞行到c21时,如果把飞行航路确定为经过c12和c21的交点,而且恰巧交点是山峰或者威胁点,易造成UAV撞山或者进入危险区,因此需要对拐角栅格进行处理.保留c11和c22栅格的一半,连接c12和c21,并以此形成航路带.计算拐角代价时,首先计算c11和c22的半栅格代价,之后计算c12到c21的代价值:J(c12→c21)=Jc12+Jc21+(Jc11+Jc22)/2.
4 仿真与分析 4.1 数字地图的预处理这里给出3种下载数字地图的官方数据库:
1) 美国国家地质勘探局:http://www.usgs.gov/
2) 中国国家基础地理信息系统: http://nfgis.nsdi.gov.cn/asp/userinfo.asp
3) SRTM下载:http://srtm.csi.cgiar.org/
本节仿真部分使用的数字地图从SRTM下载,得到汶川地区的tif格式地形数据,经纬度信息为
WEST=96°03′19.872 2″
NORTH=35°07′48.041 1″
EAST=108°55′48.839 0″
SOUTH=29°52′11.958 8″
利用Global Mapper对该地块的数字地图进行截取后,经纬度信息为
WEST=104°06′30.161 7″
NORTH=31°44′43.865 7″
EAST=105°14′57.432 0″
SOUTH=31°16′45.821 7″
截取后的汶川数字地图如图 5所示.
|
| 图 5 截取后的汶川数字地图 Fig. 5 Digital map of Wenchuan after interception |
采用本项目编写的地形预处理软件,针对截取后的汶川数字地图生成等高线,之后导出该数字地图对应的三维坐标序列,采用2.1和2.2节的方法根据无人机约束进行网格均匀化处理,图 6为剔除冗余信息后,网格点均匀化栅格地形.
|
| 图 6 网格点均匀化栅格地图 Fig. 6 Grid map after grid points homogenization |
将均匀化后的栅格地形导出为N行3列的文本文件,第1列为网格点的x坐标,第2列为网格点的y坐标,第3列为网格点的z坐标,N为栅格地形的所有网格点数.根据式(3)将网格点与高度表进行对应得到高度表矩阵H(zi,zj),其中zi=1,2，…，P,zj=1,2，…，Q.蚂蚁数量M=300,无人机在网格坐标中的起点为(1,Q/2,H(1,Q/2)+Δz),在网格坐标中的终点为(P,Q/2,H(P,Q/2)+Δz).式(6)中系数wd=0.4,wh=0.2,wr=0.2,wt=0.1,ws=0.1,将第3节改进的蚁群算法应用于4.1节的汶川灾区实际地形后(按比例1∶22缩放),规划出的无人机航路如图 7所示.
|
| 图 7 基于改进蚁群算法的三维航路规划 Fig. 7 Three-dimensional path planning based on |
由于式(6)的性能指标函数中最大的系数为wd=0.4,因此从图 7可以看出,路径最短是算法首要考虑的因素,因此航路不会过度地偏离目标点和终点连线.其次wh=0.2、wr=0.2分别为高度代价系数和地面复杂度系数,两个系数相等，因此算法在搜索最优航路时,垂向和水平方向的搜索权重相同,这使得航路表现出较好的地形跟随/回避特性,如图 7所示.由于栅格地形模型是满足无人机约束的,因此在此基础上规划出的航路是可飞的,并且是最优的,图 7说明本文的方法能够完成真实地形环境下无人机救援航路规划任务.
5 结 论针对三维真实地形环境下的无人机救援航路规划问题,本文提出了一种基于无人机约束的地形数据结构,并采用改进的蚁群算法完成航路规划,根据仿真结果得出以下结论:
1) 数字地图的预处理过程需要借助其他软件,因此算法比较适用于离线航路规划.
2) 该地形数据结构在考虑无人机约束的前提下,能够对三维数字地图实现均匀网格化,便于蚁群、遗传和A*等基于网格的航路规划方法使用.
3) 改进的蚁群方法中高度代价系数和地面复杂度系数对航路地形跟随/地形回避的能力影响较大,因此可根据不同需要进行调整.
| [1] | Zhang X Y, Wu M, Peng J, et al.A rescue robot path planning based on ant colony optimization algorithm[C]//International Conference on Information Technology and Computer Science 2009.Piscataway, NJ: IEEE Press, 2009: 180-183. |
| Click to display the text | |
| [2] | Khanmohammadi S, Zarrin R S.Intelligent path planning for rescue robot[J].World Academy of Science, Engineering and Technology, 2011, 5(7): 607-612. |
| [3] | Norouzi M, Bruijn F D, Miro J V.Planning stable paths for urban search and rescue robots[J].Computer Science, 2012, 7416: 90-101. |
| [4] | Pang T, Ruan X G, Wang E S, et al.Search and rescue robot path planning in unknown environment[J].Applied Mechanics and Materials, 2013, 241: 1682-1687. |
| [5] | Pang T, Ruan X G, Wang E S, et al.Based on A* and Q-learning search and rescue robot navigation[J]. Telkomnika-Indonesian Journal of Electrical Engineering, 2012, 10(7): 1889-1896. |
| Click to display the text | |
| [6] | Sun H L, Yue L Y, Yao S Y.Study on selection of emergency rescue based on GIS[J].Advanced Materials Research, 2014, 864: 2804-2807. |
| [7] | Sullivan T A, Van J D.Multi-objective, multi-domain genetic optimization of a hydraulic rescue spreader[J].Mechanism and Machine Theory, 2014, 80: 35-51. |
| Click to display the text | |
| [8] | Liu T L, Wu C D, Li B, et al.The adaptive path planning research for a shape-shifting robot using particle swarm optimization[C]//International Conference on Natural Computation 2009.Piscataway, NJ: IEEE Press, 2009: 324-328. |
| [9] | 洪晔, 房建成.基于HMDP的无人机三维路径规划[J].北京航空航天大学学报, 2009, 35(1): 100-103. Hong Y, Fang J C.Hierarchical Markov decision processes based path planning for UAV in three-dimensional environment[J].Journal of Beijing University of Aeronautics and Astronautics, 2009, 35(1): 100-103(in Chinese). |
| Click to display the text | |
| [10] | Adolf F M, Hirschmuller H.Meshing and simplification of high resolution urban surface data for UAV path planning[J].Journal of Intelligent and Robotic System, 2011, 61(1): 169-180. |
| [11] | Samar R, Rehman A.Autonomous terrain-following for unmanned air vehicles[J].Mechatronics, 2011, 21(5): 844-860. |
| Click to display the text | |
| [12] | Glabowski M, Musznicki B, Nowak P, et al.An algorithm for finding shortest path tree using ant colony optimization metaheuristic[J].Advances in Intelligent Systems and Computing, 2014, 233: 317-326. |
| Click to display the text | |
| [13] | Kolavali S R, Bhatnagar S.Ant colony optimization algorithms for shortest path problems[J].Computer Science, 2009, 5425: 37-44. |
| Click to display the text | |
| [14] | Roberge V, Tarbouchi M, Labonte G.Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].IEEE Transactions on Industrial Informatics, 2013, 9(1): 132-141. |
| Click to display the text | |
| [15] | Chen M, Wu Q X, Jiang C S.A modified ant optimization algorithm for path planning of UCAV[J].Applied Soft Computing, 2008, 8(4): 1712-1718. |
| Click to display the text |