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

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

作　　者：潘登 郑建华 高东 PAN Deng;ZHENG Jianhua;GAO Dong(Key Laboratory of Electronics and Information Technology for Space Systems,National Space Science Center,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 101407,China)

机构地区：[1]中国科学院国家空间科学中心复杂航天系统电子信息技术重点实验室,北京100190 [2]中国科学院大学,北京101407

出　　处：《北京航空航天大学学报》2023年第12期3419-3431,共13页Journal of Beijing University of Aeronautics and Astronautics

摘　　要：针对复杂真实环境下无人机三维路径规划解算速度慢的问题,提出一种基于二维连通图的快速三维路径规划方法。首先解析真实地理环境的地形特征和建筑要素,构建基于数字高程模型(DEM)的多层次等效三维数字地图;在此基础上,经过无人机可行空域到二维连通图的转化、连通图中的路径规划及路径的三维化与优化,快速获得一条可执行的三维路径。针对连通图中的全局路径规划,设计了一种基于步长地图的变步长稀疏A*算法,在保证路径质量的同时有效降低路径搜索的时间;针对连通图中的局部路径规划,提出一种基于障碍预测的随机路标图(PRM)实时路径重规划算法,以满足无人机的实时性避障需求。分别在山地环境和城市环境中进行仿真飞行,结果表明:所提方法能够有效降低三维路径规划的解算难度,在短时间内完成复杂环境下不同尺度和需求的路径规划,全局路径规划算法同比三维A*算法和基于二维连通图的二维A*算法搜索时间分别降低了99%和95%,局部路径重规划算法能够在1 s的单次采样周期内完成路径重规划,实时躲避未知障碍物,保证飞行过程的安全。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.

关 键 词：无人机 数字高程模型 连通图 三维路径规划 A*算法 实时避障 随机路标图算法 

分 类 号：V279[航空宇航科学与技术—飞行器设计]