Optimal Motion Planning for Two Square Robots in a Rectilinear Environment

Let $\mathrm{\square }:=\{x\in {ℝ}^2\mid ||x|{|}_{\mathrm{\infty }}⩽1/2\}$ denote the axis-aligned square of unit side length – referred to as a unit square for short – centered at the origin. Let $A$ and $B$ be two robots, each modeled as a unit square, that can translate inside the same closed rectilinear polygonal environment $𝒲\subset {ℝ}^2$. In other words, the shared workspace $𝒲$ is a rectilinear polygon, possibly with holes. Let $n$ be the number of vertices of $𝒲$. A placement of $A$ (and, similarly, of $B$) is represented by the position of its center in the workspace $𝒲$. For such a placement to be free of collision with the boundary $\partial 𝒲$ of $𝒲$, the representing point should be at ${\mathrm{\ell }}_{\mathrm{\infty }}$-distance at least $1/2$ from $\partial 𝒲$. (Note that the robot is allowed to touch an obstacle, since we define $ℱ$ to be a closed set.) We let $ℱ\subset 𝒲$ denote the free space of a single robot, which is the subset of $𝒲$ consisting of all collision-free placements. A (joint) configuration $𝒑$ of $A$ and $B$ is represented as a pair $𝒑=(p_A,p_B)\in 𝒲\times 𝒲$, where $p_A$ and $p_B$ are the placements of $A$ and $B$, respectively. The configuration space, called C-space for short, is the set of all configurations, and is thus represented as $𝒲\times 𝒲\subset {ℝ}^4$. A configuration $𝒑=(p_A,p_B)\in {ℝ}^4$ is called free if $p_A,p_B\in ℱ$ and $||p_A-p_B|{|}_{\mathrm{\infty }}⩾1$. Let $𝑭\subseteq ℱ\times ℱ$ denote the four-dimensional free space, comprising the set of all free configurations.

Let $𝒔=(s_A,s_B)$ be a given source configuration and let $𝒕=(t_A,t_B)$ be a given target configuration. An $(𝐬,𝐭)$-plan is a continuous function $𝝅:[0,T]\to 𝒲\times 𝒲$, for some $T\in {ℝ}_{⩾0}$, with $𝝅(0)=𝒔$ and $𝝅(T)=𝒕$. The image of $𝝅$ is a continuous curve in the C-space, referred to as an $(𝐬,𝐭)$-path. With a slight abuse of notation, we use $𝝅$ to denote its image as well. If $𝝅\subset 𝑭$ we say that $𝝅$ is feasible, and if there exists a feasible $(𝒔,𝒕)$-plan we say that the pair $(𝒔,𝒕)$ is reachable. For a plan $𝝅:[0,T]\to 𝒲\times 𝒲$, let ${\pi }_A:[0,T]\to 𝒲$ and ${\pi }_B:[0,T]\to 𝒲$ be the projections of $𝝅$ onto the two-dimensional plane spanned by the first two coordinates and the last two coordinates, respectively. The functions ${\pi }_A$ and ${\pi }_B$ specify the motions of $A$ and $B$ that $𝝅$ induces, that is, $𝝅(\lambda )=({\pi }_A(\lambda ),{\pi }_B(\lambda ))$ for all $\lambda \in [0,T]$. Again, with a slight abuse of notation, we also use ${\pi }_A$ and ${\pi }_B$ to denote the paths followed by $A$ and $B$, respectively. We define two versions of optimal motion planning.

• $\mathrm{■}$

  Min-Sum. For a path $\gamma$ in $𝒲$, let $\Vert \gamma \Vert$ denote its ${\mathrm{\ell }}_1$-length. We define $\Vert 𝝅\Vert$, the cost of an $(𝒔,𝒕)$-plan $𝝅$, by $\Vert 𝝅\Vert :=\Vert {\pi }_A\Vert +\Vert {\pi }_B\Vert$, that is, $\Vert 𝝅\Vert$ is the sum of the ${\mathrm{\ell }}_1$-lengths of the paths of the two robots. The problem is to decide whether a given pair $𝒔,𝒕\in 𝑭$ is reachable, and, if so, compute a minimum-cost feasible $(𝒔,𝒕)$-plan. As explained later, we can restrict our attention to rectilinear paths because we work with the ${\mathrm{\ell }}_1$-metric inside a rectilinear environment.

