Regarding jump point search and subgoal graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.

Original languageEnglish
Title of host publicationProceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019
EditorsSarit Kraus
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages1241-1248
Number of pages8
ISBN (Electronic)9780999241141
Publication statusPublished - 2019
EventInternational Joint Conference on Artificial Intelligence 2019 - Macao, China
Duration: 10 Aug 201916 Aug 2019
Conference number: 28th
https://ijcai19.org/

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2019-August
ISSN (Print)1045-0823

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2019
Abbreviated titleIJCAI-19
CountryChina
CityMacao
Period10/08/1916/08/19
Internet address

Cite this

Harabor, D. D., Uras, T., Stuckey, P. J., & Koenig, S. (2019). Regarding jump point search and subgoal graphs. In S. Kraus (Ed.), Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019 (pp. 1241-1248). (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2019-August). Association for the Advancement of Artificial Intelligence (AAAI). http://idm-lab.org/bib/abstracts/papers/ijcai19b.pdf