Jump Point Search with Temporal Obstacles
| Autor: | Shuli Hu, Daniel D. Harabor, Graeme Gange, Peter J. Stuckey, Nathan R. Sturtevant |
|---|---|
| Rok vydání: | 2021 |
| Zdroj: | Proceedings of the International Conference on Automated Planning and Scheduling. 31:184-191 |
| ISSN: | 2334-0843 2334-0835 |
| DOI: | 10.1609/icaps.v31i1.15961 |
| Popis: | 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 factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|