Routing Few Robots in a Crowded Network

A natural first question in this line of enquiry is whether GCMP is fixed-parameter tractable w.r.t. $k+\mathrm{\ell }$. We note that the reduction underlying the aforementioned W[1]-hardness result for GCMP [7, Theorem 4] requires a large number of marked robots and completely breaks if we attempt to restrict $|ℳ|$. Nevertheless, as our first result, we provide a new, multi-layered reduction which strengthens the previous lower bound:

Intuitively, Theorem 1 can be seen as ruling out a uniformly polynomial algorithm for routing a single robot even if the budget is bounded by a constant.

The alternative to restricting $\mathrm{\ell }$ is to aim for tractability by combining $k$ with natural graph-structural restrictions; this is the approach which yielded the bulk of the algorithmic contributions in several recent articles on the problem and its variants [13, 16, 7, 14, 17, 8]. Given the prominence of the graph parameter treewidth, a first question that arises here concerns the complexity of GCMP when parameterized by $k$ plus the treewidth of $G$. Unfortunately, progress here seems difficult: the polynomial-time algorithm for GCMP1 on trees is highly non-trivial [26], and whether this result can be lifted to routing two marked robots on trees is a long-standing open question in the field. In other words, even an XP-algorithm for GCMP parameterized by $k$ in the special case of treewidth $1$ would be a breakthrough.

Instead, here we propose using a stronger restriction on $G$ –notably, its treedepth. Like treewidth, treedepth is a fundamental graph parameter that has close connections to the theory of sparsity [25] and has found applications as a parameter in a number of settings, ranging from space-efficient algorithms [24] through integer programming [20], model checking [19] and graph drawing [1, 3]. As our main algorithmic contribution, we prove:

The proof of Theorem 2 is non-trivial and does not directly follow from any of the previously developed techniques for treedepth-based algorithms on their own. For the proof, we partition instances of interest into three groups and provide different fixed-parameter algorithms for each of the three groups:

1. 1.

   Instances where the number $\mathbf{|}V\mathbf{(}G\mathbf{)}\mathbf{|}\mathbf{-}\mathbf{|}ℛ\mathbf{|}$ of free vertices is small. Here, our main contribution is a structural result showing that every YES-instance admits a schedule whose length is bounded by a function of the combination of $k$, the treedepth and the number of free vertices. Towards this, we show that such an instance has an optimal schedule in which at least one robot never moves from its initial position and moreover, such an “irrelevant” robot can be computed in FPT-time. We then show how this fact can be used to design a reduction rule that ultimately produces a graph of bounded size without affecting the solution size.

2. 2.

   Instances where $\mathbf{\ell }$ is small.³³3To provide intuition, we use “small” and “large” to indicate whether or not a value is upper-bounded by a specific function of the parameter. This is by far the simplest case, as it follows by directly adapting the previous algorithm for GCMP parameterized by $\mathrm{\ell }$ on graphs of bounded local treewidth [7, Theorem 5].

3. 3.

   Instances where both $\mathbf{\ell }$ and the number $\mathbf{|}V\mathbf{(}G\mathbf{)}\mathbf{|}\mathbf{-}\mathbf{|}ℛ\mathbf{|}$ of free vertices are large. This case is handled by providing a constructive procedure which correctly solves every instance of GCMP. The challenge here lies in the fact that if we do not outright reject the instance, then our procedure must terminate within at most $\mathrm{\ell }$ steps on all graphs of bounded treedepth, including those where the walks used by the marked robots may overlap in complicated ways.

At this point, it is natural to ask whether Theorem 2 is tight in the sense of requiring both treedepth and $k$ to achieve tractability. On one hand, one can exclude fixed-parameter algorithms, as well as XP-algorithms, for GCMP w.r.t. $k$ alone due to the known NP-hardness of GCMP1. However, none of the existing lower bounds rule out such algorithms when parameterized by treedepth alone. As our final result, we close this gap by establishing:

Theorem 3 implies that neither of the two parameters in our main algorithmic result can be dropped, and is obtained via a reduction from 3D-Matching that is entirely different from the one in Theorem 1 and complements other known lower bounds for coordinated motion planning on treelike graphs [16, 17].

Coordinated motion planning problems – sometimes also called multirobot pathfinding or robot routing problems – have been extensively studied by several research communities, including computational geometry [2, 31, 21] and artificial intelligence [4, 30, 29, 22]. The energy-minimization variant of the problem (i.e., the one considered in this article) also featured in the Third Computational Geometry Challenge at SoCG 2021 [15].

