Abstract 1 Introduction 2 Preliminaries 3 Technical Overview 4 Conclusion References

Coordinated Motion Planning Is FPT on Discretized Simple Polygons

Argyrios Deligkas ORCID Department of Computer Science, Royal Holloway, University of London, Egham, UK    Eduard Eiben ORCID Department of Computer Science, Royal Holloway, University of London, Egham, UK    Robert Ganian ORCID Algorithms and Complexity Group, TU Wien, Austria    Iyad Kanj ORCID School of Computing, DePaul University, Chicago, IL, USA
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.

Keywords and phrases:
coordinated motion planning, multi-agent path finding, parameterized complexity
Category:
Track A: Algorithms, Complexity and Games
Funding:
Argyrios Deligkas: Supported by Engineering and Physical Sciences Research Council (EPSRC) grant EP/X039862/1.
Eduard Eiben: Supported by Engineering and Physical Sciences Research Council (EPSRC) grant UKRI4530: Exploring Parameterized Complexity in Blockchain Systems.
Robert Ganian: Project No. Y1329 of the Austrian Science Fund (FWF), Project No. ICT22-029 of the Vienna Science Foundation (WWTF).
Iyad Kanj: DePaul URC Grants 606601 and 350130.
Copyright and License:
[Uncaptioned image] © Argyrios Deligkas, Eduard Eiben, Robert Ganian, and Iyad Kanj; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Parameterized complexity and exact algorithms
Related Version:
Full Version: https://arxiv.org/abs/2605.07570
DOI:
10.4230/LIPIcs.ICALP.2026.75
Event:
53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)
Editors:
Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In the Coordinated Motion Planning problem (CMP) – also known as Multi-Agent Pathfinding – we are given a graph G and a set ℛ of robots, each with a designated start vertex and destination vertex in G. The goal is to compute a schedule that routes all robots to their destinations while minimizing a given objective. Such a schedule consists of a sequence of discrete time steps in which, at each step, every robot may move to an adjacent vertex, subject to the constraint that no vertex or edge is occupied by more than one robot at the same time. The two by far most prominent and well-studied objectives for CMP are the makespan (i.e., the total number of time steps) [2, 16, 20, 9] and the total distance traveled by the robots [26, 21, 8, 7]. In this work, we focus exclusively on the latter objective.

From an algorithmic standpoint, CMP has attracted substantial attention due to its intrinsic computational difficulty and its close connections to graph search, scheduling, and constraint satisfaction. The problem is further motivated by numerous real-world applications, including automated warehouse systems [38, 24], traffic management and control [25], and robotics [36]. A prominent example is the coordination of hundreds or thousands of mobile robots in Amazon fulfillment centers, where systems such as the Kiva robots rely on efficient and reliable multi-robot path planning to move inventory pods while avoiding collisions [38]. The CMP problem is known to be NP-hard [29, 12, 39] and was posed as the SoCG 2021 Computational Challenge [18].

While the classical complexity of CMP was already studied in the 1990s, investigations from the more refined perspective of parameterized complexity [14, 6] have only begun recently. Most existing work considers the number k=ℛ of robots as the natural parameter. In particular, in 2023 CMP was shown to be fixed-parameter tractable111That is, admits an algorithm running in time f⁢(k)⋅|V⁢(G)|𝒪⁢(1), for some computable function f of k. on full rectangular grids [16]. One year later, a follow-up work established the fixed-parameter tractability w.r.t. k and the treewidth tw⁢(G) of the underlying graph G, without restricting to grids [8]. In fact, that work considered a generalization of CMP, termed GCMP, in which a subset of the robots do not have destinations. In both works, the fixed-parameter (in-)tractability of CMP on subgrids and on planar graphs are identified as significant open problems in the field.

Contributions.

In most practical settings, robot motion takes place in a continuous geometric environment. While there exists a large and largely separate body of work on heuristics and approximation algorithms for robot motion in the plane [5, 22, 34, 37, 39, 40, 3, 10, 15, 28, 31, 32, 33], a common and highly successful paradigm is to discretize the environment, yielding a graph on which the CMP problem is solved. Typically, the free space of a polygonal region is discretized using grids, after which CMP algorithms are applied to the resulting graph [35, 30].

