The JPS Pathfinding System

Authors

  • Daniel Harabor NICTA and The Australian National University
  • Alban Grastien NICTA and The Australian National University

DOI:

https://doi.org/10.1609/socs.v3i1.18254

Keywords:

search a* pathfinding symmetry

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.

Downloads

Published

2021-08-20

Issue

Section

Grid-Based Path Planning Competition