Accelerated Path Planning for Large-Scale Grid Maps
Duohang Sun, Zhe Sun, Peinan Shao · IEEE Access · 2024
Path planning is a critical task in automated navigation and seeks to identify optimal collision-free routes for autonomous systems such as unmanned vehicles, aircrafts, and surface ships within a specified environment. The rapid computation of optimal paths in large-scale grid maps remains a major challenge. This paper presents an enhanced HPA$^{\ast }$pathfinding algorithm that utilizes an abstract representation of grid maps to facilitate fast navigation. The enhancements to the HPA$^{\ast }$algorithm include a detailed examination of neighborhood branch extensions, the incorporation of a high-quality heuristic function, and the implementation of repulsive force fields. The effectiveness of this improved HPA$^{\ast }$algorithm in large-scale grid environments is demonstrated by extensive experiments in real-world settings. In terms of computational efficiency, for path planning in real scenarios, the computation time of the HPA$^{\ast }$Improved algorithm can be reduced by more than 95% relative to the A$^{\ast }$algorithm, and the computation time can still be reduced by more than 80% relative to the HPATheta$^{\ast }$algorithm, even though the computation time can be reduced by more than 80%. Even compared to HPATheta$^{\ast }$algorithm, the computation time can still be reduced by more than 80%. Specifically, the improved HPA$^{\ast }$algorithm significantly reduces the time required to generate path results while also enhancing path safety. This study provides valuable insights into advanced pathfinding techniques that could advance automated navigation systems.