Heuristic Global Path Planning Algorithm Based on Neighborhood Information Fusion Transformer
Xinyu Zhang, Lei Mo, Ji Liu, Jie Han, Mufeng Wang · 2024
Inaccurate heuristic components or highly complex obstacle scenarios are challenges for traditional heuristic pathfinding algorithms since the heuristic function is simple, e.g., based on straight line distance, leading to invalid searches. To address this issue, we propose a novel heuristic with a Neighborhood Information Fusion Path Probability Map (NIFPPM) method, to reduce the number of ineffective explorations by an agent. We first apply a neighborhood information fusion filter to grid-based maps to aggregate the heuristic function value information. Then, we extract the feature matrix from the grid-based map and send the feature matrix to the transformer-based network to learn the setting of the heuristic function. On this basis, we combine NIPPM information and Greedy Focal Search to improve the efficiency of the heuristic algorithm. In simulations, we compare our method with the existing methods. The results show that compared with neural network-based A* algorithm and vanilla A* algorithm, the proposed method achieves $3 \%$ and $77 \%$ reductions in expansion ratio.