• $\mathrm{■}$

  Min-Makespan. We define the makespan of an $(𝒔,𝒕)$-plan $𝝅:[0,T]\to 𝒲\times 𝒲$, denoted by $\text{¢}(𝝅)$, to be $T$. The problem is to decide for a given pair $𝒔,𝒕\in 𝑭$ if $(𝒔,𝒕)$ is reachable and, if so, compute a feasible $(𝒔,𝒕)$-plan that minimizes the makespan under the condition that the maximum speed of each robot is at most 1. Note that we do not require the $(𝒔,𝒕)$-plan to be $C^1$ continuous, so the speed of $A$ or $B$ may instantaneously change from $0$ to $1$, and the robots may take sharp turns.

Both variants of the optimal motion planning problem are interesting in their own right. The first minimizes the total work done by the robots, while the second minimizes the total time taken until both robots have reached their destination.

It is beyond the scope of this paper to review the known results on motion-planning algorithms; for an overview of key results, we refer the reader to recent books and surveys on the topic [22, 23, 30, 31, 7, 33]. We mention here only a small sample of results – ones that are most closely related to the problem at hand.

Computing an optimal motion plan for a single translating square robot, or more generally for a single convex polygonal translating robot with a constant number of vertices, is equivalent – through C-space formulation – to computing a shortest path for a point robot amid polygonal obstacles with $O(n)$ vertices, and it can be solved in $O(n\log n)$ time [16, 25, 44]. If the robot is allowed to rotate, the problem becomes much harder and it is NP-hard in some cases [10, 9, 34, 1]. Computing the shortest path for a point robot amid polyhedral obstacles in ${ℝ}^3$ is NP-hard [15], and fast $(1+\epsilon )$-approximation algorithms are known [17, 5].

Computing a feasible (not necessarily optimal) plan for a team of translating unit square robots in a polygonal environment is PSPACE-hard [38]; see [13, 14, 24, 26, 41, 46] for related intractability results. Notwithstanding a rich literature [18, 33, 36, 42, 43] on multi-robot motion planning, little is known about algorithms for computing plans with provable quality guarantees. Even in the absence of obstacles, computing the min-sum motion plan for two unit squares/disks is non-trivial under the ${\mathrm{\ell }}_2$-metric [21, 29]. Variants with more than two robots in a setting without obstacles have been studied as well [19, 20, 27]. Recently, Agarwal et al. [4] presented the first polynomial-time approximation algorithm for the min-sum motion-planning problem for two squares that computes an $(1+\epsilon )$-approximate solution in ${\epsilon }^{-O(1)}{n}^2\log n$ time (under both the ${\mathrm{\ell }}_1$- and ${\mathrm{\ell }}_2$-metrics). They leave it as an open problem whether an optimal plan in this case can be computed in polynomial time. Approximation algorithms have been proposed for min-sum multi-robot motion planning under the assumption that the source and target positions of robots are separated from each other and from the obstacles [3, 37, 40]; see also  [2, 11]. There is also work on the unlabeled version of the problem, where each robot can end up at any of the (collective) target positions, as long as all of the target positions are occupied by robots at the end of the motion. Finally, we remark that sampling-based approaches have been proposed for optimal multi-robot motion planning [18, 28, 36, 39]; and that there is extensive work on the discrete version of the problem, where robots are moving on graphs; see e.g., [7, 42] for recent surveys.

Our main result is that Min-Sum is in P, while Min-Makespan is NP-hard. This is stated in the two following theorems.

We prove Theorem 2 by a reduction from the Partition problem, which is to decide whether a given set $Y$ of integers admits a partition into subsets $Y_A,Y_B$ such that ${\sum }_{y_i\in Y_A}p={\sum }_{y_i\in Y_B}q$. The idea of the reduction is to build a workspace $𝒲$ that consists of gadgets ${𝒲}_1,\mathrm{\dots },{𝒲}_m$, each corresponding to an element of $Y$ and to choose a parameter $\mu ⩾0$, so that both robots must pass through every gadget and there is a plan with makespan at most $\mu$ if and only if there is a valid partition of $Y$. See Figure 1.

