Jump Point Search with Temporal Obstacles

Authors

  • 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

Keywords:

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

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 factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.

Downloads

Published

2021-05-17

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. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15961