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

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).
Salvetti, Matteo ; Botea, Adi ; Gerevini, Alfonso E. ; Harabor, Daniel ; Saetti, Alessandro. / Two-oracle optimal path planning on grid maps. Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018): June 24, 2018 – June 29, 2018. editor / Sven Koenig ; Gabriele Roger. Palo Alto California USA : Association for the Advancement of Artificial Intelligence (AAAI), 2018. pp. 227-231
@inproceedings{4d3825ce33674a5791b54847b037f44b,
title = "Two-oracle optimal path planning on grid maps",
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.",
author = "Matteo Salvetti and Adi Botea and Gerevini, {Alfonso E.} and Daniel Harabor and Alessandro Saetti",
year = "2018",
language = "English",
pages = "227--231",
editor = "Sven Koenig and Roger, {Gabriele }",
booktitle = "Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018)",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States",

}

Salvetti, M, Botea, A, Gerevini, AE, 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. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto California USA, pp. 227-231, International Conference on Automated Planning and Scheduling 2018, Delft, Netherlands, 24/06/18.

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 proceedingConference PaperResearchpeer-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 -

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