Our main technical contribution is a polynomial-time exact algorithm for Min-Sum, as stated in Theorem 1. The crucial step toward designing this algorithm is to prove the existence of an optimal plan that is a canonical-grid plan, in which the path followed by each robot lies on an $O(n)\times O(n)$ non-uniform predefined grid; see Theorem 4.

For a single robot translating in a rectilinear environment in ${ℝ}^2$, it is well known that there is an optimal path, under the ${\mathrm{\ell }}_1$-metric, on the grid defined by the horizontal and vertical lines through the source and target positions and the lines containing the edges of the free space $ℱ$ [32]. For a pair of robots, the existence of an optimal plan on a suitably defined grid seems intuitive as well. Indeed, consider an optimal plan ${𝝅}^{\ast }(𝒔,𝒕)$. As argued in Section 2, we can assume each robot follows a rectilinear path (in $ℱ$) under the plan ${𝝅}^{\ast }$. Imagine trying to push a horizontal (resp. vertical) segment of ${\pi }_A^{\ast }$ to a horizontal (resp. vertical) line of the (nonuniform) grid formed by the lines supporting the edges of $ℱ$ or the lines at distance $1$ from $\partial ℱ$. It may happen that we fail to push the segment onto the grid because robot $B$ is blocking it. The hope is that we can continue to push the segment of ${\pi }_A$ and push the appropriate segment of ${\pi }_B$ in the same direction – essentially $A$ is pushing $B$ out of the way – until $B$ hits $\partial 𝒲$– without increasing the total cost. Thus, we have pushed a segment of ${\pi }_B$ onto a line containing an edge of $ℱ$ and the segment of ${\pi }_A$ onto a line at distance 1 from that line. Making this idea work is highly nontrivial, though. For instance, we must choose the direction into which we push a specific segment of ${\pi }_A$ in such a way that $\Vert {\pi }_A\Vert$ does not increase, but this may force us to push ${\pi }_B$ in such a way that $\Vert {\pi }_B\Vert$ increases. This is further complicated by the fact that $B$ may be on different sides of a segment of ${\pi }_A$ at different moments in time. Finally, a major complication is that pushing (a segment of) one robot onto a line at distance $i$ from an edge of $ℱ$, so that its length does not increase, may cause the other robot to end up on a line at distance $i+1$ from this edge, and this may cause a cascading effect so that the final grid will be too large.

To overcome these issues, we combine local pushing operations with global re-routing operations in such a way that the transformed paths lie on lines at distance 0, 1, or 2 from the edges of $ℱ$. These operations may increase the length of one path, but we prove that whenever this happens, the length of the other path decreases by at least the same amount. Thus we obtain an optimal plan that lies on a grid of size $O(n)\times O(n)$ and is still optimal.

After having established the existence of an optimal canonical-grid plan, we show that we can construct a $4$-dimensional weighted grid graph $𝒢=(𝒱,ℰ)$, with $𝒔,𝒕\in 𝒱$, of size $O(n^4)$, in $𝑭$ such that a shortest $(𝒔,𝒕$)-path in $𝒢$ corresponds to a min-sum $(𝒔,𝒕)$-plan.

Let $\mathrm{\square }$ be the unit square as defined in Section 1. Let $R_{\mathrm{\square }}:=R\oplus 2\mathrm{\square }$. Thus, $R_{\mathrm{\square }}=I_x^{\oplus }\times I_y^{\oplus }$ where $I_x^{\oplus }:=[x_R^{-}-1,x_R^{+}+1]$ and $I_y^{\oplus }:=[y_R^{-}-1,y_R^{+}+1]$. For any pair $p,q\in {ℝ}^2$, if $p\in R$ and $\left(p+\mathrm{\square }\right)\cap \left(q+\mathrm{\square }\right)\ne \mathrm{\varnothing }$, then $q\in R_{\mathrm{\square }}$. Next, we define two different extensions of $R$ that play a role in our analysis; see Figure 3. Let $R_{\leftrightarrow }:=I_x^{\oplus }\times I_y$, that is, $R_{\leftrightarrow }$ is obtained by extending $R$ by unit length to the left and to the right. Similarly, $R_{\updownarrow }:=I_x\times I_y^{\oplus }$ is the extension of $R$ by unit length in the upward and downward directions. Observe that $R_{\mathrm{\square }}\setminus (R_{\updownarrow }\cup R_{\leftrightarrow })$ consists of four semi-open unit squares, which we refer to as the corner squares of $R_{\mathrm{\square }}$. Finally, we define $Z=I_x^{\oplus }\times [y_R^{+}-1,y_R^{-}+1]$, and $Z^{-}=I_x^{\oplus }\times [y_R^{-}-1,y_R^{+}-1)$, and $Z^{+}=I_x^{\oplus }\times (y_R^{-}+1,y_R^{+}+1]$. Note that $0pt(Z)=1+\delta$ and $0pt(Z^{-})=0pt(Z^{+})=1-\delta$. The closures of $Z^{-},Z^{+}$ are translates of $R_{\leftrightarrow }$ by distance $1$ in the $y$-direction, and $Z^{-},Z,Z^{+}$ is a partition of $R_{\mathrm{\square }}$. Since no primary grid line of $L_{⩽1}$ intersects $\mathrm{int}(R)$, the regions $Z^{+}$ and $Z^{-}$ do not contain any vertices of $ℱ$. By Observation 5, the connected components of $Z^{+}\cap ℱ$ and $Z^{-}\cap ℱ$ are therefore rectangles, and $R_{\updownarrow }\cap ℱ$ is an $x$-monotone rectilinear polygon.

