电子电气工程与控制

基于剪枝可视性地图的无人机全局规划方法

  • 薛震 ,
  • 盛汉霖 ,
  • 陈欣 ,
  • 魏鹏轩 ,
  • 李嘉诚 ,
  • 陈芊
展开
  • 1.南京航空航天大学 能源与动力学院,南京 210016
    2.南京航空航天大学 通用航空与飞行学院,南京 210016
.E-mail: dreamshl@nuaa.edu.cn

收稿日期: 2024-09-27

  修回日期: 2024-11-03

  录用日期: 2024-12-30

  网络出版日期: 2025-01-10

基金资助

国家自然科学基金面上项目(52176009);国家博士后创新人才支持计划(BX20240481)

Global planning method for UAVs based on pruned visibility map

  • Zhen XUE ,
  • Hanlin SHENG ,
  • Xin CHEN ,
  • Pengxuan WEI ,
  • Jiacheng LI ,
  • Qian CHEN
Expand
  • 1.College of Energy and Power Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
    2.College of General Aviation and Flight,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

Received date: 2024-09-27

  Revised date: 2024-11-03

  Accepted date: 2024-12-30

  Online published: 2025-01-10

Supported by

National Natural Science Foundation of China(52176009);Postdoctoral Innovation Talent Support Program of China(BX20240481)

摘要

针对当前无人机在复杂场景下难以高效构建环境地图和实现远距离全局规划的难题,提出了一种基于概率更新的剪枝可视性地图构建方法和分层规划策略,采用概率更新方式生成栅格地图,通过分层映射提取障碍物边界,结合碰撞检测从而构建出可视性地图。提出一种可视性地图剪枝策略以减小搜索空间,加快路径搜索速度。构建基于搜索和优化的分层规划算法框架,外层规划采用基于探索度的改进A*算法,通过在代价函数中引入路径探索度,显著提升了无人机在复杂场景下的全局规划表现。内层规划则采用基于最小控制量(MINCO)轨迹表示的轨迹优化方法,以生成满足无人机速度、加速度约束的平滑飞行轨迹。最后,通过实验仿真和实飞验证,结果显示,基于剪枝可视性地图的改进A*算法相较传统A*算法,飞行距离减少了12.92%,飞行时间缩短了16.43%,提出的算法能够提升复杂场景下的规划效率和结果最优性。

本文引用格式

薛震 , 盛汉霖 , 陈欣 , 魏鹏轩 , 李嘉诚 , 陈芊 . 基于剪枝可视性地图的无人机全局规划方法[J]. 航空学报, 2025 , 46(10) : 331279 -331279 . DOI: 10.7527/S1000-6893.2024.31279

Abstract

To address the challenge of efficiently constructing environment maps and achieving long-distance global planning for UAVs in complex scenarios, this paper proposes a probabilistic update-based pruning visibility map construction method and a hierarchical planning strategy. The approach generates a grid map through probabilistic updates, extracts obstacle boundaries via hierarchical mapping, and constructs a visibility map with collision detection. A pruning strategy for the visibility map is introduced to reduce the search space and accelerate pathfinding. The hierarchical planning framework is based on search and optimization, where the outer planning layer employs an improved A* algorithm based on exploration degree. By incorporating path exploration degree into the cost function, global planning performance in complex environments is significantly enhanced. The inner planning layer uses trajectory optimization based on Minimum Control Effort (MINCO) trajectory representation to generate smooth flight paths that satisfy UAV speed and acceleration constraints. Experimental simulations and real-flight validations show that compared to the traditional A* algorithm, the proposed pruning visibility map-based improved A* algorithm reduces flight distance by 12.92% and flight time by 16.43%, demonstrating the algorithm’s ability to improve planning efficiency and optimality in complex scenarios.

参考文献

1 AGGARWAL S, KUMAR N. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges[J]. Computer Communications2020149: 270-299.
2 路晶, 史宇, 张书畅, 等. 无人机航迹规划算法综述[J]. 航空计算技术202252(4): 131-134.
  LU J, SHI Y, ZHANG S C, et al. A review of UAV trajectory planning algorithms[J]. Aeronautical Computing Technique202252(4): 131-134 (in Chinese).
3 刘好. 复杂环境下四旋翼无人机航迹规划算法研究[D]. 长沙: 中南大学, 2023:4-8.
  LIU H. Research on path planning algorithm of quadrotor UAV in complex environment[D]. Changsha: Central South University, 2023: 4-8 (in Chinese).
