Urban low-altitude UAV path planning based on the hierarchical bidirectional A* algorithm

Abstract

Addressing the challenge of urban low-altitude drone operations where achieving simultaneous accessibility, real-time performance, and path quality under large-scale maps, dense building clusters, and unknown obstacles proves difficult, this paper proposes a hierarchical planning methodology tailored for urban environments, termed the Hierarchical Bidirectional A* (HB-A*) algorithm. First, leveraging building polygon and height data, the method constructs a unified representation of known/unknown obstacles, analytical distance fields, and a 2.5D hierarchical occupancy environment, effectively reducing modeling and search costs while preserving three-dimensional navigation semantics. Second, it introduces a layered global planning framework comprising coarse-grained route map guidance, local scene clipping, enhanced bidirectional A* search, adaptive step-length adjustment, and line-of-sight smoothing. The approach prioritizes low-density corridors in the route map layer, constructs heuristic functions combining height and safety costs during local searches, and employs a strategy of small steps near obstacles and large steps in open areas to minimize node expansion. Simulation results demonstrate that the proposed method reduces global planning time from 223.24 seconds to 0.72 seconds, cuts node expansion from 99,068 to 116, and lowers path elongation ratio from 1.754 to 1.110 in challenging scenarios. These findings confirm the method's ability to generate shorter, safer, and more feasible urban low-altitude flight paths with lower computational costs.