Two-Oracle Optimal Path Planning on Grid Maps

Authors

  • Matteo Salvetti Università degli Studi di Brescia
  • Adi Botea IBM Research
  • Alfonso Gerevini Università degli Studi di Brescia
  • Daniel Harabor Monash University
  • Alessandro Saetti Università degli Studi di Brescia

DOI:

https://doi.org/10.1609/icaps.v28i1.13898

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.

Downloads

Published

2018-06-15

How to Cite

Salvetti, M., Botea, A., Gerevini, A., Harabor, D., & Saetti, A. (2018). Two-Oracle Optimal Path Planning on Grid Maps. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 227-231. https://doi.org/10.1609/icaps.v28i1.13898