This paradigm underlies a wide range of CMP algorithms, including classical grid-based formulations, conflict-based search and its variants, and hybrid methods that combine sampling-based motion planning with discrete multi-agent coordination [2, 30, 35, 5, 22, 34, 37, 39, 40, 3, 15, 20]. Discretization has also played a key role in recent approximation algorithms for the problem [23]. Consequently, the graphs arising in many CMP applications can naturally be viewed as discretizations of simple polygons.

In this paper, we establish the fixed-parameter tractability of Coordinated Motion Planning, as well as its aforementioned generalization GCMP, on graphs arising from discretizations of simple polygons (see Figure 1 for an illustration and Section 2 for a formal definition).

Theorem 1.

GCMP (and hence also CMP) is fixed-parameter tractable w.r.t. k on discretizations of simple polygons.

Figure 1: An illustration of a discretization of a simple polygon.

Theorem 1 extends existing tractability results beyond full rectangular grids to a broader and more realistic class of graphs. Although the gap between discretized simple polygons and full rectangular grids may appear modest at first glance, the presence of a potentially highly intricate boundary fundamentally changes the problem: any algorithm must optimally navigate robots through narrow corridors and tight geometric constraints. In this setting, both core ingredients of the fixed-parameter algorithm for full rectangular grids – namely, bounding the number of turns [16, Theorem 17] and the use of ILP formulation [16, Theorem 18]) – break down completely.

A second “direct” approach to proving Theorem 1 would be to build on the recently established fixed-parameter tractability of CMP w.r.t. k plus the treewidth of G [8]. To this end, one might hope to apply the irrelevant vertex technique [1] to iteratively identify and remove vertices from G until obtaining an equivalent instance whose underlying graph has bounded treewidth.

While the irrelevant vertex technique has been successfully applied to the related Planar Disjoint Paths problem [1], it does not preserve shortest paths, a property that is crucial for CMP. Indeed, fixed-parameter tractability for Planar Shortest Disjoint Paths was established only in a very recent breakthrough [27]. Moreover, the approach developed there does not extend to CMP, as it relies fundamentally on the requirement that the paths be disjoint.

Instead of identifying and removing irrelevant vertices, we prove Theorem 1 using a novel treewidth-reduction technique. Our approach does not necessarily yield a subgraph of the original graph; rather, it modifies the original graph by introducing “weaving” gadgets. This creates a new graph that is neither planar nor smaller than the original graph; however, it produces a graph with bounded treewidth.

Our technique conceptually rests on the following four main ingredients:

  1. 1.

    a decomposition of G into so-called sectors;

  2. 2.

    a flattening step that identifies and removes parts of G that are “too far” to be useful;

  3. 3.

    a weaving reduction step that replaces certain interior parts of sectors with a collection of vertex-disjoint paths; and

  4. 4.

    a proof that exhaustive application of these steps results in a graph of bounded treewidth.

We then solve CMP using the fixed-parameter algorithm parameterized by k+tw⁢(G) [8]. An overview of these four ingredients, together with a discussion of their relationship to previous work, is provided in Section 3.

Further Related Work.

In addition to the travel-distance minimization objective studied in this paper, coordinated motion planning has been extensively investigated from a parameterized complexity perspective under the objective of minimizing the makespan [9, 16, 20, 19].

Although the computational complexity of many fundamental coordinated motion planning variants was established several decades ago [26], recent years have witnessed renewed interest in these through the lens of parameterized-complexity. Beyond the earlier work on GCMP [8], this line of research has yielded parameterized analyses for settings involving high-speed robots [17], fixed-parameter algorithms on solid grid graphs [16], lower-bound frameworks for tree-like and other structurally restricted graph classes [20, 19], as well as fixed-parameter approximation schemes for tree graphs [9].

Importantly, several of these contributions – most notably the latter three – focus on makespan minimization in a parallel execution model, giving rise to complexity phenomena that differ markedly from those arising in energy-based objectives. For example, even deciding the existence of a constant-makespan schedule is NP-hard on full grids [16]. In contrast, when the objective is to minimize the total energy, constant-energy schedules can be computed in polynomial time; moreover, this result extends to fixed-parameter tractability for graph classes with bounded local treewidth [8, Theorem 5].

