Two-oracle optimal path planning on grid maps

Matteo Salvetti, Adi Botea, Alfonso E. Gerevini, Daniel Harabor, Alessandro Saetti

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

7 Citations (Scopus)


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 languageEnglish
Title of host publicationTwenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018)
Subtitle of host publicationJune 24, 2018 – June 29, 2018
EditorsSven Koenig, Gabriele Roger
Place of PublicationPalo Alto California USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages5
ISBN (Electronic)9781577357971
Publication statusPublished - 2018
EventInternational Conference on Automated Planning and Scheduling 2018 - Delft, Netherlands
Duration: 24 Jun 201829 Jun 2018
Conference number: 28th (Proceedings)


ConferenceInternational Conference on Automated Planning and Scheduling 2018
Abbreviated titleICAPS 2018
Internet address

Cite this