Regarding Jump Point Search and Subgoal Graphs

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

IJCAI 2019 pp. 1241-1248

doi:10.24963/IJCAI.2019/173 /ijcai/2019/harabor2019ijcai-regarding/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Harabor et al. "Regarding Jump Point Search and Subgoal Graphs." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/173

Markdown

[Harabor et al. "Regarding Jump Point Search and Subgoal Graphs." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/harabor2019ijcai-regarding/) doi:10.24963/IJCAI.2019/173

BibTeX

@inproceedings{harabor2019ijcai-regarding,
  title     = {{Regarding Jump Point Search and Subgoal Graphs}},
  author    = {Harabor, Daniel Damir and Uras, Tansel and Stuckey, Peter J. and Koenig, Sven},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1241-1248},
  doi       = {10.24963/IJCAI.2019/173},
  url       = {https://mlanthology.org/ijcai/2019/harabor2019ijcai-regarding/}
}