{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibmaox7sxqz3xpcinc5nuitmxi6waaosqtagq4uzhzm5eutpop7u4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mlkmabo574a2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.07570v1",
  "publishedAt": "2026-05-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Argyrios Deligkas",
    "Eduard Eiben",
    "Robert Ganian",
    "Iyad Kanj"
  ],
  "textContent": "**Authors:** Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj\n\nIn 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"
}