Jump Point Search with temporal obstacles

Shuli Hu, Daniel D. Harabor, Graeme Gange, Peter J. Stuckey, Nathan R. Sturtevant

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

4 Citations (Scopus)

Abstract

In 4-connected grid-based path planning one often needs to account for temporal and moving obstacles: ones that appear, disappear and which can prevent the agent from reaching its target. Such problems are common in a variety of settings (games, robotics etc.) and they can be surprisingly challenging to solve. First, because the temporal aspect increases the size of the search space; second because the search space contains many symmetric paths, indistinguishable from one another except by the order in which grid moves appear. To tackle such problems we consider a new optimal algorithm – in the style of Jump Point Search – which can identify and break these symmetries and thus improves performance; from several factors to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.

Original languageEnglish
Title of host publicationProceedings of the Thirty-First International Conference on Automated Planning and Scheduling
EditorsSusanne Biundo, Minh Do, Robert Goldman, Michael Katz, Qiang Yang, Hankz Hankui Zhuo
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages184-191
Number of pages8
ISBN (Electronic)9781713832317, 9781577358671
Publication statusPublished - 2021
EventInternational Conference on Automated Planning and Scheduling 2021 - Online, Guangzhou, China
Duration: 2 Aug 202113 Aug 2021
Conference number: 31st
https://ojs.aaai.org/index.php/ICAPS/issue/view/380 (Proceedings)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume2021-August
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2021
Abbreviated titleICAPS 2021
Country/TerritoryChina
CityGuangzhou
Period2/08/2113/08/21
Internet address

Cite this