4 YU Z, SUN F C, LU X, et al. Overview of research on 3D path planning methods for rotor UAV[C]∥2021 International Conference on Electronics, Circuits and Information Engineering (ECIE). Piscataway: IEEE Press, 2021: 368-371.
5 刘玄冰, 周绍磊, 肖支才, 等. 无人机避障方法研究综述[J]. 兵器装备工程学报202243(5): 40-47.
  LIU X B, ZHOU S L, XIAO Z C, et al. Review on UAV obstacle avoidance methods[J]. Journal of Ordnance Equipment Engineering202243(5): 40-47 (in Chinese).
6 GOLL S A, LUKSHA S S, LEUSHKIN V S, et al. Unmanned ground vehicle local trajectory planning algorithm[C]∥2016 5th Mediterranean Conference on Embedded Computing (MECO). Piscataway: IEEE Press, 2016: 317-321.
7 贾高伟, 王建峰. 无人机集群任务规划方法研究综述[J]. 系统工程与电子技术202143(1): 99-111.
  JIA G W, WANG J F. Research review of UAV swarm mission planning method?[J]. Systems Engineering and Electronics202143(1): 99-111 (in Chinese).
8 SAADI A AIT, SOUKANE A, MERAIHI Y, et al. UAV path planning using optimization approaches: A survey[J]. Archives of Computational Methods in Engineering202229(6): 4233-4284.
9 ECONOMOU J T, KLADIS G, TSOURDOS A, et al. UAV optimum energy assignment using Dijkstra’s algorithm[C]∥2007 European Control Conference (ECC). Piscataway: IEEE Press, 2007: 287-292.
10 TANG B, HIROTA K, WU X, et al. Path planning based on improved hybrid A* algorithm[J]. Journal of Advanced Computational Intelligence and Intelligent Informatics202125(1): 64-72.
11 TOIBERO J M, ROBERTI F, CARELLI R, et al. Switching control approach for stable navigation of mobile robots in unknown environments[J]. Robotics and Computer-Integrated Manufacturing201127(3): 558-568.
12 WEBB D J, VAN DEN BERG J. Kinodynamic RRT*: Optimal motion planning for systems with linear differential constraints?[DB/OL].arXiv preprint: 1205.5088;2012.
13 许万, 杨晔, 余磊涛, 等. 一种基于改进RRT*的全局路径规划算法[J]. 控制与决策202237(4): 829-838.
  XU W, YANG Y, YU L T, et al. A global path planning algorithm based on improved RRT* [J]. Control and Decision202237(4): 829-838 (in Chinese).
14 张伟民, 付仕雄. 基于改进RRT*算法的移动机器人路径规划[J]. 华中科技大学学报(自然科学版)202149(1): 31-36.
  ZHANG W M, FU S X. Mobile robot path planning based on improved RRT* algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition)202149(1): 31-36 (in Chinese).
15 ZHANG C, HU C X, FENG J R, et al. A self-heuristic ant-based method for path planning of unmanned aerial vehicle in complex 3-D space with dense U-type obstacles[J]. IEEE Access20197: 150775-150791.
16 LEE K, CHOI D, KIM D. Incorporation of potential fields and motion primitives for the collision avoidance of unmanned aircraft[J]. Applied Sciences202111(7): 3103.
17 CHEN X, ZHANG J. The three-dimension path planning of UAV based on improved artificial potential field in dynamic environment[C]∥2013 5th International Conference on Intelligent Human-Machine Systems and Cybernetics. Piscataway: IEEE Press, 2013: 144-147.
18 MELLINGER D, KUMAR V. Minimum snap trajectory generation and control for quadrotors[C]∥2011 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2011: 2520-2525.
19 GAO F, WANG L Q, ZHOU B Y, et al. Teach-repeat-replan: A complete and robust system for aggressive flight in complex environments?[J]. IEEE Transactions on Robotics202036(5): 1526-1545.
20 汪哲培. 多旋翼无人机运动规划的几何方法[D]. 杭州: 浙江大学, 2022:33-56.
  WANG Z P. Geometric method for motion planning of multi-rotor UAV[D]. Hangzhou: Zhejiang University, 2022: 33-56 (in Chinese).
21 HORN R A, JOHNSON C R. Matrix analysis[M]. 2nd ed. Cambridge: Cambridge University Press, 2012: 163-224.
22 LIU D C, NOCEDAL J. On the limited memory BFGS method for large scale optimization?[J]. Mathematical Programming198945(1): 503-528.
23 XU W, CAI Y X, HE D J, et al. FAST-LIO2: Fast direct LiDAR-inertial odometry[J]. IEEE Transactions on Robotics202238(4): 2053-2073.
24 ZHANG H X, TAO Y D, ZHU W L. Global path planning of unmanned surface vehicle based on improved A-star algorithm[J]. Sensors202323(14): 6647.
文章导航

/