- Grid Multi-Robot Path Planning with the Corner-Following Constraint: Intractability and Algorithms
- Project Year:
2023
- REU Student (s):
Marcus Gozon | University of Michigan-Ann Arbor MI
- Student 1 Institution:
University of Michigan-Ann Arbor
- Project Mentor:
Jingjin Yu
- Project Mentor Area:
Computer Science
- Project Abstract:
Grid Multi-Robot Path Planning (MRPP) has been extensively studied, but much less is known about the corner-following constraint (CFC) variant, which has applications ranging from automated garages to grocery packing warehouses. On an m1 x m2 grid, the problem has a tight upper and lower bound for the makespan objective when there are Θ(m1m2) escorts, but there is a gap when there are only Θ(m1+m2) or Θ(1) escorts. In addition, nothing is known about the intractability of this problem or its related variants. In this work, we close the gap for an arbitrary number of escorts, finding an expected constant factor algorithm when there are at most min(m1,m2) escorts and a high probability constant factor algorithm when there are more. We also show that the problem is NP-hard under the makespan objective, and by the same reduction, standard grid MRPP is NP-hard also, unifying the two grid MRPP makespan hardness results. In addition, we show that when there is a single escort, the two-colored variant and partial variant are both NP-hard, which significantly impacts the design of efficient systems using the MRPP with CFC paradigm. These results contribute to our understanding of the design of efficient algorithms from both an upper and lower bound perspective.
