TY - JOUR AU - Hu, Shuli AU - Harabor, Daniel D. AU - Gange, Graeme AU - Stuckey, Peter J. AU - Sturtevant, Nathan R. PY - 2021/05/17 Y2 - 2024/03/28 TI - Jump Point Search with Temporal Obstacles JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 31 IS - 1 SE - Main Track DO - 10.1609/icaps.v31i1.15961 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/15961 SP - 184-191 AB - 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. ER -