Coordinated Motion Planning is FPT on Discretized Simple Polygons
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915992409473024 |
|---|---|
| author | Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad |
| author_facet | Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07570 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Coordinated Motion Planning is FPT on Discretized Simple Polygons Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad Data Structures and Algorithms Computational Geometry F.2.2 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. |
| title | Coordinated Motion Planning is FPT on Discretized Simple Polygons |
| topic | Data Structures and Algorithms Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2605.07570 |