Multi-objective Path Planning for Large-scale UAV Swarms: an Enhanced A* Algorithm Based on Adaptive Diagonal Heuristics and Hierarchical Parallelism

Path planning for UAV swarms remains a core challenge in swarm intelligence, requiring multi-objective optimization balancing path optimality, computational efficiency, and system scalability in dynamic complex environments. To address the limitations of traditional A* algorithms using four-directional movement constraints and Manhattan distance heuristics-specifically path redundancy and computational bottlenecks.This paper proposes an enhanced A* algorithm integrating octagonal mobility, diagonal heuristics, and parallel acceleration. Three key innovations drive our methodological breakthrough: (1) An improved heuristic function based on diagonal distance effectively reduces path length; (2) An octagonal motion model dynamically adjusts movement costs according to moving directions; (3) A multithreaded parallel architecture implemented through Python's ThreadPoolExecutor enables task-level parallelism, dynamically distributing path planning tasks for 100 UAVs across 4 CPU cores. The experimental results indicate that our enhanced A* algorithm achieves significant improvements under strict start-goal consistency. Total path distance decreases from 7,037 to 5,675 units. When combined with parallel optimization, the algorithm shows reduced runtime and shortened planning cycles, validating its practicality in large-scale UAV swarms scenarios.