Regarding Jump Point Search and Subgoal Graphs

Regarding Jump Point Search and Subgoal Graphs

Daniel D. Harabor, Tansel Uras, Peter J. Stuckey, Sven Koenig

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1241-1248. https://doi.org/10.24963/ijcai.2019/173

In this paper, we define Jump Point Graphs (JP), a preprocessing-based path-planning technique similar to Subgoal Graphs (SG). JP allows for the first time the combination of Jump Point Search style pruning in the context of abstraction-based speedup techniques, such as Contraction Hierarchies. We compare JP with SG and its variants and report new state-of-the-art results for grid-based pathfinding.
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Robotics: Motion and Path Planning