Grid Graph Reduction for Efficient Shortest Pathfinding

Chan Young Kim, Sanghoon Sull

Research output: Contribution to journalArticlepeer-review

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 × 3 binary pattern matching. The time complexity of blocking is O(I· ⌈|V|C⌉), where |V| 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 A∗ 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.

Original languageEnglish
Pages (from-to)74263-74276
Number of pages14
JournalIEEE Access
Volume11
DOIs
Publication statusPublished - 2023

Bibliographical note

Publisher Copyright:
© 2013 IEEE.

Keywords

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

ASJC Scopus subject areas

  • General Engineering
  • General Materials Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Grid Graph Reduction for Efficient Shortest Pathfinding'. Together they form a unique fingerprint.

Cite this