UAV dynamic path planning method via heuristic incremental search
Junzhi Li, Teng Long, Jingliang Sun, Ye Luo, Zhenlin Zhou · Scientia Sinica Informationis · 2025
To meet the requirements of high efficiency and dynamic environmental adaptability for UAV path planning in dynamic environments, the dynamic path planning method via incremental heuristic search is investigated. Our approach incorporates the sparse A* (SA*) algorithm with incremental search. To reuse historical path planning information of SA*, the improved node expansion rules and node degeneracy strategy are introduced, avoiding the wastage of computing resources. Using a modified heuristic incremental search framework, the historical planning information is incrementally updated locally to adapt to dynamic environments, and the incremental dynamic sparse A* algorithm (ID-SA*) is proposed. The results of simulation and flight tests show that the proposed method can utilize historical information to speed up UAV path planning in dynamic environments. Compared with the standard SA* and anytime repairing sparse A* (AR-SA*), ID-SA* outperforms the competitors in terms of solving efficiency for dynamic path planning problems, which significantly reduces the computational time to 10^-1s, satisfying the requirements of fast dynamic path planning in the limited onboard computational resources.