Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs

In the classic multi-robot motion-planning (MRMP) problem, a set of robots operate in a common workspace, and need to reach a set of target positions. More precisely, given a set of $m$ starting positions and a set of $m$ target positions, the goal is to compute a motion strategy for the robots to reach the targets while avoiding collisions with the boundary of the workspace and with other robots. In this paper we consider unit-disk robots that are moving in a polygonal workspace in the plane. If each robot is assigned to a specific target, the problem is referred to as labeled MRMP, and otherwise it is unlabeled MRMP.

The MRMP problem and its variants have been widely investigated, both from theoretical and practical perspectives (see, e.g., [3, 4, 5, 6, 9, 11] for some of the more recent works on the problem). Very recently, both the labeled and unlabeled variants of MRMP for unit disks in polygons with holes were shown to be PSPACE-hard [1]. Many other variants of the problem are known to be hard as well, see e.g. [8, 12, 14, 16].

Interestingly, the separation between the robots plays a key role in the difficulty of the problem. Adler, de Berg, Halperin, and Solovey [2] show that in a simple polygonal workspace with $n$ vertices and $m$ unit-disk robots, when the robots-separation, denoted $\rho$, is $4$ (i.e., all the start and target positions are at least distance $4$ apart), a solution for unlabeled MRMP always exists, and can be found in $\tilde{O}(mn+m^2)$ time. In [7] this result is further improved by distinguishing between monochromatic robots-separation (i.e. the distance between two start or two target positions), and bichromatic robots-separation (i.e. the distance between a start position and a target position). The algorithmic approach in both papers [7, 2] is similar and does not provide any reasonable approximation on the length of the solution, i.e., the total length of the paths in the motion plan.

Solovey, Yu, Zamir, and Halperin [15] present a different approach for unlabeled MRMP, with optimality guarantee even in polygons with holes, but at the cost of adding an additional assumption on the distance between the obstacles to any start and target position. Specifically, they consider the case when the robots-separation is $\rho =4$, and the obstacles-separation, denoted $\omega$, is $\sqrt{5}\approx 2.236$. Under these assumptions, they present an algorithm that runs in $\tilde{O}(m^4+n^2{m}^2)$ time and returns a solution of total length at most $\text{OPT}+4m$. Here and throughout the paper, OPT denotes the minimum possible sum of lengths of the paths in a collision-free motion plan.

Notice that when assuming a large robots-separation ($\rho \ge 4$), the overall “density” of the robots inside the workspace becomes small, which may require the workspace to be much larger than the number of robots operating in it. Also, assuming a large obstacles-separation requires adding an additional buffering “layer” around the obstacles. This motivates the question of whether we can find weaker assumptions on either the robots-separation or the obstacles-separation, that are sufficient for having a polynomial time algorithm for unlabeled MRMP. Surprisingly, in this paper we show that both the robots-separation and obstacles-separation assumptions can be significantly relaxed, while still enabling a polynomial-time algorithm that achieves a constant-factor approximation of the solution length.

In previous works, namely [2, 7, 15], the algorithmic approach uses a monotone strategy, where robots move to their target position one by one according to some order, while other robots must remain at their start/target positions. The main result in our paper uses a weakly-monotone strategy. In a weakly-monotone motion plan, each start/target position $p$ is associated with a revolving area - a disk of radius $r>1$ that contains the unit disk centered at $p$ and is empty of obstacles and other unit disks centered at other start/target positions. The robots move to their target position one by one according to some order, while other robots must remain inside the revolving area associated with their current position. Such a weakly-monotone strategy was used, e.g., in [4, 13] for a variant of labeled MRMP with unit-disk robots.

We consider a set of $m$ unit-disk robots, moving in a polygonal workspace $𝒲\subseteq {ℝ}^2$ (which may be simple or cluttered with polygonal obstacles), whose overall number of edges is $n$. Below, we mostly follow the notations in [7] and [15].

