2026-09-08T01:21:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26464 2026-09-05T19:44:21Z ddc:004 open_access

Coordinated Motion Planning Is FPT on Discretized Simple Polygons Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad coordinated motion planning multi-agent path finding parameterized complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.75 urn:nbn:de:0030-drops-264648 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.75 eng https://creativecommons.org/licenses/by/4.0/legalcode