We define the influence region of $R$ to be $ℐ(R):=ℱ\cap R_{\mathrm{\square }}$. For $\lambda \in [{\lambda }_1,{\lambda }_2]$, if ${\pi }_B(\lambda )\notin ℐ(R)$ then ${\pi }_A(\lambda )$ can be pushed to $\text{top}(R)$ or $\text{bot}(R)$ without colliding with $B$, so we have to worry about subintervals of $[{\lambda }_1,{\lambda }_2]$ during which ${\pi }_B$ lies in $ℐ(R)$. As illustrated in Figure 4, the influence region $ℐ(R)$ may consist of several connected components: a giant component $\gamma (R)$ that contains $R$, and several tiny components, each of which lies inside a corner square of $R_{\mathrm{\square }}$. Tiny components are $xy$-monotone by Observation 5. Note that the giant component may intersect the corner squares. In particular, let $\rho$ be a corner square that lies, say, to the left of $R_{\updownarrow }$. By Observation 5, there is at most one connected component $\varphi$ of $\rho \cap ℱ$ adjacent to the right edge of $\rho$. If such a component $\varphi$ exists, then $\varphi =\rho \cap \gamma (R)$ and (like the tiny components) $\varphi$ is $xy$-monotone. Other components of $\rho \cap ℱ$ are tiny components of $ℐ(R)$. Let $\rho ,{\rho }^{\prime }$ be two corner squares on the same side of $R_{\updownarrow }$. If both $\rho \cap ℱ$ and ${\rho }^{\prime }\cap ℱ$ have non-empty connected components inside $\gamma (R)$, denoted by $\varphi$ and ${\varphi }^{\prime }$ respectively, then we refer to pairs of points in $\varphi \times {\varphi }^{\prime }$ as blocked pairs. The next lemma states the significance of blocked pairs.

Thus, if ${\pi }_B[{\lambda }_1,{\lambda }_2]$ contains a blocked pair, then the surgery of $𝝅$ and the proof of its correctness become significantly harder.

We next define critical subintervals of the time interval $[{\lambda }_1,{\lambda }_2]$ during which the surgery of $𝝅$ requires more care, and then prove some structural properties of $𝝅$ during these intervals. Again, we begin with a few definitions. A configuration $𝒑=(p_A,p_B)$ is called $x$-separated if $|{(p_A)}_x-{(p_B)}_x|⩾1$ and $y$-separated if $|{(p_A)}_y-{(p_B)}_y|⩾1$. We say that two $x$-separated configurations $𝒑,𝒒$ have the same $x$-order if $\mathrm{sign}({(p_A)}_x-{(p_B)}_x)=\mathrm{sign}({(q_A)}_x-{(q_B)}_x)$; otherwise the $x$-order is swapped. An interval $[{\nu }_1,{\nu }_2]$ is called $x$-separated if $𝝅({\nu }_1)$ and $𝝅({\nu }_2)$ are both $x$-separated. Note that this definition does not require that $𝝅(\nu )$ is $x$-separated for all $\nu \in [{\nu }_1,{\nu }_2]$.

