ACTA AERONAUTICAET ASTRONAUTICA SINICA >
Global planning method for UAVs based on pruned visibility map
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)
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.
Zhen XUE , Hanlin SHENG , Xin CHEN , Pengxuan WEI , Jiacheng LI , Qian CHEN . Global planning method for UAVs based on pruned visibility map[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2025 , 46(10) : 331279 -331279 . DOI: 10.7527/S1000-6893.2024.31279
| 1 | AGGARWAL S， KUMAR N. Path planning techniques for unmanned aerial vehicles： A review， solutions， and challenges［J］. Computer Communications， 2020， 149： 270-299. |
| 2 | 路晶， 史宇， 张书畅， 等. 无人机航迹规划算法综述［J］. 航空计算技术， 2022， 52（4）： 131-134. |
| LU J， SHI Y， ZHANG S C， et al. A review of UAV trajectory planning algorithms［J］. Aeronautical Computing Technique， 2022， 52（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］. 兵器装备工程学报， 2022， 43（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 Engineering， 2022， 43（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］. 系统工程与电子技术， 2021， 43（1）： 99-111. |
| JIA G W， WANG J F. Research review of UAV swarm mission planning method?［J］. Systems Engineering and Electronics， 2021， 43（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 Engineering， 2022， 29（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 Informatics， 2021， 25（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 Manufacturing， 2011， 27（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］. 控制与决策， 2022， 37（4）： 829-838. |
| XU W， YANG Y， YU L T， et al. A global path planning algorithm based on improved RRT* ［J］. Control and Decision， 2022， 37（4）： 829-838 （in Chinese）. | |
| 14 | 张伟民， 付仕雄. 基于改进RRT*算法的移动机器人路径规划［J］. 华中科技大学学报（自然科学版）， 2021， 49（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）， 2021， 49（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 Access， 2019， 7： 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 Sciences， 2021， 11（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 Robotics， 2020， 36（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 Programming， 1989， 45（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 Robotics， 2022， 38（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］. Sensors， 2023， 23（14）： 6647. |
/
| 〈 |
|
〉 |
CJA