# The Parameterized Complexity of Coordinated Motion Planning

arXiv: https://arxiv.org/abs/2312.07144 · HTML: https://mlsanity.com/paper/2312.07144/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 39 references that are in the map.
- First posted on arXiv 12 Dec 2023.

## Builds on (most cited first, 11 of 11)

- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch](https://mlsanity.com/paper/1801.01689/) (2018)
- [Refined Hardness of Distance-Optimal Multi-Agent Path Finding](https://mlsanity.com/paper/2203.07416/) (2022)
- [A simple proof that the (n2-1)-puzzle is hard](https://mlsanity.com/paper/1707.03146/) (2017)
- [Computing Coordinated Motion Plans for Robot Swarms: The CG:SHOP Challenge 2021](https://mlsanity.com/paper/2103.15381/) (2021)
- [Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time](https://mlsanity.com/paper/1801.10465/) (2018)
- [Almost Polynomial Hardness of Node-Disjoint Paths in Grids](https://mlsanity.com/paper/1711.01980/) (2017)
- [An Exponential Time Parameterized Algorithm for Planar Disjoint Paths](https://mlsanity.com/paper/2103.17041/) (2021)
- [Positive Planar Satisfiability Problems under 3-Connectivity Constraints](https://mlsanity.com/paper/2108.12500/) (2021)
- [Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds](https://mlsanity.com/paper/2205.07777/) (2022)

## Built on by (most cited first, 3 of 3)

- [Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology](https://mlsanity.com/paper/2312.09646/) (2023)
- [Solving Multiagent Path Finding on Highly Centralized Networks](https://mlsanity.com/paper/2412.09433/) (2024)
- [Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures](https://mlsanity.com/paper/2412.08556/) (2024)

## Abstract (arXiv)

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n2-1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.