School of Computing, DePaul University, Chicago,
<EMAIL_ADDRESS>School of Computing, DePaul University,
Chicago<EMAIL_ADDRESS>Iyad Kanj, Salman Parsa
[300]Theory of computation Parameterized complexity and exact algorithms

###### Acknowledgements.

# On the Parameterized Complexity of Motion Planning for Rectangular Robots

Iyad Kanj  Salman Parsa

###### Abstract

We study computationally-hard fundamental motion planning problems where the
goal is to translate $k$ axis-aligned rectangular robots from their initial
positions to their final positions without collision, and with the minimum
number of translation moves. Our aim is to understand the interplay between
the number of robots and the geometric complexity of the input instance
measured by the input size, which is the number of bits needed to encode the
coordinates of the rectangles’ vertices. We focus on axis-aligned
translations, and more generally, translations restricted to a given set of
directions, and we study the two settings where the robots move in the free
plane, and where they are confined to a bounding box. We also consider two
modes of motion: serial and parallel. We obtain fixed-parameter tractable
(FPT) algorithms parameterized by $k$ for all the settings under
consideration.

In the case where the robots move serially (i.e., one in each time step) and
axis-aligned, we prove a structural result stating that every problem instance
admits an optimal solution in which the moves are along a grid, whose size is
a function of $k$, that can be defined based on the input instance. This
structural result implies that the problem is fixed-parameter tractable
parameterized by $k$.

We also consider the case in which the robots move in parallel (i.e., multiple
robots can move during the same time step), and which falls under the category
of Coordinated Motion Planning problems. Our techniques for the axis-aligned
motion here differ from those for the case of serial motion. We employ a
search tree approach and perform a careful examination of the relative
geometric positions of the robots that allow us to reduce the problem to FPT-
many Linear Programming instances, thus obtaining an FPT algorithm.

Finally, we show that, when the robots move in the free plane, the FPT results
for the serial motion case carry over to the case where the translations are
restricted to any given set of directions.

###### keywords:

motion planning of rectangular robots, coordinated motion planing of
rectangular robots, parameterized complexity

###### category:

##  1 Introduction

###  1.1 Motivation

We study the parameterized complexity of computationally-hard fundamental
motion planning problems where the goal is to translate $k$ axis-aligned
rectangular robots from their initial positions to their final positions
without collision, and with the minimum number of translation moves. The
parameter under consideration is the number $k$ of robots, and the input
length $N$ is the number of bits needed to encode the coordinates of the
vertices of the rectangles. We point out that, in our study, we deviate from
using the real RAM model [shamos], which assumes that arithmetic operations
over the reals can be performed in constant time, and use the Turing machine
model instead. We believe that our study is more faithful to the geometric
setting under consideration than the real RAM model. The input length $N$ can
be much larger than the number $k$ of rectangles, and hence, our study of the
parameterized complexity of the problem, which aims at investigating whether
the problem admits algorithms whose running time is polynomially-dependent on
the input size, is both meaningful and significant in such settings.

We study two settings where the robots move in the free plane, and where they
are confined to a bounding box. We also consider two modes of motion: serial
and parallel. Problems with the latter motion mode fall under the category of
Coordinated Motion Planning problems. We point out that the problems under
consideration have close connections to well-studied motion planning and
reconfiguration problems, including the famous NP-complete $(n^{2}-1)$-puzzle
[nphard2, nphard1] and the PSPACE-hard warehouseman’s problem [hopcroft1984]
where the movement directions are limited, among many others. Moreover, the
Coordinated Motion Planning for robots moving on a rectangular grid featured
as the SoCG 2021 Challenge [socg2021].

For most natural geometric (or continuous) motion planning problems,
pertaining to the motion of well-defined geometric shapes in an environment
with/without polygonal obstacles, the feasibility of an instance of the
problem can be formulated as a statement in the first-order theory of the
reals. Therefore, it is decidable using Tarski’s method in time that is
polynomially-dependent on the input length, and exponentially-dependent on the
number of variables, number of polynomials and the highest degree over all the
polynomials in the statement (see [renegar1, renegar2, renegar3,
schwartzsharir2]). When the parameter is the number $k$ of robots, if an upper
bound in $k$ on the number of moves in a solution exists, then the existence
of a solution can be decided in FPT-time using the above general machinery.
However, this approach is non-constructive, and we might not be able to
extract in FPT-time a solution to a feasible instance, as the only information
we have about the solution is that it is algebraic.

There has been very little work on the parameterized complexity of these
fundamental geometric motion planning problems, and our understanding of their
parameterized complexity is lacking. Most of the early work (e.g., see
[alagar, schwartzsharir3]) on such problems have resulted in algorithms for
deciding _only_ the feasibility of the instance and whose running time takes
the form ${\mathcal{O}}(n^{f(k)})$, where $n$ is the number of edges/walls
composing the polygonal obstacles in the environment. Therefore, it is natural
to investigate the parameterized complexity of the more practical variants of
the problems, where one seeks a solution that meets a given upper bound on the
number of robot moves or an optimal solution w.r.t. the number of robot moves,
which remained unanswered by the earlier works.

The goal of this paper is to shed light on the parameterized complexity of
these motion planning problems by considering the very natural setting of
axis-aligned translations (i.e., horizontal and vertical), and more generally,
translations restricted to a given (or a fixed) set of directions. We aim to
understand the interplay between the number of robots and the complexity of
the input instance (i.e., the input size). Our results settle the
parameterized complexity of most of the studied problem variants by showing
that they are FPT.

###  1.2 Related Work

There has been a lot of work, dating back to the 1980’s, on the motion
planning of geometric shapes (e.g., disks, rectangles, polygons) in the
Euclidean plane (with or without obstacles), motivated by their applications
in robotics. In this setting, robots may move along continuous curves. The
problem is very hard, and most of the work focused on the feasibility of the
problem for various shapes and environment settings (disks, rectangles,
obstacle-free environment, environment with polygonal obstacles, etc.).

The early works by Schwartz and Sharir [schwartzsharir3, schwartzsharir1,
schwartzsharir2] showed that deciding the feasibility of an instance of the
problem for two disks in a region bounded by $n$ “walls” can be done in time
${\mathcal{O}}(n^{3})$ [schwartzsharir3]; they mentioned that their result can
be generalized to any number, $k$, of disks to yield an
${\mathcal{O}}(n^{h(k)})$-time algorithm, for some function $h$ of $k$. When
studying feasibility, the moves can be assumed to be performed serially, and a
move may extend over any Euclidean length. Ramanathan and Alagar [alagar]
improved the result of Schwartz and Sharir [schwartzsharir3] to
${\mathcal{O}}(n^{k})$, conjecturing that this running time is asymptotically
optimal. The feasibility of the coordinated motion planning of rectangular
robots confined to a bounding box was shown to be PSPACE-hard [hopcroft1984,
hopcroft1986]. The problem of moving disks among polygonal obstacles in the
plane was shown be strongly NP-hard [spirakis]; when the shapes are unit
squares, Solovey and Halprin [solovey] showed the problem to be PSPACE-hard.

