The JPS pathfinding system

Daniel Harabor, Alban Grastien

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

    55 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 5th Annual Symposium on Combinatorial Search, SoCS 2012
    Pages207-208
    Number of pages2
    Publication statusPublished - 2012
    Event5th International Symposium on Combinatorial Search, SoCS 2012 - Niagara Falls, ON, Canada
    Duration: 19 Jul 201221 Jul 2012

    Publication series

    NameProceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012

    Conference

    Conference5th International Symposium on Combinatorial Search, SoCS 2012
    Country/TerritoryCanada
    CityNiagara Falls, ON
    Period19/07/1221/07/12

    Fingerprint

    Dive into the research topics of 'The JPS pathfinding system'. Together they form a unique fingerprint.

    Cite this