The Improved A* Algorithm for Quadrotor UAVs under Forest Obstacle Avoidance Path Planning
Source abstract
Abstract
In order to improve the obstacle avoidance and endurance capability of quadrotor UAVs performing tasks such as forest inspection and rescue search, this paper proposes improvements to address the problems of too many traversed nodes, too many redundant corners, too-large turning angles and unsmooth generated paths in the traditional A* algorithm in path planning. The traditional A* algorithm is improved by using a segmented evaluation function with dynamic heuristic and weighting processing, a steering cost heuristic function based on heading angle deviation control, a redundant turning points removal strategy, and a quasi-uniform cubic b-spline. Through the test comparison of different complexity map scenarios, it is found that the improved A* algorithm reduces the number of traversed nodes by 64.87% on average, the total turning angle by 54.53% on average, the path search time by 49.64% on average, and the path length by 12.52% on average compared to the traditional A* algorithm, and there is no obvious turning point in the path. The real-world applicability of the improved A* algorithm is confirmed by comparing the effect of different algorithms on obstacle avoidance in a map of a real plantation forest environment.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Robotics and Sensor-Based Localization · Autonomous Vehicle Technology and Safety
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Key Laboratory of State Forestry and Grassland Administration on Forestry Equipment and Automation, School of Technology, Beijing Forestry University, Beijing 100083, China
UAV Center Amy Aviation Institute, Beijing 101116, China
Funding
Fundamental Research Funds for the Central Universities
References (53)
Show source-provided references
1. Application analysis of multi-rotor UAV in forest fire prevention and control
2. Application analysis of UAV in forest fire prevention
3. Multi-Area Throughput and Energy Optimization of UAV-aided Cellular Networks Powered by Solar Panels and Grid10.1109/TMC.2020.2980834 ↗
4. Di Franco, C., and Buttazzo, G. (2015, January 8–10). Energy-aware coverage path planning of UAVs. Proceedings of the International Conference on Autonomous Robot Systems and Competitions, Vila Real, Portugal.10.1109/ICARSC.2015.17 ↗
5. E2PP: An Energy-Effifcient Path Planning Method for UAV-Assisted Data Collection10.1155/2020/8850505 ↗
6. Kuwata, Y. (2003). Real-Time Trajectory Design for Unmanned Aerial Vehicles Using Receding Horizon Control, Institute of Technology.10.23919/ACC.2004.1383721 ↗
7. Algorithm for low altitude penetration aircraft path planning with improved ant colony algorithm10.1016/S1000-9361(11)60249-5 ↗
8. Path planning and collision avoidance for a multi-arm space maneuverable robot10.1109/TAES.2017.2747938 ↗
9. Path planning of mobile robot based on Improved-RRT algorithm
10. Rapidly-exploring random trees: Progress and prospects
11. LaValle, S., and Kuffner, J. (2000, January 24–28). RRT-connect: An efficient approach to single-query path planning. Proceedings of the 2000 ICRA. Millennium Conference, San Francisco, CA, USA. IEEE International Conference on Robotics and Automation, Symposia Proceedings (Cat. No. 00CH37065).
12. Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate10.1016/j.eswa.2019.01.032 ↗
13. Gammell, J., Srinivasa, S., and Barfoot, T. (2014, January 14–18). Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Chicago, IL, USA.10.1109/IROS.2014.6942976 ↗
14. Gammell, J., Srinivasa, S., and Barfoot, T. (2015, January 26–30). Batch informed trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.10.1109/ICRA.2015.7139620 ↗
15. Obstacle Avoidance Path Planning for UAV Based on Improved RRT Algorithm10.1155/2022/4544499 ↗
16. Trajectory Planning for UAV Based on Improved ACO Algorithm10.1109/ACCESS.2019.2962340 ↗
17. A newly bio-inspired path planning algorithm for autonomous obstacle avoidance of UAV10.1016/j.cja.2020.12.018 ↗
18. Zhang, J., Chadha, R.G., Velivela, V., and Singh, S. (2018, January 1–5). P-CAP: Precomputed alternative paths to enable aggressive aerial maneuvers in cluttered environments. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, Spain.10.1109/IROS.2018.8593826 ↗
19. Zhang, J., Chadha, R.G., Velivela, V., and Singh, S. (2019, January 29–31). P-CAL: Pre-computed alternative lanes for aggressive aerial collision avoidance. Proceedings of the 12th International Conference on Field and Service Robotics (FSR), Tokyo, Japan.
20. Zhang, J., Hu, C., Chadha, R.G., and Singh, S. (2019, January 3–8). Maximum Likelihood Path Planning for Fast Aerial Maneuvers and Collision Avoidance. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Macao, China.10.1109/IROS40897.2019.8967828 ↗
21. Hopfield neural networks for path planning in dynamic and unknown environments
22. Gao, M., Wei, P., and Liu, Y. (2020, January 11–14). Competitive Self-Organizing Neural Network Based UAV Path Planning. Proceedings of the IEEE 6th International Conference on Computer and Communications (ICCC), Chengdu, China.10.1109/ICCC51575.2020.9344904 ↗
23. Path planning of mobile robots based on ion motion-artificial bee colony algorithm
24. A Deep Learning Trained by Genetic Algorithm to Improve the Efficiency of Path Planning for Data Collection with Multi-UAV10.1109/ACCESS.2021.3049892 ↗
25. Solving fuzzy dynamic ship routing and scheduling problem through new genetic algorithm10.31181/dmame181221030d ↗
26. Chen, X., Chen, J., Du, C., and Xu, Y. (2021, January 13–15). Region Coverage Path Planning of Multiple Disconnected Convex Polygons Based on Simulated Annealing Algorithm. Proceedings of the IEEE 4th International Conference on Computer and Communication Engineering Technology (CCET), Beijing, China.10.1109/CCET52649.2021.9544414 ↗
27. Path Planning of UAV Based on Improved Adaptive Grey Wolf Optimization Algorithm10.1109/ACCESS.2021.3090776 ↗
28. Optimization of Complex System Reliability using Hybrid Grey Wolf Optimizer10.31181/dmame210402241n ↗
29. Multi-objective distributed generation penetration planning with load model using particle swarm optimization10.31181/dmame2003065g ↗
30. A note on two problems in connexion with graphs10.1007/BF01386390 ↗
31. A novel potential field method for path planning of mobile robots by adapting animal motion attributes10.1016/j.robot.2016.04.007 ↗
32. Mobile robot path planning using membrane evolutionary artificial potential field10.1016/j.asoc.2019.01.036 ↗
33. Path planning and cooperative control for automated vehicle platoon using hybrid automata10.1109/TITS.2018.2841967 ↗
34. Intelligent rebar layout in rc building frames using artificial potential field10.1016/j.autcon.2020.103172 ↗
35. Path planning of moving robot based on path optimization of D*Lite algorithm
36. A formal basis for the heuristic determination of minimum cost paths
37. Ju, C., Luo, Q., and Yan, X. (2020, January 23–25). Path Planning Using an Improved A-star Algorithm. Proceedings of the 11th International Conference on Prognostics and System Health Management (PHM), Jinan, China.10.1109/PHM-Jinan48558.2020.00012 ↗
38. Multi-machine Cooperation Global Path Planning Based on A-star Algorithm and Bezier Curve
39. Gochev, K., Safonova, A., and Likhachev, M. (2014, January 15–17). Anytime tree-restoring weighted A* graph search. Proceedings of the Seventh Annual Symposium on Combinatorial Search, Prague, Czech Republic.
40. Huang, X., Dong, X., Ma, J., Liu, K., Ahmed, S., Lin, J., and Qiu, B. (2021). The Improved A* Obstacle Avoidance Algorithm for the Plant Protection UAV with Millimeter Wave Radar and Monocular Camera Data Fusion. Remote Sens., 13.10.3390/rs13173364 ↗
41. An improved A* algorithm for searching infinite neighborhoods
42. Path planning method of mobile robot based on improved A* algorithm
43. Research on Improved A* Algorithm of Bidirectional Search Mechanism
44. Lin, M., Yuan, K., Shi, C., and Wang, Y. (2017, January 28–30). Path planning of mobile robot based on improved A∗ algorithm. Proceedings of the 29th Chinese Control and Decision Conference (CCDC), Chongqing, China.10.1109/CCDC.2017.7979125 ↗
45. Islam, F., Narayanan, V., and Likhachev, M. (2015, January 26–30). Dynamic multi-heuristic A*. Proceedings of the IEEE International Conference on Robotics and Automation, Seattle, WA, USA.10.1109/ICRA.2015.7139515 ↗
46. An improved A* algorithm for the industrial robot path planning with high success rate and short length10.1016/j.robot.2018.04.007 ↗
47. Robust and efficient quadrotor trajectory generation for fast autonomous flight10.1109/LRA.2019.2927938 ↗
48. Bi-Directional Adaptive A* Algorithm Toward Optimal Path Planning for Large-Scale UAV Under Multi-Constraints10.1109/ACCESS.2020.2990153 ↗
49. Muñoz, J., Li, B., Rong, X., Xiao, J., Tian, Y., and Arditi, A. (August, January 31). An assistive indoor navigation system for the visually impaired in multi-floor environments. Proceedings of the IEEE 7th Annual International Conference on CYBER Technology in Automation, Control, and Intelligent Systems (CYBER), Honolulu, HI, USA.10.1109/CYBER.2017.8446088 ↗
50. A dynamic fusion pathfinding algorithm using delaunay triangulation and improved A-star for mobile robots10.1109/ACCESS.2021.3055231 ↗
51. Zhou, S., Kang, F., Li, W., Kan, J., Zheng, Y., and He, G. (2019). Extracting Diameter at Breast Height with a Handheld Mobile LiDAR System in an Outdoor Environment. Sensors, 19.10.3390/s19143212 ↗
52. Mobile robot planning based on improved a* algorithm
53. A low-cost autonomous navigation system for a quadrotor in complex outdoor environments10.1177/1729881420905150 ↗