We also note recent work on the parameterized complexity of other variants of coordinated motion planning [11, 3], which differ from the problem considered here in both their modeling assumptions and optimization objectives.

2 Preliminaries

We use standard graph-theoretic terminology [13]. For z∈ℕ∗, we write [z] for {1,…,z}.

Let P be a simple polygon, that is, a non-self-intersecting polygon without holes, embedded in the Euclidean plane and containing a unit-length grid H. The discretization of P is the subgraph of H consisting of all vertices and edges that are fully contained in P. A finite subgrid G is called a discretized polygon if it is the discretization of some simple polygon P222We note that the notion of discretized polygons considered here can also be seen as a graph representation of simply connected polyominos..

We assume that every discretized polygon is equipped with a fixed embedding that specifies whether each edge is vertical or horizontal. Accordingly, we say that a vertex v is a →-neighbor of a vertex w if v can be reached from w by traversing an edge that travels rightward, and analogously for {↑,↓,←}.

Given a path P in a discretized polygon G, a vertex v∈V⁢(P) is called a bend if it has two incident edges in P and these edges do not leave v in opposite directions. If P has no bends, we call it a straight path. Moreover, a vertex v∈V⁢(G) is called a boundary vertex if it has degree at most 3; intuitively, such vertices lie near the boundary of the polygon P underlying G.

The Motion Planning Problem.

In our problem of interest, we are given a graph G together with a set ℛ={R1,R2,…,Rk} of k robots. The set ℛ is partitioned into two subsets ℳ and ℱ; the former, ℳ, consists of robots with prescribed destinations, while ℱ contains the remaining “free” robots. Each robot Ri∈ℳ is associated with a starting vertex si and a destination vertex ti in V⁢(G), whereas each robot Ri∈ℱ is associated only with a starting vertex si∈V⁢(G). The elements of the set {si∣i∈[k]}∪{ti∣Ri∈ℳ} are called terminals. We assume that all starting vertices si are pairwise distinct and that all destination vertices ti are pairwise distinct.

Intuitively, at each time step a robot may either move to an adjacent vertex or remain at its current vertex, and all robots may move simultaneously. To formalize this, a route for a robot Ri be a tuple Wi=(u0,…,uq) of vertices in G satisfying: (1) u0=si and uq=ti, and (2) for all j∈[q], either uj−1=uj or uj−1⁢uj∈E⁢(G).

We use a discrete time interval [0,q], where t∈ℕ, to index the sequence of robot movements; at each time step x∈[0,q], every robot either remains stationary or moves to an adjacent vertex.

Two routes Wi=(u0,…,uq) and Wj=(v0,…,vq), where i≠j∈[k], are said to be non-conflicting if (i) for all r∈{0,…,q}, ur≠vr, and (ii) there does not exist an r∈{0,…,t−1} such that vr+1=ur and ur+1=vr. Otherwise, the routes Wi and Wj are said to conflict. Intuitively, two routes conflict if, at the same time, the corresponding robots either occupy the same vertex or traverse the same edge in opposite directions. A schedule 𝒮 is a set of pairwise non-conflicting routes Wi, i∈[k], defined over a common time interval [0,q]. The (traveled) length of a route (or of its associated robot) in 𝒮 is the number of time steps j such that uj≠uj+1. The total traveled length of a schedule is the sum of the lengths of all its routes; this quantity is commonly referred to as the energy in the literature (see, e.g., [18]).

Using the terminology introduced above, we can formally define the problem of interest.

GCMP

  Input: A tuple (G,ℛ=(ℳ,ℱ),k,ℓ), where G is an undirected graph, k,ℓ∈ℕ, and ℛ={Ri∣i∈[k]} is a set of robots partitioned into sets ℳ and ℱ, where each robot in ℳ is given as a pair of vertices (si,ti) and each robot in ℱ as a single vertex si. Problem: Is there a schedule for ℛ of total traveled length at most ℓ?

