High-performance path planning in complex environments: a hierarchical adaptive neighborhood search A* algorithm for mobile robots
TL;DR
Experimental results in dense and complex environments demonstrate that the HANSA* algorithm outperforms conventional approaches, exhibiting improved adaptability and robustness under varying obstacle-density distributions while generating paths with lower redundancy and fewer sharp corners.
Abstract
In grid-based robotic path planning, traditional A* algorithms are often constrained by severe path redundancy, low search efficiency, and poor adaptability to complex environments with varying obstacle densities. To overcome these limitations, this article proposes the Hierarchical Adaptive Neighborhood Search A* (HANSA*) algorithm, which integrates a dual adaptive search mechanism with local environmental complexity evaluation. This mechanism enables dynamic switching between a 16-neighborhood pattern for rapid global exploration and a directional 5-neighborhood pattern for localized refinement based on real-time planning progress and local obstacle density. Phase-specific heuristic functions are introduced to balance search efficiency, path quality, and trajectory smoothness across different planning stages. Furthermore, a two-stage path optimization strategy is employed to reduce path redundancy, remove unnecessary waypoints, and alleviate sharp corners. Experimental results in dense and complex environments demonstrate that the HANSA* algorithm outperforms conventional approaches, exhibiting improved adaptability and robustness under varying obstacle-density distributions while generating paths with lower redundancy and fewer sharp corners. The results also show that HANSA* can replan paths after newly detected obstacles are incorporated into the updated occupancy grid map. These findings confirm the effectiveness of HANSA* for grid-based global path planning of mobile robots in complex environments.