The obstacle space $𝒪$ is the complement of the workspace $𝒲$, that is, $𝒪={ℝ}^2\setminus 𝒲$. We refer to the points in $𝒲$ as positions, and say that a robot is at position $x\in 𝒲$ when its center is positioned at the point $x$. For a point $x\in {ℝ}^2$ and a radius $r\in {ℝ}_{+}$, we define $D_r(x)$ to be the open disk of radius $r$ centered at $x$. The unit-disk robots are defined to be open sets, and therefore two robots collide if and only if the distance between their positions is strictly less than $2$. In addition, a robot collides with the obstacle space $𝒪$ if and only if its center is at distance strictly less than $1$ from $𝒪$. The set of all positions in $𝒲$ where a unit-disk robot does not collide with the obstacle space is called the free space, denoted $ℱ=\{x\in {ℝ}^2\mid D_1(x)\cap 𝒪=\mathrm{\varnothing }\}$. Note that the free space is a closed set, and denote by $\partial ℱ$ the boundary of $ℱ$.

In the multi-robot motion-planning problem, we are given a workspace $𝒲$ with $n$ edges and two sets $S=\{s_1,\mathrm{\dots },s_m\}$ and $T=\{t_1,\mathrm{\dots },t_m\}$ of points in the free space $ℱ$. The goal is to plan a collision-free motion for $m$ robots, each positioned on a different starting point in $S$, such that by the end of the motion every target position in $T$ is occupied by some robot. When the robots are distinguishable (i.e. labeled), the robot that starts at position $s_i$ is required to end up at the target $t_i$. Otherwise, when the robots are indistinguishable (i.e., unlabeled), it does not matter which robot ends up at which target position, as long as all targets are occupied at the end of the motion.

Formally, we wish to find a set $\mathrm{\Gamma }$ of continuous paths ${\gamma }_1,\mathrm{\dots },{\gamma }_m$, where ${\gamma }_i:[0,1]\to ℱ$ for every $1\le i\le m$, and such that ${\bigcup }_{i=1}^m{\gamma }_i(0)=S$ and ${\bigcup }_{i=1}^m{\gamma }_i(1)=T$. In addition, the paths need to be collision-free, i.e., at any point in time $t\in [0,1]$, there are no $i,j$ such that ${\gamma }_i(t)$ and ${\gamma }_j(t)$ are at distance strictly less than $2$. Denote the size of a solution $\mathrm{\Gamma }$ by $|\mathrm{\Gamma }|={\sum }_{{\gamma }_i\in \mathrm{\Gamma }}|{\gamma }_i|$, where $|\gamma |$ is the length of a path $\gamma$ in the $L_2$ norm. In the optimization version of the problem, we are interested in finding a solution $\mathrm{\Gamma }$ which minimizes $|\mathrm{\Gamma }|$, i.e., minimizing the sum of lengths of the paths.

To give an intuition for the required constraints, we first provide a high-level overview of our strategy. The algorithm is recursive, and its input is the overlap parameter $\epsilon$, a set $S$ of starting positions, a set $T$ of target positions, and a workspace $𝒲$. In each recursive iteration, one robot is moving to a target position, then $S$,$T$ and $𝒲$ are updated accordingly.

The first step is to compute an optimal-assignment path set, as it is defined in [15]:

Note that an optimal assignment path set $\mathrm{\Gamma }$ is not necessarily a feasible solution, because it ignores possible collisions between robots. This also means that the sum of paths in $\mathrm{\Gamma }$ is at most the length of an optimal solution to our MRMP problem. Let $\mathrm{\Gamma }=\{{\gamma }_1,\mathrm{\dots },{\gamma }_m\}$ be an optimal-assignment path set for $S,T,𝒲$.

In Section 3.1 we present a useful lemma showing that a blocking robot can enter the geodesic path that it blocks. This lemma will be useful throughout the analysis, and it requires one constraint on the obstacles-separation, and another on the robots-separation.

The next step is to find a target $t\in T$ which does not block any path in $\mathrm{\Gamma }$ (other than the path $\gamma$ from $s\in S$ to $t$). Then we can move a robot from $s$ to $t$ along $\gamma$, and it will not block other paths in the following iterations. Note that $t$ may still interrupt other paths. In Section 3.2 we show that such a target always exists, when assuming an additional constraint on the robots-separation.

