A fruit fly-inspired path planning algorithm for unmanned aerial vehicle in underground environments based on low-discrepancy sequences

Sampling planning algorithms are crucial in high-dimensional path planning for unmanned aerial vehicle (UAV), particularly in underground environments where Global Positioning System (GPS) signals are absent. The Rapidly-exploring Random Tree (RRT) algorithm, however, faces challenges due to the use of pseudo-random sequences, resulting in issues such as under-sampling, over-sampling, and they also suffer from high computational costs and redundant paths. To address these limitations, the (Halton-based Clustering) HBC-RRT algorithm is proposed. This algorithm utilizes the Halton sequence, replacing the pseudo-random sequence, which fundamentally resolves the problems of under-sampling and over-sampling in the RRT method. Additionally, a novel sampler is introduced, inspired by the fruit fly guidance mechanism, which optimizes the dual-tree sampling process by selecting either the optimal sampling candidate strategy or virtual sub-goal points. The optimal sampling candidate strategy conducts global sampling in three-dimensional space, effectively reducing sampling time. The virtual sub-goal points accelerate the dual-tree connection process, enhancing the directional guidance. The fruit fly mechanism reconstructs the path, leading to a reduction in UAV path costs. The performance of the HBC-RRT algorithm is evaluated through simulation experiments, demonstrating superior results in comparison to four baseline algorithms, including reductions in path length, convergence time, and memory usage. The practical applicability of the algorithm is further validated through real-world experiments involving a UAV and radar in an underground environment.