The Coordinated Motion Planning Problem (CMP) is the restriction of GCMP to instances with ℱ=∅. Throughout the paper, we use CMP-D as shorthand for CMP restricted to graphs which are discretized polygons. We note that our result (Theorem 1) is constructive: it also outputs a schedule of length at most ℓ, if one exists.

3 Technical Overview

In this section, we present an overview of our fixed-parameter algorithm for CMP-D, parameterized by the number k of robots (Theorem 1).

3.1 Preprocessing: Initial Set-Up

The starting point for our work is a preprocessing subroutine developed in recent work by Deligkas, Eiben, Ganian, Kanj and Ramanujan [8, Theorem 15 – full version]. This subroutine can be viewed as a fixed-parameter Turing-reduction which solves any instance of GCMP by making calls to structurally “simpler” instances. In particular, in the resulting instances we only seek schedules in which every robot travels at most c⁢k5 steps, where c is a constant, beyond its shortest-path distance; that is, each robot has travel slack at most λ=c⁢k5.

Moreover, we may assume that every robot in the new instance has a prescribed destination, allowing us to focus exclusively on CMP. The reduction preserves the property of being a discretized polygon. Consequently, in all subsequent steps we restrict our attention to solving CMP-D with the above bound λ on the travel slack.

3.2 Step 1: Sectors and Sector Graphs

To exploit the geometry induced by discretized polygons, we adapt the notion of sectors recently introduced in the setting of fixed-parameter extension algorithms for orthogonal (geometric) drawings [4]. Specifically, we associate with each vertex a bend vector that records, for every terminal and every directional axis d∈{↕,↔}, the minimum number of bends on any shortest path arriving from direction d. Connected subgraphs whose vertices share the same bend vector form a sector. These sectors partition the graph into regions whose vertices exhibit similar behavior with respect to the number of turns required to reach all terminals.

We then define the sector graph Γ, whose vertices correspond to the sectors of G and whose edges capture adjacencies between sectors. A key contribution of our work is establishing the following structural insights about Γ, which will later be used to bound the treewidth of G after exhaustive application of our reduction rules.
Insight 1. The treewidth of Γ is bounded by a function of k.
Insight 2. Every straight path in Γ intersects at most 12⁢k sectors.
Insight 3. Every sector has at most 8 “non-trivial” neighbors in Γ.

▶ Remark.

In prior work introducing sectors [4] in the geometric setting, d ranged over {↑,↓,←,→} and the anchors defining the sectors were required to lie on the boundary of the polygon. In our setting, the change to {↕,↔} is necessary; without it, several of the lemmas underpinning the treewidth proof would not hold. This is one – though not the primary – reason why the treewidth bound from [4, Theorem 22] in the geometric setting cannot be reused. The main reason we cannot directly adapt the proofs from the previous paper is that those rely on prior pruning steps that have removed “dangling” sectors (which cannot be replicated for CMP-D).

Figure 2: Left: An illustration of the sectors of a discretized polygon w.r.t. three terminals defining six ports p1,…,p6. Three of the sectors have highlighted their baselines, showcasing the three non-trivial types of a sector. Notice that terminals form their own “degenerate” singleton sectors. Right: The corresponding sector graph Γ as defined by the sectors.

As a secondary structural insight, we show that each nontrivial sector contains a canonical baseline: a straight path from which the entire sector is reachable by straight extensions. Depending on the baselines present, we obtain a small taxonomy (see Figure 2).

  • ■

    Histogram sectors, with a single baseline.

  • ■

    Staircase sectors, with two orthogonal baselines.

  • ■

    Rectangle sectors, with two parallel baselines forming a full subgrid.

Crucially, there exists a shortest path from a terminal to a vertex in a nontrivial sector which intersects one of the sector’s baselines. This fundamental geometric constraint enables us to apply localized reductions while preserving shortest-path feasibility.

3.3 Steps 2-3: The Reductions

Building on the taxonomy and structural insights described above, we design reduction rules tailored to each sector type. These rules simplify the instance while preserving full equivalence with respect to the existence of a feasible schedule.

Reduction for Histogram Sectors.