Dumitrescu and Jiang [dumitrescu2013] studied the problem of moving unit disks
in an obstacle-free environment. They consider two types of moves: translation
(i.e., a linear move) and sliding (i.e., a move along a continuous curve). In
a single step, a unit disk may move any distance either along a line
(translation) or a curve (sliding) provided that it does not collide with
another disk. They showed that deciding whether the disks can reach their
destinations within $r\in\mathbb{N}$ moves is NP-hard, for either of the two
movement types. Constant-ratio approximation algorithms for the coordinated
motion planning of unit disks in the plane, under some separation condition,
where given in [demaine]. For further work on the motion planning of disks, we
refer to the survey of Dumitrescu [survey].

The problem of moving unit disks in the plane is related to the problem of
reconfiguring/moving coins, which has also been studied and shown to be NP-
hard [coins]. Moreover, there has been work on the continuous collision-free
motion of a constant number of rectangles in the plane, from their initial
positions to their final positions, with the goal of optimizing the total
Euclidean covered length; we refer to [agarwal2023, esteban2023] for some of
the most recent works on this topic.

Perhaps the most relevant, but orthogonal, work to ours, in the sense that it
pertains to studying the parameterized complexity of translating rectangles,
is the paper of Fernau et al. [fernaucccg]. In [fernaucccg], they considered a
geometric variant of the PSPACE-complete Rush-Hour problem, which itself was
shown to be PSPACE-complete [flake2002]. In this variant, cars are represented
by rectangles confined to a bounding box, and cars move serially. Each car can
either move horizontally or vertically (or not move at all, i.e., is an
obstacle), but never both during its whole motion; that is, each car slides on
a horizontal track, or a vertical track. The goal is to navigate each car to
its destination and a designated car to a designated rectangle in the box
(whose corner coincides with the origin). They showed that the problem is FPT
when parameterized by either the number of cars or the number of moves.

Finally, we mention that Eiben et al. [egksocg2023] studied the parameterized
complexity of Coordinated Motion Planning in the combinatorial setting where
the robots move on a rectangular grid. Among other results, they presented FPT
algorithms, parameterized by the number of robots, for each of the two
objective targets of minimizing the makespan and the total travel length
[egksocg2023].

###  1.3 Contributions

We present fixed-parameter algorithms parameterized by the number $k$ of
(rectangular axis-aligned) robots for most of the problem variants and
settings under consideration. A byproduct of our results for the problems
under consideration is that rational instances of these problems admit
rational solutions.

  * (i)

We give an FPT-algorithm for the axis-aligned serial motion in the free plane.
Our proof relies on a structural result stating that every problem instance
admits an optimal solution in which the moves are along a grid that can be
defined based on the input instance. This structural result, combined with an
upper bound of $4k$ that we prove on the number of moves in the solution to a
feasible instance, implies that the problem is solvable in time
${\mathcal{O}}^{*}(k^{16k}\cdot 2^{20k^{2}+8k})$, and hence is FPT.

The structural result does not apply when the translations are not axis-
aligned. To obtain FPT results for these cases, we employ a search-tree
approach, and perform a careful examination of the relative geometric
positions of the robots, that allow us to reduce the problem to FPT-many
Linear Programming instances.

  * (ii)

We show that the problem for serial motion in the free plane for any fixed-
cardinality given set $\mathcal{V}$ of directions (i.e., part of the input) is
solvable in time ${\mathcal{O}}^{*}((4^{32k}\cdot k\cdot|\mathcal{V}|)^{4k})$.
A byproduct of this FPT algorithm is that the problem is in NP, a result that
– up to the authors’ knowledge – was not known nor is obvious. We complement
this result by showing that the aforementioned problem for any fixed set
$\mathcal{V}$ of directions that contains at least two nonparallel directions
(which includes the case where the motion is axis-aligned) is NP-hard, thus
concluding that the problem is NP-complete.

  * (iii)

We give an FPT algorithm for the problem where the serial motion is axis-
aligned and confined to a bounding box, which was shown to be PSPACE-hard in
[hopcroft1984]. This result is obtained after proving an upper bound of
$2k\cdot 5^{k(k-1)}$ on the number of moves in a feasible instance of the
problem.

The approach used in (ii) and (iii) does not extend seamlessly to the case of
coordinated motion (i.e., when robots move in parallel), as modelling
collision in the case of parallel motion becomes more involved. Nevertheless,
by a more careful enumeration and examination of the relative geometric
positions of the robots, we give:

  * (iv)

An FPT algorithm for the axis-aligned coordinated motion planing in the free
plane that runs in ${\mathcal{O}}^{*}(5^{2k^{3}}\cdot 8^{4k^{2}})$ time, and
an FPT algorithm for the axis-aligned coordinated motion planning confined to
a bounding box that runs in time ${\mathcal{O}}^{*}(5^{k^{2}}\cdot
8^{2k^{2}\cdot 5^{k^{2}}}\cdot 5^{k^{3}\cdot 5^{k^{2}}})$. The FPT algorithm
for the former problem implies its membership in NP.

##  2 Preliminaries and Problem Definition

We denote by $[k]$ the set $\\{1,\ldots,k\\}$. Let $\mathcal{R}=\\{R_{i}\mid
i\in[k]\\}$ be a set of axis-aligned rectangular robots. For
$R_{i}\in\mathcal{R}$, we denote by $x(R_{i})$ and $y(R_{i})$ the horizontal
and vertical dimensions of $R_{i}$, respectively. We will refer to a robot by
its identifying name (e.g., $R_{i}$), which determines its location in the
schedule at any time step, even though, when it is clear from the context, we
will identify the robot with the rectangle it represents/occupies at a certain
time step.

A _translation move_ , or a _move_ , for a robot $R_{i}\in\mathcal{R}$ w.r.t.
a direction $\overrightarrow{v}$, is a translation of $R_{i}$ by a vector
$\alpha\cdot\overrightarrow{v}$ for some $\alpha>0$. For a vector $\vec{u}$,
translate($R_{i}$, $\overrightarrow{u}$) denotes the axis-aligned rectangle
resulting from the translation of $R_{i}$ by vector $\overrightarrow{u}$. We
denote by _axis-aligned motion_ the translation motion with respect to the set
of four directions
$\mathcal{V}=\\{\overrightarrow{H}^{-},\overrightarrow{H}^{+},\overrightarrow{V}^{-},\overrightarrow{V}^{+}\\}$,
which are the negative and positive unit vectors of the $x$\- and $y$-axis,
respectively.

In this paper, we consider two types of moves: _serial_ and _parallel_ , where
the former type corresponds to the robots moving one at a time (i.e., a robot
must finish its move before the next starts), and the latter type corresponds
to (possibly) multiple robots moving simultaneously. We now define collision
for the two types of motion.

