The JPS pathfinding system

Daniel Harabor, Alban Grastien

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

20 Citations (Scopus)

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