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

1 Citation (Scopus)

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 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)
Pages227-231
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
http://icaps18.icaps-conference.org/

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2018
Abbreviated titleICAPS 2018
CountryNetherlands
CityDelft
Period24/06/1829/06/18
Internet address

Cite this

Salvetti, M., Botea, A., Gerevini, A. E., Harabor, D., & Saetti, A. (2018). Two-oracle optimal path planning on grid maps. In S. Koenig, & G. Roger (Eds.), Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018): June 24, 2018 – June 29, 2018 (pp. 227-231). Palo Alto California USA: Association for the Advancement of Artificial Intelligence (AAAI).