For a robot $R_{i}$ that is translated by a vector $\overrightarrow{v}$, we
say that $R_{i}$ _collides_ with a stationary robot $R_{j}\neq R_{i}$, if
there exists $0\leq x\leq 1$ such that $R_{j}$ and
translate($R_{i},x\cdot\overrightarrow{v}$) intersect in their interior. For
two distinct robots $R_{i}$ and $R_{j}$ that are simultaneously translated by
vectors $\overrightarrow{v}$ and $\overrightarrow{u}$, respectively, we say
that $R_{i}$ and $R_{j}$ _collide_ if there exists $0\leq x\leq 1$ such that
translate($R_{i},x\cdot\overrightarrow{v}$) and
translate($R_{j},x\cdot\overrightarrow{u}$) intersect in their interior.

We think of $\mathcal{R}$ as a set of axis-aligned rectangular robots, where
each robot is given by the rectangle of its starting position and the
congruent rectangle of its desired final position. We assume that the starting
rectangles (resp. final destination rectangles) of the robots are pairwise
non-overlapping (in their interiors). Let
$\mathcal{V}=\\{\overrightarrow{\theta_{1}},\ldots,\overrightarrow{\theta_{c}}\\}$,
where $c\in{\rm Nature}$, be a set of unit vectors. We assume that if a vector
$\overrightarrow{\theta_{i}}$ is in $\mathcal{V}$ then the vector
$-\overrightarrow{\theta_{i}}$ is also in $\mathcal{V}$. For a vector
$\vec{v}$, we denote by $x(\vec{v})$ and $y(\vec{v})$ the
$x$-component/coordinate (i.e., projection of $\vec{v}$ on the $x$-axis) and
$y$-component/coordinate of $\vec{v}$, respectively.

A _valid serial schedule_ (resp.  _valid parallel schedule_) $\mathcal{S}$ for
$\mathcal{R}$ w.r.t $\mathcal{V}$ is a sequence of collision-free serial
(resp. parallel) moves, where each move in $\mathcal{S}$ is along a direction
(resp. a set of directions) in $\mathcal{V}$, and after all the moves in
$\mathcal{S}$, each $R_{i}$ ends at its final destination, for $i\in[k]$. The
_length_ $|\mathcal{S}|$ of the schedule is the number of moves in it. In this
paper, we study the following problem:

Rectangles Motion Planning (Rect-MP)
Given: A set of pairwise non-overlapping axis-aligned rectangular robots
$\mathcal{R}=\\{R_{i}\mid i\in[k]\\}$ each given with its starting and final
positions/rectangles; a set $\mathcal{V}$ of directions; $k,\ell\in{\rm
Nature}$.
Question: Is there a valid schedule for $\mathcal{R}$ w.r.t. $\mathcal{V}$ of
length at most $\ell$?

We note that the time complexity for solving the above decision problem will
be essentially the same (up to a polynomial factor) as that for solving its
optimization version (where we seek to minimize $\ell$), as we can binary-
search for the length of an optimal schedule.

We also study The Rectangles Coordinated Motion Planning problem (Rect-CMP),
which is defined analogously with the only difference that the moves could be
performed in parallel. More specifically, the schedule of the robots consists
of a sequence of moves, where in each move a subset $S$ of robots move
simultaneously, along (possibly different) directions from $\mathcal{V}$, at
the same speed provided that no two robots in $\mathcal{R}$ collide. The move
ends when all the robots in $S$ reach their desired locations during that
move; no new robots (i.e., not in $S$) can move during that time step.

We focus on the restrictions of Rect-MP and Rect-CMP to instances in which the
translations are axis-aligned, but we also extend our results to the case
where the directions are part of the input (or are fixed). We also consider
both settings where the rectangles move freely in the plane, and where their
motion is confined to a bounding box. For a problem $P\in$ $\\{\textsc{{Rect-
MP}}{},\textsc{{Rect-CMP}}\\}$, denote by $\bigplus$-$P$ the restriction of
$P$ to instances in which the translations are axis-aligned (i.e.,
$\mathcal{V}=\\{\overrightarrow{H}^{-},\overrightarrow{H}^{+},\overrightarrow{V}^{-},\overrightarrow{V}^{+}\\}$),
by $P$-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ its restriction to instances in
which the robots are confined to a bounding box (which we assume that it is
given as part of the input instance), and by
$\bigplus$-$P$-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ the problem satisfying
both constraints. For instance, $\bigplus$-Rect-
MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ denotes the problem in which the
motion mode is serial, the translations are axis-aligned, and the movement is
confined to a bounding box.

In parameterized complexity [CyganFKLMPPS15, DowneyFellows13], the running-
time of an algorithm is studied with respect to a parameter $k\in{\rm Nature}$
and input size $N$. The basic idea is to find a parameter that describes the
structure of the instance such that the combinatorial explosion can be
confined to this parameter. In this respect, the most favorable complexity
class is FPT (fixed-parameter tractable) which contains all problems that can
be decided in time $f(k)\cdot N^{\mathcal{O}(1)}$, where $f$ is a computable
function. Algorithms with this running-time are called _fixed-parameter
algorithms_.

The ${\mathcal{O}}^{*}()$ notation hides a polynomial function in the input
size $N$, which is the length of the binary encoding of the instance.

##  3 Upper Bounds on the Number of Moves

In this section, we prove upper bounds – w.r.t. the number of robots $k$ – on
the number of moves in an optimal schedule for feasible instances of several
of the problems under consideration in this paper. Those upper bounds will be
crucial for obtaining the FPT results in later sections.

###  3.1 Motion in the Free Plane

The upper bound in the case where the robots move in the free plane is
straightforward to obtain:

######  Proposition 3.1.

Let $\mathcal{I}=(\mathcal{R},\mathcal{V},k,\ell)$ be an instance of Rect-MP
or Rect-CMP. If $\mathcal{V}$ contains at least two non-parallel directions,
then there is a schedule for $\mathcal{I}$ of length at most $4k$.

######  Proof 3.2.

Choose two non-parallel directions $\overrightarrow{v}$ and
$\overrightarrow{w}$ in $\mathcal{V}$, and assume that $\overrightarrow{v}$
has a positive slope and $\overrightarrow{w}$ has a negative slope. The
arguments for the other cases are analogous. An easy observation shows that
there is a robot $R_{i}\in\mathcal{R}$ such that the bottom-left quadrant
defined by its top-right vertex does not overlap with any other robots. We can
use a single move in the direction of $\pm\overrightarrow{v}$ to translate the
center of $R_{i}$ to a point that is extremely far from the other robots. By
repeating this argument, we can separate every pair of robots by any arbitrary
distance of our choice using $k$ moves. We can also perform this operation
starting from the end positions following the direction
$\pm\overrightarrow{w}$ and we can place the one-to-last position of $R_{i}$
and the second position of $R_{i}$, say on concentric circles $C_{i}$ of
distances arbitrarily-large from each other, see Figure 1. Hence, each robot
$R_{i}$ has now two positions that need to be connected. This is possible with
$2$ moves per robot. In total, we incur at most $4k$ moves to translate the
robots in $\mathcal{R}$ from their starting positions to their destinations.