For any unsafe interval $[{\nu }_1,{\nu }_2]$, either robot $B$ lies above $A$ throughout the interval – that is, ${\pi }_B{(\nu )}_y⩾{\pi }_A{(\nu )}_y$ for all $\nu \in [{\nu }_1,{\nu }_2]$ – or $B$ lies below $A$ throughout the interval. Indeed, the robots cannot change their $y$-order during an unsafe interval, because they must remain $y$-separated. If an endpoint ${\nu }_i\in \{{\nu }_1,{\nu }_2\}$ is not $x$-separated then either ${\nu }_i={\lambda }_i$ or ${\pi }_B({\nu }_i)\in \partial ℐ(R)$. An important type of unsafe interval is the so-called swap interval, as defined next.

Roughly speaking, the roles of unsafe and swap intervals are as follows. If a time $\lambda \in [{\lambda }_1,{\lambda }_2]$ does not lie in an unsafe interval, translating ${\pi }_A(\lambda )$ vertically within $R$ does not cause a conflict with ${\pi }_B(\lambda )$ because $𝝅(\lambda )$ is $x$-separated or ${\pi }_B(\lambda )\notin ℐ(R)$. If an unsafe interval is not $x$-separated, we show that we can modify ${\pi }_B$ to avoid conflicts after translating ${\pi }_A(\lambda )$ vertically without increasing the length of ${\pi }_B$. We prove the following crucial property of $x$-separated unsafe intervals using Lemma 6. Suppose $\lambda ,\mu \in [{\lambda }_1,{\lambda }_2]$ are the endpoints of $x$-separated unsafe intervals, not necessarily endpoints of the same unsafe interval, such that and $𝝅(\lambda ),𝝅(\mu )$ have the same $x$-order. If ${\pi }_B(\lambda )$, ${\pi }_B(\mu )$ lie in the same component of $ℐ(R)$ and are not a blocked pair, then we can obtain another feasible plan ${𝝅}^{\ast }[\lambda ,\mu ]$ by re-parametrizing $𝝅[\lambda ,\mu ]$ such that the configuration ${𝝅}^{\ast }(\nu )$ is $x$-separated for all $\nu \in [\lambda ,\mu ]$. Thus, we can eliminate all such unsafe intervals during $[\lambda ,\mu ]$ and push ${\pi }_A[\lambda ,\mu ]$ vertically to $\text{top}(R)\cup \text{bot}(R)$ as above.

Hence, the challenging case is to perform surgery when $[{\lambda }_1,{\lambda }_2]$ contains a swap interval. We keep the situation under control using Lemma 9, which bounds the number of swap intervals and which relies on the above property of $x$-separated unsafe intervals. The proof of this lemma is involved and needs a sequence of intermediate lemmas; see the full version.

We say that a modification ${𝝅}^{\ast }$ of $𝝅$ is compliant if the Feasibility (P1), Optimality (P2), Vertical alignment (P4) and Alternation (P5) properties hold, and all bad segments of ${𝝅}^{\ast }$ are either present in $𝝅$ or are a segment of ${\pi }_A^{\ast }[{\lambda }_1,{\lambda }_2]$.

We now describe the surgery we perform on ${\pi }_A$ and ${\pi }_B$ to align a given bad horizontal segment $e$ of ${\pi }_A$ with a grid line. The surgery consists of a sequence of one or more Push operations, described below, which push a part of ${\pi }_A$ or ${\pi }_B$ vertically onto a grid line. Let ${𝝅}^{\ast }$ denote the (modified) plan after the surgery.

A Push operation takes three parameters: a robot $X\in \{A,B\}$, a time interval $I=[{\mu }_1,{\mu }_2]$, and a $y$-coordinate $y^{\ast }$ of a horizontal grid line – a line from the set $L_{⩽2}$ – and it pushes the subpath ${\pi }_X[I]$ onto the grid line $\mathrm{\ell }:y=y^{\ast }$. More formally, the new plan ${𝝅}_X^{\ast }$ resulting from the operation $\text{Push}(X,I,y^{\ast })$ is obtained by setting

Thus a Push operation only changes the $y$-coordinates on the subpath ${\pi }_X[I]$. The exact surgery – the values of the parameters $X,I,y^{\ast }$ used in the Push operations that we perform – depends on the location of ${\pi }_A({\lambda }_1)$, the set of unsafe and swap intervals during $[{\lambda }_1,{\lambda }_2]$, and the position of $B$ during the swap intervals, as explained later.