For histogram sectors, we observe that any vertex that lies more than λ2 steps away from the baseline cannot be part of any route in a feasible solution. We therefore “flatten” histogram sectors by removing all such vertices, as illustrated in Figure 3.

Figure 3: Illustration of the reduction for histogram sectors. The gray vertices are removed from the graph.

Reduction for Staircase Sectors.

A staircase sector S contains two orthogonal baselines PS1 and PS2 that separate all terminals from the rest of the sector (and from any sectors attached to the interior). We show that if there exists a hypothetical solution that routes a robot out of a “buffer zone” of radius (k+1)⁢(λ+1) around these baselines into a staircase, then a sequence of rerouting arguments yields an alternative solution in which all robots stay within the buffer zone. This, in turn, allows us to safely remove all vertices outside the buffer zone. An illustration is provided in Figure 4.

Figure 4: Illustration of the reduction for staircase sectors. The red region highlights a staircase sector S. Gray vertices indicate the vertices removed by the application of the reduction.

Reduction for Rectangle Sectors.

Rectangle sectors require a more intricate reduction. We show that any feasible schedule can be transformed into a semi-canonical form in which all turns and waiting steps occur within a bounded-width frame along the boundary of the sector. As a consequence, the second frame S∗ – a central rectangular region in a rectangle sector S – contains no turns or waiting vertices/steps (see Figure 5). The proof is non-trivial and relies on a sequence of buffer-shifting arguments, together with a previously established upper bound μ∈k𝒪⁢(k2) on the number of turns in a hypothetical solution, for full rectangular grids [16].

Figure 5: Illustration for reducing the rectangle sectors. The red part is the part of the rectangle sector S that is not inside the second frame S∗. The horizontal and vertical lines connecting the opposite sides of the second frame S∗ do not intersect each other.

We then remove all internal vertices of S∗ and replace them with degree-2 weaving paths connecting pairs of opposite boundary vertices. These paths preserve the relative distances relevant to robot routing. Although this “reduction” results in an instance with more vertices and destroys planarity, we later show that it makes tangible progress toward reducing the treewidth of G.

3.4 Step 4: From Reductions to Bounded Treewidth

By exhaustively applying the reductions outlined above, we obtain a graph in which every sector either has small width or small height, or can be decomposed into at most four components of small width or height, together with a set of additional degree-2 paths. At this stage, it is not difficult to show that each sector individually has bounded treewidth. The main technical challenge lies in proving that the entire graph – where sectors are interconnected along the edges of the sector graph Γ – has bounded treewidth.

▶ Remark.

A treewidth bound on G does not follow directly from the fact that Γ has bounded-treewidth and its nodes represent connected components of G with bounded-treewidth. For instance, consider a long sequence of “flat but wide” sectors stacked on top of each other, i.e., connected along a single long path Γ. A graph G with this structure could have arbitrarily large treewidth, even though each individual sector and the sector graph Γ are of bounded treewidth. While Insight 2 excludes this particular configuration, more complex arrangements of sectors could arise and be chained together, requiring a more careful argument.

Our treewidth-bounding argument for G leverages a bounded-width tree-decomposition 𝒯 of the sector graph Γ (as per Insight 1) to guide the construction of a tree-decomposition of G. We first preprocess G according to Γ to safely detach all sectors that are “trivial” in the sense of Insight 3; this reduces the task to bounding the treewidth of G under the assumption that Γ has degree at most 8. Crucially, this implies that the 12⁢k-th power graph Γ+ – the supergraph of Γ that contains an edge between each pair of sectors of distance at most 12⁢k – also has bounded treewidth. Let (𝒯+,β+) denote a tree-decomposition witnessing this bound.

Next, for any arbitrarily chosen sector in Γ+, we show that it is possible to carefully identify a set of special vertices in the sector (see Figure 6); the number of special vertices per sector is upper-bounded by a function of k, and their positions allow them to act as “semi-separators”. Using the special vertices, we construct a tree-decomposition of G via a two-step approach.

