A∗-plus path planning algorithm for large-scale grid maps

The A* algorithm is widely recognized as one of the most effective solutions for grid-based path planning. However, when it comes to complex obstacle fields, its performance significantly degrades on large-scale grid maps exceeding 10,000×10,000 in size, where computational complexity and memory usage increase drastically. To address these challenges and accelerate the path planning tasks, we propose the A*-plus algorithm , which introduces a node compression strategy by aggregating 2×2 grid cells into single nodes, thereby substantially reducing the search space. Derived entirely from the A* framework, A*-plus is fully compatible with existing optimization techniques designed for A*, such as priority queues and heuristic functions. Experimental evaluations on 10,000×10,000 grid maps with varying obstacle densities show that A*-plus achieves a 93% reduction in search time and a 60% decrease in memory usage compared to the traditional A* algorithm, without compromising path optimality. These results demonstrate the effectiveness of A*-plus in enabling real-time path planning in expansive grid environments.