A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots

We present a fixed-parameter algorithm for CSMP parameterized by the number $k$ of robots, and a fixed-parameter algorithm for Planar-CSMP-1 parameterized by the makespan $\mathrm{\ell }$. A crucial common ingredient for both results is showing that the solution to a problem instance admits a succinct representation, whose size is a function of the parameter, as a topological minor of the input graph. To the best of our knowledge, this is a novel approach in the context of coordinated motion planning problems.

Showing that the solution admits a succinct representation entails first bounding the makespan in an optimal solution by a function of the number $k$ of robots. Towards this end, we preprocess the graph by shortening (to $𝒪(k)$) sufficiently long paths comprising degree-2 vertices and focus on two cases. In one case, where the graph has bounded¹¹1In the rest of this description, we simply say bounded to refer to values bounded by a function of $k$. treedepth, we show that the instance can be reduced iteratively without altering the solution. This reduction process ultimately results in an instance of bounded size, implying the existence of a solution with a bounded makespan.

In the other case, we use ideas from [10] to define a notion of havens, which are subgraphs of bounded size with the following property: if a robot has to pass through a haven, then with a bounded number of additional steps, we can enable it to pass through the haven regardless of the other robots in the haven (i.e., without collision), effectively “untangling” all the robots’ traversals within the haven. Building on this, we construct a schedule in which each robot interacts with only a bounded number of havens, ultimately leading to a bounded-makespan schedule.

After bounding the makespan in an optimal solution, we show that it essentially describes a graph $H$ of bounded size as a topological minor in the input graph. Here, we have to work with rooted topological minors since all robots have specified starting points and some have specified destinations. For us, the roots are just the starting and ending vertices, as we have boundedly-many roots. Towards our goal, we partition the vertices of the graph induced by the edges participating in an optimal solution into two sets: important and unimportant vertices. We show that the number of important vertices is bounded, and that the unimportant vertices form paths whose internal vertices have degree $2$. This structure enables us to show that the graph induced by the edges in the solution (with terminals as roots) is a realization of some rooted graph with a bounded number of vertices as a topological minor in the input graph. We also prove the converse, namely that from any realization of $H$ as a topological minor in $G$, one can obtain an optimal solution for the given instance. Towards proving this, we show that if a robot follows a path that is devoid of important vertices, then it slides on that path without stopping. Finally, we leverage known results on topological minor containment to verify the existence of the correct rooted graph.

It is easy to see here that the solution admits a succinct representation since the parameter itself is the makespan. The difficulty is that the number of robots in the instance can be very large compared to the parameter $\mathrm{\ell }$, and we cannot find a realization of the succinct solution which avoids the “blocker” robots that do not contribute to the realization. To cope with this hurdle, we exploit the planarity of the graph to reduce its diameter, thus reducing the instance to an instance on a graph with bounded treewidth. The fixed-parameter tractability of the problem will then follow from Courcelle’s Theorem [8, 2].

The heart of our reduction method is finding an “irrelevant edge” in the graph that can be safely contracted to produce an equivalent instance of the problem. While the method of finding an irrelevant edge and contracting it has been employed in several results in the literature to exclude large grids, thus reducing the treewidth of the graph, in our setting the grid approach seems unworkable. Instead, we show that a sufficiently-large component $C$ of free vertices (i.e., vertices with no blockers on them) must contain an irrelevant edge. We reduce all the cases to one where $C$ is formed by a skeleton consisting of a “long” path of degree-2 vertices (the degree is taken in $C$), plus a “small” number of additional vertices. We then show that if the instance is a YES-instance of the problem, then it admits a solution that interacts nicely with this skeleton, in the sense that we can identify a subgraph of the representation of the solution, i.e., a topological minor that is essentially a roadmap of the solution, separated from the rest of the solution by a small cut. We can enumerate each possible representation of the part of the solution that interacts with the skeleton, and for each possible representation, test whether it exists near the skeleton; if it does, we mark the vertices in the graph that realize this representation. Since the skeleton is long, the total number of marked vertices on the skeleton is small, and an edge with both endpoints unmarked – and hence can be contracted – must exist.

