基于二维连通图的无人机快速三维路径规划

潘登; 郑建华; 高东

doi:10.13700/j.bh.1001-5965.2022.0147

基于二维连通图的无人机快速三维路径规划

doi: 10.13700/j.bh.1001-5965.2022.0147

潘登^{1, 2},
郑建华^{1, 2},
高东^{1, 2, ,}

1.
中国科学院国家空间科学中心复杂航天系统电子信息技术重点实验室，北京 100190
2.
中国科学院大学，北京 101407

详细信息

通讯作者:
E-mail： gaodong@nssc.ac.cn

中图分类号: V279
计量
- 文章访问数: 902
- HTML全文浏览量: 77
- PDF下载量: 26
- 被引次数: 0
出版历程
- 收稿日期: 2022-03-14
- 录用日期: 2022-05-13
- 网络出版日期: 2022-08-29
- 整期出版日期: 2023-12-29

Fast 3D path planning of UAV based on 2D connected graph

PAN Deng^{1, 2},
ZHENG Jianhua^{1, 2},
GAO Dong^{1, 2
, ,}

1.
Key Laboratory of Electronics and Information Technology for Space Systems，National Space Science Center， Chinese Academy of Sciences，Beijing 100190，China
2.
University of Chinese Academy of Sciences，Beijing 101407，China

More Information

Corresponding author: E-mail：gaodong@nssc.ac.cn

摘要

摘要:
针对复杂真实环境下无人机三维路径规划解算速度慢的问题，提出一种基于二维连通图的快速三维路径规划方法。首先解析真实地理环境的地形特征和建筑要素，构建基于数字高程模型（DEM）的多层次等效三维数字地图；在此基础上，经过无人机可行空域到二维连通图的转化、连通图中的路径规划及路径的三维化与优化，快速获得一条可执行的三维路径。针对连通图中的全局路径规划，设计了一种基于步长地图的变步长稀疏A*算法，在保证路径质量的同时有效降低路径搜索的时间；针对连通图中的局部路径规划，提出一种基于障碍预测的随机路标图（PRM）实时路径重规划算法，以满足无人机的实时性避障需求。分别在山地环境和城市环境中进行仿真飞行，结果表明：所提方法能够有效降低三维路径规划的解算难度，在短时间内完成复杂环境下不同尺度和需求的路径规划，全局路径规划算法同比三维A*算法和基于二维连通图的二维A*算法搜索时间分别降低了99%和95%，局部路径重规划算法能够在1 s的单次采样周期内完成路径重规划，实时躲避未知障碍物，保证飞行过程的安全。
- 无人机 /
- 数字高程模型 /
- 连通图 /
- 三维路径规划 /
- A*算法 /
- 实时避障 /
- 随机路标图算法
Abstract:
A fast 3D path planning method based on a 2D connected graph is proposed in order to address the issue of the unmanned aerial vehicle 3D path planning problem's slow problem-solving speed in a complicated real environment. In order to create a multi-level equivalent 3D digital map based on digital elevation model, it is first necessary to analyze the topographic features and architectural components of the actual geographic environment. Based on this analysis, a 2D connected graph is transformed into a 3D connected graph, which is then transformed into and optimized in 3D. For global path planning in a connected graph, a sparse A* search algorithm with changeable steps based on a step size map is designed, which can effectively reduce the path search time while ensuring the quality of path. For local path planning in connected graphs, a real-time path replanning algorithm using probabilistic roadmap method based on obstacle prediction is proposed to meet the real-time obstacle avoidance requirements of UAVs. The simulation flight is carried out in a mountain scene and an urban scene respectively, the results show that the proposed method can effectively reduce the difficulty of solving 3D path planning and complete the path planning of different scales and requirements in a complex environment in a short time; compared with the 3D A* algorithm and the 2D A* algorithm based on 2D connected graph, global path planning algorithm reduces the search time by 99% and 95% respectively, local path replanning algorithm can complete the path replanning in a single sampling period of 1 s, avoid unknown obstacles in real-time and ensure the safety of the flight process.
- unmanned aerial vehicle /
- digital elevation model /
- connected graph /
- 3D path planning /
- A* algorithm /
- real time obstacle avoidance /
- probabilistic roadmap algorithm

HTML全文

图 1 规则格网模型DEM的示意图

Figure 1. Schematic diagram of DEM of regular grid model

下载: 全尺寸图片幻灯片

图 2 某区域DEM还原地图

Figure 2. DEM-reduced map of a region

下载: 全尺寸图片幻灯片

图 3 DXF中“buildings”图层示意图

Figure 3. Schematic diagram of “buildings”layer in DXF files

