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 language | English |
---|---|
Title of host publication | Proceedings of the Fifth Annual Symposium on Combinatorial Search |
Editors | Daniel Borrajo, Ariel Felner, Richard Korf, Maxim Likhachev, Carlos Linares Lopez, Wheeler Ruml, Nathan Sturtevant |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 207-208 |
Number of pages | 2 |
ISBN (Print) | 9781577355847 |
Publication status | Published - 2012 |
Externally published | Yes |
Event | International Symposium on Combinatorial Search 2012 - Niagara Falls, Canada Duration: 19 Jul 2012 → 21 Jul 2012 Conference number: 5th http://socs12.org/ |
Conference
Conference | International Symposium on Combinatorial Search 2012 |
---|---|
Abbreviated title | SoCS 2012 |
Country/Territory | Canada |
City | Niagara Falls |
Period | 19/07/12 → 21/07/12 |
Internet address |