The CSMP problem, with $p=k$, has been studied in [7] on several graph classes, and with respect to various settings, based on whether or not the destinations of the robots are distinguished (referred to as labeled or unlabeled). The graph classes that were considered include trees, grids, planar graphs, and general graphs, and it was shown that the problem is NP-hard even for (full rectangular) grids. Upper and lower bounds on the makespan of a solution, as well as computational complexity and approximation results, were derived for the various settings considered in [7].

A related problem to CSMP is that of moving unit disks (or objects [16]) in the plane, which has been studied in the context of reconfiguring/moving coins in the plane [1, 4], and was shown to be NP-hard [1]. We also mention the related work on coordinated pebble motion on graphs (and permutation groups), which was studied in [25] motivated by the work on the ($n^2-1$)-puzzle. The variant of coordinated motion planning in which only one designated robot is required to reach its destination, that is $p=1$, and each move is along a single edge, was studied as Graph Motion Planning with 1 Robot in [27].

Despite the tremendous amount of work on coordinated motion planning problems, not much work has been done from the parameterized complexity perspective. The work in [10] studied the parameterized complexity of the non-sliding version of CSMP, that is, where each motion step is along a single edge, parameterized by the makespan in the serial setting. Another recent work [17] studied the parameterized complexity of the classical coordinated motion planning problem on grids, presenting parameterized algorithms for various objective measures (makespan, travel length). The work in [20] established the W[1]-hardness of the classical coordinated motion planning problem parameterized by the makespan in the parallel motion setting, and also showed the NP-hardness of this problem on trees, among other results. Finally, the parameterized complexity of a geometric variant of the PSPACE-complete Rush-Hour problem, which itself was shown to be PSPACE-complete [21], was studied [19]; in particular, that problem was shown to be FPT when parameterized by either the number of robots (i.e., cars) or the number of moves.

A rooted graph is a graph where some vertices are labeled – formally:

Note that for $\partial (G)=\mathrm{\varnothing }$ the above coincides with the usual definition of topological minors.

In our problems of interest, we are given an undirected graph $G$ and a set $ℛ=\{R_1,R_2,\mathrm{\dots },R_k\}$ of $k$ robots where $ℛ$ is partitioned into two sets $ℳ$ and $ℱ$. Each $R_i\in ℳ$, has a starting vertex $s_i$ and a destination vertex $t_i$ in $V(G)$ and each $R_i\in ℱ$ is associated only with a starting vertex $s_i\in V(G)$. We refer to the elements in the set $\{s_i\mid i\in [k]\}\cup \{t_i\mid R_i\in ℳ\}$ as terminals. We assume that all the $s_i$ are pairwise distinct and that all the $t_i$ are pairwise distinct. We use a discrete time frame $[0,q]$, $q\in \mathbb{N}$, to reference the sequence of moves of the robots. In each time step $x\in [0,q]$, exactly one robot moves and the rest remain stationary.

In Coordinated Sliding-Motion Planning (CSMP), we are given a tuple $(G,ℛ=(ℳ,ℱ),k,\mathrm{\ell })$, where $G,ℛ$ and $k$ are as described in the last paragraph and $\mathrm{\ell }\in \mathbb{N}$. The goal is to decide whether there is a sequence of $q\le \mathrm{\ell }$ moves such that robots move serially one at a time, where a robot’s move consists of a move along a free/unobstructed path (i.e., a path in which no other robot is located at the time of the move), and such that each $R_i\in ℛ$ starts in $s_i$ at time step $0$ and each $R_i\in ℳ$ is positioned on $t_i$ at the end of time step $q$. The second problem that we consider is a restriction of CSMP to the case where $G$ is planar and $ℳ$ contains exactly one robot, referred to as the main robot. We refer to this restriction as Planar-CSMP-1, and for simplicity represent its instances as tuples of the form $(G,s,t,\mathrm{\ell },ℛ)$, where $s$ and $t$ are the starting and destination vertices of the main robot, respectively, and $ℛ$ is the set of all robots.