If there is a position $s^{\prime }\in S$, which blocks the path $\gamma$, we need to make a switch, i.e., we construct a new path in $ℱ$ from $s^{\prime }$ to $t$, which is not blocked by any other robot. In Section 3.3 we show how to construct such a switch path ${\gamma }^{\prime }$, under all the constraints defined earlier. If there is no such blocking position $s^{\prime }$, we simply set ${\gamma }^{\prime }\leftarrow \gamma$.

We now have a path ${\gamma }^{\prime }$ from some $s^{\prime \prime }\in S$ (which may be either $s$ or $s^{\prime }$) to the target $t$, which in not blocked by any robots, but may be interrupted. In Section 3.4 we show how to move a robot from $s^{\prime \prime }$ to $t$ along ${\gamma }^{\prime }$, while all interrupting robots (either on start or target positions) move slightly in order to clear the path. For this we introduce two additional constraints, one on the obstacles-separation, and one on the robots-separation.

Finally, we prepare the input for the next recursive iteration, by removing $s^{\prime \prime }$ from $S$, $t$ from $T$, and $D_{1-\epsilon }(t)$ from $𝒲$. Removing $D_{1-\epsilon }(t)$ from $𝒲$ ensures that the robots placed on $t$ does not block any path that will be computed in any of the next iterations.

In Section 4 we present the complete algorithm based on the building blocks presented in this section, prove its correctness and analyze its running time and approximation factor.

In this section we present and analyze the algorithm based on the tools developed in the previous section. The input for the algorithm is an overlap parameter $\epsilon$, a workspace $𝒲$, a set $S$ of starting positions and a set $T$ of target positions, such that Constraints 1, 2, 3, 4, and 5 hold. In addition, we assume that each connected component of $ℱ$ contains an equal number of start and target positions (as otherwise, there is no solution).

For the simplicity of the analysis, in this section we provide an iterative version of the algorithm. In the $i$’th iteration, for $1\le i\le m$, the algorithm constructs a collision-free motion plan for all the robots over the time interval $[i-1,i]$, in which a single robot is moving from a start position to a target position along an $\epsilon$-interrupted path (Section 3.3), and the other robots may move in their small neighborhood to clear the way (Section 3.4). The output path for a robot $A$ will then be the concatenation ${\gamma }_A^{\ast }:[0,m]\to ℱ$ of the paths ${\gamma }_A:[i-1,i]\to ℱ$ constructed for it in all iterations. We then update $S$ and $T$ according to the path that was chosen, and remove from $𝒲$ a disk of radius $1-\epsilon$ around the target.

At the beginning of this section we gave a high level description of our algorithm, and a more detailed pseudo code is provided in Algorithm 1. Below, we prove that this algorithm returns a collision-free motion plan, with total length $O(\text{OPT})$, where OPT is the optimal size of a solution to the problem.

In this section we introduce a different algorithmic strategy for MRMP which we call the Exodus Algorithm. This strategy is more global in the sense that it also moves robots that do not directly block a path, and therefore it allows for robots-separation of $2$, while requiring obstacles-separation of only $3$. Whereas the previous algorithm relies on local path-clearing and larger robots-separation, Exodus replaces these local adjustments with a synchronized outward movement of all robots in order to clear the trace of a geodesic path, so that the selected robot can reach its target via this path. Note that in this section, we assume that the workspace $𝒲$ is a simple polygon. Due to space considerations, we give an overview of the algorithm and the main result here, see [10] for a formal description and proofs.

In this paper we provide multi-robot motion plans that require tighter assumptions on the density of the input setting. Note that for the Exodus algorithm we require $\rho =2$. This separation bound is tight for monochromatic robots-separation, however, the bichromatic robots-separation can potentially be $0$. This raises the question of what is the minimum obstacles-separation for which we can remove the robots-separation assumption completely.

In the full version of the paper [10] we also present lower bounds for the amount of obstacles-separation needed so that a solution to the MRMP problem always exists, without any assumptions on the separation between robots. In the unlabeled case, we prove that obstacles-separation of at least $1.5$ is sometimes needed (see Figure 6), and in the labeled case, we observe that obstacles-separation of at least $2$ is sometimes necessary (see Figure 7).