Figure 6: Illustration of initial special vertices for the three types of sector. For each sector S, initial special vertices split the sector into connected components such that each connected component has bounded treewidth and is connected either only to components in the horizontal neighbors of S or only to components in the vertical neighbors of S. Further special vertices are added during the course of our procedure, but we maintain a bound on their number in each sector.
  1. 1.

    We first construct a tree-decomposition template (𝒯+,β′) for a subgraph of G as follows: for each t∈𝒯+, β′⁢(t) replaces each sector in β+⁢(t) with its corresponding special vertices. Crucially, the size of each bag in this template can be upper-bounded by the product of (a) the maximum number of special vertices in a sector and (b) the width of (𝒯+,β+).

  2. 2.

    Next, we show that every connected component C in G−⋃t∈V⁢(𝒯+)β′⁢(t) is a subgraph formed by sectors intersected by the same straight path. Using Insight 2, we can show that C has bounded treewidth and that its entire neighborhood N⁢(C) is contained in the bag β′⁢(t) for some node t∈V⁢(𝒯+). This allows us to append a tree-decomposition of C∪N⁢(C), rooted at the bag containing N⁢(C), to t.

3.5 Putting Everything Together

Having introduced the technical components of our approach, we now combine them to derive an algorithm that proves Theorem 1. Let ℐ=(G,ℛ,k,ℓ) be an instance of GCMP on discretized polygons. We solve ℐ via the following steps.

  1. 1.

    Preprocess ℐ following the procedure described in Subsection 3.1 to ensure bounded slack and to reduce GCMP on discretized polygons to CMP-D.

  2. 2.

    Construct the sectors and the sector graph, as detailed in Subsection 3.2.

  3. 3.

    Exhaustively apply all sector-specific reductions described in Subsection 3.3 yielding a graph whose treewidth is bounded by a function of k.

  4. 4.

    Apply the existing fixed-parameter algorithm for CMP parameterized by k and the treewidth of the resulting graph [8].

This completes the description of the algorithm and establishes Theorem 1.

4 Conclusion

In this paper, we establish the fixed-parameter tractability of Coordinated Motion Planning on graphs arising from discretizations of simple polygons. Our result extends previously-known tractability results beyond full rectangular grids to a broader and more realistic class of graphs.

The central contribution of our work is a reduction of the input graph to one of bounded treewidth. We achieve this by introducing a novel notion of equivalence among vertices, defined in terms of having equivalent “roadmaps” to the set of designated terminal vertices. This notion enables us to partition the graph into regions, called sectors, analyze their structure, and derive appropriate reduction rules based on a characterization of these sectors. Notably, our reduction rules do not follow the standard paradigm of iteratively removing vertices. Instead, they go beyond vertex deletion by introducing auxiliary gadgets, resulting in a reduced graph that may fall outside the original graph class (e.g., violating planarity), while still having bounded treewidth. This contrasts with classical approaches, which typically obtain bounded treewidth by successively deleting vertices from the original graph.

It is not too difficult to extend the FPT result presented here to full grids containing a single hole, which can be viewed as a “flipped” discretized polygon. This naturally leads to the following open questions:

  1. (i)

    Can the FPT techniques developed in this paper be extended to full grids with a constant number of holes, or even a parameter-bounded number of holes?

  2. (ii)

    Is the CMP problem FPT on subgrids, or even on planar graphs?

We strongly believe that the answer to the first question is affirmative and that a fixed-parameter algorithm is attainable by refining the approach introduced here. For question (ii), we conjecture that the answer remains affirmative as well, and that reducing the graph to one of bounded treewidth remains the correct high-level strategy. Such a result, however, would likely require new insights, including more sophisticated vertex classifications and novel treewidth reduction rules. In our view, this constitutes the most pressing open problem arising from the study of the CMP problem. Finally, we remark that fixed-parameter (in)tractability for CMP w.r.t. the number of agents is not settled even for general graphs.