Note that we do not care about the geometric complexity or the number of bits
required to encode the intermediate positions as we only need to show an upper
bound on the number of moves.

Figure 1: Top: robots at their starting position. Bottom: Robots (made smaller
for visibility) can be separated by arbitrary large distance using a single
direction. The numbers indicate the order in which the robots have to move.
The figure is not at scale, as we might need very large distances to guarantee
non-intersection in third and fourth moves of the robots.

###  3.2 Axis-Aligned Motion in a Bounding Box

In this section, we present upper bounds on the number of axis-aligned moves
in the case where the (serial/parallel) axis-aligned motion takes place within
an axis-aligned bounding box $\Gamma$, as opposed to the free plane. The crux
of the proof is showing that if the instance is feasible (i.e., admits a
schedule within $\Gamma$), then it admits a schedule whose length is upper
bounded by a computable function of the number $k$ of robots.

Let $\mathcal{I}=(\mathcal{R},\mathcal{V},k,\ell,\Gamma)$ be an instance of
$\bigplus$-Rect-MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$. Fix an ordering on
the vertices of any rectangle (say the clockwise ordering, starting always
from the top left vertex). For any two robots $R$ and $R^{\prime}$, the
_relative order_ of $R$ w.r.t. $R^{\prime}$ is the order in which the vertices
of $R$, when considered in the prescribed order, appear relatively to the
vertices of $R^{\prime}$ (considered in the prescribed order as well), with
respect to each of the $x$\- and $y$-axes. Note that the relative order of $R$
with respect to $R^{\prime}$ determines, for each vertex $p$ of $R$, the
relative position of the $x$-coordinate (resp. $y$-coordinate) of $p$ with
respect to the $x$-coordinate (resp. $y$-coordinate) of each vertex of
$R^{\prime}$ (e.g, with respect to $\overrightarrow{x^{\prime}x}$, the
relative position of a vertex $p$ of $R$ w.r.t. to a vertex $q$ of
$R^{\prime}$ indicates whether $x(p)\leq x(q)$).

######  Definition 3.3.

Fix an arbitrary ordering of the 2-sets of robots in $\mathcal{R}$. A
_configuration_ of $\mathcal{R}$ is a sequence indicating, for each 2-set
$\\{R,R^{\prime}\\}$ of robots in $\mathcal{R}$, considered in the prescribed
order, the relative order of $R$ with respect to $R^{\prime}$. A _realization_
of a configuration $C$ is an embedding of the robots in $\mathcal{R}$ such
that the relative order of any two robots in $\mathcal{R}$ conforms to that
described by $C$ and the robots in the embedding are pairwise nonoverlapping
in their interiors.111We can alternatively use the notion of order types
instead of configurations, but this would result in a much worse upper bound
on the number of moves.

######  Proposition 3.4.

For any two realizations $\rho,\rho^{\prime}$ of a configuration $C$, there is
a sequence of at most $2k$ valid moves within the bounding box $\Gamma$ that
translate the robots from their positions in $\rho$ to their positions in
$\rho^{\prime}$.

######  Proof 3.5.

The sequence of moves consists of two contiguous subsequences, the first in
the horizontal direction and the second in the vertical direction. For the
first subsequence of moves, we partition the robots in $\mathcal{R}$ into two
subsets: those whose positions in $\rho^{\prime}$ have smaller $x$-coordinates
than their positions in $\rho$, referred to as $\mathcal{R}_{left}$, and those
whose positions in $\rho$ have larger or equal $x$-coordinates than those in
$\rho$, referred to as $\mathcal{R}_{right}$. We sort the robots in
$\mathcal{R}_{left}$ in a nondecreasing order of the $x$-coordinates of their
left vertical segments, and those in $\mathcal{R}_{right}$ in a nonincreasing
order of the $x$-coordinates of their right vertical segments. For each robot
in $\mathcal{R}_{left}$, considered one by one in the sorted order, we
translate it horizontally so that its left (or equivalently right) vertical
segment is aligned with the vertical extension of its left (or equivalently
right) vertical segment in $\rho^{\prime}$. We do the same for the robots in
$\mathcal{R}_{right}$. Since $\Gamma$ is rectangular, both $\rho$ and
$\rho^{\prime}$ are in $\Gamma$, and the translations are axis-aligned, it
follows that all the aforementioned translations are within $\Gamma$.

After each robot in $\mathcal{R}$ has reached its vertical extension in
$\rho^{\prime}$, we again partition $\mathcal{R}$ into two subsets, those
whose top horizontal segments in $\rho^{\prime}$ are above theirs in $\rho$,
referred to as $\mathcal{R}_{above}$, and those whose top horizontal segments
in $\rho^{\prime}$ are below theirs in $\rho$, referred to as
$\mathcal{R}_{below}$. We sort $\mathcal{R}_{above}$ in nonincreasing order of
the their top horizontal segments (i.e., in decreasing order of their
$y$-coordinates) and those in $\mathcal{R}_{below}$ in nondecreasing order of
their bottom horizontal segments. We then route the robots in each partition
in the sorted order to its horizontal line in $\rho^{\prime}$, and hence to
its final destination.

It is obvious that the above sequence of moves has length at most $2k$, and
that at the end each robot is at its final destination in $\rho^{\prime}$.
Therefore, what is left is arguing that no move in the above sequence causes
collision. It suffices to argue that for the subsequence of horizontal moves;
the argument for the vertical moves is analogous.

Let $R$ and $R^{\prime}$ be two robots that are translated horizontally.
Suppose first that both $R$ and $R^{\prime}$ are moving in the same direction
(either both in the direction of $\overrightarrow{x^{\prime}x}$ or
$\overrightarrow{xx^{\prime}}$), say in the direction of
$\overrightarrow{xx^{\prime}}$. Assume, w.l.o.g., that $R$ is moved before
$R^{\prime}$, and hence, its left vertical segment has a smaller
$x$-coordinate than that of $R^{\prime}$. Since $\rho$ is a realization of
$C$, and since we move the robots in the described sorted order, clearly $R$
cannot collide with $R^{\prime}$ when $R$ was translated horizontally while
$R^{\prime}$ was stationary. Consider now the horizontal translation of
$R^{\prime}$. Since the relative position of $R$ and $R^{\prime}$ are the same
in $\rho$ and $\rho^{\prime}$, and since the vertical segments of $R$ are now
positioned on their vertical lines in $\rho^{\prime}$, if $R^{\prime}$
collides with $R$ during the translation of $R^{\prime}$ then the relative
position of the vertical segments of $R^{\prime}$ with respect to those in $R$
(and hence, the relative positions of $R^{\prime}$ w.r.t. $R$) will have to
change and will never change back. Since $R$ and $R^{\prime}$ have the same
relative order in $\rho$ and $\rho^{\prime}$, this collision cannot occur. The
argument is similar when $R$ and $R^{\prime}$ are moving in opposite
directions. This completes the proof.

