Prioritised Planning with Guarantees

Authors

  • Jonathan Morag Ben-Gurion University of the Negev Monash University
  • Yue Zhang Monash University
  • Daniel Koyfman Ben-Gurion University of the Negev
  • Zhe Chen Monash University
  • Ariel Felner Ben-Gurion University of the Negev
  • Daniel Harabor Monash University
  • Roni Stern Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v17i1.31545

Abstract

Prioritised Planning (PP) is a family of incomplete and sub-optimal algorithms for multi-agent and multi-robot navigation. In PP, agents compute collision-free paths in a fixed order, one at a time. Although fast and usually effective, PP can still fail, leaving users without explanation or recourse. In this work, we give a theoretical and empirical basis for better understanding the underlying problem solved by PP, which we call Priority Constrained MAPF (PC-MAPF). We first investigate the complexity of PC-MAPF and show that the decision problem is NP-hard. We then develop Priority Constrained Search (PCS), a new algorithm that is both complete and optimal with respect to a fixed priority ordering. We experiment with PCS in a range of settings, including comparisons with existing PP baselines, and we give first-known results for optimal PC-MAPF on a popular benchmark set.

Downloads

Published

2024-06-01