References

  • [1] Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Irrelevant vertices for the planar disjoint paths problem. J. Comb. Theory B, 122:815–843, 2017. doi:10.1016/J.JCTB.2016.10.001.
  • [2] Jacopo Banfi, Nicola Basilico, and Francesco Amigoni. Intractability of time-optimal multirobot path planning on 2D grid graphs with holes. IEEE Robotics and Automation Letters, 2(4):1941–1947, 2017. doi:10.1109/LRA.2017.2715406.
  • [3] Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot. Unlabeled multi-robot motion planning with tighter separation bounds. In SoCG, volume 224, pages 12:1–12:16, 2022. doi:10.4230/LIPIcs.SOCG.2022.12.
  • [4] Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, and Martin Nöllenburg. Extending orthogonal planar graph drawings is fixed-parameter tractable. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 18:1–18:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.SOCG.2023.18.
  • [5] Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, David Tolpin, Oded Betzalel, and Solomon Eyal Shimony. ICBS: Improved conflict-based search algorithm for multi-agent pathfinding. In IJCAI, pages 740–746, 2015. URL: http://ijcai.org/Abstract/15/110.
  • [6] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
  • [7] Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, Dominik Leko, and M. S. Ramanujan. Routing few robots in a crowded network. J. Comput. Syst. Sci., 157:103753, 2026. doi:10.1016/J.JCSS.2025.103753.
  • [8] Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1–53:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. Full version available at https://arxiv.org/abs/2404.15950. doi:10.4230/LIPIcs.ICALP.2024.53.
  • [9] Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. Parameterized algorithms for multiagent pathfinding on trees. In Sanmay Das, Ann Nowé, and Yevgeniy Vorobeychik, editors, Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, Detroit, MI, USA, May 19-23, 2025, pages 584–592. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2025. doi:10.5555/3709347.3743574.
  • [10] Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Henk Meijer, and Christian Scheffer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. SIAM Journal on Computing, 48(6):1727–1762, 2019. doi:10.1137/18M1194341.
  • [11] Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Dániel Marx. Minimizing movement: Fixed-parameter tractability. ACM Trans. Algorithms, 11(2):14:1–14:29, 2014. doi:10.1145/2650247.
  • [12] Erik D. Demaine and Mikhail Rudoy. A simple proof that the (n2−1)-puzzle is hard. Theoretical Computer Science, 732:80–84, 2018.
  • [13] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
  • [14] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.
  • [15] Adrian Dumitrescu. Motion planning and reconfiguration for systems of multiple objects. In Sascha Kolski, editor, Mobile Robots, chapter 24. IntechOpen, Rijeka, 2007.
  • [16] Eduard Eiben, Robert Ganian, and Iyad Kanj. The parameterized complexity of coordinated motion planning. In SoCG, volume 258, pages 28:1–28:16, 2023. full version at https://arxiv.org/abs/2312.07144.
  • [17] Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. A minor-testing approach for coordinated motion planning with sliding robots. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry, SoCG 2025, Kanazawa, Japan, June 23-27, 2025, volume 332 of LIPIcs, pages 44:1–44:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SOCG.2025.44.
  • [18] Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Computing coordinated motion plans for robot swarms: The CG: SHOP challenge 2021. ACM Journal on Experimental Algorithmics, 27:3.1:1–3.1:12, 2022. doi:10.1145/3532773.
  • [19] Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišt’an, Nikolaos Melissinos, and Michal Opler. Exact algorithms for multiagent path finding with communication constraints on tree-like structures. In Toby Walsh, Julie Shah, and Zico Kolter, editors, Thirty-Ninth AAAI Conference on Artificial Intelligence, Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence, Fifteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2025, Philadelphia, PA, USA, February 25 - March 4, 2025, pages 23177–23185. AAAI Press, 2025. doi:10.1609/AAAI.V39I22.34483.
  • [20] Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, and Michal Opler. Exact algorithms and lowerbounds for multiagent path finding: Power of treelike topology. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, Thirty-Eighth AAAI Conference on Artificial Intelligence, pages 17380–17388. AAAI Press, 2024. doi:10.1609/aaai.v38i16.29686.
  • [21] Tzvika Geft and Dan Halperin. Refined hardness of distance-optimal multi-agent path finding. In AAMAS, pages 481–488, 2022. doi:10.5555/3535850.3535905.
  • [22] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107, 1968. doi:10.1109/TSSC.1968.300136.
  • [23] Benjamin Holmgren, Pankaj K. Agarwal, and Alex Steiger. Near-optimal min-sum multi-robot motion planning in a planar polygonal environment. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. SIAM, 2026. to appear. doi:10.1137/1.9781611978971.28.
  • [24] Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K. Satish Kumar, and Sven Koenig. Lifelong multi-agent path finding in large-scale warehouses. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 11272–11281. AAAI Press, 2021. doi:10.1609/AAAI.V35I13.17344.
  • [25] Robert Morris, Corina S. Pasareanu, Kasper Søe Luckow, Waqar Malik, Hang Ma, T. K. Satish Kumar, and Sven Koenig. Planning, scheduling and monitoring for airport surface operations. In Daniele Magazzeni, Scott Sanner, and Sylvie Thiébaux, editors, Planning for Hybrid Systems, Papers from the 2016 AAAI Workshop, Phoenix, Arizona, USA, February 13, 2016, volume WS-16-12 of AAAI Technical Report. AAAI Press, 2016. URL: http://www.aaai.org/ocs/index.php/WS/AAAIW16/paper/view/12611.
  • [26] Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, and Hisao Tamaki. Motion planning on a graph (extended abstract). In STOC, pages 511–520, 1994. doi:10.1109/SFCS.1994.365740.
  • [27] Michał Pilipczuk, Giannos Stamoulis, and Michał Włodarczyk. Planar disjoint shortest paths is fixed-parameter tractable. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. SIAM, 2026. to appear.
  • [28] Geetha Ramanathan and Vangalur S. Alagar. Algorithmic motion planning in robotics: Coordinated motion of several disks amidst polygonal obstacles. In ICRA, volume 2, pages 514–522, 1985. doi:10.1109/ROBOT.1985.1087248.
  • [29] Daniel Ratner and Manfred Warmuth. The (n2−1)-puzzle and related relocation problems. Journal of Symbolic Computation, 10(2):111–137, 1990.
  • [30] Alberto Rivas, Mohamed Alshamsi, Sergio García, Patrizio Pelliccione, and Francisco Chicano. An empirical evaluation of learning-based multi-agent path finding algorithms in warehouse environments. Robotics and Autonomous Systems, 194:105149, 2025. doi:10.1016/J.ROBOT.2025.105149.
  • [31] Jacob T. Schwartz and Micha Sharir. On the piano movers’ problem: III. coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers. The International Journal of Robotics Research, 2:46–75, 1983.
  • [32] Jacob T. Schwartz and Micha Sharir. On the “piano movers’” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Communications on Pure and Applied Mathematics, 36(3):345–398, 1983.
  • [33] Jacob T. Schwartz and Micha Sharir. On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4(3):298–351, 1983.
  • [34] Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40–66, 2015. doi:10.1016/J.ARTINT.2014.11.006.
  • [35] Irving Solis, James Motes, Read Sandström, and Nancy M. Amato. Representation-optimal multi-robot motion planning using conflict-based search. IEEE Robotics and Automation Letters, 6(3):4608–4615, 2021. doi:10.1109/LRA.2021.3068910.
  • [36] Manuela M. Veloso, Joydeep Biswas, Brian Coltin, and Stephanie Rosenthal. Cobots: Robust symbiotic autonomous mobile service robots. In Qiang Yang and Michael J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, page 4423. AAAI Press, 2015. URL: http://ijcai.org/Abstract/15/656.
  • [37] Glenn Wagner and Howie Choset. Subdimensional expansion for multirobot path planning. Artificial Intelligence, 219:1–24, 2015. doi:10.1016/J.ARTINT.2014.11.001.
  • [38] Peter Wurman, Raffaello D’Andrea, and Mick Mountz. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine, 29:9–20, March 2008. doi:10.1609/AIMAG.V29I1.2082.
  • [39] Jingjin Yu and Steven M. LaValle. Structure and intractability of optimal multi-robot path planning on graphs. In AAAI, pages 1443–1449, 2013. doi:10.1609/AAAI.V27I1.8541.
  • [40] Jingjin Yu and Steven M. LaValle. Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics. IEEE Transactions on Robotics, 32(5):1163–1177, 2016. doi:10.1109/TRO.2016.2593448.