下载: 全尺寸图片幻灯片

图 4 “bulidings”图层转化为DEM地图示意图

Figure 4. Schematic diagram of converting “buildings” layer to DEM map

下载: 全尺寸图片幻灯片

图 5 MAP2图层示意图

Figure 5. Schematic diagram of MAP2 layer

下载: 全尺寸图片幻灯片

图 6 等效三维地图

Figure 6. Equivalent 3D map

下载: 全尺寸图片幻灯片

图 7 本文方法流程

Figure 7. Flow chart of proposed method

下载: 全尺寸图片幻灯片

图 8 生成二维连通图示意图

Figure 8. Schematic diagram of generating 2D connectivity diagram

下载: 全尺寸图片幻灯片

图 9 变步长示意图

Figure 9. Schematic diagram of variable step size

下载: 全尺寸图片幻灯片

图 10 转化为三维路径的示意图

Figure 10. Schematic diagram of converting to 3D path

下载: 全尺寸图片幻灯片

图 11 路径修剪示意图

Figure 11. Schematic diagram of path pruning

下载: 全尺寸图片幻灯片

图 12 基于二维连通图的局部路径重规划流程

Figure 12. Flow chart of path replanning based on 2D connected graph

下载: 全尺寸图片幻灯片

图 13 障碍预测示意图

Figure 13. Schematic diagram of obstacle prediction

下载: 全尺寸图片幻灯片

图 14 重规划区域示意图

Figure 14. Schematic diagram of replanning area

下载: 全尺寸图片幻灯片

图 15 连通图中路径规划结果对比

Figure 15. Comparison of path planning results in connectivity graph

下载: 全尺寸图片幻灯片

图 16 三维A*算法和本文算法对比

Figure 16. Comparison of 3D A* algorithm and proposed algorithm

下载: 全尺寸图片幻灯片

图 17 山地场景的全局路径规划

Figure 17. Global path planning in mountain scenes

下载: 全尺寸图片幻灯片

图 18 山地场景的路径重规划

Figure 18. Path replanning in mountain scenes

下载: 全尺寸图片幻灯片

图 19 城市场景的全局路径规划

Figure 19. Global path planning in urban scenes

下载: 全尺寸图片幻灯片

图 20 三维路径优化过程

Figure 20. The process of 3D path optimization

下载: 全尺寸图片幻灯片

图 21 城市场景的路径重规划

Figure 21. Path replanning in urban scenes

下载: 全尺寸图片幻灯片

表 1 DXF文件中楼房建筑的部分组码

Table 1. Partial grouping codes of “buildings ”layer in DXF files

组码	说明
0	图元类型（网格图元MESH）
8	图层名（buildings）
100	子类标记
92	0级顶点数
10	顶点位置x
20	顶点位置y
30	顶点位置z

下载: 导出CSV

表 2 二维路径规划算法对比

Table 2. Comparison of 2D path planning algorithms

规划算法	参数设置	路径长度/pix	规划时间/s
A*算法	步长1像素	918.1800	10.9231
Bi-RRT算法	步长20像素	1083.9088	0.0885
VORONOI算法		1122.6981	0.1100
PRM算法	采样点数200	1076.2962	4.3746
GA	种群数200，代数300	1579.1426	71.7549
本文算法	步长1~20像素	950.2214	0.3706

下载: 导出CSV

表 3 三维路径规划算法对比

Table 3. Comparison of 3D path planning algorithms

规划算法	修剪	路径长度/像素	规划时间 /s
三维A*算法	否	223.443	329.9670
三维A*算法	是	214.4229	330.2463
本文算法	否	295.8179	0.910911
本文算法	是	205.6610	0.988584

下载: 导出CSV

表 4 山地场景的全局路径规划

Table 4. Global path planning in mountain scenes

路线编号	终点坐标/像素	路径长度/像素	规划时间 /s
1	（630,350,270）	710.9418	1.0469
2	（140,330,300）	464.0216	1.9923
3	（630,70,250）	576.6748	0.8638

下载: 导出CSV

表 5 城市场景的全局路径规划

Table 5. Global path planning in urban scenes

路线编号	终点坐标/像素	路径长度/像素	规划时间/s
1	（1200,730,55）	1408.0388	5.2401
2	（530,600,95）	773.1240	1.6845
3	（145,705,160）	694.6993	0.6461

下载: 导出CSV

参考文献(28)

