Two-Oracle Optimal Path Planning on Grid Maps


  • 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



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.




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.