A Push operation may have two side effects that we need to address. First, $\text{Push}(X,I,y^{\ast })$ may introduce a discontinuity at ${\mu }_1$ and/or ${\mu }_2$, the endpoints of $I$.

In other words, for $\mu \in \{{\mu }_1,{\mu }_2\}$ we may have $p^{-}(\mu )\ne p^{+}(\mu )$, where $p^{-}(\mu ):={lim}_{\lambda \uparrow \mu }{\pi }_X^{\ast }(\lambda )$ and $p^{+}(\mu ):={lim}_{\lambda \downarrow \mu }{\pi }_X^{\ast }(\lambda )$. This happens when ${\pi }_X(\mu )\ne {\pi }_X^{\ast }(\mu )$. We can resolve the discontinuity by adding the vertical segment $p^{-}(\mu )p^{+}(\mu )$, called a ghost segment, to ${\pi }_X^{\ast }$ to make the path continuous, and by re-parametrizing the motion along the ghost segments so that the resulting motion plan is feasible. The second side effect of pushing ${\pi }_X[I]$ to ${\pi }_X^{\ast }[I]$ is that $X$ may collide with the other robot during the interval $I$. When this happens we perform a set of secondary pushes, as described later.

Without loss of generality, we assume that ${\pi }_A({\lambda }_2)\in \text{top}(R)$. Our modification of $𝝅$ into ${𝝅}^{\ast }$ follows three main cases:

• $\mathrm{■}$

  Case I: ${\pi }_A({\lambda }_1)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">top</em>}(R)$.
  We perform one push operation: $\text{Push}(A,[{\lambda }_1,{\lambda }_2],y(\text{top}(R)))$; see Figure 5(ii).

• $\mathrm{■}$

  Case II: ${\pi }_A({\lambda }_1)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">bot</em>}(R)$. Furthermore, either there is at most one swap interval, or there are two swap intervals and ${\pi }_B$ lies above ${\pi }_A$ during the first swap interval.
  In this case, we pick $\overline{\lambda }\in [{\lambda }_1,{\lambda }_2]$ suitably and perform two push operations:
  $\text{Push}(A,[{\lambda }_1,\overline{\lambda }],y(\text{bot}(R)))$ and $\text{Push}(A,[\overline{\lambda },{\lambda }_2],y(\text{top}(R)))$. Thus, robot $A$ moves along $\text{bot}(R)$ from time ${\lambda }_1$ to $\overline{\lambda }$, and then it switches to moving along $\text{top}(R)$ until time ${\lambda }_2$.

  We have three subcases for the choice of $\overline{\lambda }$, illustrated in Figure 6.

  • –

    Case II(a): There are no swap intervals. If every configuration in $𝝅[{\lambda }_1,{\lambda }_2]$ is $y$-separated, then either $B$ lies below $A$, or above $A$, during the entire interval $[{\lambda }_1,{\lambda }_2]$. If $B$ lies below (resp. above) $A$ during $[{\lambda }_1,{\lambda }_2]$, set $\overline{\lambda }={\lambda }_1$ (resp. $\overline{\lambda }={\lambda }_2$). On the other hand, if there is a configuration in $𝝅[{\lambda }_1,{\lambda }_2]$ that is not $y$-separated, set $\overline{\lambda }:=sup\{\lambda \in [{\lambda }_1,{\lambda }_2]:𝝅(\lambda )\text{ is not }y\text{-separated}\}$.

  • –

    Case II(b): There is one swap interval and ${\pi }_B$ is below ${\pi }_A$ during this swap interval. Let $[{\mu }_0,{\mu }_1]$ be this swap interval. Set $\overline{\lambda }:={\mu }_0$.

  • –

    Case II(c): There is at least one swap interval and ${\pi }_B$ lies above ${\pi }_A$ during the first one. Let $[{\mu }_0,{\mu }_1]$ be this swap interval. Set $\overline{\lambda }:={\mu }_1$.