######  Proposition 3.6.

Let $\mathcal{I}=(\mathcal{R},\mathcal{V},k,\ell,\Gamma)$ be a feasible
instance of $\bigplus$-Rect-MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ or
$\bigplus$-Rect-CMP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$. Then there is a
schedule for $\mathcal{I}$ of length at most $2k\cdot 5^{k(k-1)}$.

######  Proof 3.7.

Since the upper bound on the number of serial moves is also an upper bound on
the number of parallel moves, it suffices to prove the theorem for
$\bigplus$-Rect-MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$.

Suppose that $\mathcal{I}$ is feasible and consider an optimal schedule for
$\mathcal{I}$. Observe that there are five possible relative positions of any
two axis-aligned rectangles along each of the two axes, and thus at most
twenty five possible relative orderings for any two robots. It follows that
the total number of (distinct) configurations is at most $25^{{k\choose 2}}$,
where ${k\choose 2}$ is the number of 2-sets of $\mathcal{R}$. Since the
schedule under consideration is optimal, the same configuration can appear at
most $2k$ times in the schedule; otherwise, by Proposition 3.4, the schedule
could be “shortcut” by considering a sequence of at most $2k$ moves that would
translate the robots from the realization of the first occurrence of such a
configuration to its last occurrence, thus reducing the length of schedule and
contradicting its optimality. It follows that there is a schedule for $I$ of
length at most $2k\cdot 25^{{k\choose 2}}=2k\cdot 5^{k(k-1)}$.

We note that the obtained upper bounds on the length of the schedule of a
feasible instance already suggest an approach for obtaining FPT algorithms,
namely that of enumerating all sequences of configurations and then checking
their realizability. This approach results in much worse running times than
the ones for the FPT algorithms presented in this paper, and reveals less
about the structure of the solution than the presented results.

##  4 Axis-Aligned Motion

In this section, we prove a structural result about $\bigplus$-Rect-MP. This
result, in particular, and the upper bound on the number of moves imply that
$\bigplus$-Rect-MP is FPT parameterized by the number $k$ of robots. In brief,
the structural result states that, in order to obtain an optimal schedule to
an instance of $\bigplus$-Rect-MP, it is enough to restrict the robots to move
along the lines of an axis-aligned grid (i.e., a collection of horizontal and
vertical lines of the plane), that can be determined from the input instance.
Moreover, the number of lines in the grid is a computable function of the
number of robots, and the robots’ moves will be defined using intersections of
the grid lines.

######  Definition 4.1.

Let $\mathcal{I}=(\mathcal{R},\mathcal{V},k,\ell)$ be an instance of
$\bigplus$-Rect-MP. We define an axis-aligned grid $G_{\mathcal{I}}$,
associated with the instance $\mathcal{I}$, as follows.

  * •

Initialize $G_{\mathcal{I}}$ to the set of horizontal and vertical lines
through the starting and final positions of the centers of the robots in
$\mathcal{R}$; call these lines the basic grid lines.

  * •

Add to $G_{\mathcal{I}}$ the lines which are defined using “stackings” of
robots on the basic lines as follows; see Figure 2. Let $b\in G_{\mathcal{I}}$
be a vertical basic line with $x$-coordinate $x(b)$, and $w_{b}$ be the width
of the robot whose center could be on $b$. For each number $1\leq i\leq\ell$,
and each $i$-multiset $\\{R_{j_{1}},\ldots,R_{j_{i}}\\}$ of robots, and for
each choice of a horizontal width $w$ of a robot, add to $G_{\mathcal{I}}$ the
two vertical lines with $x$-coordinates
$x(b)\pm(w_{b}/2+w/2+\sum_{r=1}^{i}x(R_{j_{r}}))$.

  * •

Add to $G_{\mathcal{I}}$ the analogous lines for the horizontal basic lines.

Figure 2: An illustration of a stacking to define new vertical lines.

######  Theorem 4.2.

Every instance $\mathcal{I}=(G,\mathcal{R},k,\ell)$ of $\bigplus$-Rect-MP has
an optimal schedule in which every robot’s move is between two grid points
along a grid line in $G_{\mathcal{I}}$. The number of vertical (resp.
horizontal) lines in $G_{\mathcal{I}}$ is at most $k^{3}\cdot 2^{k+\ell+1}$.

######  Proof 4.3.

We argue by induction on the number $\ell^{\prime}$ of moves in the schedule.
If $\ell^{\prime}=1$, then the schedule has a single move that must be along a
line defined by both the starting and ending positions of a robot in
$\mathcal{R}$, and the statement is true in this case. Thus, assume henceforth
that the statement of the theorem is true when the optimal schedule has at
most $\ell^{\prime}-1$ moves. Let $R$ be the robot that performs the first
move (in the schedule) from some point $p_{1}$ to some point $p_{2}$, and
assume, w.l.o.g., that the move is horizontal in the direction of
$\overrightarrow{xx^{\prime}}$. We define a new problem instance
$\mathcal{I}^{\prime}$, which is the same as $\mathcal{I}$, with the
exceptions that in $\mathcal{I}^{\prime}$ the robot $R$ now has starting
position $p_{2}$ and the upper bound on the number of moves is
$\ell^{\prime}-1$. Let $G_{\mathcal{I}}$ and $G_{\mathcal{I}^{\prime}}$ be the
grids associated with instances $\mathcal{I}$ and $\mathcal{I}^{\prime}$,
respectively, as defined in Definition 4.1. The instance
$\mathcal{I}^{\prime}$ has a schedule of $\ell^{\prime}-1$ moves and hence,
there is a schedule for $\mathcal{I}^{\prime}$ such that each robot moves
along a grid line in $G_{\mathcal{I}^{\prime}}$.

The lines in the set $L_{2}=G_{\mathcal{I}^{\prime}}-G_{\mathcal{I}}$ are
basic vertical grid lines defined by $R$ being at $p_{2}$ plus all the lines
defined by stackings of these lines. Note that $L_{2}$ contains only vertical
lines and that $G_{\mathcal{I}^{\prime}}-L_{2}\subseteq G_{\mathcal{I}}$. Let
$G^{\prime}$ be the set of grid lines in $G_{\mathcal{I}^{\prime}}-L_{2}$
union the set of vertical lines obtained by stacking every robot on every line
in $G_{\mathcal{I}^{\prime}}-L_{2}$. Observe that $G^{\prime}\subset
G_{\mathcal{I}}$, and that we are allowed to perform this additional stacking
operation since the construction of $G_{\mathcal{I}}$ involves $\ell^{\prime}$
stackings, whereas the construction of $G_{\mathcal{I}}^{\prime}$ involves
$\ell^{\prime}-1$ stackings.

From among all schedules of length $\ell^{\prime}-1$ for
$\mathcal{I}^{\prime}$ along the grid lines $G_{\mathcal{I}^{\prime}}$,
consider a schedule that uses the maximum number of grid lines from
$G^{\prime}$.

