Grid Graph Reduction for Efficient Shortest Pathfinding

Abstract

Single-pair shortest pathfinding (SP) algorithms are used to identify the path with the minimum cost between two vertices in a given graph. However, their time complexity can rapidly increase as the graph size grows. In this paper, we propose a pattern-based blocking algorithm in a grid graph (PBGG) that iteratively blocks or reduces free space vertices that do not require exploration. The blocking process is based on the neighbors of each vertex and utilizes $3 \times 3$ binary pattern matching. The time complexity of blocking is $O(I\cdot \lceil \vert V\vert /C\rceil)$ , where $\vert V\vert $ is the number of vertices, $I$ is the maximum number of iterations, and $C$ is the number of parallelized cores. PBGG significantly reduces the total computation time when utilized to preprocess an input grid graph before applying existing SP algorithms. It also guarantees that if a minimum-cost path exists in the original graph, then the SP algorithms can find at least one path with the same minimum cost in the reduced graph. The proposed method is formulated by convolutions that can be easily implemented using machine learning platforms, such as PyTorch. Experimental results show that when PBGG can significantly reduce the total computation time when employed in conjunction with SP algorithms such as $\text{A}\ast $ and Jump Point Search. On average, PBGG reduces the total computation times by 71% for A and 41% for Jump Point Search, compared to the times taken by the SP algorithms alone.

Keywords

• Blocking
• convolution
• dead-end/avoidable vertices
• nonblockable vertices
• pattern matching
• shortest path problem