UAV trajectory planning based on improved bidirectional RRT algorithm

Abstract

In response to the problems of low sampling efficiency, strong randomness of sampling points, and the tortuous shape of the planned path in the traditional rapidly-exploring random tree (RRT) algorithm and bidirectional RRT algorithm used for unmanned aerial vehicle (UAV) path planning in complex environments, an improved bidirectional RRT algorithm was proposed. The algorithm firstly adopted a goal-oriented strategy to guide the sampling points towards the target point, and then the artificial potential field acted on the random tree nodes to avoid collision with obstacles and reduced the length of the search path, and the random tree node growth also combined the UAV’s own flight constraints, and by combining the triangulation method to remove the redundant node strategy and the third-order B-spline curve for the smoothing of the trajectory, the planned path was better. The planned paths were more optimized. Finally, the simulation experiments in complex and dynamic environments showed that the algorithm effectively improved the speed of trajectory planning and shortened the length of the trajectory, and could generate a safe, smooth and fast trajectory in complex environments, which could be applied to online trajectory planning.

Keywords

complex environment / bidirectional RRT algorithm / target orientation strategy / artificial potential field method / triangular inequality cut / cubic B-spline / online trajectory planning

References

[1] CHENG J, ZHENG Y, LI C L, et al. Multi-aircraft cooperative trajectory planning algorithm for ultra-low altitude logistics scenarios. Journal of System Simulation, 2024, 36(1): 50-66.

[2] SUN F C, GAN X S. Lateral manoeuvring path planning for unmanned aerial combat confrontation between two aircraft. Modern Defence Technology, 2022, 50(3): 109-118.

[3] LIN W X, XIE W J, ZHANG P, et al. Three-dimensional path planning for unmanned aerial vehicles based on group optimization improved particle swarm algorithm. Fire Control & Command Control, 2023, 48(1): 20-25.

[4] HU H J. Intelligent trajectory planning and simulation research of rotorcraft in complex environment. Nanjing: Nanjing University of Aeronautics and Astronautics, 2023.

[5] ICHTER B, HARRISON J, PAVONE M. Learning sampling distributions for robot motion planning//2018 IEEE International Conference on Robotics and Automation, May 21-25, 2018, Brisbane, QLD, Australia. New York: IEEE, 2018: 7087-7094.

[6] DENG Y, JIANG X J. Four-rotor UAV track planning algorithm based on improved artificial potential field method. Transducer and Microsystem Technologies, 2021, 40(7): 130-133.

[7] JIANG H, CHAO Y S, ZHOU J L, et al. Improved RRT algorithm for robotic arm path planning. Machinery Design & Manufacture, 2023, 12(5): 288-292.

[8] JIANG X J, HUANG B D, YANG X J. An improved bidirectional RRTs algorithm for UAV global path planning. Mechanical Science and Technology for Aerospace Engineering, 2024, 43(5): 897-903.

[9] LIU A B, YUAN J. Robot path planning based on goal biased bidirectional RRT* algorithm. Computer Engineering and Applications, 2022, 58(6): 234-240.

[10] ZHANG S, XIE X H, CHEN D P. UAV path planning algorithm based on improved RRT-Connect. Transducer and Microsystem Technologies, 2020, 39(12): 146-148.

[11] YU C, CHEN M, YONG K N. Round-trip path planning for unmanned aerial vehicle based on improved RRT* algorithm. Scientia Sinica Technologica, 2023, 53(11): 1911-1921.

[12] HAO G Q, LV Q, HUANG Z, et al. UAV path planning based on improved artificial potential field method. Aerospace, 2023, 10(6): 562.

[13] LIAO B, WAN F Y, HUA Y, et al. F-RRT*: an improved path planning algorithm with improved initial solution and convergence rate. Expert Systems with Applications, 2021, 184: 115457.

[14] ZHANG W M, FU S X. Mobile robot path planning based on improved RRT^* algorithm. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2021, 49(1): 31-36.

[15] LI C L, HE J L, DENG Y, et al. Obstacle-free trajectory planning algorithm for quadrotor UAV based on improved RRT-connect. Transducer and Microsystem Technologies, 2019, 38(5): 136-139.

[16] SHIARLIS K, MESSIAS J, WHITESON S. Rapidly exploring learning trees//2017 IEEE International Conference on Robotics and Automation, May 29 - June 3, 2017, Singapore. New York: IEEE, 2017: 1541-1548.

[17] KANG J G, LIM D W, CHOI Y S, et al. Improved RRT-connect algorithm based on triangular inequality for robot path planning. Sensors, 2021, 21(2): 333.

[18] ZHANG L P, SHI X X, YI Y M, et al. Mobile robot path planning algorithm based on RRT_Connect. Electronics, 2023, 12(11): 2456.