Note that the move of $R$ from $p_{1}$ to $p_{2}$ and the schedule for
$\mathcal{I}^{\prime}$ give an optimal schedule for the original problem
instance $\mathcal{I}$; however, this schedule is not along the grid lines of
$G_{\mathcal{I}}$, and some robots may move along the lines in $L_{2}$.

Let $M$ be the set of segments of the grid lines in $L_{2}$ traversed by robot
moves that are along the lines of $L_{2}$; note that all of these are
vertical. Now we push back the robot $R$ from $p_{2}$ towards $p_{1}$. Let
$R(p)$ denote the robot $R$ located at point $p\in p_{1}p_{2}$. The move from
$p_{1}$ to $p$ remains valid, however, there might be intersections between
$R(p)$ and other robots in future moves, and between this move and future
positions of $R$ itself.

When $p=p_{2}$, we have a schedule, and thus no collisions exist. From the
construction of the grid lines, it follows that when the robot $R$ moves, the
(updated) grid lines in $L_{2}$ move by exactly the same distance in the same
direction. We now move all the segments of $M$ also in the same direction and
distance, i.e., we move the grid lines in $L_{2}$ together with all the robot
moves along them; see Figure 3. As we push back $R$ towards $p_{1}$, we stop
the first time that the right edge of some robot, say $Q$, that travels along
a segment in $M$, hits a vertical line that is defined by the left edge of a
robot $Q^{\prime}$ located on a line in $G_{\mathcal{I}^{\prime}}-L_{2}$, and
hence cannot be pushed further without potentially introducing a collision.
Now the center of $Q$ is positioned at a line that is defined by some stacking
of $G_{\mathcal{I}^{\prime}}-L_{2}$, and hence is a vertical line of
$G^{\prime}$. Since we have not introduced any collisions during the pushing,
we have obtained a grid schedule that uses more grid lines from $G^{\prime}$,
which contradicts the maximality of the chosen schedule for
$\mathcal{I}^{\prime}$. Therefore, there is a schedule in which all moves are
along $G^{\prime}$.

Figure 3: An illustration for the proof of Theorem 4.2. The blue broken line
is the path traversed by the center of $R$ in a schedule. The black broken
lines are the paths for the centers of other robots. The vertical dashed blue
lines are grid lines in $L_{2}$. The red segment is a move along a line in
$L_{2}$. The blue rectangle is $R$ after the first move, and the green and red
rectangles are some other robots at some time during their movement. After
moving the lines in $L_{2}$ to the right, the red segment becomes a stacking
over lines not in $L_{2}$.

Finally, we upper bound the number of lines in the grid. We upper bound the
number of vertical lines; the upper bound on the number of horizontal lines is
the same. Let ${\cal L}_{V}$ be the set of vertical lines in the grid, and
${\cal L}_{H}$ be that of the horizontal lines.

The number of starting and ending positions of the robots is $2k$, and hence
the number of basic vertical lines is at most $2k$. For each $i$, where $1\leq
i\leq\ell$, and for each basic vertical line $b$, we fix two robots: the one
of width $w_{b}$ whose center could fall on $b$ and the one of width $w$ whose
center could fall on the newly-defined vertical line based on the stacking.
There are ${k\choose 2}\leq k^{2}/2$ choices for these two robots. Afterwards,
we enumerate each selection of an $i$-multiset of robots, and for each
$i$-multiset $\\{R_{j_{1}},\ldots,R_{j_{i}}\\}$, we add the two vertical lines
with offset $(w_{l}/2+w/2+\sum_{k=1}^{i}x(R_{j_{k}}))$ to the left and right
of $b$. Note that this offset is determined by the two fixed robots and the
$i$-multiset of robots, and hence by the two fixed robots and the set of
robots in this multiset together with the multiplicity of each robot in this
set. Therefore, in step $i$, to add the vertical lines, we can enumerate every
2-set of robots, each $r$-subset of robots, where $r\leq i$, order the robots
in the $r$-set, and for each of the at most $2^{k}$ $r$-subsets of robots,
enumerate all partitions $(\alpha_{1},\ldots,\alpha_{r})$ of $i$ into $r$
parts. The number of such partitions is at most $2^{i}$. Hence, the number of
vertical lines we add in step $i$ is at most $2k\cdot k^{2}/2\cdot 2^{k}\cdot
2^{i}$, and the total number of vertical lines we add over all the $\ell$
steps is at most $k^{3}\cdot 2^{k}\cdot\sum_{i=1}^{\ell}2^{i}\leq k^{2}\cdot
2^{k}\cdot 2^{\ell+1}=k^{3}\cdot 2^{k+\ell+1}$. It follows that $|{\cal
L}_{V}|\leq k^{3}\cdot 2^{k+\ell+1}$ and $|{\cal L}_{H}|\leq k^{3}\cdot
2^{k+\ell+1}$ as well. Therefore, the total number of lines in the grid is
${\mathcal{O}}(k^{3}\cdot 2^{k+\ell})$.

######  Theorem 4.4.

$\bigplus$-Rect-MP, parameterized by the number of robots, can be solved in
${\mathcal{O}}^{*}(k^{16k}\cdot 2^{20k^{2}+8k})$ time, and hence is FPT.

######  Proof 4.5.

By the above theorem and by Proposition 3.1, the total number of
horizontal/vertical lines in the grid is ${\mathcal{O}}^{*}(k^{3}\cdot
2^{5k+1})$. The algorithm enumerates all potential schedules of length at most
$\ell\leq 4k$ along the grid. To do so, the algorithm enumerates all sequences
of at most $\ell\leq 4k$ moves of robots along the grid lines. To choose a
move, we first choose a robot from among the $k$ robots, then choose the
direction of the move (i.e., horizontal or vertical), and finally choose the
grid line in either ${\cal L}_{V}$ (if the move is horizontal) or ${\cal
L}_{H}$ (if the move is vertical) that the robot moves to. The number of
choices per move is at most $k\cdot 2\cdot k^{3}2^{5k+1}$. It follows that the
number of sequences that the algorithm needs to enumerate in order to find a
desired schedule (if it exists) is at most $(k^{4}\cdot 2\cdot
2^{5k+1})^{\ell}\leq(k^{4}\cdot 2^{5k+2})^{4k}$ by Proposition 3.1. Since the
processing time over any given sequence is polynomial, it follows that the
running time of the algorithm is ${\mathcal{O}}^{*}(k^{16k}\cdot
2^{20k^{2}+8k})$.

The following result is also a byproduct of our structural result, since one
can, in polynomial time, “guess” and “verify” a schedule of length at most
$\ell$ to an instance of $\bigplus$-Rect-MP based on the grid corresponding to
the instance:

######  Corollary 4.6.

$\bigplus$-Rect-MP is in NP.

The above corollary will be complemented with Theorem LABEL:thm:nphard in
Section LABEL:sec:nphardfixeddirections to show that $\bigplus$-Rect-MP is NP-
complete.

##  5 An FPT Algorithm When the Directions are Given

