Research on deterministic path replanning algorithm in dynamic low-altitude environments

Abstract

With the rapid development of the urban low-altitude economy, unmanned aerial vehicle (UAV) path planning in complex dynamic environments faces dual challenges of real-time performance and reliability. Traditional shortest path algorithms exhibit computational efficiency bottlenecks when processing large-scale grid graphs and dynamic obstacles. This paper proposes a deterministic path replanning framework based on the Breaking the Sorting Barrier theory, applying the latest single-source shortest path algorithm to UAV dynamic path planning. Based on the Urban Multi-UAV Path Planning Simulation Dataset (PAIR), comprehensive scenarios including Static, Dynamic, and Non-Uniform Density Gradients are selected for experimental verification. Furthermore, the framework integrates sensor noise tolerance. The experimental results show that the proposed algorithm significantly reduces the computation time, performing particularly prominently in high-density dynamic scenarios and complex density-changing environments, achieving an obvious efficiency improvement over the traditional Dijkstra algorithm and Bellman-Ford algorithm. This research provides an efficient, robust, and deterministic solution for UAV path planning in dynamic low-altitude environments, which can effectively support real-time navigation tasks.