| Citation: | PAN D，ZHENG J H，GAO D. Fast 3D path planning of UAV based on 2D connected graph[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（12）：3419-3431 （in Chinese） doi: 10.13700/j.bh.1001-5965.2022.0147
|
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.
| [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).
|
Figures(21) / Tables(5)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
