Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments

This paper proposes an Adaptive Bi-directional Rapidly-exploring Random Tree (ABi-RRT) algorithm with the objective of addressing challenges in three-dimensional path planning of unmanned aerial vehicle (UAV) operating in complex environments. The algorithm utilizes an adaptive sampling strategy and an adjustable step size to enhance performance relative to the Bi-RRT algorithm. In contrast to the Bi-RRT algorithm, which utilizes a random sampling strategy and a fixed step size, potentially leading to inefficiencies and limited search effectiveness, the ABi-RRT algorithm incorporates a dynamic mechanism. This mechanism adjusts the sampling strategy and step size based on the complexity of the search environment. This adaptive approach reduces the randomness in sampling, improves the target-oriented nature of the search, and consequently enhances overall search efficiency. Additionally, a greedy path pruning algorithm is integrated to minimize the path length and reduce the number of points along the path. The utilization of cubic B-spline curves further improves the coherence and smoothness of the generated paths. Simulation results demonstrate that the ABi-RRT algorithm can rapidly and effectively produce paths that are smoother, shorter, and of superior quality compared to existing RRT algorithms. Notably, the ABi-RRT algorithm achieves a 100% success rate in path planning. Furthermore, its average running time is significantly reduced, outperforming the ABA* and AAE-RRT* algorithms by approximately a factor of fifteen and three, respectively. This performance is particularly valuable for UAVs operating under stringent performance constraints in complex three-dimensional environments.