The JPS pathfinding system

Daniel Harabor, Alban Grastien

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

Abstract

We describe a pathfinding system based on Jump Point Search (JPS): a recent and very successful search strategy that performs symmetry breaking to speed up optimal pathfinding on grid maps. We first modify JPS for grid maps where corner-cutting moves are not allowed. We then describe JPS+: a new derivative search strategy that reformulates an input graph into an equivalent symmetry-reduced form that can be searched more efficiently. JPS and JPS+ were both submitted to the 2012 Grid-based Path Planning Competition.

Original languageEnglish
Title of host publicationProceedings of the Fifth Annual Symposium on Combinatorial Search
EditorsDaniel Borrajo, Ariel Felner, Richard Korf, Maxim Likhachev, Carlos Linares Lopez, Wheeler Ruml, Nathan Sturtevant
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages207-208
Number of pages2
ISBN (Print)9781577355847
Publication statusPublished - 2012
Externally publishedYes
EventInternational Symposium on Combinatorial Search 2012 - Niagara Falls, Canada
Duration: 19 Jul 201221 Jul 2012
Conference number: 5th
http://socs12.org/

Conference

ConferenceInternational Symposium on Combinatorial Search 2012
Abbreviated titleSoCS 2012
CountryCanada
CityNiagara Falls
Period19/07/1221/07/12
Internet address

Cite this

Harabor, D., & Grastien, A. (2012). The JPS pathfinding system. In D. Borrajo, A. Felner, R. Korf, M. Likhachev, C. L. Lopez, W. Ruml, & N. Sturtevant (Eds.), Proceedings of the Fifth Annual Symposium on Combinatorial Search (pp. 207-208). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI).
Harabor, Daniel ; Grastien, Alban. / The JPS pathfinding system. Proceedings of the Fifth Annual Symposium on Combinatorial Search. editor / Daniel Borrajo ; Ariel Felner ; Richard Korf ; Maxim Likhachev ; Carlos Linares Lopez ; Wheeler Ruml ; Nathan Sturtevant. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2012. pp. 207-208
@inproceedings{01301dcedad04b41a6fbe392edfa1da6,
title = "The JPS pathfinding system",
abstract = "We describe a pathfinding system based on Jump Point Search (JPS): a recent and very successful search strategy that performs symmetry breaking to speed up optimal pathfinding on grid maps. We first modify JPS for grid maps where corner-cutting moves are not allowed. We then describe JPS+: a new derivative search strategy that reformulates an input graph into an equivalent symmetry-reduced form that can be searched more efficiently. JPS and JPS+ were both submitted to the 2012 Grid-based Path Planning Competition.",
author = "Daniel Harabor and Alban Grastien",
year = "2012",
language = "English",
isbn = "9781577355847",
pages = "207--208",
editor = "Daniel Borrajo and Ariel Felner and Richard Korf and Maxim Likhachev and Lopez, {Carlos Linares} and Wheeler Ruml and Nathan Sturtevant",
booktitle = "Proceedings of the Fifth Annual Symposium on Combinatorial Search",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States of America",

}

Harabor, D & Grastien, A 2012, The JPS pathfinding system. in D Borrajo, A Felner, R Korf, M Likhachev, CL Lopez, W Ruml & N Sturtevant (eds), Proceedings of the Fifth Annual Symposium on Combinatorial Search. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 207-208, International Symposium on Combinatorial Search 2012, Niagara Falls, Canada, 19/07/12.

The JPS pathfinding system. / Harabor, Daniel; Grastien, Alban.

Proceedings of the Fifth Annual Symposium on Combinatorial Search. ed. / Daniel Borrajo; Ariel Felner; Richard Korf; Maxim Likhachev; Carlos Linares Lopez; Wheeler Ruml; Nathan Sturtevant. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2012. p. 207-208.

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

TY - GEN

T1 - The JPS pathfinding system

AU - Harabor, Daniel

AU - Grastien, Alban

PY - 2012

Y1 - 2012

N2 - We describe a pathfinding system based on Jump Point Search (JPS): a recent and very successful search strategy that performs symmetry breaking to speed up optimal pathfinding on grid maps. We first modify JPS for grid maps where corner-cutting moves are not allowed. We then describe JPS+: a new derivative search strategy that reformulates an input graph into an equivalent symmetry-reduced form that can be searched more efficiently. JPS and JPS+ were both submitted to the 2012 Grid-based Path Planning Competition.

AB - We describe a pathfinding system based on Jump Point Search (JPS): a recent and very successful search strategy that performs symmetry breaking to speed up optimal pathfinding on grid maps. We first modify JPS for grid maps where corner-cutting moves are not allowed. We then describe JPS+: a new derivative search strategy that reformulates an input graph into an equivalent symmetry-reduced form that can be searched more efficiently. JPS and JPS+ were both submitted to the 2012 Grid-based Path Planning Competition.

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

M3 - Conference Paper

SN - 9781577355847

SP - 207

EP - 208

BT - Proceedings of the Fifth Annual Symposium on Combinatorial Search

A2 - Borrajo, Daniel

A2 - Felner, Ariel

A2 - Korf, Richard

A2 - Likhachev, Maxim

A2 - Lopez, Carlos Linares

A2 - Ruml, Wheeler

A2 - Sturtevant, Nathan

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

CY - Palo Alto CA USA

ER -

Harabor D, Grastien A. The JPS pathfinding system. In Borrajo D, Felner A, Korf R, Likhachev M, Lopez CL, Ruml W, Sturtevant N, editors, Proceedings of the Fifth Annual Symposium on Combinatorial Search. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2012. p. 207-208