In this section, we give an FPT algorithm for the case of axis-aligned
rectangles that serially translate along a given (i.e., part of the input)
fixed-cardinality set of directions. We first start by discussing the case
where the robots move in the free plane, and then explain how the algorithm
extends to the case where the robots are confined to a bounding box.

Let $\mathcal{I}=(R,\mathcal{V},k,\ell)$ be an instance of Rect-MP, where
$\mathcal{R}=\\{R_{1},\ldots,R_{k}\\}$ is a set of axis-aligned rectangular
robots, and
$\mathcal{V}=\\{\overrightarrow{\theta_{1}},\ldots,\overrightarrow{\theta_{c}}\\}$,
where $c\in{\rm Nature}$ is a constant, is a set of unit vectors; we assumed
herein that $c$ is a constant, but in fact, the results hold for any set of
directions whose cardinality is a function of $k$. Let $(s_{i}^{1},s_{i}^{2})$
be the coordinates of the initial position of the center of $R_{i}$ and
$(t_{i}^{1},t_{i}^{2})$ be those of its final destination. We present a
nondeterministic algorithm for solving the problem that makes a function of
$k$ many guesses. The purpose of doing so is two fold. First, it will serve
the purpose of proving the membership of Rect-MP in NP since the
nondeterministic algorithm runs in polynomial time (assuming that
$|\mathcal{V}|$ is a constant or polynomial in $k$). Second, it will render
the presentation of the algorithm much simpler. We will then show in Theorem
LABEL:thm:lpfpt how to make the algorithm deterministic by enumerating all
possibilities for its nondeterministic guesses, and analyze its running time.

At a high level, the algorithm consists of three main steps: (1) guess the
order in which the $k$ robots move in a schedule of length $\ell$ (if it
exists); (2) guess the direction (i.e., the vector in $\mathcal{V}$) of each
move; and (3) use Linear Programming (LP) to check the existence of
corresponding amplitudes for the unit vectors associated with the $\ell$ moves
that avoid collision.

We start by guessing the exact length, w.l.o.g. call it $\ell$ (since it is a
number between $0$ and $\ell$), of the schedule sought. We then guess a
sequence of $\ell$ events ${\cal E}=\langle e_{1},\ldots,e_{\ell}\rangle$,
where each event is a pair $(R_{i},\overrightarrow{v_{j}})$,
$i\in[k],j\in[c]$, that corresponds to a move/translation of a robot
$R_{i}\in\mathcal{R}$ along a vector $\overrightarrow{v_{j}}\in\mathcal{V}$ in
the sought schedule.

The remaining part of the algorithm is to check if there is a schedule of
length $\ell$ that is “faithful” to the guessed sequence ${\cal E}$ of events.

##  6 On the Visibility Regions

We are given $k$ robots $R_{1},\ldots,R_{k}$. Each robot is a rectangle of
fixed width and length $w_{i},l_{i}$, respectively, $i=1,\ldots,k$. We are
also given $k$ start positions for robots, denoted
$s_{1},\ldots,s_{k}\in{\mathbb{R}}^{2}$ and $k$ end positions
$e_{1},\ldots,e_{k}\in{\mathbb{R}}^{2}$. We assume that each coordinate of the
the start and end positions is a rational number. The size of the input is the
total number of bits that is used to encode the coordinates of the starting
and end positions and the dimensions of the $k$ robots.

The

######  Problem 6.1.

problem asks to find the smallest number of translations that moves all of the
robots from their starting positions to their end positions, and such that
during the whole process no intersection happens between two robots. We denote
the optimal number of moves by $L$.

#### The feasibility region

Suppose we have an instance $S$ of the

######  Problem 6.2.

. Let $s\in{\mathbb{R}}^{2k}$ be a $k$-tuple of points. We now fix the
endpoints $e_{1},\ldots,e_{n}$. For each $l\geq 0$, the feasibility region
(with respect to the fixed endpoints) is defined as

$A_{l}:=\\{s\in{\mathbb{R}}^{2k}|\text{there is an optimal solution with $l$
moves starting from $s$}\\}.$

the plane by fixing all but one starting point. The feasibility regionof
$R_{i}$, fixing $R_{j}$ at $p_{j}$, $j\neq i$, is defined as

$A_{l,{\hat{i}}}(p_{1},\ldots,p_{i-1},p_{i},\ldots,p_{k}):=\\{p\in{\mathbb{R}}^{2}|(p_{1},\ldots,p_{i-1},p,p_{i+1},\ldots,p_{k})\in
A_{l}\\}.$

Let $\pi=(m_{1},m_{2},\ldots,m_{l})$ be an $l$-tuple of numbers
$m_{i}\in\\{1,\ldots,k\\}$ that gives the ordered sequence of the robots that
move, potentially in an optimal solution for the problem instance $S$. Given a
sequence of moves $\pi$, we can restrict the feasibility regionto those where
the sequence of moves agrees with the given order. We call these sequences
$A^{\pi}_{l}$ and
$A^{\pi}_{l,\hat{i}}(p_{1},\ldots,p_{i-1},p_{i+1},\ldots,p_{k})$. From now on,
we write $P=(p_{1},\ldots,p_{k})$ and $P({\hat{i}})$ for the sub-sequence
obtained by removing $p_{i}$. Therefore, we can write
$A^{\pi}_{l}(P(\hat{i}))$ for short.

#### reachability

TO DO- This is same as visibility but considers only valid positions that the
center of the robot can reach without causing intersection. The reach of a
region $B$ is denoted as $V(B)$.

#### Determining feasibility region

It is possible to determine $A^{\pi}_{1}(P(\hat{i}))$ for all possible
$P(\hat{i})$ in terms of the end positions.

In this section we want to write formulas that express the sets
$A^{\pi}_{l}(P(\hat{i}))$ for all possible $P(\hat{i})$ in terms of
$A_{l-1}(P(\hat{i}))$ for all possible $P(\hat{i})$. Notice that we are moving
backwards from the end positions.

Assume that we know the sequence of move $\pi$ and that we know
$A_{l-1}(P(\hat{i}))$ for all possible $P(\hat{i})$.

The sequence $\pi$ provides us with the robot that move at each step. Without
loss of generality we assume that the robot that moves in the $L-(l-1)$-th
move is $R_{1}$. $R_{1}$ moves from $p^{\prime}_{1}$ into $p_{1}$ in the
forward direction. The rest of the robots are fixed at $p_{2},\ldots,p_{k}$.
We know that $p_{1}\in A^{\pi}_{l-1}(P(\hat{1}))$.

######  Lemma 6.3.

If robot $R_{1}$ moves in the $L-(l-1)$-th move of an optimal solution with
ordering $\pi$, and other robots are fixed at $P(\hat{1})$, then

$A^{\pi}_{l}(P(\hat{1}))=V(A^{\pi}_{l-1}(P(\hat{1})))-A^{\pi}_{l-1}(P(\hat{1})).$

