重庆理工大学学报2026，Vol.40Issue(15)：44-53,10.DOI:10.3969/j.issn.1674-8425(z).2026.08.006
面向城市低空无人机的三维路径规划算法研究
3D path planning algorithm for urban low-altitude UAVs
摘要
Abstract
As an emerging field,the low-altitude economy is developing rapidly with unmanned aerial vehicles(UAVs)as core carriers.However,safe and efficient autonomous navigation in complex three-dimensional(3D)urban environments remains a significant technical challenge.Path planning directly determines UAVs' smooth performances.Traditional A* algorithm guarantees an optimal path in static environments,but faces an exponential increase in computational complexity within high-dimensional spaces.To address the issue,this paper proposes an improved A* path planning algorithm for urban low-altitude UAVs. First,the algorithm introduced a dynamically weighted heuristic function at the two-dimensional level.Unlike conventional strong-to-weak dynamic weight patterns,this function adopts a weak-to-strong mode by adjusting the weight according to the search depth.The weight approaches zero during the initial search phase to fully explore the global space,and converges to one as the search accelerates target orientation.Meanwhile,the algorithm employs a three-neighborhood search strategy.By restricting the 2D maximum turning angle to 45 degrees,this strategy minimizes redundant neighborhood calculations while UAVs maintain forward motion.To prevent local deadlocks in extreme U-shaped dead-end layouts,the algorithm includes a failure fallback mechanism,temporarily restoring the eight-neighborhood search when all three neighborhoods fail. Then,to reduce the computational complexity in 3D environments,a constrained 3D search space was proposed.The algorithm modeled the 3D urban environment using a rasterization method.It decomposed the 3D problem into multiple 2D sub-problems by identifying and extracting key layers.The key layer screening mechanism effectively avoided redundant calculations on horizontal layers with similar free space distributions.The algorithm solved 2D paths on each key layer using the improved 2D A*algorithm.Following this,it vertically expanded the resulting 2D path grids into free space,significantly compressing the search range.To enhance robustness and prevent pathfinding failures,the algorithm introduced a constrained 3D space expansion coefficient,incorporating adjacent layer free space grids into the original constrained space when the initial search failed.Theoretical analysis shows the method guarantees path existence,approaches global optimality,and maintains the same worst-case time complexity upper bound as the traditional 3D A*. Next,a bidirectional line-of-sight(LOS)pruning method is adopted to optimize the initial path.The method works in three phases.Initially,it performed forward path pruning from the start point to the end point to eliminate redundant turning points.Next,it uniformly inserted equidistant intermediate nodes into the pruned path segments to increase point density.Finally,it executed reverse pruning from the end point back to the start point to further refine the path morphology.This bidirectional mechanism balanced path length and safety more effectively than traditional single pruning. Experiments validated the algorithm in both simulated and real-world 3D urban environments.In the simulated urban environment,the algorithm achieved the same path length as the traditional A*algorithm while reducing the runtime by 79.4％.In a real-world 3D environment with a 1-meter grid size,which exhibited higher environmental complexity,the algorithm reduced the runtime by 86.4％.Moreover,the algorithm employs an obstacle inflation method to ensure a safe flight distance for UAVs.Applying the proposed bidirectional LOS pruning further cut the path length by 8.1％and reduced the number of turning points by 84.6％. The proposed method effectively improves the computational efficiency and path safety of the A*algorithm in 3D environments.It provides a viable technical solution for UAV path planning in urban low-altitude airspace.The framework has huge potentials in urban low-altitude logistics and emergency rescues,offering a new approach for dimensionality reduction in high-dimensional path planning within structured environments.关键词
路径规划/改进A*算法/受限三维搜索空间/城市低空/双向视线法剪枝Key words
path planning/improved A* algorithm/constrained 3D search space/urban low altitude/bidirectional line-of-sight pruning分类
信息技术与安全科学引用本文复制引用
李丹阳,郝思宝,康建荣,卢玥..面向城市低空无人机的三维路径规划算法研究[J].重庆理工大学学报,2026,40(15):44-53,10.基金项目
国家自然科学基金项目(52074133) （52074133）
江苏省自然资源科研课题(2025048) （2025048）
江苏省地质局科技项目(2024KJ14) （2024KJ14）