We next introduce some notation that will be used in our technical sections. A route for robot $R_i$ is a tuple $W_i=(u_0^i,P_1^i,u_1^i,\mathrm{\dots },P_q^i,u_q^i)$ where each $u_j^i$ is a vertex in $G$ and each $P_j^i$ is a simple path in $G$, such that (i) $u_0^i=s_i$ and $u_q^i=t_i$ if $R_i\in ℳ$ and (ii) $\forall j\in [q]$, $P_j^i$ is a $u_{j-1}^i$-$u_j^i$ path in $G$ (if $u_{j-1}^i=u_j^i$, then $P_j^i$ is the singleton path comprising the same vertex).

Put simply, each $W_i$ corresponds to a “walk” in $G$. If vertices of $W_i$ at two consecutive time steps $j-1$ and $j$ are identical, then $j$ is a waiting time step for the robot $R_i$. Moreover, each $R_i$ begins at its starting vertex at time step $0$, and if $R_i\in ℳ$ then $R_i$ is at its destination vertex at time step $q$. Though we work with undirected graphs and the paths described above are undirected paths, each path $P_j^i$ has a natural starting vertex and ending vertex designated by the time step $j$.

In particular, in the above definition, for every $i\ne j\in [k]$ and $\forall r\in \{0,\mathrm{\dots },q\}$, $u_r^i\ne u_r^j$.

A schedule S for $ℛ$ is a set of pairwise non-conflicting routes $W_i,i\in [k]$, during a time interval $[0,q]$, where exactly one robot moves in each time step. The number of moves in a route $W_i=(u_0^i,P_1^i,\mathrm{\dots },P_q^i,u_q^i)$ or the number of moves of its associated robot is the number of time steps $j$ such that $u_j^i\ne u_{j+1}^i$. The total number of moves (or makespan) in a schedule is the sum of the number of moves in its routes. A schedule of minimum total moves is called an optimal schedule.

A vertex $v$ is occupied at time step $i$ if some robot is located at $v$ at time step $i$; otherwise, $v$ is said to be free (or unoccupied). If the time step is not specified, it is assumed to be time step $0$ (i.e., in the initial state). At each time step, a robot may either move to a different vertex, or stay at its current vertex. Finally, we always assume that the input graph is connected since otherwise, we can work on individual connected components.

When only considering feasibility, CSMP is equivalent to the version where each move is along a single edge instead of an unobstructed path. Hence, feasibility testing is linear-time solvable [39, 10] and we can work under the assumption that every instance of CSMP is feasible (otherwise, we can reject the instance).

The following observation is straightforward:

We refer to a path where the above observation does not result in solving the instance as a resilient path. In other words, a path $Q$ is resilient if and only if for every pair of vertices $x,y$ in $V(Q)$ whose distance on $Q$ is at least $\mathrm{\ell }$, there is no $x$-$y$ path $Z$ in $G-Q$ with at most $\mathrm{\ell }-\text{<em class="ltx\_emph ltx\_font\_italic">blockd</em>}(s,x)-\text{<em class="ltx\_emph ltx\_font\_italic">blockd</em>}(y,t)-1$ blockers. Our goal is to show that every “sufficiently large” free component contains a “still sufficiently long” path with certain special properties that, intuitively, allow the path to be “cleanly separated” from a hypothetical solution. This is formalized in the following definition and lemma, where the property of being “still sufficiently long” is given by the function $g(\mathrm{\ell })=32{\mathrm{\ell }}^6\cdot 2^{14{\mathrm{\ell }}^2}+1$.