While the classical complexity of several variants of coordinated motion planning was settled already in the ’90s [26], there has been a recent concentrated effort to obtain a deeper understanding of these problems via the lens of parameterized complexity. Apart from the previously mentioned work on GCMP [7], recent advances include a parameterized study of the setting with fast robots [14], fixed-parameter algorithms on solid grids [13], parameterized lower bounds for tree-like and other well-structured graphs [16, 17] and fixed-parameter approximation algorithms on trees [8]. We remark that the latter three articles primarily consider the task of makespan minimization in the parallel motion setting, which exhibits different complexity-theoretic behavior than the energy minimization setting targeted in our work. For instance, determining the existence of a schedule of constant makespan is NP-hard even when restricted to solid grid graphs [13], but schedules involving constant energy can be computed in polynomial time (and this can even be lifted to fixed-parameter tractability on graph classes of bounded local treewidth [7, Theorem 5]).

Treewidth is a fundamental graph parameter which can be seen as a measure of how similar a graph is to a tree; trees have treewidth $1$, while the complete $n$-vertex graph has treewidth $n-1$. A formal definition of treewidth will not be necessary to obtain our results; however, we will make use of Courcelle’s Theorem [5], which essentially says that problems expressible in a certain fragment of logic can be solved efficiently on graphs of bounded treewidth. Hence, we proceed by defining our other parameter of interest.

Below, we state three facts about treedepth which will be useful for our considerations.

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. The set $ℳ$ contains robots that have specific destinations they must reach, whereas $ℱ$ is the set of remaining “free” robots. We assume that all the $s_i$’s are pairwise distinct and that all the $t_i$’s are pairwise distinct. A vertex $v\in V(G)$ is free at time step $x\in [0,t]$ if no robot is located at $v$ at time step $x$; otherwise, $v$ is occupied. We use a discrete time frame $[0,t]$, $t\in \mathbb{N}$, to reference the sequence of moves of the robots and in each time step $x\in [0,t]$, exactly one robot moves from its current vertex to an adjacent free vertex.

A route for robot $R_i$ is a tuple $W_i=(u_0,\mathrm{\dots },u_t)$ of vertices in $G$ such that (i) $u_0=s_i$ and $u_t=t_i$ if $R_i\in ℳ$ and (ii) $\forall j\in [t]$, either $u_{j-1}=u_j$ or $u_{j-1}{u}_j\in E(G)$. Put simply, $W_i$ corresponds to a “walk” in $G$, with the exception that consecutive vertices in $W_i$ may be identical (representing waiting time steps), in which $R_i$ begins at its starting vertex at time step $0$, and if $R_i\in ℳ$ then $R_i$ reaches its destination vertex at time step $t$. Two routes $W_i=(u_0,\mathrm{\dots },u_t)$ and $W_j=(v_0,\mathrm{\dots },v_t)$, where $i\ne j\in [k]$, are non-conflicting if $\forall r\in \{0,\mathrm{\dots },t\}$, $u_r\ne v_r$. Otherwise, we say that $W_i$ and $W_j$ conflict. Intuitively, two routes conflict if the corresponding robots are at the same vertex at the end of a time step.

A schedule S for $ℛ$ is a set of pairwise non-conflicting routes $W_i,i\in [k]$, during a time interval $[0,t]$ such that at every time step $x\in [0,t-1]$, exactly one robot moves; i.e., there is $i\in [k]$ with route $W_i=(u_0,\mathrm{\dots },u_t)$ such that $u_{x+1}\ne u_x$ and for every other robot $j\in [k]\setminus \{i\}$ with route $W_j=(v_0,\mathrm{\dots },v_t)$, it holds $v_{x+1}=v_x$. The (traveled) length of a route (or its associated robot) within S is the number of time steps $j$ such that $u_j\ne u_{j+1}$. The total traveled length of a schedule is the sum of the lengths of its routes; this value is often called the energy in the literature (e.g., see [15]).

We denote by GCMP1 the restriction of GCMP to instances where $|ℳ|=1$. We remark that even though GCMP is stated as as a decision problem, all the algorithms provided in this paper are constructive and can output a corresponding schedule (when it exists).

Intuitively, the decision component $G_D$ is the part of the construction where $R_1$ will choose the aforementioned lanes, and it is depicted in reference to Figure 1(b). Let a lane be a full path of length $k-1$. For each color $W_m$, the component $G_D$ contains an induced subgraph called a layer consisting of $|W_m|$ many vertex-disjoint lanes – one for each vertex in $W_m$.

The reason each lane has length precisely $k-1$ is that each vertex on it will be used to check adjacency between the vertex it represents in $G^{\prime }$ and a chosen vertex in one of the remaining $k-1$ colors. To facilitate this intuition, we use the following indexing for the individual vertices over the layers and lanes. Refer to Figure 1(b) for visual aid. For $m,n\in [k]$ with $m\ne n$ and $j\in [|W_m|]$, we define $v_{m,j,n}$ as follows:

• $\mathrm{■}$

  if , then $v_{m,j,n}$ is the $(n-1)$-st vertex in the $j$-th lane of the $m$-th layer, and