[1]	张宏宏, 甘旭升, 李双峰, 等. 复杂低空环境下考虑区域风险评估的无人机航路规划[J]. 仪器仪表学报, 2021, 42(1): 257-266. doi: 10.19650/j.cnki.cjsi.J2007192 ZHANG H H, GAN X S, LI S F, et al. UAV route planning considering regional risk assessment under complex low altitude environment[J]. Chinese Journal of Scientific Instrument, 2021, 42(1): 257-266(in Chinese). doi: 10.19650/j.cnki.cjsi.J2007192
[2]	张广林, 胡小梅, 柴剑飞, 等. 路径规划算法及其应用综述[J]. 现代机械, 2011(5): 85-90. doi: 10.3969/j.issn.1002-6886.2011.05.031 ZHANG G L, HU X M, CHAI J F, et al. Summary of path planning algorithm and its application[J]. Modern Machinery, 2011(5): 85-90(in Chinese). doi: 10.3969/j.issn.1002-6886.2011.05.031
[3]	WANG H L, LYU W T, YAO P, et al. Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system[J]. Chinese Journal of Aeronautics, 2015, 28(1): 229-239. doi: 10.1016/j.cja.2014.12.031
[4]	杜云, 彭瑜, 邵士凯, 等. 基于改进粒子群优化的多无人机协同航迹规划[J]. 科学技术与工程, 2020, 20(32): 13258-13264. doi: 10.3969/j.issn.1671-1815.2020.32.025 DU Y, PENG Y, SHAO S K, et al. Cooperative path planning of multi-unmanned aerial vehicle based on improved particle swarm optimization[J]. Science Technology and Engineering, 2020, 20(32): 13258-13264(in Chinese). doi: 10.3969/j.issn.1671-1815.2020.32.025
[5]	封硕, 舒红, 谢步庆. 基于改进深度强化学习的三维环境路径规划[J]. 计算机应用与软件, 2021, 38(1): 250-255. doi: 10.3969/j.issn.1000-386x.2021.01.042 FENG S, SHU H, XIE B Q. 3d environment path planning based on improved deep reinforcement learning[J]. Computer Applications and Software, 2021, 38(1): 250-255(in Chinese). doi: 10.3969/j.issn.1000-386x.2021.01.042
[6]	张鑫. 基于规则DEM的地形识别及路径规划研究[D]. 桂林: 桂林电子科技大学, 2017: 6-8. ZHANG X. Research on terrain recognition and path planning based on regular DEM[D]. Guilin: Guilin University of Electronic Technology, 2017: 6-8(in Chinese).
[7]	李东正. 复杂环境下多机器人路径规划方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2015: 49-55. LI D Z. Research on problems of multi-robots path planning under complicated environment[D]. Harbin: Harbin Engineering University, 2015: 49-55(in Chinese).
[8]	张启钱, 许卫卫, 张洪海, 等. 复杂低空物流无人机路径规划[J]. 北京航空航天大学学报, 2020, 46(7): 1275-1286. doi: 10.13700/j.bh.1001-5965.2019.0455 ZHANG Q Q, XU W W, ZHANG H H, et al. Path planning for logistics UAV in complex low-altitude airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(7): 1275-1286(in Chinese). doi: 10.13700/j.bh.1001-5965.2019.0455
[9]	PRIMATESTA S, GUGLIERI G, RIZZO A. A risk-aware path planning strategy for UAVs in urban environments[J]. Journal of Intelligent & Robotic Systems, 2019, 95(2): 629-643.
[10]	贾广芝. 基于遗传算法和稀疏A算法的无人机三维航迹规划研究[D]. 南京: 南京邮电大学, 2017: 21-46. JIA G Z. Research on three-dimensional path planning of UAV based on genetic algorithm and sparse A algorithm[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2017: 21-46(in Chinese).
[11]	唐龙伟. 真实DEM地图下一种航迹规划算法的研究和应用[D]. 成都: 电子科技大学, 2014: 16-17. TANG L W. Research and implementation of trajectory planning in real DEM maps based on milp[D]. Chengdu: University of Electronic Science and Technology of China, 2014: 16-17 (in Chinese).
[12]	张顺, 谢习华, 陈定平. 基于改进RRT-Connect的无人机航迹规划算法[J]. 传感器与微系统, 2020, 39(12): 146-148. doi: 10.13873/J.1000-9787(2020)12-0146-03 ZHANG S, XIE X H, CHEN D P. UAV path planning algorithm based on improved RRT-Connect[J]. Transducer and Microsystem Technologies, 2020, 39(12): 146-148(in Chinese). doi: 10.13873/J.1000-9787(2020)12-0146-03
[13]	YANG L, QI J T, XIAO J Z, et al. A literature review of UAV 3D path planning[C]// Proceeding of the 11th World Congress on Intelligent Control and Automation. Piscataway: IEEE Press, 2015: 2376-2381.
[14]	谭建豪, 肖友伦, 刘力铭, 等. 改进PRM算法的无人机航迹规划[J]. 传感器与微系统, 2020, 39(1): 38-41. doi: 10.13873/J.1000-9787(2020)01-0038-04 TAN J H, XIAO Y L, LIU L M, et al. Improved PRM algorithm for path planning of UAV[J]. Transducer and Microsystem Technologies, 2020, 39(1): 38-41(in Chinese). doi: 10.13873/J.1000-9787(2020)01-0038-04
[15]	RUAN S P, MA Q L, POBLETE K L, et al. Path planning for ellipsoidal robots and general obstacles via closed-form characterization of minkowski operations[C]//International Workshop on the Algorithmic Foundations of Robotics. Berlin: Springer, 2020: 3-18.
[16]	陈都, 孟秀云. 基于改进ARA算法的无人机在线航迹规划[J]. 飞行力学, 2021, 39(1): 60-65. doi: 10.13645/j.cnki.f.d.20201112.002 CHEN D, MENG X Y. UAV online path planning based on improved ARA algorithm[J]. Flight Dynamics, 2021, 39(1): 60-65(in Chinese). doi: 10.13645/j.cnki.f.d.20201112.002
[17]	中国科学院计算机网络信息中心. 地理空间数据云 [DB/OL]. (2021-06-11) [2021-06-11]. http://www.gscloud.cn. Computer Network Information Center, Chineses Acadamy of Sciences. Geospatial data clond[DB/OL]. (2021-06-11) [2021-06-11]. http://www.gscloud.cn(in Chinese).
[18]	OpenStreetMap. Instant CAD files for any location on earth [DB/OL]. (2021-06-11) [2021-06-11].https://cadmapper.com.
[19]	Autodesk. AutoCAD 2011 support[EB/OL]. (2021-06-11)[2021-06-11]. http://docs.autodesk.com/ACD/2011/CHS/landing.html.
[20]	张胜祥. 基于滚动时域MILP的小型无人机航迹规划[D]. 广州: 华南理工大学, 2009: 19-21. ZHANG S X. Path planning of small-scale unmanned helicopters using receding horizon MILP[D]. Guangzhou: South China University of Technology, 2009: 19-21(in Chinese).
[21]	全权, 李刚, 柏艺琴, 等. 低空无人机交通管理概览与建议[J]. 航空学报, 2020, 41(1): 023238. QUAN Q, LI G, BAI Y Q, et al. Low altitude UAV traffic management: an introductory overview and proposal[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(1): 023238(in Chinese).
[22]	SZCZERBA R J, GALKOWSKI P, GLICKTEIN I S, et al. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems, 2000, 36(3): 869-878. doi: 10.1109/7.869506
[23]	黄文刚, 张怡, 姜文毅, 等. 变步长稀疏A^*算法的无人机航路规划[J]. 计算机工程与应用, 2012, 48(29): 206-209. doi: 10.3778/j.issn.1002-8331.2012.29.042 HUANG W G, ZHANG Y, JIANG W Y, et al. SAS algorithm with changeable steps for route planning of UAVs[J]. Computer Engineering and Applications, 2012, 48(29): 206-209(in Chinese). doi: 10.3778/j.issn.1002-8331.2012.29.042
[24]	王生印, 龙腾, 王祝, 等. 基于即时修复式稀疏A^算法的动态航迹规划[J]. 系统工程与电子技术, 2018, 40(12): 2714-2721. doi: 10.3969/j.issn.1001-506X.2018.12.14 WANG S Y, LONG T, WANG Z, et al. Dynamic path planning using anytime repairing sparse A^ algorithm[J]. Systems Engineering and Electronics, 2018, 40(12): 2714-2721(in Chinese). doi: 10.3969/j.issn.1001-506X.2018.12.14
[25]	GOSS K, MUSMECI R, SILVESTRI S. Realistic models for characterizing the performance of unmanned aerial vehicles[C]// 2017 26th International Conference on Computer Communication and Networks (ICCCN). Piscataway: IEEE Press, 2017: 1-9.
[26]	KAVRAKI L, LATOMBE J C. Randomized preprocessing of configuration for fast path planning[C]// Proceedings of the 1994 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2002: 2138-2145.
[27]	Rahal Kala. Source codes[DB/OL]. (2021-06-11)[2021-06-11]. http://rkala.in/codes.php.
[28]	何雨枫. 室内微小型无人机路径规划算法研究[D]. 南京: 南京航空航天大学, 2014: 40-45. HE Y F. Research on indoor MUAV path planning[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2014: 40-45(in Chinese).