The above lemma describe the relation in an easy case (say why). The hard case
is to update the feasibility region where the first robot is fixed. Let
$\sigma_{l}$ be a segment that the center of a robot $R$ traces in the $l$th
move. We defined the thickening of $\sigma_{l}$ as
$Th(R,\sigma_{l})=\bigcup_{x\in\sigma_{l}}R(x)$, where $R(x)$ is the robot at
position $x$.

######  Lemma 6.4.

If robot $R_{1}$ moves in the $L-(l-1)$-th move of an optimal solution with
ordering $\pi$ from $p^{\prime}_{1}$ to $p_{1}$, and other robots are fixed at
$P(\hat{1})$, then for $j\neq 1$

$A^{\pi}_{l}(p^{\prime}_{1},p_{2},\ldots,p_{j-1},p_{j+1},\ldots,p_{k})=\bigcup_{p}\big{[}A^{\pi}_{l-1}(p,p_{2},\ldots,p_{j-1},p_{j+1},\ldots,p_{k})-Th(R_{1},pp^{\prime}_{1})\big{]}.$

###  6.1 Moving along Fixed Directions

In this section, we prove that for Rect-
MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ restricted to a fixed set of
directions, under certain necessary conditions, we can obtain an upper bound
on the number of moves that depends only on $k$. The notion of a configuration
is defined analogously to that for the axis-aligned case.

######  Proposition 6.5.

Let $\mathcal{V}_{0}$ be a fixed set of directions. Consider an instance
$\mathcal{I}=(\mathcal{R},\mathcal{V}_{0},k,\ell,\Gamma)$ of Rect-
MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ or Rect-
CMP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$. In addition, assume that the
sizes of the robots in $\mathcal{R}$ satisfy the following relation

$M(B)-M(\mathcal{R})>\varepsilon>0,$

where $M(\Gamma)$ is the length of the longest side of the bounding box, and
$M(\mathcal{R})$ is the summation of longest sides of all the robots, and
$\varepsilon$ is a constant. Then, there is a constant $c$ (depending on
$\varepsilon$ and $\mathcal{V}_{0}$) such that, for any two realizations
$\rho,\rho^{\prime}$ of a configuration $C$ within $\Gamma$, there is a
sequence of at most $ck$ valid moves that translate the robots from their
positions in $\rho$ to their positions in $\rho^{\prime}$.

######  Proof 6.6.

If all directions in $\mathcal{V}_{0}$ are parallel, then clearly if the
instance is feasibly then it has a schedule of length at most $k$. So assume
$\mathcal{V}_{0}$ contains at least two non-parallel directions
$\overrightarrow{v}$ and $\overrightarrow{w}$. In the proof of Proposition
3.4, it was shown that two realizations $\rho$ and $\rho^{\prime}$ for the
same configuration can be obtained from each other by a sequence of horizontal
and vertical moves. We now prove that each of these moves can be simulated by
a sequence of moves in the directions of $\overrightarrow{v}$ and
$\overrightarrow{w}$. W.l.o.g, we can assume that the move we are simulating
is horizontal and to the left. We intend to replace the horizontal move by a
zigzag of moves along $\overrightarrow{v}$ and $\overrightarrow{w}$, see
Figure LABEL:. If it turns out that $\overrightarrow{v}$ and
$\overrightarrow{w}$ are close to each other, then we potentially need many
zigs and zags. The directions are constant for us.11todo: 1Iyad: This is not
clear. Also, it can be easily observed that the number of moves in the zigzag
depends on the “width” of the passageway we need to cross.22todo: 2Iyad: This
is not clear. To increase this width, we separate the robots as follows.

33todo: 3Iyad: This proof needs clarifications.

If the robot has already a non-zero vertical distance to all robots above it,
or to all robots below it, we can replace the horizontal move by a sequence of
$Ck$ zigzag moves where $C$ depends on the coordinates of the directions and
the extensions of the robots. If there is a stack of robots touching each
other on top of a robot $R$ that we want to move, and also a stack on bottom
(imagine this as a “connected component” of robots), then at least one of
these stacks must not touch the horizontal line of the bounding box, since
then no move will be possible in a direction other than that direction is
horizontal. W.l.o.g, assume that the stack on top of $R$ ends before the top
edge of the bounding box. We first move the stack by at most $k-1$ moves a
little away from $R$ (this can be done for instance by moving a robot whose
upper and left edges do not touch anything first, and then repeat this process
for the remaining component), and then perform $Ck$ moves to move $R$ to the
left, and then move back the stack by at most $k-1$ moves to their original
place. We therefore can simulate each horizontal move by $C^{\prime}k$ moves
where $C^{\prime}$ is constant depending on the bit-size of the directions and
the extensions of the robots.

If the motion is not axis-aligned, we can only obtain FPT result for the case
where $\mathcal{V}$ is fixed and satisfies the conditions in Proposition 6.5:

######  Theorem 6.7.

Given an instance $(\mathcal{R},\mathcal{V},k,\ell,\Gamma)$ of Rect-
MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ in which the box and $\mathcal{R}$
satisfy the conditions in Proposition 6.5, in time
${\mathcal{O}}^{*}(5^{k^{2}}\cdot(4^{32k}\cdot
k\cdot|\mathcal{V}|)^{{\mathcal{O}}(k)})$, we can construct a solution to the
instance or decide that no solution exists, and hence Rect-
MP-$\mathord{{[}0.7]{\scalerel*{\Box}{}}}$ is FPT.

##  7 Extension to Polygons

In this section, we show that the FPT algorithm for Rect-MP, presented in
Section 5, can be extended to Rect-MP for any set $\mathcal{R}$ of closed
polygons such that the number of edges of each polygon is upper bounded by a
constant, or even by any computable function $p(k)$ of the parameter $k$. The
algorithm proceeds in the same fashion by guessing $0\leq\ell\leq 2k$ and then
guessing the sequence ${\cal E}$ of $\ell$ events. For a polygonal robot $R$,
a vector $\overrightarrow{v}\in\mathcal{V}$ and $\alpha>0$,
trace($R_{i},\alpha\cdot\overrightarrow{v}$) is defined similarly, but now it
can have at most $2p(k)$ edges. Therefore, to stipulate non-collision between
$R$ and a robot $R_{j}\in\mathcal{R}$, $2(p(k))^{2}$ many pairs of segments
need to be considered, each pair giving rise to four cases to guess from. By a
similar analysis to that in the previous section, we have the following
theorem:

######  Theorem 7.1.

Given an instance $(\mathcal{R},\mathcal{V},k,\ell)$, where each robot in
$\mathcal{R}$ is a closed polygon with at most $p(k)$ edges, for some
computable function $p(k)$, in time ${\mathcal{O}}^{*}((4^{(2p(k))^{2}}\cdot
k\cdot|\mathcal{V}|)^{2k})$, we can construct a solution to the instance or
decide that no solution exists, and hence Rect-MP is FPT.

######  Corollary 7.2.

Let $c>0$ be an integer constant. The restriction of Rect-MP to instances in
which each polygon has at most $c$ edges is in NP.