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 | Canada |
| City | Niagara Falls |
| Period | 19/07/12 → 21/07/12 |
| Internet address |
Cite this
}
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 proceeding › Conference Paper › Other
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 -