Multi-Agent Path Finding with Temporal Jump Point Search

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

DOI:

https://doi.org/10.1609/icaps.v32i1.19798

Keywords:

Multi-Agent Path Finding, Jump Point Search, Temporal Obstacles, Conflict-Based Search

Abstract

Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.
ICAPS-22 Proceedings Cover

Downloads

Published

2022-06-13

How to Cite

Hu, S., Harabor, D. D., Gange, G., Stuckey, P. J., & Sturtevant, N. R. (2022). Multi-Agent Path Finding with Temporal Jump Point Search. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 169-173. https://doi.org/10.1609/icaps.v32i1.19798

Issue

Vol. 32 (2022): Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling

Section

Main Track