• $\mathrm{■}$

  Case III: ${\pi }_A({\lambda }_1)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">bot</em>}(R)$ and there are exactly two swap intervals, and ${\pi }_B$ lies below ${\pi }_A$ the during the first swap interval.
  Let $[{\mu }_0,{\mu }_1]$ and $[{\mu }_2,{\mu }_3]$ be the two swap intervals, with . Since all configurations in $𝝅[{\mu }_0,{\mu }_1]$ are $y$-separated and $B$ lies below $A$ during $[{\mu }_0,{\mu }_1]$, the path ${\pi }_B[{\mu }_0,{\mu }_1]$ lies in a connected component of $ℱ\cap Z^{-}$, which is a rectangle $Q^{\prime }$. We prove that ${\pi }_B[{\mu }_0,{\mu }_1]$ is contained in a rectangle $Q\supseteq Q^{\prime }$ of the subdivision of $ℱ$ induced by the lines of $L_0$. Let $[{\nu }_0,{\nu }_1]$ be the maximal interval containing $[{\mu }_0,{\mu }_1]$ such that ${\pi }_B({\nu }_0,{\nu }_1)\subset \mathrm{int}(Q)$. The push operations depend on which of ${\pi }_B({\nu }_0),{\pi }_B({\nu }_1)$ lie on $\text{top}(Q)$.

  • –

    Case III(a): ${\pi }_B({\nu }_0)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">bot</em>}(Q)$ and ${\pi }_B({\nu }_1)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">top</em>}(Q)$. We perform two push operations, $\text{Push}(A,[{\lambda }_1,{\lambda }_2],y(\text{bot}(R)))$ and $\text{Push}(B,[{\nu }_0,{\mu }_1],y(\text{bot}(Q)))$.

  • –

    Case III(b): ${\pi }_B({\nu }_0)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">top</em>}(Q)$ and ${\pi }_B({\nu }_1)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">bot</em>}(Q)$. Symmetric to the previous case.

  • –

    Case III(c): ${\pi }_B({\nu }_0),{\pi }_B({\nu }_1)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">top</em>}(Q)$. Again, we perform two push operations. The first is $\text{Push}(A,[{\lambda }_1,{\lambda }_2],y(\text{top}(R)))$. (Note that, unlike in the previous two subcases, we pushed $A$ to $\text{top}(R)$ instead of $\text{bot}(R)$.) Recall that ${\pi }_B[{\mu }_0,{\mu }_1]\subset ℱ\cap Z^{-}$, and let $[{\rho }_0,{\rho }_1]\supseteq [{\mu }_0,{\mu }_1]$ be the maximal interval such that ${\pi }_B[{\rho }_0,{\rho }_1]$ lies on or below the horizontal line ${\mathrm{\ell }}^{-}:y=y(\text{top}(R))-1$ that contains $\text{top}(Z^{-})$. The second push operation is $\text{Push}(B,[{\rho }_0,{\rho }_1],y(\text{top}(R))-1)$.

  • –

    Case III(d): ${\pi }_B({\nu }_0),{\pi }_B({\nu }_1)\in \text{<em class="ltx\_emph ltx\_font\_sansserif">bot</em>}(Q)$. We argue that this case does not occur.

After applying the above surgery, we possibly apply secondary pushes to ${\pi }_B$, as follows. For every unsafe interval $[{\nu }_1,{\nu }_2]$, if there is a time $\nu \in [{\nu }_1,{\nu }_2]$ such that ${\pi }_A^{\ast }(\nu )$ conflicts with ${\pi }_B^{\ast }(\nu )$, then we execute $\text{Push}(B,({\nu }_1,{\nu }_2),y^{\ast })$ , where

