Coordinated Motion Planning Is FPT on Discretized Simple Polygons

Abstract

In the coordinated motion planning problem, we are given a graph together with the starting and destination vertices of k robots. At each time step, any subset of robots may move, each traversing an edge of the graph, provided that no two robots collide. The goal is to compute a schedule that routes all robots to their destinations while minimizing some objective function. In this paper, we focus on the well-studied objective of minimizing the total travel length of all robots. This problem is known to be NP-hard, and it has been shown to be fixed-parameter tractable (FPT), when parameterized by the number k of robots, on full grids (SoCG 2023) and on bounded-treewidth graphs (ICALP 2024). We present a fixed-parameter algorithm for coordinated motion planning, parameterized by the number k of robots, on graphs arising from discretizations of simple polygons. Such graphs are of particular interest in real-world applications, where planar motion is often constrained to discretized representations of polygonal environments. Moreover, these graphs generalize rectangular grids; consequently, our result constitutes a significant step toward resolving the parameterized complexity of coordinated motion planning on subgrids and, ultimately, planar graphs - two prominent open problems in the field.