Regarding jump point search and subgoal graphs

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

Regarding jump point search and subgoal graphs

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019
Editors	Sarit Kraus
Place of Publication	Marina del Rey CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	1241-1248
Number of pages	8
ISBN (Electronic)	9780999241141
Publication status	Published - 2019
Event	International Joint Conference on Artificial Intelligence 2019 - Macao, China Duration: 10 Aug 2019 → 16 Aug 2019 Conference number: 28th https://ijcai19.org/ https://www.ijcai.org/proceedings/2019/ (Proceedings)

Publication series

Name	IJCAI International Joint Conference on Artificial Intelligence
Volume	2019-August
ISSN (Print)	1045-0823

Conference

Conference	International Joint Conference on Artificial Intelligence 2019
Abbreviated title	IJCAI 2019
Country/Territory	China
City	Macao
Period	10/08/19 → 16/08/19
Internet address	https://ijcai19.org/ https://www.ijcai.org/proceedings/2019/ (Proceedings)

Access to Document

279249431-oaFinal published version, 369 KB

http://idm-lab.org/bib/abstracts/papers/ijcai19b.pdf

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

Harabor, Daniel D. ; Uras, Tansel ; Stuckey, Peter J. et al. / Regarding jump point search and subgoal graphs. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019. editor / Sarit Kraus. Marina del Rey CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. pp. 1241-1248 (IJCAI International Joint Conference on Artificial Intelligence).

@inproceedings{af68dab2dd1e417196f2a1901eb0270c,

title = "Regarding jump point search and subgoal graphs",

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.",

author = "Harabor, {Daniel D.} and Tansel Uras and Stuckey, {Peter J.} and Sven Koenig",

year = "2019",

language = "English",

series = "IJCAI International Joint Conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

pages = "1241--1248",

editor = "Sarit Kraus",

booktitle = "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019",

address = "United States of America",

note = "International Joint Conference on Artificial Intelligence 2019, IJCAI 2019 ; Conference date: 10-08-2019 Through 16-08-2019",

url = "https://ijcai19.org/, https://www.ijcai.org/proceedings/2019/",

}

Harabor, DD, Uras, T, Stuckey, PJ & 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. IJCAI International Joint Conference on Artificial Intelligence, vol. 2019-August, Association for the Advancement of Artificial Intelligence (AAAI), Marina del Rey CA USA, pp. 1241-1248, International Joint Conference on Artificial Intelligence 2019, Macao, China, 10/08/19. <http://idm-lab.org/bib/abstracts/papers/ijcai19b.pdf>

Regarding jump point search and subgoal graphs. / Harabor, Daniel D.; Uras, Tansel; Stuckey, Peter J. et al.
Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019. ed. / Sarit Kraus. Marina del Rey CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 1241-1248 (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2019-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Regarding jump point search and subgoal graphs

AU - Harabor, Daniel D.

AU - Uras, Tansel

AU - Stuckey, Peter J.

AU - Koenig, Sven

N1 - Conference code: 28th

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85074943052&partnerID=8YFLogxK

M3 - Conference Paper

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 1241

EP - 1248

BT - Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019

A2 - Kraus, Sarit

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Marina del Rey CA USA

T2 - International Joint Conference on Artificial Intelligence 2019

Y2 - 10 August 2019 through 16 August 2019

ER -

Harabor DD, Uras T, Stuckey PJ, Koenig S. Regarding jump point search and subgoal graphs. In Kraus S, editor, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 2019. Marina del Rey CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2019. p. 1241-1248. (IJCAI International Joint Conference on Artificial Intelligence).

Regarding jump point search and subgoal graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

The Future of Urban Routing and Navigation

Cite this

Regarding jump point search and subgoal graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

The Future of Urban Routing and Navigation

Cite this