To prove the correctness of the surgery, we need to prove that the new plan has properties (P1)–P(5). The proofs of (P3)–(P5) are not difficult – they are essentially satisfied by construction. The proof of Feasibility (P1) for the surgery performed in Cases (I) and (II) is not hard either, but it is highly nontrivial for Case (III) because ${\pi }_B$ might get modified beyond the interval $[{\lambda }_1,{\lambda }_2]$, e.g. during the interval $[{\nu }_0,{\mu }_1]$ with in Case III(a) or during the interval $[{\rho }_0,{\mu }_1]$ in Case III(c). Since $A$ might not lie in $R$ during $[{\nu }_0,{\mu }_1]$ (or $[{\rho }_0,{\mu }_1]$), we have to prove that the modified plan ${𝝅}^{\ast }$ during the interval $[{\nu }_0,{\lambda }_1]$ (or $[{\rho }_0,{\lambda }_1]$) remains feasible. We can prove the feasibility of ${𝝅}^{\ast }[{\nu }_0,{\lambda }_1]$ in Case III(a) by showing that if ${𝝅}^{\ast }[{\nu }_0,{\lambda }_1]$ were not feasible then $𝝅$ would not have been an optimal plan. We prove the feasibility of ${𝝅}^{\ast }[{\rho }_0,{\mu }_1]$ in Case III(c) by showing the existence of an optimal plan with additional structural properties, performing a compliant modification on $𝝅$, if necessary, to ensure these properties, and arguing that these properties ensure that ${𝝅}^{\ast }[{\rho }_0,{\mu }_1]$ is feasible. Finally, we need to prove Optimality (P2) of the modified path, which is also nontrivial because the surgery may increase the length of one of the paths. To illustrate this, we show that the surgery in Case I does not increase the total length of the plan, even though it may increase the length of the plan of robot $A$.

By construction, $\Vert {\pi }_A^{\ast }[{\lambda }_1,{\lambda }_2]\Vert ⩽\Vert {\pi }_A[{\lambda }_1,{\lambda }_2]\Vert$. If ${\pi }_B$ remains unchanged then trivially $\Vert {𝝅}^{\ast }\Vert ⩽\Vert 𝝅\Vert$, so assume there is an unsafe interval $[{\nu }_1,{\nu }_2]$ in which ${\pi }_B$ lies in $Z^{+}$ and is pushed to $\text{top}(R_{\mathrm{\square }})$. If $𝝅({\nu }_1)$ is not $x$-separated then either ${\nu }_1={\lambda }_1$ or ${\pi }_B$ enters $ℐ(R)$ through $\text{top}(R_{\mathrm{\square }})$. (It cannot enter through the right or left edge of $R_{\mathrm{\square }}$, because then $𝝅({\nu }_1)$ would be $x$-separated.) Since ${\pi }_A({\lambda }_1)\in \text{top}(R)$, we have ${\pi }_B({\nu }_1)\in \text{top}(R_{\mathrm{\square }})$ if ${\nu }_1={\lambda }_1$; this is true since $𝝅(\nu )$ is $y$-separated for all $\nu \in [{\nu }_1,{\nu }_2]$. Hence, if $𝝅({\nu }_1)$ is not $x$-separated then ${\pi }_B{({\nu }_1)}_y=y_R^{+}+1$. Since ${\pi }_B$ is pushed to $\text{top}(R_{\mathrm{\square }})$ during $[{\nu }_1,{\nu }_2]$, we prove that this push procedure does not increase the length of the path of $B$. The same holds if $𝝅({\nu }_2)$ is not $x$-separated. Hence, ${𝝅}^{\ast }$ is still optimal in these cases.

Now assume that both $𝝅({\nu }_1)$ and $𝝅({\nu }_2)$ are $x$-separated. By Lemma 9, we know that $[{\nu }_1,{\nu }_2]$ is a swap interval. Since there is at most one swap interval with $B$ above $A$, by Lemma 9, there is at most one swap interval $[{\nu }_1,{\nu }_2]$ during which ${\pi }_B$ is modified. Pushing $B$ to $\text{top}(R_{\mathrm{\square }})$ during $[{\nu }_1,{\nu }_2]$ increases $\Vert {\pi }_B^{\ast }\Vert$ by at most the total length of the ghost segments $g({\nu }_1)$ and $g({\nu }_2)$, which is $2y_R^{+}+2-{\pi }_B{({\nu }_1)}_y-{\pi }_B{({\nu }_2)}_y$. Pushing $A$ to $\text{top}(R)$ during $[{\nu }_1,{\nu }_2]$ decreases the length of its path by at least $2y_R^{+}-{\pi }_A{({\nu }_1)}_y-{\pi }_A{({\nu }_2)}_y$. By definition, the configurations $𝝅({\nu }_i)$ are $y$-separated for $i=1,2$, so ${\pi }_B{({\nu }_i)}_y-{\pi }_A{({\nu }_i)}_y⩾1$. Hence,

We thus conclude that ${𝝅}^{\ast }$ is optimal. $◀$ Omitting further details of the correctness, we conclude that Theorem 4 holds, which is the crucial ingredient for Theorem 1. This concludes our sketch of the proof of our main result.