Abstract
Path planning on grid maps has progressed significantly in recent years, partly due to the Grid-based Path Planning Competition GPPC. In this work we present an optimal approach which combines features from two modern path planning systems, SRC and JPS+, both of which were among the strongest entrants at the 2014 edition of the competition. Given a current state s and a target state t, SRC is used as an oracle to provide an optimal move from s towards t. Once a direction is available we invoke a second JPS-based oracle to tell us for how many steps that move can be repeated, with no need to query the oracles between these steps. Experiments on a range of grid maps demonstrate a strong improvement from our combined approach. Against SRC, which remains an optimal solver with state-of-the-art speed, the performance improvement of our new system ranges from comparable to more than one order of magnitude faster.
| Original language | English |
|---|---|
| Title of host publication | Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018) |
| Subtitle of host publication | June 24, 2018 – June 29, 2018 |
| Editors | Sven Koenig, Gabriele Roger |
| Place of Publication | Palo Alto California USA |
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Pages | 227-231 |
| Number of pages | 5 |
| ISBN (Electronic) | 9781577357971 |
| Publication status | Published - 2018 |
| Event | International Conference on Automated Planning and Scheduling 2018 - Delft, Netherlands Duration: 24 Jun 2018 → 29 Jun 2018 Conference number: 28th http://icaps18.icaps-conference.org/ |
Conference
| Conference | International Conference on Automated Planning and Scheduling 2018 |
|---|---|
| Abbreviated title | ICAPS 2018 |
| Country | Netherlands |
| City | Delft |
| Period | 24/06/18 → 29/06/18 |
| Internet address |
Cite this
}
Two-oracle optimal path planning on grid maps. / Salvetti, Matteo; Botea, Adi; Gerevini, Alfonso E.; Harabor, Daniel; Saetti, Alessandro.
Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018): June 24, 2018 – June 29, 2018. ed. / Sven Koenig; Gabriele Roger. Palo Alto California USA : Association for the Advancement of Artificial Intelligence (AAAI), 2018. p. 227-231.Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
TY - GEN
T1 - Two-oracle optimal path planning on grid maps
AU - Salvetti, Matteo
AU - Botea, Adi
AU - Gerevini, Alfonso E.
AU - Harabor, Daniel
AU - Saetti, Alessandro
PY - 2018
Y1 - 2018
N2 - Path planning on grid maps has progressed significantly in recent years, partly due to the Grid-based Path Planning Competition GPPC. In this work we present an optimal approach which combines features from two modern path planning systems, SRC and JPS+, both of which were among the strongest entrants at the 2014 edition of the competition. Given a current state s and a target state t, SRC is used as an oracle to provide an optimal move from s towards t. Once a direction is available we invoke a second JPS-based oracle to tell us for how many steps that move can be repeated, with no need to query the oracles between these steps. Experiments on a range of grid maps demonstrate a strong improvement from our combined approach. Against SRC, which remains an optimal solver with state-of-the-art speed, the performance improvement of our new system ranges from comparable to more than one order of magnitude faster.
AB - Path planning on grid maps has progressed significantly in recent years, partly due to the Grid-based Path Planning Competition GPPC. In this work we present an optimal approach which combines features from two modern path planning systems, SRC and JPS+, both of which were among the strongest entrants at the 2014 edition of the competition. Given a current state s and a target state t, SRC is used as an oracle to provide an optimal move from s towards t. Once a direction is available we invoke a second JPS-based oracle to tell us for how many steps that move can be repeated, with no need to query the oracles between these steps. Experiments on a range of grid maps demonstrate a strong improvement from our combined approach. Against SRC, which remains an optimal solver with state-of-the-art speed, the performance improvement of our new system ranges from comparable to more than one order of magnitude faster.
UR - http://www.scopus.com/inward/record.url?scp=85054953487&partnerID=8YFLogxK
M3 - Conference Paper
SP - 227
EP - 231
BT - Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018)
A2 - Koenig, Sven
A2 - Roger, Gabriele
PB - Association for the Advancement of Artificial Intelligence (AAAI)
CY - Palo Alto California USA
ER -