The Parameterized Complexity of Coordinated Motion Planning Authors: Eduard Eiben, Robert Ganian, Iyad Kanj Published: 2026 ABSTRACT AbstractIn Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target—prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n2-1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish—as a simpler case—the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids. Introduction Who among us has not struggled through solving the 15-puzzle? Given a small square board, tiled with 15 tiles numbered 1,…,15, and a single hole in the board, the goal of the puzzle is to slide the tiles in order to reach the final configuration in which the tiles appear in (sorted) order; see Figure 1 for an illustration. The 15-puzzle has been generalized to an n×n square-board, with tiles numbered 1,…,n2-1. Unsurprisingly, this generalization is called the (n2-1)-puzzle. Whereas deciding whether a solution to an instance of the (n2-1)-puzzle exists (i.e., whether it is possible to sort the tiles starting from an initial configuration) is in P [22], determining whether there is a solution that requires at most ℓ∈N tile moves has been shown to be NP-hard [9, 28]. The left figure shows an initial configuration of the 15-puzzle and the right figure shows the desirable final configuration. Source: https://en.wikipedia.org/wiki/15_puzzle Deciding whether an (n2-1)-puzzle admits a solution is a special case of Coordinated Motion Planning (CMP), a prominent task originating from robotics which has been extensively studied in the fields of Computational Geometry and Artificial Intelligence (where it is often referred to as Multi-Agent Path Finding). In CMP, we are given an n×m rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. Robots may move simultaneously at each time step, and at each time step, a robot may move to a neighboring gridpoint or stay in its current gridpoint provided that (in either case) it does not collide with any other robots; two robots collide if they are occupying the same gridpoint at the end of a time step, or if they are traveling along the same grid-edge (in opposite directions) during the same time step. We are also given an objective target, and the goal is to compute a schedule for moving the k robots to their destination gridpoints which satisfies the specified target. The two objective targets we consider here are (1) the number of time steps used by the schedule (i.e., the makespan), and (2) the total length traveled by all the robots (also called the “total energy”, e.g., in the SoCG 2021 Challenge [6]); the former gives rise to a problem that we refer to as CMP-M, while we refer to the latter as CMP-L. An illustration is provided in Figure 2. An illustration (left) of an instance of CMP-M with six robots, indicated using distinct colors (blue, green, yellow, red, orange, purple), and a makespan ℓ=4. The starting points are marked using a disk shape (filled circle) and destination points using an annular shape. A schedule indicating each of the robot’s position at each of the four time steps is shown in the table (right) In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number k of robots, and the objective target. In particular, we obtain fixed-parameter algorithms for both problems when parameterized by k and for CMP-L when parameterized by the target, but show that CMP-M remains NP-hard even for fixed values of the target. Given how extensively CMP has been studied in the literature (see the related work below), we consider it rather surprising that fundamental questions about the problem’s complexity have remained unresolved. We believe that one aspect contributing to this gap in our knowledge was the fact that, even though the problems seem deceptively easy, it was far from obvious how to obtain exact and provably optimal algorithms in the parameterized setting. Furthermore, en route to the aforementioned intractability result, we establish the NP-hardness of the classical Vertex Disjoint Paths and Edge Disjoint Paths problems on grids when restricted to bounded-length paths. Related Work CMP has been extensively studied by researchers in the fields of computational geometry, AI/Robotics, and theoretical computer science in general. In particular, CMP-M and CMP-L were posed as the Third Computational Geometry Challenge of SoCG 2021, which took place during the Computational Geometry Week in 2021 [6]. The CMP problem generalizes the (n2-1)-puzzle, which was shown to be NP-hard as early as 1990 by Ratner and Warmuth [28]. A simpler NP-hardness proof was given more recently by Demaine et al. [9]. Several recent papers studied the complexity of CMP with respect to optimizing various objective targets, such as: the makespan, the total length traveled, the maximum length traveled (over all robots), and the total arrival time [1, 11, 17]. The continuous geometric variants of CMP, in which the robots are modeled as geometric shapes (e.g., disks) in a Euclidean environment, have also been extensively studied [2, 7, 11, 13, 29]. Finally, we mention that there is a plethora of works in the AI and Robotics communities dedicated to variants of the CMP problem, for both the continuous and the discrete settings [3, 19, 20, 30, 31, 34, 35]. The fundamental vertex and edge disjoint paths problems have also been thoroughly studied, among others due to their connections to graph minors theory. The complexity of both problems on grids was studied as early as in the 1970’s motivated by its applications in VLSI design [15, 23, 27, 32], with more recent results focusing on approximation [4, 5]. High-Level Overview of Our Results and Contributions As our first set of results, we show that CMP-M and CMP-L are fixed-parameter tractable (FPT) parameterized by the number k of robots, i.e., can be solved in time f(k)·nO(1) for some computable function f and input size n. Both results follow a two-step approach for solving each of these problems. In the first step, we obtain a structural result revealing that every YES-instance of the problem has a canonical solution in which the number of “turns” (i.e., changes in direction) made by any robot-route is upper bounded by a function of the parameter k; this structural result is important in its own right, and we believe that its applications extend beyond this paper. This first step of the proof is fairly involved and revolves around introducing the notion of “slack” to partition the robots into two types, and then exploiting this notion to reroute the robots so that their routes form a canonical solution. In the second step, we show that it is possible to find such a canonical solution (or determine that none exists) via a combination of delicate branching and solving subinstances of Integer Linear Programming (ILP) in which the number of variables is upper bounded by a function of the parameter k; fixed-parameter tractability then follows since the latter can be solved in FPT-time thanks to Lenstra’s result [16, 21, 25]. Next, we consider the other natural parameterization of the problem: the objective target. For CMP-L, this means parameterizing by the total length traveled, and there we establish fixed-parameter tractability via exhaustive branching. The situation becomes much more intriguing for CMP-M, where we show that the problem remains NP-hard even when the target makespan is a fixed constant. As a by-product of our reduction, we also establish the NP-hardness of the classical Vertex and Edge Disjoint Paths problems on grids when restricted to bounded-length paths. The contribution of our intractability results are twofold. First, the NP-hardness of CMP with constant makespan is the first result showing its NP-hardness in the case where one of the parameters is a fixed constant. As such, it refines and strengthens several existing NP-hardness results for CMP [1, 11, 17]. It also answers the open questions in [17] about the complexity of the problem in restricted settings where the optimal path of each robot passes through a constant number of starting/destination points, or where the overlap between any two optimal paths is upper bounded by a constant, by directly implying their NP-hardness. Second, the NP-hardness results for the bounded-length vertex and edge disjoint paths problems on grids also refine and deepen several intractability results for these problems. All previous NP-hardness (and APX-hardness) results for the vertex and edge disjoint paths problems on grids [1, 5, 9, 11, 17, 23, 27, 28] yield instances in which the path length is unbounded. Last but not least, we believe that the NP-hardness results we derive are of independent interest, and have the potential of serving as a building block in NP-hardness proofs for problems in geometric and topological settings, where it is very common to start from a natural problem whose restriction to instances embedded on a grid remains NP-hard. Preliminaries and Problem Definition We use standard terminology for graph theory [28] and assume basic familiarity with the parameterized complexity paradigm including, in particular, the notions of fixed-parameter tractability and para-NP-hardness [8, 12]. For n∈N, we write [n] for the set {1,…,n}. Let G be an n×m rectangular grid, where n,m∈N. Let {Ri∣i∈[k]}, k∈N, be a set of robots that will move on G. Each Ri, i∈[k], is associated with a starting gridpoint si and a destination gridpoint ti in V(G), and hence can be specified as the pair Ri=(si,ti); we assume that all the si’s are pairwise distinct and that all the ti’s are pairwise distinct, and we denote by R={(si,ti)∣i∈[k]} the set of all robots. At each time step, a robot may either stay at the gridpoint it is currently on, or move to an adjacent gridpoint, and robots may move simultaneously. We reference the sequence of moves of the robots using a time frame [0, t], t∈N, and where in time step x∈[0,t] each robot remains stationary or moves. Let a route for Ri be a tuple Wi=(u0,…,ut) of vertices in G such that (i) u0=si and ut=ti and (ii) ∀j∈[t], either uj-1=uj or uj-1uj∈E(G). Intuitively, Wi corresponds to a “walk” in G, with the exception that consecutive vertices in Wi may be identical (representing waiting time steps), in which Ri begins at its starting point at time step 0, and is at its destination point at time step t. Two routes Wi=(u0,…,ut) and Wj=(v0,…,vt), where i≠j∈[k], are non-conflicting if (i) ∀r∈{0,…,t}, ur≠vr, and (ii) ∄r∈{0,…,t-1} such that vr+1=ur and ur+1=vr. Otherwise, we say that Wi and Wj conflict. Intuitively, two routes conflict if the corresponding robots are at the same vertex at the end of a time step, or go through the same edge (in opposite directions) during the same time step. A schedule S for R is a set of routes Wi,i∈[k], during a time interval [0, t], that are pairwise non-conflicting. The integer t is called the makespan of S. The (traveled) length of a route Wi (or the traveled length of a robot Ri), denoted |Wi|, within S is the number of time steps j such that uj≠uj+1, and the total traveled length of a schedule is the sum of the lengths of its routes. We are now ready to define the problems under consideration. Coordinated Motion Planning with Makespan Minimization (CMP-M) Given: An n×m rectangular grid G, where n,m∈N, and a set R={(si,ti)∣i∈[k]} of pairs of gridpoints of G where the si’s are distinct and the ti’s are distinct; k,ℓ∈N. Question: Is there a schedule for R of makespan at most ℓ? The Coordinated Motion Planning with Length Minimization problem (CMP-L) is defined analogously but with the distinction being that, instead of ℓ, we are given an integer λ and are asked for a schedule of total traveled length at most λ. For an instance I of CMP-M or CMP-L, we say that a schedule is valid if it has makespan at most ℓ or has total traveled length at most λ, respectively. We remark that even though both CMP-M and CMP-L are stated as decision problems, all the algorithms provided in this paper are constructive and can output a valid schedule (when it exists) as a witness. We will assume throughout the paper that k≥2; otherwise, both problems can be solved in linear time. Furthermore, we remark that the inputs can be specified in O(k·(logn+logm)+logℓ) (or +logλ) bits, and our fixed-parameter algorithms work seamlessly even if the inputs are provided in such concise manner. On the other hand, the lower-bound result establishes “strong” NP-hardness of the problem (i.e., also applies to cases where the input contains a standard encoding of G as a graph). For two gridpoints p=(xp,yp) and q=(xq,yq), the Manhattan distance between p and q, denoted Δ(p,q), is Δ(p,q)=|xp-xq|+|yp-yq|. For two robots Ri,Rj∈R and a time step x∈N, denote by Δx(Ri,Rj) the Manhattan distance between the grid points at which Ri and Rj are located at time step x. The following notion will be used in several of our algorithms: Definition 1 Let (G,R,k,∙) be an instance of CMP-M or CMP-L and let T=[t1,t2] for t1,t2∈N. For a robot Ri with corresponding route Wi, let up and uq be the gridpoints in Wi at time steps t1 and t2, respectively. Define the slack of Ri w.r.t. T, denoted slackT(Ri), as (t2-t1)-Δ(up,uq) (alternatively, (q-p)-Δ(up,uq)). Observe that the slack measures the amount of time (i.e., number of time steps) that robot Ri “wastes” when going from up to uq relative to the shortest time needed to get from up to uq. For a robot Ri with route Wi, for convenience we write slackT(Wi) for slackT(Ri). When dealing with CMP-M, we write slack(Ri) as shorthand for slack[0,ℓ](Ri), and when dealing with CMP-L, we write slack(Ri) as shorthand for slack[0,λ](Ri). CMP Parameterized by the Number of Robots In this section, we establish the fixed-parameter tractability of CMP-M and CMP-L parameterized by the number k of robots. Both results follow the two-step approach outlined in Subsection 1.2: showing the existence of a canonical solution, and then reducing the problem via branching to a tractable fragment of Integer Linear Programming. These two steps are described for CMP-M in Subsections 3.1 and 3.2, while Subsection 3.3 shows how the same technique is used to establish the fixed-parameter tractability of CMP-L. Canonical Solutions for CMP-M We begin with a few definitions that formalize some intuitive notions such as “turns”. Let W=(u0,…,uℓ), where ℓ>2, be a route in an n×m grid G, where n,m∈N. We say that W makes a turn at ui=(xi,yi), where i∈{1,…,ℓ-1} if ui+1≠ui and moreover the following holds. Let uj be the element of W with maximum j such that j3kk. Let Mi be the sequence of turns that W makes in Ti, and note that, by Observation 2, Mi is monotone. Let Ci be the sequence of cells determined by one of the two alternating sequences of turns in Mi, and note that |Ci|>3kk/3=kk. We would like to show that there is a route in S that contains a cell C formed during Ti that can be flattened, contradicting the minimality of the schedule w.r.t. the number of turns made during Ti. In what follows, for convenience, we will abuse the terminology and say that a route Wj conflicts with Wi in C if Wj collides with the route resulting from the flattening of C in Wi . For any cell C in Ci, since S is minimal with respect to the number of turns, C cannot be flattened in Wi. Therefore, there must exist a route that conflicts with Wi in C. Since the total number of routes is k, there exists a route Wj, j∈[k]∧j≠i, that conflicts with Wi in at least |Ci|/(k-1)>kk-1 many cells. Moreover, Wj cannot have any slack in the interval Tj⊆Ti determined by the first time step Wj conflicts with Wi in Ci and the step before the last time it does; otherwise, it would not conflict with Wi in subsequent cells in Ci. Observe that, in order for Wj to conflict with Wi in a cell C that Wj has no slack in, Wj must make a turn inside C. Moreover, it is easy to verify that this turn must be in the same direction as the turn forming C; otherwise, Wj would not conflict with Wi in any subsequent cells. (Note that, since Wj has no slack in C, if it does not make a turn at all, then it would conflict with Wi, which would contradict the validity of S.) Let Mj be the sequence of turns made by Wi during Tj, and note that, by Observation 2, Mj is monotone. Let Cj be the sequence of cells formed by one of the two alternating sequences of turns in Mj that are nested within the cells in Ci, and observe that |Cj|≥|Ci|/k>kk-1 and that Wj has no slack in any of the cells in Cj. Since Mj is monotone and the cells in Cj are nested within those in Ci, we can repeat the process on Wj with respect to Cj in the interval Tj⊆Ti, and the process must end after at most k-1 many iterations with a cell (corresponding to some route) that can be flattened, contradicting the minimality of the schedule S. □ By carefully subdividing a time interval into roughly σ(k) subintervals, for a function σ(k) that upper bounds the slack of a robot, and applying Lemma 4 to each of these subintervals, we can extend the result in Lemma 4 to robots whose slack is upper bounded by σ(k): Lemma 5 Let (G,R,k,ℓ) be a YES-instance of CMP-M, and let Ti⊆[0,ℓ]. Then (G,R,k,ℓ) has a minimal schedule such that, for each Ri, i∈[k], satisfying slackTi(Wi)≤σ(k) for an arbitrary function σ, its route Wi satisfies νTi(Wi)≤τ(k), where τ(k)=3kk(σ(k)+1)+σ(k). Proof Let (G,R,k,ℓ) be a YES-instance of CMP-M, let S be a minimal schedule for (G,R,k,ℓ), and let Ti⊆[0,ℓ]. Suppose that the route Wi for a robot Ri satisfies slackTi(Wi)≤σ(k). Then there exists a set Γ⊂Ti of at most σ(k) many time steps such that Ti\Γ is partitioned into at most r≤σ(k)+1 many intervals I1,…,Ir, and such that in each Ij, j∈[r], Wi has no slack. The partitioning of Ti into I1,…,Ir can be done iteratively, from left to right, by choosing I1 to be the largest prefix subinterval of Ti during which there is no slack, and repeating this construction starting from the right endpoint of I1. Observe that, from the definition of slack, and the fact that Δ satisfies the triangular inequality, for any time interval T=[a,b] and any t∈[a,b], we have slack[a,b](Wi)≥slack[a,t](Wi)+slack[t,b](Wi). Now applying Lemma 4 to each interval Ij, we obtain an equivalent route to the subroute of Wi restricted to Ij that makes at most 3kk many turns (in Ij). By an additive argument, and accounting for the possible turns at the σ(k)-many points in Γ, we get νTi(Wi)≤3kk(σ(k)+1)+σ(k). Applying the above argument to each route Wi of slack at most σ(k), the result follows. □ Lemma 5 already provides us with the property we need for “small-slack” robots: their number of turns can be upper-bounded by a function of the parameter. We still need to deal with the more complicated situation of “large-slack” robots. Our next course of action will be establishing the existence of a sufficiently large time interval during which the “large-slack” robots are far from the “small-slack” ones. We begin with an observation linking the slack of two robots that “travel together”. Observation 6 Let R,R′∈R and let T=[t1,t2]⊆[0,ℓ]. Let u,u′ be the gridpoints at which R and R′ are located at time step t1, respectively, and v,v′ those at which R and R′ are located at time t2, respectively. Suppose that Δ(u,u′)≤d(k) and Δ(v,v′)≤d(k), for some function d(k). Then slackT(R′)≤slackT(R)+2d(k). Proof Let ℓT=t2-t1. By definition, we have slackT(R′)=ℓT-Δ(u′,v′). Since Δ satisfies the triangular inequality, we have Δ(u,v)≤Δ(u,u′)+Δ(u′,v′)+Δ(v′,v)≤Δ(u′,v′)+2d(k), and hence, Δ(u′,v′)≥Δ(u,v)-2d(k). It follows that slackT(R′)≤ℓT-Δ(u,v)+2d(k)=slackT(R)+2d(k). □ Intuitively speaking, the above observation implies that a robot with a large slack in some time interval cannot be close to a robot with a small slack for the whole interval (otherwise, both robots would be moving at “comparable speeds”, which would contradict that one of them has a small slack and the other a large-slack). Next, we observe that either the slack of all the robots can be upper-bounded by a function h, or there is a sufficiently large multiplicative gap between the slack of some robots. This will allow us to partition the set of robots into those with small or large slack. For any function h, let h(j)=h∘⋯∘h⏟jtimes denote the composition of h with itself j times. Lemma 7 Let (G,R,k,ℓ) be an instance of CMP-M and let T⊆[0,ℓ]. Let h(k) be any computable function satisfying h(p)(k)≤h(q)(k) for p≤q∈[k]. Then either slackT(Ri)≤h(k)(k) for every i∈[k], or there exists j∈N with 2≤j≤k, such that R can be partitioned into (RS,RL) where RL≠∅, slackT(R)≤h(j-1)(k) for every R∈RS, and slackT(R′)>h(j)(k) for every R′∈RL. Proof Create the partitioning (RS,RL) of R by iterating the following process. Start with RS=∅. In iteration j, for j=1,…,k, add to RS every robot R∈R such that slackT(R)≤h(j)(k); if no robot is added to RS in iteration j then stop the process. Cleary, the process stops after at most j≤k iterations. If the process stops at iteration j with RS=R then slackT(R)≤h(j)(k)≤h(k)(k) for every R∈R. Otherwise, RL=R\RS≠∅, and since in each iteration of the process at least one robot is added to RS and RS≠R, no robot was added to RS in iteration j, and hence, we have slackT(R)≤h(j-1)(k) for every R∈RS, and slackT(R′)>h(j)(k) for every R∈RL. □ The next definition yields a time interval with the property that small-slack robots are sufficiently far from large-slack ones during that interval. Such an interval will be useful, since within it we will be able to re-route the large-slack robots (which are somewhat flexible) to reduce the number of turns they make, while avoiding collision with small-slack robots. Definition 8 Let σ(k),γ(k),d(k) be functions such that σ(k)<γ(k). An interval T=[t1,t2]⊆[0,ℓ] is a [σ,γ]-good interval w.r.t. d(k) if R can be partitioned into RS and RL such that: (i) every R∈RS satisfies slackT(R)≤σ(k) and every R′∈RL satisfies slackT(R′)≥γ(k); (ii) for every time step t∈T, Δt(R,R′)≥d(k) for every R∈RS and every R′∈RL; and (iii) there exists a robot Ri∈RL such that νT(Wi)>3kk(σ(k)+1)+σ(k). If the function d(k) is specified or clear from the context, we will simply say that T is a [σ,γ]-good interval (and thus omit writing “w.r.t. d(k)”). The following key lemma asserts the existence of a good interval assuming the solution contains a robot that makes a large number of turns: Lemma 9 Let (G,R,k,ℓ) be a YES-instance of CMP-M and let S be a minimal schedule for (G,R,k,ℓ). If there exists R′∈R with route W′ such that ν(W′)>3k3+1·(3kk·(32k2-2k·k2k2-2k+1)+32k2-2k·k2k2-2k), then there exists a [σ,γ]-good interval T⊆[0,ℓ] w.r.t. a function d(k) such that kk-1≤σ(k)≤32k2-2k·k2k2-2k, and d(k)=γ(k)=σ13(k). Proof We define T recursively using the following process. Let h(k)=k13 and T′=[0,ℓ]. Since νT′(W′)>3kk(kk+1)+kk, we have slack(R′)>kk. By Lemma 7, R can be partitioned into (RS,RL) such that R′∈RL, slackT′(Ri)≤h(j-1)(k) for every Ri∈RS where 2≤j≤k, and slackT′(Ri)≥h(j)(k) for every Ri∈RL. Let σ0=kk-1 and γ0(k)=d0(k)=h(σ1)=σ013. If Δt(Ri,Rj)≥d0(k) for every Ri∈RL, every Rj∈RS, and every t∈T′, then T′ is a [σ0,γ0]-good interval w.r.t. d0(k). Otherwise, there must exist a first/smallest time step t1∈T′ (possibly t1=0), a robot R′′∈RL, and a robot R∈RS such that Δt1(R,R′′) is at most d0(k); let t1′ be the last time step in T′ (possibly t1′=ℓ) such that Δt1(R,R′′) is at most d0(k). Consider the subinterval T0=[t1,t1′] of T′ and note that R and R′′ are at distance more than d0(k) at each time step in T′\T0. The subinterval T0 splits T′ into at most three subintervals: I1,T0,I2, where I1,I2 are the subintervals before and after T0, respectively. The route W′ of R′ satisfies that ν(W′), restricted to at least one of I1, T0, I2 is at least νT(W′)/3. Consider the interval T1 in {I1,T0,I2} such that νT1(W′)≥νT(W′)/3; clearly T1≠∅. Observe that, for any Ri∈R, slackT1(Ri)≤slackT′(Ri). We distinguish the following two cases. Case (1): T1∈{I1,I2}. In this case, for any t in T1, we have Δt(R,R′′)>d0(k), and hence robots R and R′′ will no longer get within a Manhattan distance of d0(k) at any time step during T1. We set σ1(k)=σ0(k), γ1(k)=d1(k)=d0(k), and repeat the process w.r.t. T1. Note that this case can occur less than k2-many times with respect to the same distance function. Case (2): T1=T0. By Observation 6, we have slackT1(R′′)≤slackT1(R)+2d0(k). In this case, we apply Lemma 7 to partition R into (RS,RL) such that slackT′(Ri)≤h(j′-1)(σ0(k)+2d0(k)) for every Ri∈RS where 2≤j′≤k, and slackT′(Ri)≥h(j′)(σ0(k)+2d0(k)) for every Ri∈RL. We set σ1(k)=h(j′-1)(σ0(k)+2d0(k)), γ1(k)=d1(k)=h(σ1(k))=σ113(k), and repeat the above process w.r.t. T1. Note that, in each of the above two cases, R′ satisfies νT1(W′)≥νT′(W′)/3. If case (2) applies (i.e., T1=T0), then the set of robots Ri satisfying slackT′(Ri)≤σ0(k) is a proper subset of that satisfying slackT1(Ri)≤σ1(k) since the former excludes R′′∈RL, which is included in the latter. It follows that Case (2) can occur at most k-1 times during the whole process, and for each occurrence of Case (2), a new (and larger) distance function dp(k), p∈N, is defined. Moreover, with respect to the same function dp(k), Case (1) can occur at most k2-many times, since for each such occurrence, at least one pair of robots that were within a Manhattan distance of dp(k) becomes at distance more than dp(k) in the new time interval under consideration. It follows that the above process ends after at most r<(k-1)·k2≤k3-1 iterations, during which the distance function dp(k) has been increased at most k-1 times. By a straightforward inductive argument, it can be easily shown that: (i) σr(k)≤32k2-2k·k2k2-2k and γr(k)=dr(k)=h(σr(k))=σr13(k); (ii) for every t∈T, we have Δt(Rj,Ri)≥dr(k) for every Rj∈RS and Ri∈RL; (iii) slackT(Rj)≤σr(k) for every Rj∈RS and slackT(Ri)≥γr(k) for every Ri∈RL; and (iv) νT(W′)>3kk(σr(k)+1)+σr(k) and hence R′∈RL. Therefore, by letting σ(k)=σr(k) and d(k)=γ(k)=h(σ(k))=σr13(k), the process stops with a [σ,γ]-good interval T with respect to d(k). This completes the proof. □ Once we fix a good interval T, we can finally formalize/specify what it means for a robot to have small or large slack within T: Definition 10 Let T=[t1,t2]⊆[0,ℓ] be a [σ,γ]-good interval with respect to some function d(k), where σ(k)<γ(k) are two functions, and let Ri∈R. We say that Ri is a T-large slack robot if slackT(Ri)≥γ(k); otherwise, slackT(Ri)≤σ(k) and we say that Ri is a T-small slack robot. At this point, we are finally ready to prove the core tool that establishes the existence of a solution with a bounded number of turns (w.r.t. the parameter), even in the presence of large-slack robots: for each solution with too many turns, we can produce a different one with strictly less turns. The proof of this statement differs substantially depending on whether the input grid is mainly one-dimensional (in particular, when the size of one dimension can be upper-bounded by a specific function of k), or two-dimensional (the “usual” case), as each of these two cases leads to a different rerouting scheme for the large-slack robots. Both cases, however, rely on the properties of a good interval. Note that the property that large-slack robots are far from small-slack ones during the good interval does not immediately lead to a rerouting of the large-slack robots that makes fewer turns. The issue is that if we replace the route of a large-slack robot so as to reduce its number of turns, then the new route may bring the large-slack robot much closer to the small-sack robots, and hence may lead to collisions. Therefore, the desired rerouting scheme needs to be carefully designed, and it exploits the properties of a good interval as follows. First, the rerouting scheme exploits the property that the large-slack robots are far from the small-slack ones at the beginning of the good interval to reposition/reorder the large-slack robots nicely on the grid lines, and to place them on some safe gridpoints (i.e., where no other robots will pass). Then, we define organized routes that make very few turns for the large-slack robots toward some intermediate safe gridpoints close to their locations at the end of the good interval. We will then exploit the large slack of these robots to route them to these safe gridpoints by having them wait an appropriate amount of time at certain places so as to avoid collision. Finally, we will again exploit the property that large-slack robots are far from small-slack ones at the end of the good interval to reorder these robots at their current (safe) gridpoints and route them so that they are present at their locations at the end of the good interval. The following lemma is used in the proof of Lemma 12, which establishes the existence of a canonical solution in the special case where exactly one of the two grid dimensions is upper bounded by a function of the parameter. Before proceeding, we introduce some additional terminology. We say that a robot Ri∈R uses gridline L if there exist two consecutive points in Wi that belong to L. We say that a gridpoint u is to the left of grid point v if the x-coordinate of u is smaller or equal to the x-coordinate of v. Lemma 11 Let (G,R,k,ℓ) be a YES-instance of CMP-M such that the vertical dimension of G is upper bounded by a function p(k)>1, and let S be a solution for this instance. Let T=[t1,t2]⊆[0,ℓ], and let Ri be a robot such that slackT(Wi)≤σi(k), σi(k) is an arbitrary upper-bound on the slack of Wi and Wi is Ri’s route in S. Let Rj∈R and suppose that, for each t∈T, Δt(Ri,Rj)≥d(k) for some function d(k)>σi(k)+2p(k). Let pi,qi be the starting and ending points of Ri at time steps t1 and t2, respectively, and pj,qj those for Rj. Then (i)the relative order of pi,pj is the same as that of qi,qj; that is, pi is to the left of pj if and only if qi is to the left of qj. Moreover, Δ(qi,qj)≥d(k). the relative order of pi,pj is the same as that of qi,qj; that is, pi is to the left of pj if and only if qi is to the left of qj. Moreover, Δ(qi,qj)≥d(k). (ii)For any route Wj′T for Rj in T between pj and qj such that |Wj′T|-Δ(pj,qj)≤δj(k), for some function δj(k), and for any t∈T, if at t Ri is at grid point ui in Wi and Rj is at uj in Wj′, then Δ(ui,uj)≥d(k)-2p(k)-σi(k)-δj(k). For any route Wj′T for Rj in T between pj and qj such that |Wj′T|-Δ(pj,qj)≤δj(k), for some function δj(k), and for any t∈T, if at t Ri is at grid point ui in Wi and Rj is at uj in Wj′, then Δ(ui,uj)≥d(k)-2p(k)-σi(k)-δj(k). Proof For (i), we show the statement for the case where pi is to the left of pj; the other case is symmetric. For any t∈T, let xit and xjt denote the x-coordinates of the gridpoints at which Ri and Rj are located at time step t, respectively. We proceed by contradiction and assume that qi is not to the left of qj. For t=t1, since pi is to the left of pj and Δ(pi,pj)≥d(k), we have xjt-xit>0. Since qj is to the left of qi, at time step t=t2 we have xjt-xjt≤0. Since in each time step the difference xjt-xit can decrease by at most 2, there must exist a time step t at which xjt-xjt≤2, which implies that Δt(Ri,Rj)≤p(k)+2 contradicting the hypothesis. It follows that qi is to the left of qj, and since Δ(qi,qj)=Δt2(Ri,Rj), we have Δ(qi,qj)≥d(k). To prove (ii), let Wj′T be a route for Rj in T between pj and qj such that |Wj′T|-Δ(pj,qj)≤δj(k). Without loss of generality, assume that pi is to the left of pj as the proof is analogous for the other case. Then it follows from part (i) (proved above) that qi is to the left of qj and that Δ(qi,qj)≥d(k). Since Δ(pi,pj)≥d(k) and the grid’s vertical dimension is at most p(k), the horizontal distance, dH, between pi and pj satisfies dH≥d(k)-p(k). For any t∈T, let xit and xjt denote the x-coordinates of the gridpoints at which Ri and Rj are located at time step t, respectively. Suppose first that qi is to the left of pi. For any t∈T, xit satisfies xit≤xi+σi(k)+p(k)-(t-t1), where xi is the x-coordinate of pi. Regardless of how the route Wj′T for Rj is, for any t∈T, the x-coordinate of the point of Wj′T at time t, xj′t, satisfies: xj′t≥xj-(t-t1)≥xi+dH-(t-t1), where xj is the x-coordinate of pj. It follows that xj′t≥xit-σi(k)-p(k)+(t-t1)+dH-(t-t1) and hence, xj′t-xit≥d(k)-2p(k)-σi(k). Observing that, for any t∈T, Δ(ui,uj) is lower bounded by xj′t-xit, it follows that, for any t∈T we have Δ(ui,uj)≥d(k)-2p(k)-σi(k)≥d(k)-2p(k)-σi(k)-δj(k). Suppose now that qi is to the right of pi. Let tj∈T be the time step at which Rj reaches qj. For any t∈[t1,tj], xit satisfies xit≤xi+(t-t1), where xi is the x-coordinate of pi. Regardless of how the route Wj′T for Rj is, for any t∈[t1,tj], the x-coordinate of the point of Wj′T at time t, xj′t, satisfies: xj′t≥xj+(t-t1)-p(k)-δj(k), where xj is the x-coordinate of pj. It follows that xj′t-xit≥d(k)-2p(k)-δj(k). Observing that, for any t∈[t1,tj], Δ(ui,uj) is lower bounded by xj′t-xit, it follows that, for any t∈[t1,tj] we have Δ(ui,uj)≥d(k)-2p(k)-δj(k)≥d(k)-2p(k)-σi(k)-δj(k). Now for any t∈[tj+1,t2], Rj is located at qj. Since qi is to the left of qj, slackT(Ri)≤σi(k), and Δ(qi,qj)≥d(k), it follows that for any t∈[tj+1,t2], Δ(ui,uj)≥d(k)-σi(k). Therefore, for any t∈T, we have Δ(ui,uj)≥d(k)-2p(k)-σi(k)-δj(k). □ The following two lemmas prove the existence of a canonical solution. Lemma 12 handles the special case where exactly one of the two grid dimensions is upper bounded by a function of the parameter, whereas Lemma 13 treats the case where both dimensions are unbounded. (The simple case, in which both dimensions are bounded, is FPT, as explained in the proof of Theorem 15.) Lemma 12 Let (G,R,k,ℓ) be a YES-instance of CMP-M and let S be a minimal schedule for (G,R,k,ℓ). Let T=[t1,t2]⊆[0,ℓ] be a [σ,γ]-good interval with respect to d(k), where kk-1≤σ(k)≤32k2-2k·k2k2-2k, and d(k)=γ(k)=σ13(k). Assume that exactly one dimension of the grid G is at least p(k)=2k·(3kk(σ(k)+1)+σ(k))+4k. Then for every T-large-slack robot Ri, there is a route Wi′ that is equivalent to Wi and such that νT(Wi′) is at most 3k3 and Wi′ is identical to Wi in [0,ℓ]\T. Proof For Ri∈R, denote by WiT the restriction of Wi to T. Let RL be the set of T-large slack robots and RS be that of T-small slack robots, as defined in Definition 10. By Lemma 5, we may assume that for every Ri∈RS, we have νT(Wi)≤τ(k)=3kk(σ(k)+1)+σ(k). From the hypothesis of the current lemma, we may assume in what follows that exactly one of the (two) grid dimensions, say w.l.o.g. the horizontal dimension, is larger than p(k), whereas the vertical dimension is upper bounded by p(k). Recall that, at any time step t∈T, for every Ri∈RS and for every Rj∈RL, we have Δt(Ri,Rj)≥d(k). It follows from part (i) of Lemma 11 that, for every Ri∈RS and for every Rj∈RL, the starting point pi of Ri at time t1 is to the left of the starting point pj of Rj if and only if the destination point qi of Ri at t2 is to left of the destination point qj of Rj; moreover, Δ(qj,qj)≥d(k). Now we define the route Wi′ for each Ri∈RL. If there is only one horizontal line in the grid, then since (G,R,k,ℓ) is a YES-instance, the order of the starting points of the robots on this horizontal line must match that of their destination points, and we define each Wi′ to be the sequence of points on the horizontal line segment joining its starting point to its destination point. Clearly, νT(Wi′)=0 for each Ri∈RL, and no two routes for any two robots conflict. Moreover, each robot in R is routed along a shortest path between its starting and destination points, and the statement of the lemma obviously follows in this case. Suppose now that there are at least two horizontal lines in G. We define the route Wi′ for each Ri∈RL in three phases. In phase (1), we simultaneously shift the robots in RL horizontally so that each occupies a distinct vertical line; this can be achieved in at most k time steps (by shifting so that robots occupying the same vertical line are shifted properly by different lengths) and such that each robot in RL makes at most 1 turn (during the shifting). We arbitrarily designate two horizontal lines, Dleft and Dright, where Dleft will be used to route every Ri∈RL whose destination point is to the left of its current point, and Dright will be used to route every Ri∈RL whose destination point is to the right of its current point. In phase (2), we route every Ri∈RL to its designated horizontal line in {Dleft,Dright} along its distinct vertical line; this can be done in at most p(k) time steps (i.e., the vertical dimension of G) and such that each robot in RL makes at most 1 turn. In phase (3), we route each Ri∈RL along its designated horizontal line (either Dleft or Dright) to the vertical line containing its destination point; note that all the robots that have the same designated line move in the same direction. That is robots in Dleft move towards left and on Dright right. Once a robot reaches the vertical line containing its destination point, it is routed along that vertical line to its destination on it. Conflicts among the robots in RL may arise in phase (3), and we discuss how to resolve them next. We treat the case where there are exactly two horizontal lines in G, Dleft and Dright; the case where there are more horizontal lines is easier since there is more space to move/swap the robots. We clarify first how, in phase (3), a robot R that has reached the vertical line LR containing its destination point, and that needs to move vertically to its destination point (i.e., its destination point is on the other horizontal line), is routed along to its destination point. Without loss of generality, we assume that R reached LR by moving on Dright. If R’s destination point is not occupied by any robot, then in the next time step, only R moves to its destination point while all other robots wait; note that there can be at most k such time steps during which a robot moves to its destination point. Otherwise, R’s destination point p′ is occupied by a robot R′, and in such case a conflict arises; we call such conflicts vertical-conflicts. When a vertical-conflict arises, we prioritize it over the other type of conflicts (discussed below) and resolve them one at a time (in arbitrary order), while freezing the desired motion of all the robots that are not involved in the vertical-conflict. To resolve a vertical-conflict, let p be the gridpoint at which R currently is, and we distinguish two cases. If p is the destination point of R′, then we swap R and R′ by simultaneously shifting horizontally by one position all the robots located on the side of LR that contains at least k vertical lines (thus creating an empty space on that side of LR), and then rotating R and R′ using that empty space so that they exchange positions in 3 time steps, and then simultaneously shifting back by one position all the robots that were shifted. Clearly, this swap can be achieved in at most 5 time steps, in which each robot makes at most 5 turns, and resolves the vertical-conflict. Suppose now that p is not the destination point of R′, and hence, the destination point of R′ must be to the left of LR. Consider the sequence S of robots (if any) that appear consecutively to the left of R′ on Dleft. If no robot in this sequence has its destination point above its current point, then there must exist at least one empty space to the left of this sequence on Dleft; moreover, the destination point of each robot in this sequence is to its left. To resolve the vertical-conflict in this case, we simultaneously shift R′ and the robots in S by one position to the left while moving R to its destination p′. This incurs one time step and at most one turn per robot. Suppose now that one robot in this sequence S has its destination point above it. Let R′′ be the closest such robot to R′, and let p′′ be the gridpoint above R′′. At least one side of LR (either left or right or both) contains at least k vertical lines; without loss of generality, assume it is the right side and the treatment is analogous if it was the left side. We horizontally and simultaneously shift all robots to the right of LR on both Dleft and Dright by one position to the right thus creating one unoccupied gridpoint on each of Dleft and Dright to the right of LR, move R in two steps using the unoccupied gridpoints to the right of p′, and simultaneously shift any robots between p′′ and p one position to the right, R′′ to p′′ and all robots in S other than R′′ one position to the left. Finally, move R to p′. This sequence of moves resolves the vertical-conflict in at most 3 time steps and incurs at most 3 turns per robot. It follows that the at most k vertical conflicts can be resolved in at most 5k time steps and by making at most 5 turns per robot. Suppose now that there are no vertical-conflicts and that a conflict arises in phase (3) when a robot is moving into a point on its designated line that is already occupied by another robot. We will call such conflicts horizontal-conflicts. When multiple horizontal conflicts arise during a time step, we prioritize them as follows. A horizontal-conflict on Dright has higher priority than one on Dleft, and for conflicts on the same line, we prioritize them from right (highest) to left (lowest) for Dright and left to right for Dleft. When multiple horizontal conflicts arise during a time step t, we only consider one conflict at a time, in order of priority, and freeze the motion of all the robots that are not involved in the conflict and its resolution, by keeping their current position before time step t. Without loss of generality, we discuss how to resolve a horizontal-conflict C on Dright. Suppose that R, which is currently located at grid point p on Dright, wants to move during time step t into a gridpoint p′ on Dright that is currently occupied by a robot R′. If p′ is not the destination of R′, then the point, p′′, to the right of R′ on Dright must be unoccupied (and conflict C would not have arisen); otherwise, a conflict of higher priority, which is that resulting from moving R′ from p′ to p′′ should have been considered before C. Therefore, we may now assume that p′ is the destination of R′. Let q′ be the gridpoint on the same vertical line as p′ and q that on the same vertical line as R. Note that since the destination point of R must be to the right of p, there are gridlines to p′’s right. We resolve conflict C as follows. We first move R′ vertically to the point q′ on Dleft; if q′ is occupied, we simultaneously shift by one position each robot on Dleft starting from q′ and residing on the larger vertical side of q′ in the direction of the larger side. We simultaneously move R′ to q′ and R to p′. In the next time step, we attempt moving only R to the point p′′ to the right of p′ on Dright. If no conflicts arise, we simultaneously move R to p′′, reverse any shifts on Dright that we performed to resolve C, and move R′ back to p′ on Dright. If, however, a conflict arises when moving R to p′′, we recursively resolve the new conflict, and when we are done, reverse any shifting performed on Dright when resolving C, and move R′ back to p′. Note that, since during these recursive calls, we are resolving conflicts that proceed in the same direction on Dright (and shifts that follow the same direction on Dleft), no cyclical dependencies can arise during the recursion. In the worst case, to resolve such a conflict we incur no more than 2k time steps and no more than 2k turns, and since there can be at most k2-many horizontal conflicts (where robots could be in reverse order), resolving all horizontal-conflicts incurs no more than k3 time steps, and no more than k3 turns per robot. It is easy to see that, over the three phases of the process, each Wi′ satisfies that ν(Wi′)≤1+1+5k+k3≤3k3 (assuming k≥2). Moreover, over all three phases of the process, the length of Wi′ deviates from that of a shortest path between the endpoints of Wi′ by δi(k), which is at most the number of additional time steps spent in the three phases to shift the robots so that they occupy distinct vertical lines, route them to their designated horizontal lines, and resolve their conflicts. It follows that δi(k)≤k+p(k)+5k+k3≤p(k)+3k3. Since d(k)=σ13(k) and σ(k)≥kk-1, it is straightforward to verify that d(k)>3p(k)+σ(k)+3k3 for k≥2, and it follows from part (ii) of Lemma 11 that no route Wi′ of a robot Ri∈RL conflicts with a route of a robot in RS. Moreover, since γ(k)>δi(k), it follows that each Ri∈RL arrives to its destination (where it stays) no later than time step t2, and the statement of the lemma is proved in this case. □ Lemma 13 Let (G,R,k,ℓ) be a YES-instance of CMP-M and let S be a minimal schedule for (G,R,k,ℓ). Let T=[t1,t2]⊆[0,ℓ] be a [σ,γ]-good interval with respect to d(k), where kk-1≤σ(k)≤32k2-2k·k2k2-2k, and d(k)=γ(k)=σ13(k). Assume that both dimensions of the grid G are at least p(k)=2k·(3kk(σ(k)+1)+σ(k))+4k. Then for every T-large-slack robot Ri, there is a route Wi′ that is equivalent to Wi and such that νT(Wi′) is at most 4 and Wi′ is identical to Wi in [0,ℓ]\T. Proof For Ri∈R, denote by WiT the restriction of Wi to T. Let RL be the set of T-large slack robots and RS be that of T-small slack robots as defined in Definition 10. By Lemma 5, we may assume that, for every Ri∈RS, we have νT(Wi)≤τ(k)=3kk(σ(k)+1)+σ(k). From the hypothesis of the current lemma, we may assume in what follows that both grid dimensions are at least p(k). Since for each Ri∈RS, we have ν(WiT)≤τ(k), the number of grid lines used by each Ri∈RS is at most 2τ(k), and hence, the number of lines in the set U of grid lines used by all robots in RS is at most 2·k·τ(k). Let F be the set of grid lines not used by any robot in RS and notice that, since p(k)=2k·τ(k)+4k, both the number of horizontal gridlines and the number of vertical gridlines in F are at least p(k)-|U|≥4k. We will define another valid schedule S′ in which every Ri∈RL performs a route Wi′T in T, while the routes performed by the robots in RS are unchanged. For each robot Ri, denote by pi its location (i.e., grid point) at time t1 and qi its location at time t2. To define the new routes for the robots in RL, we apply the following process, which consists of three phases. In phase (1), we will relocate the robots in RL so that each robot Ri∈RL occupies a point pi′ such that: (i) both the horizontal and vertical lines containing pi′ are in F; and for any two distinct Ri,Rj∈RL, points pi′,pj′ belong to different horizontal and vertical lines. Since |U|≤2k·τ(k) and both the number of horizontal and vertical gridlines in |F| are at least 4k, clearly this relocation can be achieved in at most |U|+2k≤4k·τ(k) many steps, and by performing routes such that each makes at most 2 turns (shifting vertically and then shifting horizontally). Let t1′ be the time step at which relocating the robots in RL is complete, and each Ri has been relocated to pi′. For each Ri∈RL, choose a point qi′ satisfying: (i) both the horizontal and vertical lines containing qi′ are in F; (ii) Δ(qi,qi′)≤d(k)/8k and qi and qi′ belong to different horizontal and vertical lines; and (iii) for any two distinct Ri,Rj∈RL, qi′ and qj′ and qi′ and qj belong to different horizontal and vertical lines. Clearly, the qi′’s exist since both the number of horizontal and vertical lines in |F| are at least 4k and d(k)/(8k)>|U|+8k. In phase (2), we will define a route Wi′, where T′=[t1′,t2′] with t2′ to be defined later, for each Ri∈RL, whose endpoints are pi′ and qi′. To define Wi′, consider the projection xi′ of qi′ on the horizontal line containing pi′; Wi′ is simply defined as the route that consists of the horizontal segment joining pi′ to xi′ followed by the vertical segment xi′qi′. Clearly, each Wi′ makes at most one turn. Moreover, by the choice of the pi′’s and the qi′’s, any two routes Wi′ and Wj′ intersect at most twice. Furthermore, since the two gridlines used by Wi′ are in F, each Wi′ has at most η(k)=2k·τ(k) many intersections with the routes of T-small-slack robots; note that a T-small-slack robot may intersect a route Wi′ multiple times at the same point, but those would constitute different intersections and are accounted for in the upper bound η(k) on the number of intersections. Moreover, since each T-small slack robot has slack at most σ(k), the waiting time for any T-small slack robot at any gridpoint is at most σ(k). Now we are ready to define the valid schedule for each Ri∈RL during [t1′,t2′]. We will impose an arbitrary ordering on the robots in RL. We will define the valid schedule of the robots in RL in decreasing order. More specifically, a robot of lower order will always wait for a robot of higher order, and hence, the definition of the route of a robot Ri∈RL will not be affected by the routes of the robots in RL of lower-order than Ri. For the robot Ri∈RL with the highest order, Ri will follow its pre-defined route Wi′ from pi′ to qi′. Suppose that Ri has traversed the following sequence of points ⟨u1=pi′,…,ur⟩, and suppose that the move of Ri during the next time step t will cause it to collide with a robot R∈RS, then Ri will wait at its current point ur for σ(k) many time steps, and if during any of these time steps Ri collides with any robot in RS, then Ri would instead wait twice that number of steps (i.e., 2σ(k)) at point ur-1 and so on and so forth. Since pi′ does not belong to any line in U (i.e., and hence does not belong to any route of a robot in RS) there is a wait time of at most σ(k)·η′(k) time steps at a point in ⟨u1=pi′,…,ur⟩ that would resolve the initial collision, where η′(k) is the number of intersections (counting point multiplicities) between ⟨u1=pi′,…,ur⟩ and the routes of the robots in RS. Since the number of possible collisions between Wi′ and the routes of T-small slack robots is at most η(k), it follows that there is a valid schedule for Ri to traverse Wi′ with wait-time at most η(k)·σ(k) that does not collide with any T-small-slack robots. Suppose, inductively, that for each Ri∈RL whose order is s, there is a valid schedule for Ri that traverses Wi′ with wait time at most 2s·η(k)·σ(k). Recalling that any two routes Wi′ and Wj′ intersect at most twice, it is easy to verify that the total wait time for the robot with order s+1 in RL is at most 2s+1·η(k)·σ(k). It follows that we can define a valid schedule Wi′, for each Ri∈RL, that makes two turns in T′ and that has wait time at most 2k·η(k)·σ(k). Let t2′ be the time step at which the last robot Ri∈RL arrives to qi′. Since γ(k)=σ13(k), it is easy to see that γ(k)>2k·η(k)·σ(k), and each robot Ri∈RL will arrive to qi′ with ample slack, namely with a slack of at least σ13(k)-2k·η(k)·σ(k), which can be easily verified to be larger than σ13(k)/4=d(k)/4, for all k≥2. In phase (3), each robot Ri∈RL will wait at qi′ until time step t2-d(k)/4. We will re-route each Ri∈RL from qi′ to its final destination qi so that it arrives at qi at time precisely t2. First, for each Ri, define the smallest subgrid Gi that contains both qi′ and qi and whose dimension is at most Δ(qi,qi′), and observe that the dimension of Gi is upper bounded by d(k)/8k. Let G={Gi∣Ri∈RL}. If two subgrids Gi and Gj in G overlap, remove them from G and replace them with the smallest rectangular subgrid containing both Gi and Gj; repeat this process until no resulting subgrids in G overlap. Observe that at the end of this process, |G|≤k and for each Gi∈G, its dimensions are upper bounded by k·d(k)/8k≤d(k)/8. Therefore, for each Gi∈G, no R∈RS is located in Gi during the interval (t2-d(k)/4,t2] as otherwise, its Manhattan distance from qi would be less than d(k)/2, and hence, its Manhattan distance from Ri at t2 would be less than d(k), contradicting the assumption that T is a good interval. Therefore, it suffices route all the robots Ri∈RL from qi′ and qi during the interval (t2-d(k)/4,t2]. Now it is straightforward to see that the robots in each Gi can be routed so that we have a valid schedule taking each robot Ri from qi′ to qi in (t2-d(k)/4,t2] and such that each robot makes at most 2 turns. We outline how this can be done. We order the destination points qi′ of the robots in Gi in lexicographic order (say from left to right, and bottom to top, with the largest being the rightmost and then topmost), and order the robots in the same order as that of their destination points. We route the robots sequentially, starting with the highest ordered robot in lexicographic order by routing it horizontally until it reaches the vertical line on which its destination point is located, followed by routing it vertically to its destination point. Once a robot arrives to its destination, we start routing the next robot in lexicographic order. Routing each robot takes at most Δ(qi,qi′) time steps, and makes at most 1 turn. Therefore, all robots can be routed to their destination points in at most k·max{Δ(qi,qi′)∣Ri∈RL}≤d(k)/8 time steps, and hence in the interval (t2-d(k)/4,t2]. Note that the number of turns made by each robot over the three phases of the process is at most 4. □ We now establish the canonical-solution result that culminates this section. Theorem 14 Let (G,R,k,ℓ) be an instance of CMP-M such that at least one dimension of the grid G is lower bounded by 2k·(3kk(32k2-2k·k2k2-2k+1)+32k2-2k·k2k2-2k)+4k. If (G,R,k,ℓ) is a YES-instance, then it has a valid schedule S in which each route makes at most ρ(k)=3k3+1·(3kk(32k2-2k·k2k2-2k+1)+32k2-2k·k2k2-2k) turns. Proof Suppose that (G,R,k,ℓ) is a YES-instance of CMP-M. We proceed by contradiction. Let S be a minimal schedule for (G,R,k,ℓ) and assume that S has a route Wi for Ri that makes more than ρ(k) turns. By Lemma 9, there exists a [σ,γ]-good interval T⊆[0,ℓ] such that νT(Wi)>3kk(σ(k)+1)+σ(k), where σ and γ are the function specified in Lemma 9. By Lemma 12 and Lemma 13, there is an equivalent route Wi′ to Wi that agrees with Wi outside of T and such that νT(Wi′)≤3k3<3kk(σ(k)+1)+σ(k), which contradicts the minimality of S. □ Finding Canonical Solutions Having established the existence of canonical solutions with a bounded number of turns, we can proceed to describe the proof of the FPT result. In the proof, we identify a “combinatorial snapshot” of a solution whose size is upper-bounded by a function of the parameter k. We then branch over all possible combinatorial snapshots and, for each such snapshot, we reduce the problem of determining whether there exists a corresponding solution to an instance of Integer Linear Programming in which the number of variables is upper-bounded by a function of the parameter, which can be solved in FPT-time by existing algorithms [16, 21, 25]. Theorem 15 CMP-M is FPT parameterized by the number of robots. Proof Let I=(G,R,k,ℓ) be an instance of CMP-M. If both dimensions of G are upper bounded by p(k)=2k·(3kk(32k2-2k·k2k2-2k+1)+32k2-2k·k2k2-2k)+4k, then it follows from the results in [11] that there is an approximate solution to the instance in which the length of the route of each robot is upper bounded by a linear function of the distance between the starting and destination point of the robot, and hence is O(p(k)). Therefore, we can assume that ℓ=O(p(k)), and we can enumerate all possible routes for the robots in FPT-time to decide if there is a valid schedule. We may now assume that at least one dimension of G is lower bounded by p(k). By Theorem 14, I is a YES-instance if and only if it admits a solution S in which each route makes at most ρ(k)=3k3+1·(3kk(32k2-2k·k2k2-2k+1)+32k2-2k·k2k2-2k) turns. Therefore, it suffices to provide a fixed-parameter procedure to verify whether I admits such a solution. We will do so by applying a two-step procedure: first, we apply exhaustive branching to determine the combinatorial “snapshot” of a hypothetical solution S, and then we use this to construct a set of instances of Integer Linear Programming (ILP) which will either allow us to construct a solution with the assumed combinatorial snapshot, or rule out the existence of any such solution. Crucially, the number of variables used in the ILP will be upper-bounded by a function of k, making it possible to solve it by the classical result of Lenstra [16, 21, 25]. Let us now formalize the notion of “snapshot” mentioned above: a snapshot is a tuple (Gsnap, Rsnap, Wsnap,ι) where Gsnap is a grid with at most k2·(ρ(k)+2) many rows and columns (which we will sometimes refer to as coordinates), Gsnap is a grid with at most k2·(ρ(k)+2) many rows and columns (which we will sometimes refer to as coordinates), Rsnap={(si′,ti′)|si′,ti′∈V(Gsnap)∧i∈[k]} is a tuple of k pairs of starting and ending vertices in Gsnap, Rsnap={(si′,ti′)|si′,ti′∈V(Gsnap)∧i∈[k]} is a tuple of k pairs of starting and ending vertices in Gsnap, Wsnap is a tuple of k routes, where for each i∈[k] the i-th route starts at si′, ends at ti′, does at most ρ(k) turns and does not wait, and Wsnap is a tuple of k routes, where for each i∈[k] the i-th route starts at si′, ends at ti′, does at most ρ(k) turns and does not wait, and ι is a mapping from V(Gsnap) to tuples from {[k]j|j∈[k·ρ(k)]} with the following property: a vertex v is visited by route wi∈Wsnap precisely p times if and only if the tuple ι(v) contains precisely p many entries i. ι is a mapping from V(Gsnap) to tuples from {[k]j|j∈[k·ρ(k)]} with the following property: a vertex v is visited by route wi∈Wsnap precisely p times if and only if the tuple ι(v) contains precisely p many entries i. Let Snap be the set of all possible snapshots. Observe that since the first three elements of the snapshot can be completely identified by specifying the grid size and the coordinates of all starting and ending vertices as well as of all the turns, we can bound the number of snapshots by |Snap|≤ρ(k)O(k·ρ(k)). Next, we need to establish the connection between snapshots and solutions for I. First, let us consider an arbitrary hypothetical solution S′ where each route makes at most ρ(k) turns. We begin by marking each x-coordinate containing at least one turn, at least one starting vertex or at least one ending vertex as important, and proceed analogously for y-coordinates; this results in at most k·(ρ(k)+2) coordinates being marked as important. A vertex is important if it lies at the intersection of an important x-coordinate and an important y-coordinate. Observe that at each time step, each robot is either at an important vertex, or has precisely one unimportant coordinate; in the latter case, the robot has a clearly defined direction and can either wait or travel in that direction until it reaches an important vertex. We say that a vertex is a rest vertex if it can be reached from an important vertex by a route of length at most k without turns. The reason we define these is that we will show that one can restrict the waiting steps of the robots to only these two kinds of vertices. In particular, let us call a solution organized if robots only wait at important and rest vertices. Claim 1 If I admits a solution S′, then it also admits an organized solution S. Proof of the Claim Assume that S′ is not organized, and choose an arbitrary robot R that waits at some time step on some vertex v that is neither important nor rest; let i be the last time step during which R waits on v. Recall that v must have a clearly defined direction; without loss of generality, let us consider the direction to be “right” (the arguments are completely symmetric for the three other directions). Hence, while at time step i+1 R still remains on v, at time step i+2 R moves to the neighbor of v on the right. Let R′ be the set of robots with the following property: at time step i+1, each robot in R′ can be reached by going right from R by a path of vertices in G all of which are occupied by robots. Note that in most cases R′ will contain only R, but if, e.g., the 3 vertices to the right of R are occupied by other robots, R′ will contain these three as well. Crucially, no robot in R′ can be located on an important vertex at time step i+1, and the vertex to the right of the rightmost robot in R′ at time step i+1 cannot be important either (R′ could, however, include some robots placed on rest vertices). Furthermore, since R moves to the right at time step i+1 and no robots in R′ lie on important vertices, all robots in R′ move to the right as well. Similarly, since R was waiting at time step i, all robots in R′ had to wait at time step i as well (otherwise they could not be immediately to the right of R without turning). Now, consider a new solution S∗ that is obtained from S′ by swapping the order of the wait and move commands for R′, i.e., at time step i all robots in R′ move to the right, while at time step i+1 all robots in R′ wait. Since no robot in R′ lies at an important vertex, this local swap cannot cause any collisions in S∗, and hence S∗ is also a solution. Notice that repeating the procedure described above always results in a new solution with the same makespan, and each application of the procedure postpones the times of some wait commands. Hence, after a finite number of iterative calls, we obtain a solution Sorganized where no robot waits on vertices that are neither important nor rest. □ Claim 1 will allow us to restrict our attention to organized hypothetical solutions of I, meaning that robots can only “move straight” on non-rest vertices (they can neither wait nor make turns there). Now, let us return to the connection between snapshots and solutions. Let a horizontal (or vertical) coordinate be active if it contains at least one vertex that is rest or important. Let a row contraction at a horizontal coordinate a be the operation of contracting every edge between a and horizontal coordinate a+1; column contractions are defined analogously for a vertical coordinate a. A row or column contraction at coordinate a is admissible if no vertex at coordinate a+1 contains a rest or important vertex. To obtain the snapshot of S, we perform the following operations. First, we delete all vertices in rows whose horizontal coordinates are lower than the smallest horizontal coordinate containing at least one important or rest vertex, and store the number of rows deleted in this manner as w↓(0). Next, for each horizontal coordinate a such that a is the i-th smallest horizontal coordinate, we exhaustively iterate admissible row contractions and we store the total number of such contractions carried out for a as w↓(i). We then proceed analogously for vertical coordinates to obtain the values w→(0) and w→(i). This procedure results in a new grid Gsnap with k terminal pairs stored in Rsnap, a set Wsnap of routes connecting the terminal pairs obtained from S. Finally, observe that V(Gsnap)⊆V(G), and hence, for each v∈V(Gsnap) there is a precise order in which the individual routes in S intersect v, and this is what is used to define ι. Formally: ι(v)=∅ if v is not used by any route in S; otherwise ι(v)=∅ if v is not used by any route in S; otherwise ι(v)[i] is the index of the i-th route that visits v.1 ι(v)[i] is the index of the i-th route that visits v.1 The tuple (Gsnap,Rsnap,Wsnap,ι) is then the snapshot corresponding to S witnessed by the functions w↓, w→. While this settles the construction of a snapshot from a solution (a step that will be required to argue correctness), what we actually need to do in the algorithm is the converse: given a snapshot (Gsnap,Rsnap,Wsnap,ι), determine whether there is a solution corresponding to it. Here, it will be useful to notice that when constructing a snapshot from an organized solution S, we lost two types of information about S: the amount of contraction that took place (captured by the functions w↓, w→), and the amount of waiting that took place. However, since S is organized, no robot could have waited on any vertex outside of V(Gsnap). Hence, all the waiting times in S can be captured by a mapping which specifies how long robot i waits at each individual visit of a vertex v. Since all visits of v are captured by ι, we can formalize this by defining, for each v∈V(Gsnap), the mapping waitv:q∈[|ι(v)|]→N, with the following semantics: waitv(q)=x if and only if the q-th robot visiting v, i.e., ι(v)[q], waits precisely x time steps after arriving at v for that visit. The values of w↓, w→ and of the functions waitv for all v∈V(Gsnap) cannot be directly inferred from a snapshot alone, and will serve as the variables for the constructed ILP. Note that the total number of variables capturing the values of w↓ and w→ is upper-bounded by 2·(k2·(ρ(k)+2)), while the total number of such variables for each of the at most (k2·(ρ(k)+2)2 many waitv functions is upper-bounded by k·ρ(k). We now describe the constraints which will be used for the ILP. As a basic condition, we restrict all variables to be non-negative. To give our constraints, it will be useful to note that the time robot i arrives at some vertex v for the j-th time (over all routes)—hereinafter denoted arrival(i,v,j)—can be completely captured using our snapshot and variables. To do so, one can follow the route Rsnap[i] from its starting point until it visits some vertex v∈V(Gsnap); if this is the j-th visit of v by some route, then we define arrival(i,v,j) as a simple sum of the following variables: for each j′-th visit of a vertex v′ (counted over all visits of v′ by all robots) by i, the variable waitv′(j′) (which semantically captures the number of time steps i waited at v at this visit), and for each j′-th visit of a vertex v′ (counted over all visits of v′ by all robots) by i, the variable waitv′(j′) (which semantically captures the number of time steps i waited at v at this visit), and for each move along a horizontal edge between vertical coordinates z and z+1 in Gsnap, the variable w→(z) plus one (which semantically captures the number of time steps i had to continuously travel in G between these two rest and/or important vertices), and for each move along a horizontal edge between vertical coordinates z and z+1 in Gsnap, the variable w→(z) plus one (which semantically captures the number of time steps i had to continuously travel in G between these two rest and/or important vertices), and for each move along a vertical edge between horizontal coordinates z and z+1 in Gsnap, the variable w↓(z) plus one (as before). for each move along a vertical edge between horizontal coordinates z and z+1 in Gsnap, the variable w↓(z) plus one (as before). The first set of constraints are the timing constraints, which are aimed to ensure that each robot arrives to its final destination in time. These simply state that for each robot i with target vertex t and where the route i in Rsnap visits t a total of j times, arrival(i,v,j)≤ℓ. The second set of constraints are size constraints, which make sure that the w↓ and w→ functions reflect the initial size of G. Let row be the number of rows of Gsnap, and similarly for col; then the size contraints simply require that (1) row+∑i∈0,⋯,roww↓(i) equals the number of rows in G, and similarly (2) col+∑i∈0,⋯,colw→(i) equals the number of columns in G. The last set of constraints we need are the traffic constraints, which ensure that the individual robots visit the vertices in Gsnap in the order prescribed by ι and do not collide with each other. Essentially, these make sure that for each vertex v that is consecutively visited by some robot a and then b (where b could, in principle, be the same robot), robot a leaves v before b arrives to v. These are fairly easy to formalize: for each vertex v such that ι(v)(q)=i and ι(v)(q+1)=j, we set arrival(i,v,q)+waitv(q)4 vertices, there is a linear time algorithm that constructs a plane orthogonal drawing of G on a grid with area O(n2). By Theorem 29, we can compute a plane orthogonal drawing Ω of Gφ in a grid with O(n2) vertices. Next, we refine the grid underlying Ω by a factor of 1000—more formally, we replace each cell in the grid underlying Ω with a 1000×1000 subgrid. We note that the refinement by a factor of 1000 was not chosen very accurately, and probably a smaller refinement would be sufficient. (We need a large-enough refinement to have ample space for constructing and connecting the gadgets in the reduction.) For all three problems, the instances obtained from the reductions will be composed of three parts: Clause Gadget. For every clause C, there is a “clause gadget” that will be placed around the point Ω(C), where the vertex representing the clause C is embedded. Variable Cycle. For every variable x, there is a “variable cycle”. The role of the variable cycle is to propagate the information about the choice/assignment made for the variable to the clause. This is necessary since the edges of the orthogonal drawing can be very long (i.e., span many edges of the grid) and can have bends. One can think about this as replacing the variable with a long cycle of implications, stipulating that the choices made along the cycles are consistent. For us, it will be a very long cycle consisting of different instances of a small “variable gadget” connected in a way so that the choices in all the gadgets along the cycle have to be the same. The variable cycle wraps around the edges incident to x in the drawing Ω; see Figure 6. More precisely, the variable cycle for a variable x is a rectilinear polygon that follows the drawing of the edges incident to x at distance 250 (1/4 of the width of an “original” cell of the drawing Ω before the refinement) and crosses the edges at distance 500 (1/2 of the width of an “original” cell of the drawing Ω before the refinement) from each of the clause vertices that x belongs to. This way, variable cycles are far apart, each straight-line segment (i.e., each edge of the polygon) of the variable cycle has length at least 250, and each clause vertex is at distance 500 from the variable cycle. In a concrete instance of each of the problems, this cycle will be constructed from a series of “variable gadgets” that roughly follow the outline of this cycle. Part of an orthogonal drawing of Gφ. Clause C contains variable x, y, z. The variable x is also in clauses C1 and C2. The dashed lines represent the variable cycles. The variable cycle for x is fully drawn Connection Gadget. For every pair of a clause and a variable in the clause, there is a “connection gadget” that connects the clause gadget to the variable cycle. For both problems, this will be a path of “variable gadgets” roughly following the drawing of the edge between the clause and the variable until it intersect the variable cycle. This finishes the common part of the two proofs. In the next subsection, we will show the NP-hardness of d-Bounded Length Vertex Disjoint Paths on grids, and in the last subsection, we will show the para-NP-hardness of CMP-M. Bounded Length Disjoint Paths on Grids In this subsection, we show the NP-hardness of d-Bounded Length Vertex Disjoint Paths on grids with constant path length (specifically, 27), and extend this result to its edge variant. We first present the NP-hardness proof for d-Bounded Length Vertex Disjoint Paths on grids. For d-Bounded Length Vertex Disjoint Paths on grids, the fact that the paths in the solution have to be vertex disjoint allows us to artificially place an obstacle on a vertex v in the grid to “block” that vertex (i.e., to prevent it from being used by any path other than (v, v)) by adding the request (v, v) to R, thus forcing the set of possible paths between s and t for every (s,t)∈R, where s≠t, to be chosen from the paths prescribed by the encoding of the instance of 4-Bounded Planar 3-SAT. The choice of a path corresponds to either a variable-assignment in variable gadgets, or to the choice of the variable that satisfies a clause in our clause gadgets. The main result of this subsection is the following. Theorem 30 d-Bounded Length Vertex Disjoint Paths is NP-hard even when restricted to instances where d=27 and G is a grid-graph. We start by giving a low-rigor description of the NP-hardness reduction from 4-Bounded Planar 3-SAT to d-Bounded Length Vertex Disjoint Paths. We will encode variable assignment and clause satisfaction using bounded-length path requests that conform to the drawing Ω. To model a variable-assignment, we create a variable gadget with a single request between two vertices, s and t, on this gadget such that this request can be fulfilled by selecting one of the two s-t paths in this gadget, each of length 27. Selecting one of the two paths corresponds to assigning the variable a truth value. We model clause-satisfaction by creating, for each clause, a clause-gadget, where a clause-gadget for a clause C contains two vertices, sC and tC, with a request between them that can be fulfilled in one of three ways, each corresponding to choosing a length-27 path between sC and tC in the gadget. To implement the above idea, it was necessary to overcome several issues. First, the position of a variable in the embedding could be very far from the position of the clauses that it is incident to, hence prohibiting us from using bounded-length requests to encode the variable-clause incidences. Second, due to planarity constraints, embedding the three paths corresponding to a clause-gadget such that each intersects a different variable gadget, is only possible if two of the clause-paths intersect, which could create shortcuts (i.e., paths that do not intersect the variable gadgets). Third, requests may use grid paths that are not part of the embedding (i.e., are not intended to be used). To handle the first issue, instead of using a single variable-gadget per variable, we use a “cycle” of copies of variable gadgets such that a variable assignment in any gadget of this cycle forces the same variable assignment in all copies, thus ensuring assignment consistency. The clause gadget for C is placed around the position of the vertex corresponding to C in Ω, whereas the cycle corresponding to a variable x is placed around the edges of Ω joining the position of x in Ω to that of C. To fit all the variable cycles around a clause gadget in the embedding, we use a connection gadget, which is a path of copies of variable gadgets propagating the same variable assignment as in the corresponding variable cycle. To model clause-satisfaction for a clause C, each of the three sC-tC paths in the clause gadget of C overlaps with a copy of a variable gadget corresponding to one of the variables whose literal occurs in C. If an assignment to variable x whose literal occurs in C does not satisfy C, then the path corresponding to this assignment in the copies of the variable gadgets for x intersects the sC-tC path corresponding to x in the clause-gadget of C, thus prohibiting the simultaneous choice of these clause-path and variable path. To handle the second issue, we prevent any shortcuts from being taken by making each created shortcut longer than the upper bound on the path length (i.e., 27). Finally, to handle the third issue, the fact that the paths in the solution have to be vertex disjoint allows us to artificially place an obstacle on a vertex v in the grid to “block” that vertex (i.e., to prevent it from being used by any path other than (v, v)) by adding the request (v, v), thus forcing the set of possible paths between s and t for every request (s, t), where s≠t, to be chosen from the paths prescribed by the encoding of the instance of 4-Bounded Planar 3-SAT. We now proceed to give the formal proof. There are two main building blocks in the NP-hardness reduction: the variable gadget and the clause gadget. Variable Gadget. This gadget is rather flexible and consists of a rectangular a×b grid such that 2(a+b-2)=54 (i.e., there are 54 vertices on the outer layer of the gadget) and both a and b are at least four. We do exploit the flexibility of this gadget in the connection gadget, which connects the clause gadget to the variable cycle gadget; see Figure 7 for some examples of this variable gadget, with a=20 and b=9. There is a request (s, t) such that both s and t are on the outer layer of the gadget and the lengths of the two paths that use only the vertices on the outer layer are the same and equal to 27 in both cases. For the vertices inside the gadget, we have requests of the form (v, v) (for each such vertex v) that block the s-t path from using any vertex inside the gadget. Therefore, there are only two possible s-t paths that are disjoint from all (v, v) paths and have length at most 27—the clockwise path and the counter-clockwise path following the outer layer. The vertices s and t will either be on the top and bottom of the gadget—in this case the leftmost column of the gadget is fully on one of these paths and the rightmost column on the other, or they can be on the left and right sides of the gadget, where the top row is fully on one path and the bottom row on the other. We will call the clockwise path the orange path and the counter-clockwise path the purple path, and we will use these colors to depict the gadgets in all our figures. Variable Gadget examples. In both cases, there is a request (sx,tx). Each of the full black circles is a request (v, v) forcing only two different paths of length at most 27 between sx and tx. On the left there is an example of left-right variable gadget and on the right a top-bottom variable gadget Both the variable cycle and connection gadgets consist of many variable gadgets connected to each others in a way that a choice of one variable gadget propagates to the others. Each variable cycle is a long cycle of these gadgets. This forces that the only way to satisfy all requests of a variable cycle will be to either choose only the orange paths or only the purple paths for all gadgets on the cycle. Similarly, the connection gadget is a path of these gadgets. Since the height and width of the variable gadgets are very flexible and we subdivided the grid such that these cycles are very long and consist of very long straight-line stretches, we can always place the variable gadgets so that they conform to the outline of the variable cycles and the connection gadgets stipulated by the drawing Ω. Clause Gadget. We have one gadget for every clause C of φ. This gadget is very rigid and there is only one type for it, up to rotations by 90/180/270 degrees. The gadget is depicted in Figure 8. We will describe only one of the four possible rotations of the gadget, which is the one depicted in the figure. The remaining rotations are analogous. There is a vertex sC at position Ω(C), where the drawing Ω places the vertex representing clause C on the grid. There is a vertex tC at the position Ω(C)+(8,-5). There is a request (sC,tC). The blocking requests of the form (v, v) force only three possible ways for a path to leave from sC: Here we are forced to go seven steps left, then five steps down and 15 steps to the right. This is the only path of length at most 27 that starts by going left from sC. Here we are forced to go three steps down, two to the right, six up, two right, three down, and three right. This brings us to 19 steps and leaves us with only 8 steps. While the point going down is not blocked, it leads to a path that needs an additional ten steps to reach tC, which would bring the total to 29. Hence, we have to continue two more steps to the right, then five down and finally one left. The total length of the path is then 27. Here we are forced to go five steps up. Then we can go seven steps right, and five steps down, reaching the intersection point that we reached on the “Down” path after 19 steps. However, we arrive to this intersection point after only 17 steps, and we can continue down on the path taking 10 additional steps and arriving after 27 steps to tC (purple path), or we can go right and reach tC in 25 steps (orange path). Since both options arrive to tC within the prescribed makespan, and taking the purple path from the intersection point down to tC does not intersect any variable gadgets, it is safe to assume that in this case the robot follows the longer purple path. Note that there are a few more paths of length 25 or 27 that go 5 steps up. This is not an issue since, as we will see after introducing the connection gadgets, all these paths intersect the variable gadget that the purple path intersects. Clause gadget example. There is a request (sC,tC). Each of the full black circles is a request (v, v). There are three possible ways to leave sC. Choosing to go left forces us to take the green path of length 27. The orange path going down reaches the intersection point with the purple path (going up) after 19 steps on the orange path, but only 17 on the purple. Hence, the purple can choose between going down and taking 10 steps to reach tC, or going right and taking 8 more steps, but the orange is forced to go right and reach tC in 8 steps from the intersection point After describing these two building blocks, we are now ready to describe the full reduction. We start by placing, for each clause C in the instance, the clause gadget at position Ω(C). The rotation of the gadget depends on which of the four grid-edges incident to Ω(C) does not contain a drawing of any of the three edges incident to C. For example, the rotation of the clause gadget in Figure 8 is for the case where there is no edge going down from C in the drawing Ω. If the edge going left were missing, we would rotate the gadget 90 degrees clockwise around sC. Afterwards, we place the variable gadgets in a cycle along the variable cycle such that two consecutive variable gadgets always intersect on one of the paths for the gadget. See Figure 9 for an illustration of a (very short) variable cycle. It is rather straightforward to verify that there are only two ways to selects all the sx-tx paths of length at most 27 for all the variable gadgets on the variable cycle: in the figure we either take all “purple” paths or all “orange” paths. We will associate the setting of a variable to True with the choice of taking all the orange paths, and to False with that of taking all the purple paths. An very small example of a variable cycle Finally, we describe how to place the connection gadget. This is again just a path of variable gadgets going between a clause gadget and a variable cycle. Note that consecutive variable gadgets do not need to be perfectly aligned; they just need to intersect. Moreover, the width/height of a variable cycle is variable (between 4 and 25). Hence, we can easily shift the gadgets inside the path to perfectly connect to the the gadgets as needed. The connections between a clause gadget and the connection gadgets is depicted in Figure 10. Note that all sC-tC paths of length at most 27 of the clause gadget intersect one of the variable gadgets at the end of a connection gadget. Moreover, an sC-tC path P intersects the variable gadget on an orange path if and only if the negation of the variable is in the clause. This means that only if the purple path of the variable gadget is chosen (signifying a variable being assigned False), we can use the path P to reach from sC to tC. Otherwise, P intersects the variable gadget in the purple path, i.e., if the orange path in the variable gadget is selected, P can be selected as an sC-tC path. There are also two ways to connect the connection gadget and the variable-cycle depending on whether the variable appears positively or negatively. See Figure 11 for an illustration of how these two possibilities are achieved for the case where the clause is to the left of a variable cycle. The remaining cases are symmetric. The basic idea is that we shift one of the variable gadgets away of the clause gadget; this allows us to connect a variable gadget to either the orange path of the gadget immediately after the shifted gadget or the purple path of the gadget immediately before the shifted gadget without interfering with any other gadgets. Connecting a clause gadget for clause C=(x∨¬y∨¬z) to respective clause-variable connection gadgets Connecting to a “variable cycle”. In this case the clause gadget is to the left of the variable cycle. The other three possibilities are symmetric This finishes the construction and we are ready to prove Theorem 30. Proof of Theorem 30 We start from an instance φ of 4-Bounded Planar 3-SAT with a set of variables X, a set of clauses C, and the incidence graph Gφ. We follow the construction described above and construct an instance (G, R, 27) of d-Bounded Length Vertex Disjoint Paths on grids. Note that this construction takes polynomial time, and the number of vertices of G is O((n+m)2)=O(n2), where n=|X| and m=|C|. We now prove that φ is satisfiable if and only if there is a set P of vertex disjoint paths, each of length at most 27, such that for every (s,t)∈R, there is an s-t path in P. Let α:X→{True, False} be a satisfying assignment for α. For all requests (v,v)∈R, we add the single vertex path (v) to P. Each variable gadget in the instance is either on a variable cycle for some variable x, or on a connection gadget between a variable x and a clause C containing x or its negation. Hence, each variable gadget is associated with a single variable. If the variable gadget is associated with variable x such that α(x)=True, then we choose the orange path on this variable gadget; otherwise, we choose the purple path. It is straightforward to see—from the construction of the gadgets—that all of these paths are vertex disjoint. Moreover, if a variable x appears positively in a clause C, then there is an sC-tC path of length 27 that intersects only the single variable gadget associated with variable x on the purple path. Hence, if α(x)=True and x satisfies C, then this path is disjoint from all the other chosen paths. Similarly, if a variable x appears negatively in a clause C, then there is an sC-tC path of length 27 that intersects only the single variable gadget associated with variable x on the orange path. Hence, if α(x)=False and x satisfies C, then this path is disjoint from all other chosen paths. Since α is a satisfying assignment, each clause is satisfied by at least one variable, and for all clauses C∈C, we can choose an sC-tC path that is disjoint from all the other paths in P. This finishes the construction of the solution and the forward direction of the proof. For the converse, let P be a solution for the instance (G, R, 27). Note that, by construction, either all the variable gadgets on the single variable cycle of a variable x use the orange paths, or they all use the purple paths. We construct the assignment α such that α(x)=True if the variable gadgets on the variable cycle for x use the orange paths, and α(x)=False otherwise. We claim that this is a satisfying assignment. Let C∈C. Clearly there is an sC-tC path P∈P of length at most 27 that does not intersect any other paths in P. From the description of the clause and connection gadgets, it is rather straightforward to verify that P intersects at least one variable gadget of the connection gadget between the clause gadget and the variable cycle. Let us assume that P intersects the variable gadget for variable x. We show that in this case x satisfies clause C. If x appears positively in C, then the sC-tC path P intersects the purple path of the gadget and the variable gadget has to choose the orange path. By the construction of the connection gadget, the orange path of this first variable gadget connected to the clause gadget intersects a purple path of a second variable gadget on the connection gadget and the second variable gadget also has to choose the orange path, and so on until the last variable gadget on the connection gadget intersects a variable gadget of a variable cycle for x on a purple path. Hence, the variable gadgets on the variable cycle for x all choose the orange path and α(x)=True and x satisfies C. The case where x appears negatively in C is analogous; the only difference is that the sC-tC path P intersects the variable gadget in the orange path in this case. It follows that C is indeed satisfied by the assignment α. Since C was chosen arbitrarily, α is a satisfying assignment for φ, and the proof is complete. □ The above NP-hardness result can be extended to the edge-disjoint paths problem, which has been studied extensively, in the case where the path length is upper bounded by a constant: d -Bounded Length Edge Disjoint Paths Given: A graph G=(V,E), a set R of pairs of vertices, and an integer d∈N. Question: Is there a set P of edge-disjoint paths, each of length at most d, such that there is an s-t path in P for every (s,t)∈R? We will now describe how to modify the constructed instance of d-Bounded Length Vertex Disjoint Paths to obtain an equivalent instance of d-Bounded Length Edge Disjoint Paths. First, notice that we already constructed our gadgets in a way that if the non-trivial paths (i.e., paths of length at most 27 for the unique request (s, t) in the gadget where s≠t) of some variable gadget and some clause gadget intersect, then they also intersect in an edge. Hence, we only need to enforce that the path for the (s, t) request in each gadget does not go through any vertex with request (v, v) (for some v∈V(G)) without blocking any of the edges that the s-t gadget paths use in the solution for the instance of d-Bounded Length Vertex Disjoint Paths. This is rather straightforward. Let (v, v) be a request in the constructed instance of d-Bounded Length Vertex Disjoint Paths for some vertex at the grid position (a, b). Let vL,vR,vU,vD be the vertices at positions (a-1,b),(a+1,b),(a,b+1),(a,b-1), i.e., on the right, left, top, and bottom, respectively, of vertex v in the grid. For i∈{L,R,U,D}, we add the request (v,vi) to the instance of d-Bounded Length Edge Disjoint Paths. Note that if (vi,vi) is also a request in the original reduction, then we are also adding the request (vi,v), however, the graph is not directed, hence we treat the request (v,vi) and (vi,v) as the same request and a single path can satisfy both of them. Note that, in order to satisfy all these requests with edge-disjoint paths, we have to use all the edges incident to v, as there are four edges and four requests for edge-disjoint paths. Moreover, taking the paths (v,vR),(v,vL),(v,vU),(v,vD) satisfies these requests. Therefore, on one hand, no path between two vertices s and t such that s≠v and t≠v can pass through v in a valid solution of d-Bounded Length Edge Disjoint Paths. On the other hand, we can always assume that (v,vR),(v,vL),(v,vU),(v,vD) are the paths satisfying the requests for v and their requests do not block any edge that is not incident to v. Hence, the set of valid s-t paths of length at most 27 that we can use to satisfy all the remaining requests remains the same and the rest of the NP-hardness proof follows from the NP-hardness proof for d-Bounded Length Vertex Disjoint Paths. Theorem 31 d-Bounded Length Edge Disjoint Paths is NP-hard even when restricted to instances where d=27 and G is a grid-graph. NP-hardness of CMP-M with Constant Makespan In this subsection, we show the NP-hardness of CMP-M for makespan 26. The high-level ideas are the same as in the NP-hardness proof for d-Bounded Length Vertex Disjoint Paths starting from 4-Bounded Planar 3-SAT: An (s, t) path request corresponds to routing some robot from its starting gridpoint s to its destination gridpoint t. However, the way we force robots to follow the prescribed paths here is completely different and presents the main difficulty when going from d-Bounded Length Vertex Disjoint Paths on grids to CMP-M. To ensure that the prescribed paths are followed, we block certain regions of the embedding by adding a large number of auxiliary non-stationary robots, and coordinating their motion so that they block the desired regions while still allowing the original robots to follow the set of paths prescribed by the encoding; this task turns out to be highly technical. To overcome these complications, we introduce a set of new gadgets whose role is to force the main robots in the reduction to follow the paths prescribed by the embedding. Those gadgets are dynamic, as opposed to the static blocker gridpoints used in the d-Bounded Length Vertex Disjoint Paths on grids reduction. The two main new gadgets employed are a gadget simulating a “stream” of robots and a gadget simulating an “arrow” of robots. The stream gadget consists of a relatively large number of robots, all moving along the same line, such that each needs to move precisely the makespan many steps in the same direction, and hence cannot afford to waste a single time step. The robots in the stream gadget will be used to either push the main robots in a certain direction, or to prevent them from taking shorter paths than the prescribed ones. The starting point of the reduction is exactly the same as that in the previous subsection. We start from an instance φ of 4-Bounded Planar 3-SAT with a set of clauses C, a set of variables X, and incidence graph Gφ that is planar. We obtain an orthogonal drawing of Gφ on a grid with area O(n2), and refine it by a factor of 1000. We call the final drawing Ω, and let Ω(C), for C∈C, be the point of the grid where the vertex of Gφ representing clause C is placed. We also assume that we have the outline of the variable cycle for every variable, and we now only need to describe the clause gadget, the variable gadget that we have on the variable cycle, and how the connection gadget connects to the variable cycle and the clause gadgets. Clause Gadget We start with the description of the clause gadget. This gadget is again rather rigid, and there are only four different placements of a clause gadget, which correspond to the gadget and its three rotations by 90/180/270 degrees, depending on which direction there is no outgoing edge out of C. See Figure 12 for the gadget in the case where there is no edge going to the right out of C. An illustration of a clause gadget All the blue robots in the figure want to go 26 steps to the left. All the green robots want to go 26 steps to the right. The red robot, which we call the “clause robot”, wants to go 7 steps down and 4 steps right. The red robot starts at position Ω(C). Finally, the pink robot wants to go 25 steps to the right and 1 up. In order for the blue and green robots to reach their respective destinations in at most 26 steps, they have to move left and right, respectively, in each step. It is rather straightforward to see that the purple robot can go up only after it passes the stream of the blue robots. Lemma 32 If the clause robot reaches its destination in 26 steps then one of the following holds: The red robot is at position Ω(C)+(11,-1) after 12 steps, i.e., 11 steps right and one down. The red robot is at position Ω(C)+(11,-1) after 12 steps, i.e., 11 steps right and one down. The red robot is at position Ω(C)+(-7,-1) after 8 steps, i.e., one step down and 7 left. The red robot is at position Ω(C)+(-7,-1) after 8 steps, i.e., one step down and 7 left. The red robot is at position Ω(C)+(2,7) or at position Ω(C)+(1,7) after 9 steps, i.e., 7 steps up, and either one or two to the right. Moreover, in the 10th step, the robot either waits or moves right. The red robot is at position Ω(C)+(2,7) or at position Ω(C)+(1,7) after 9 steps, i.e., 7 steps up, and either one or two to the right. Moreover, in the 10th step, the robot either waits or moves right. Proof We can distinguish the following cases based on the first starting steps of the red clause robot: (1) either the clause robot goes at least two steps to the right, or (2) the robot goes one step down, or (3) the robot goes one step right followed by one step up or immediately goes one step up. Note that the robot cannot start by going left (as it would collide with the green robots), and also cannot go one step right followed by one step down (as it would collide with the blue robots). If the first two steps of the clause robot are both to the right, then since the blue robots are moving only to the left in each step, and the green robots are moving only to the right in each step, it follows that in each position between the position after step 2 and the position after step 10: There is a green robot to the left of the clause robot forbidding the robot to move left or to wait. There is a green robot to the left of the clause robot forbidding the robot to move left or to wait. There is a blue robot that would be above the clause robot in the next step. There is a blue robot that would be above the clause robot in the next step. There is a blue robot that would be below the clause robot in the next step. There is a blue robot that would be below the clause robot in the next step. After step 11, the robot is free to go up, down, or to continue right. However, it cannot wait or go left. Moreover, it is at position Ω(C)+(11,0), which is at distance 14 from Ω(C)+(4,7). Going up or right would mean that, after step 12, it would be at distance 15 from the final destination with only 14 steps left. Since it cannot wait due to the presence of a green robot to its left, it has to go one step down and reach Ω(C)+(11,-1) at step 12. Note that in the 13th step, the purple robot could finally do its one step up and allow the clause robot to go down. After that, the route to the destination for the clause robot is not blocked by anything, and it can reach it by step 26 (even 25) by just going towards the destination in every step. See Figure 13 for an illustration of the configurations after 11, 12, and 13 steps, respectively. Clause gadget. A clause robot going right after steps 11, 12, and 13 If the first step is down, then after each step between step one and step seven, there is a robot (green or purple) that would be in the next step below and above of the clause robot. Moreover, there is a robot to the right that is going left. Hence, the clause robot is forced to move left between step one and step seven, and reaches position Ω(C)+(-7,-1) after 8 steps (see Fig. 14). Moreover, if it goes down in the 8th step, then the route to the destination is again not blocked by anything. Clause gadget. A clause robot going left after steps 1 and 8 Finally, the clause robot can either go immediately up, or go one step right and then up. After that it can either move another 6 steps up, or move left together with the stream of blue robots. If the robot finishes seven steps going up, then it needs to do an additional 14 steps going down and (at least) 4 steps going right. This sums up to 25 steps. Therefore, the robot in this case can wait only once, otherwise, it has to move either right or down (besides the 7 steps up). Hence, in this case it is indeed after 9 steps at position Ω(C)+(1,7) or Ω(C)+(2,7), since the blue stream forces the robot to go at least 2 steps (or 3 if it does not wait) right before it goes down. After that, the robot can, for example, finish all 4 steps right and continue going down. If it did not wait until then, then it has to wait for one step, after 5 steps down, to let the top blue stream pass. However, after waiting one step it just passes between the blue and green streams. See Figure 15 for an illustration of this case. Clause gadget. A clause robot going up If the robot does not complete seven steps going up, then it can follow the blue stream going left, and at some point eventually turn down. Note that it can only turn down if the robot went one step right and then only one step up, or if it went at most two times up with the first up being in the first step. The important observation here is that the robot cannot wait in any step while it is following the blue stream. Hence, it cannot wait until it returns to the y-coordinate of Ω(C). Moreover, it can only return to this coordinate at the left end of the top green stream. Since there are 14 green robots, it follows by a parity argument that the clause robot cannot return to the position immediately behind the last green robot in the top green stream (the grid is a bipartite graph and the last green robot and the clause robot start at vertices in the same part of the bipartition). However, at the beginning, the position two steps behind the last green is at distance 27 from the destination of the clause robot, and hence at step i, it is at distance at least 27-i from the destination. Any place to the left of this position is at an even larger distance. Hence, if the robot starts by going up, it is not possible for it to reach the destination without going 7 steps up. See Figure 16 for the two closest steps when the clause robot can return to the original y-coordinate. □ Clause gadget. The closest position to the destination where the robot can return to its original y-coordinate is after 9 steps if it went up and left (left subfigure); the closest position to the destination where the robot can return to its original y-coordinate is after 10 steps if it went one right, one up, and then left (right subfigure) The three different positions highlighted in Lemma 32 will be precisely the points that will be intersected by the routes of the robots in a variable gadget, if the assignment represented by the choice of the robot in this gadget does not satisfy the clause (similarly as in the d-Bounded Length Vertex Disjoint Paths problem on grids). Variable Gadgets The variable gadget is again very flexible. Each variable gadget will have one variable robot that needs to move from its starting position s to position s+(dx,dy) such that |dx|+|dy|=26 and 1≤dx,dy≤25. If dx≥2 and dy≥2, the gadget will also contain a stream of robots called arrow that forces the robot to chose one of the two directions towards the destination in the first step and then stick to this selection for a number of steps that depends on the size of the arrow. For example, in Figure 17, we can see an orange variable robot that wants to go 7 steps down and 19 steps left. There is a so-called “right arrow” of green robots that all want to go 26 steps right. The right arrow forces the variable robot to either take the first 5 steps all to the right, or the first 7 steps all down. Note that after 5 steps to the right, the arrow does not restrict the variable robot from going down. In our gadgets, the diagonal part of the arrow will usually force the robot to take all the steps in a given direction, while the straight part will often be shorter. An example of a variable gadget Chaining the variable gadgets is rather simple and depicted in Figure 18. The two orange variable robots want to go seven steps to the right and 19 steps down. The purple variable robot wants to go seven steps left and 19 up. Clearly, if the orange robot on the left chooses to start by going right, it forces the purple robot to start by going up, and this subsequently forces the right orange robot to start by going right as well. On the other hand, if the orange robot on the right starts by going down, it forces the purple robot to start by going left, and this subsequently forces the left orange robot to start by going down as well. However, this is not the only way that variable gadgets can be chained. Sometimes, to avoid some collisions, it could be beneficial to chain arrows going in the same direction. See Figure 19 for an example of chaining up-arrows. In this case where a variable robot of some arrow chooses to go right and the variable robot of the next arrow chooses to start down, then these two intersect after 7 steps. Here, it is important that the difference of the x-coordinates and the y-coordinates of two consecutive variable robots is the same (it is 7 in the example). Example of a variable gadgets connecting Alternative example of a variable gadget moving diagonally Changing the orientation from left/right arrows to up/down arrows in the corners is a little tricky, but it can be done with the help of a variable gadget with either dx=1 or dy=1 that does not need an arrow. An example of using such a variable gadget in a chain can be seen in Figure 20. There, both purple robots want to go 12 steps down and 14 steps left. The light blue robot wants to go one step up and 25 steps right. If the bottom purple robot chooses to first go left, then the light blue robot is forced to move up in the first step, and the top purple robot is forced to choose to go left as well. On the other hand, if the top robot chooses to start by going down, then the light blue robot cannot do its one up move until it passes the top purple robot, and the bottom purple robot is forced to choose down as well. An example of the corner case is seen in Figure 21. The orange robot wants to go 12 steps right and 14 steps up, and the purple robot wants to go 12 steps down and 14 steps left. If the orange robot goes first 12 steps right and the purple robot goes 12 steps down, then all their remaining moves are forced, and in step 24, they are forced to either wait or collide. The light blue and pink robots are the special robots without an arrow as in Figure 20. Alternative example of a variable gadget chaining using a light blue robot that wants to go one up and 25 right Variable gadgets connecting at a corner. A similar construction is also used when connecting to a variable cycle Connecting Gadgets The connection of a clause gadget for clause C and a variable gadget for the corresponding variables is depicted in Figure 22. There are three variable gadgets in the figure; we will refer to them as left, right, and top, depending on which side of the clause gadget the variable robot starts. Connecting a clause gadget with variable gadgets. We can use alternative (diagonal) chaining of variable gadgets for the right variable in order to not interfere with the variable gadgets for the left variable Left Variable Gadget. The variable robot on the left starts at position Ω(C)+(-15,-1) and wants to go 8 steps to the right and 18 steps down. The up-arrow forces this robot to start by either moving 8 steps right or 5 steps down. If it chooses to go right, the variable robot is after 8 steps at position Ω(C)+(-7,-1), and by Lemma 32, it would intersect the clause robot of C if the robot’s route conforms to case (2) in the lemma. The choice will be propagated by the chaining depicted in Figure 18 such that there will be a down-arrow to the left of the variable gadget and the choice “up” in that arrow will intersect the choice “down” of the connection variable gadget within the first 5 steps. It is important to mention that it now comes into play the gap created in the blue stream of the clause gadget that allows the clause gadget to go first one step to the right and only then up since the the rightmost robot of the up-arrow will precisely fit in that gap. Right Variable Gadget. The variable robot on the right starts at position Ω(C)+(23,-1) and wants to go 12 steps left and 14 steps down. The right arrow below it forces the robot to either first do 12 steps to the left or first do 11 steps down. If it chooses to go 12 steps left, then it will be after the 12th step at position Ω(C)+(11,-1), and by Lemma 32, it would intersect the clause robot of C if the robot’s route conforms to case (1) in the lemma. To propagate the information, we will start with chaining diagonally down and right by putting another variable gadget with variable robot at Ω(C)+(34,-12) with right-arrow that forces it to go at least 11 steps left or some number of steps down. This allows us to not interfere with the arrows on the left. Top Variable Gadget. The variable robot in the top starts at position Ω(C)+(4,14) and wants to go 7 steps down and 19 steps left. It is forced by a right-arrow to either start with 7 steps down or with 5 steps left. If it starts down, then after the 7 steps down all the steps have to be to the left. Hence, after 9 steps, it is at position Ω(C)+(2,7) and in the 10th step it goes left. Therefore, by Lemma 32, it would intersect the clause robot of C if the robot’s route conforms to case (3) in the lemma. The choice is again propagated by the chaining depicted in Figure 18. One thing worth noticing is that, if the variable robot starts by going left, then going straight left for 19 steps would intersect the up arrow of the left variable gadget. However, after 5 steps left, it is actually free to take the 7 steps down and then to continue the remaining 14 steps left. This does not intersect the up-arrow on the left. Connecting to a Variable Cycle. To connect to a variable cycle, we need a way to distinguish between a variable appearing positively or negatively in the cycle. Both of these connections are very similar to how we change the direction on the variable cycle depicted in Figure 21. In this figure, on the left, we have a stream of up and down arrows that connect to a stream of left and right arrows. To change this corner gadget to a connection between a connection gadget and a variable cycle, we need to add a stream of up and down arrows going right. This is done again by using the variable gadgets without arrows. How this can be done precisely is depicted in Figure 23. All orange variable robots want to go 12 steps right and 14 steps up. The leftmost robot is forced to either start with 12 steps left or with 14 steps up. The purple robot wants to go 12 steps down or 14 steps left. It is forced to start by either going 14 steps down or 3 steps left. The pink robots all want to go one step right and 25 steps down. If the purple robot chooses to go down, then the leftmost orange robot cannot choose to go up, as they would intersect after 25 steps. Connecting a variable cycle with the connection gadget. The choice “up” on the leftmost variable gadget of the cycle intersects with the choice “down” on the first variable gadget of the connection gadget Theorem 33 CMP-M is NP-hard when restricted to instances where ℓ=26. Proof We summarize the proof of the theorem. We start from an instance φ of 4-Bounded Planar 3-SAT with a set of variables X, a set of clauses C, and the incidence graph Gφ. We follow the construction described above and construct an instance (G,R,26) of CMP-M. Note that this construction takes polynomial time, and the number of grid-points of G is O((n+m)2)=O(n2), where n=|X| and m=|C|. We prove that φ is satisfiable if and only if there is a schedule for R of makespan at most 26. The proof is now basically identical to the proof of Theorem 30. First, let α:X→{True, False} be a satisfying assignment for φ. We again construct the variable cycles and the connection gadgets so that each variable gadget is associated with a variable. Moreover, we can set routes for all the variable gadgets for a variable x in a way that they are all consistent among themselves and they block the route of Lemma 32 for a clause C if and only if the negation of α(x) satisfies C. Since every clause is satisfied by α, setting the routes for variable gadgets this way allows us to always select one of the routes of Lemma 32 for the clause robot that does not collide with a route of any other robot. For the converse, let us assume that we have a valid schedule for all the robots. From the construction of the variable cycle, it follows that there are only two ways of setting routes for all variable gadgets on the variable cycle, since for a fixed variable gadget on the cycle, the route of the variable robot either forces a choice for the variable robot in the consecutive variable gadget in the clockwise direction around the cycle, or the one in the counter-clockwise direction. Hence, if two consecutive variable gadgets on a cycle are not consistent, the variable robots for these gadgets either collide, or they force opposite choices to be propagated on the cycle in the two directions going away from these two gadgets. Hence, there has to be a collision somewhere on the cycle. During the construction of the variable gadgets, we assigned one of these two settings to represent assigning the associated variable True and the other setting to represent False. This gives us the truth assignment of the variable and we only need to verify that this assignment satisfies all the clauses. By Lemma 32 and the construction of connection gadgets, for each clause, the clause robot has to intersect one of the two possible routes of one of the three variable gadgets associated with the three variables whose literals are in the clause. If the route of the clause robot intersects one of the possible routes of the variable robot associated with variable x, then the variable robot has only one choice for its route and this choice is propagated for all variable robots in variable gadgets on the connection gadget between the clause gadget and the variable cycle. Finally, the connection between the last variable gadget in the connection gadget and the variable cycle is set in a way that this forced route for the variable robot at this end of the connection gadget intersects a route of some variable robot on the variable cycle that represents setting the variable x in a way that it does not satisfy C. Hence, this variable robot on the variable cycle (and hence all variable robots on the variable cycle) had to choose the route that represents setting the truth value of the variable x such that it satisfies C. Therefore, all clauses of φ, and hence φ, are satisfied by this assignment. □ Concluding Remarks In this work, we settled the parameterized complexity of both CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. Along the way, we established the NP-hardness of the classical Vertex Disjoint Paths and Edge Disjoint Paths problems with constant path-lengths on grids, strengthening the existing lower bounds for these problems as well. Our results reveal structural insights into the properties of optimal solutions that may also prove useful in contexts that lie outside of this work. We conclude by stating two open questions that arise from our work. What is the parameterized complexity of other variants of CMP, such as the ones where the objective is to minimize the maximum length traveled or the total arrival time? What is the parameterized complexity of other variants of CMP, such as the ones where the objective is to minimize the maximum length traveled or the total arrival time? Can the fixed-parameter tractability of CMP-M or CMP-L parameterized by the number k of robots be lifted to grids with obstacles/holes, or more generally to planar graphs? It is worth noting that neither the structural results developed in this paper, nor other known techniques [25], seem to be applicable to these more general settings. Can the fixed-parameter tractability of CMP-M or CMP-L parameterized by the number k of robots be lifted to grids with obstacles/holes, or more generally to planar graphs? It is worth noting that neither the structural results developed in this paper, nor other known techniques [25], seem to be applicable to these more general settings. Acknowledgements Robert Ganian acknowledges support from Projects No. 10.55776/Y1329 and 10.55776/COE12 of the Austrian Science Fund (FWF) and from Project No. 10.47379/ICT22029 of the Vienna Science Foundation (WWTF). Iyad Kanj acknowledges support from DePaul URC Grants 606601 and 350130. Funding Open access funding provided by TU Wien (TUW). Footnotes We consider a visit to be a situation where a robot was not on v at some time step j-1, and then enters v at time step j. This means that waiting on v does not amount to repeated visits, but a single robot may leave and then return to v multiple times. A preliminary and shortened version of this manuscript appeared in the proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023) [13]. Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References