• $\mathrm{■}$

  if $m>n$, then $v_{m,j,n}$ is the $n$-th vertex in the $j$-th lane of the $m$-th layer.

Connect $s_1$ to each $\{v_{1,j,2}\mid j\in [|W_1|]\}$ with an edge. For $m\in [k-1]$, connect $\{v_{m,j,k}\mid j\in [|W_m|]\}$ and $\{v_{m+1,j,1}\mid j\in [|W_{m+1}|]\}$ with an empty path $Q_m=q_{m,1},\mathrm{\dots },q_{m,k^6}$ of length $k^6$. $Q=G[\{Q_m\mid m\in [k-1]\}]$ are the tiny separators. Let $L_m=G[\{v_{m,j,n}\mid n\in [k]\setminus \{m\},j\in |W_m|\}]$ be the $m$-th layer and let $L=G[L_m\mid m\in [k]]$ be the graph induced on all lanes of all layers. We add two more sets of paths, the clear paths and the return paths.

Create for every a free vertex $c_{m,n}$. Then connect $\{c_{m,n}\}$ to $\{v_{m,j,n}\mid j\in |W_m|\}$ with a full path $C_{m,n}$ of length $k^5-1$. The set of all $C_{m,n}$ constitutes the clear paths. We define .

For every edge $(w_{m,j_1}^{\prime },w_{n,j_2}^{\prime })\in E^{\prime }$ with , connect $\{v_{m,j_1,n}\}$ and $\{v_{n,j_2,m}\}$ with a full path $T_{m,j_1,n,j_2}$ of length $k^4(n-m)-1$. The set constitutes the return paths. Let the decision component be $G_D=G[L\cup Q\cup C\cup T]$.

The separator component $G_S$ is an empty path $(x,b_2,\mathrm{\dots },b_{k^{20}-1},y)$ of length $k^{20}$. The first vertex $x$ is connected to all vertices in $\{v_{k,j,k-1}\mid j\in [|W_k|]\}$. We further partition $G_S$ into $G_{S,1}=G[\{x,b_2,\mathrm{\dots },b_{k^8}\}]$ and $G_{S,2}=G[\{b_{k^8+1},\mathrm{\dots },b_{k^{20}-1},y\}]$.

Connect $\{y\}$ and $\{t_1\}$ with a full path $P$ of length $k^6(k-1)+\left(\genfrac{}{}{0pt}{}{k}{2}\right)+k^8+1$. Connect vertices in $P$ with vertices in $G_D$ and $G_{S,1}$ with full paths consisting of $k^{11}-1$ vertices, the so-called test paths. To define how the test paths are connected to the remainder of the graph, partition $P$ into the following sequence of consecutive subpaths: $P_0$, $P_1$, $P_1^{\prime }$, $P_2$, $P_2^{\prime }$, …, $P_{k-1}^{\prime }$, $P_k$, $P_k^{\ast }$.

1. 1.

   $P_0$ consists of a single vertex and is connected to $\{s_1\}$ with a test path.

2. 2.

   For each $m\in [k]$, we set $|P_m|=m-1$ (hence $P_1$ is empty and only listed for uniformity) and let $P_m=p_1,\mathrm{\dots },p_{m-1}$. For $n\in [m-1]$, connect $\{v_{m,j,n}\mid j\in [|W_m|]\}$ and $\{p_n\}$ with a test path.

3. 3.

   For each $m\in [k-1]$, we set $|P_m^{\prime }|=k^6$ and let $P_m^{\prime }=p_{m,1},\mathrm{\dots },p_{m,k^6}$. For each $i\in [k^6]$, we connect $\{p_{m_i}\}$ and $\{q_{m,i}\}$ with a test path.

4. 4.

   We set $|P_k^{\ast }|=k^8$ and let $P_k^{\ast }=p_1,\mathrm{\dots },p_{k^8}$. Connect $\{p_1\}$ and $\{x\}$ with a test path. Then for $i\in \{2,\mathrm{\dots },k^8\}$, connect $\{p_i\}$ and $\{b_i\}$ with a test path.

Finally, subdivide every edge in $P$, $k^8$ times. The vertices created in the subdivisions should not hold robots. The resulting path is the test component $G_T$. Note that for $m\in [k],n\in [k]\setminus \{m\},j\in [|W_m|]$, the vertex $v_{m,j,n}\in L$ is incident to a clear path if . Otherwise it is incident to a test path. We set $\mathrm{\ell }={\mathrm{\ell }}_{1,1}+{\mathrm{\ell }}_{1,2}+{\mathrm{\ell }}_2+{\mathrm{\ell }}_3+{\mathrm{\ell }}_4$, where the terms have the values shown in Table 1. This completes the description of the reduction.