文章快速检索 高级检索

1. 沈阳航空航天大学 自动化学院, 沈阳 110136;
2. 北京航空航天大学 无人驾驶飞行器设计研究所, 北京 100191

Path planning for UAV under three-dimensional real terrain in rescue mission
LIANG Xiao1 , WANG Honglun2, MENG Guanglei1, CHEN Xia1
1. School of Automation, Shenyang Aerospace University, Shenyang 110136, China;
2. Research Institute of Unmanned Aerial Vehicle, Beijing University of Aeronautics and Astronautics, Beijing 100191, China
Abstract:Basing on the capability of three-dimensional flight and planning of optimal path, unmanned aerial vehicles (UAVs) can reach the disaster areas within shorter time than ground vehicles, which will improve the efficiency of rescue. Firstly, according to the real geographical environment, terrain is modeled by a mesh uniform method based on UAV constraints. Secondly, a data structure which is suitable for calculation is designed based on the characteristics of terrain data. Finally, the integrative performance function includes the deviation cost, height cost, terrain following/avoidance cost, threat cost and security distance cost. Both methods of waypoints cross and grid search instead of waypoints are engaged in the improved ant colony algorithm to make three-dimensional UAV path planning. The simulation results show that the method can deal with three-dimensional terrain data directly. While maintaining the topography of the premise, it can find the three-dimensional optimal path of UAV and improve the practical value of path planning technology.
Key words: unmanned aerial vehicle (UAV) rescue     three-dimensional path planning     ant colony algorithm     digital map     real terrain

2008-05-12中国汶川发生了里氏8.0级的地震,带来了巨大的人员伤亡和经济损失,尽管及时抢修了道路,但是地面救援仍然无法在第一时间到达核心灾区.无人机的低成本特点以及三维飞行能力,使其在空中救援方面优于地面救援[1],无人机按照规划的最优路径飞行能够在最短的时间到达救援区域,许多学者在这方面展开了研究.

1 数字地图的预处理

2 满足无人机约束的均匀化网格地形建模 2.1 无人机约束的处理

 图 1 基于无人机约束的二维栅格模型示意图 Fig. 1 Schematic diagram of two-dimensional grid model based on UAV constraints
2.2 均匀化栅格地形

2.3 满足航路计算的地形数据结构设计

H为地形高度表,用H(zi,zj)表示网格(zi,zj)处的垂向高度,其中zi=1,2，…，P,zj=1,2，…，Q.三维网格地形如图 2所示,图中α为垂向爬升角,θ为水平面内的转弯角.设无人机当前所在的网格点为O,则根据无人机约束,下一时刻的可行网格点为ABCDO′.

 图 2 基于无人机约束的三维地形网格模型示意图 Fig. 2 Schematic diagram of three-dimensional terrain grid model based on UAV constraints

Δz为垂向网格点间距.结合前文的定义可知:Δx=OO′y=O′B=O′Dz=O′A=O′C.根据无人机约束设计的地形数据结构,可以确保在此基础上规划出的航路对于无人机是可行的.

3 改进的三维蚁群航路规划方法

3.1 性能优化指标设计

3.2 路径交叉方法

 图 3 航路交叉示意图 Fig. 3 Schematic diagram of path crossing

3.3 网格搜索代替航路点搜索

 图 4 栅格转移示意图 Fig. 4 Schematic diagram of grid transforming

4 仿真与分析 4.1 数字地图的预处理

1) 美国国家地质勘探局:http://www.usgs.gov/

2) 中国国家基础地理信息系统: http://nfgis.nsdi.gov.cn/asp/userinfo.asp

3) SRTM下载:http://srtm.csi.cgiar.org/

WEST=96°03′19.872 2″

NORTH=35°07′48.041 1″

EAST=108°55′48.839 0″

SOUTH=29°52′11.958 8″

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 截取后的汶川数字地图 Fig. 5 Digital map of Wenchuan after interception

 图 6 网格点均匀化栅格地图 Fig. 6 Grid map after grid points homogenization
4.2 基于改进蚁群算法的无人机航路规划

 图 7 基于改进蚁群算法的三维航路规划 Fig. 7 Three-dimensional path planning based on

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

#### 文章信息

LIANG Xiao, WANG Honglun, MENG Guanglei, CHEN Xia

Path planning for UAV under three-dimensional real terrain in rescue mission

Journal of Beijing University of Aeronautics and Astronsutics, 2015, 41(7): 1183-1187.
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0479