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 $(n^2-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.

在这篇论文中，我们解决了关于协调运动规划（CMP）的参数化复杂性问题，即最小化机器人数量和目标的问题。我们通过对问题的最优解的结构性洞察，建立了这两个问题在前者参数化条件下的固定参数可解性。此外，我们还证明了CMP-L在目标参数化条件下保持固定参数可解，而CMP-M则成为了para-NP-hard问题。后者的结果不仅改进了该问题不可解性的已知边界，还使我们能够通过底层约简来简化情况，从而证明了网格上具有常数路径长度的经典顶点不相交和边不相交路径问题的NP-hard性。

坐标运动规划的参数化复杂性