Scholarlink

<p>In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which <i>k</i> robots occupy <i>k</i> distinct starting gridpoints and need to reach <i>k</i> 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 <i>k</i> 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 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\((n^2-1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-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-<Emphasis FontCategory="SansSerif">NP</Emphasis>-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 <Emphasis FontCategory="SansSerif">NP</Emphasis>-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The Parameterized Complexity of Coordinated Motion Planning

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月15日

查看全文
  • Eduard Eiben,
  • Robert Ganian,
  • Iyad Kanj

摘要

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 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)\) ( 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.