Jump Point Search with Temporal Obstacles


  • Shuli Hu Northeast Normal University
  • Daniel D. Harabor Monash University
  • Graeme Gange Monash University
  • Peter J. Stuckey Monash University
  • Nathan R. Sturtevant University of Alberta




Classical Planning Techniques And Analysis, Multi-agent And Distributed Planning


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.




How to Cite

Hu, S., Harabor, D. D., Gange, G., Stuckey, P. J., & Sturtevant, N. R. (2021). Jump Point Search with Temporal Obstacles. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 184-191. https://doi.org/10.1609/icaps.v31i1.15961