A Game-Theoretic A-Star Method for Multi-UAV Path Planning in Urban Low-Altitude Airspace

This study addresses the collaborative path planning challenge for multiple unmanned aerial vehicles (UAVs) operating in complex urban environments by proposing a game-theoretic A-star (A*) algorithm to achieve Nash equilibrium among UAV paths. First, the geographical environment is represented using a hexagonal grid structure, providing more natural neighborhood connectivity and smoother paths compared to traditional square grids. Second, risk maps are constructed by incorporating static risk factors such as buildings, roads, and population density. For single-UAV scenarios, risk-minimized path planning is achieved through the A* algorithm searching within the constructed risk map. Subsequently, in the multi-UAV collaborative planning phase, dynamic risk costs arising from inter-path interactions are modeled using a Gaussian diffusion approach, effectively simulating the accumulation of risk. An iterative optimization strategy is implemented, allowing each UAV path to progressively adjust through mutual interactions until reaching Nash equilibrium, thereby optimizing the overall system performance. Experimental validation using actual building data from Beijing demonstrates that the proposed method effectively reduces path conflicts and rapidly converges in overall cost, highlighting its suitability for practical urban UAV operations.