Sliding Squares in Parallel

Computing reconfiguration paths is not a simple task and, for many models, it is computationally intractable (even $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete [3]). Scaffolding (proposed independently by [23] and [26]) aims at making reconfiguration simpler by restricting the scope to configurations containing a regular substructure (the scaffold) that remains connected between moves (thus removing complexity from the connectivity constraint) while having enough empty positions to allow modules to move through the scaffold (thus removing complexity from the free space constraints). They obtain a scaffold by using meta-modules, groups of modules that cooperate to move as a higher-level functional unit. Previous work has used these to translate algorithms for a particular model to another (see, e.g., [21, 27, 28]).

The drawback of these techniques is that their input must belong to the subset of configurations where modules are already organized into meta-modules (the scaffold exists in both the initial and target configuration). The authors of [8, 16] proposed an algorithm that first builds the scaffold from an arbitrary scaled configuration. They achieve constant stretch, i.e., a makespan within a constant factor of the maximum minimum distance for a single robot (based on previous work [7, 12]). This was extended for labeled modules [18], and between obstacles [17]. Although their techniques apply to a wider range of configurations, there are still restrictions on the input. The algorithm presented in this paper also makes use of scaffolding and meta-module techniques. To the best of our knowledge, our algorithm is the first universal one to build the scaffold and meta-modules (i.e., from arbitrary input).

Our model is more constrained than existing models for parallel reconfiguration under connectivity constraints [15, 16, 18, 21, 24]. Michail, Skretas, and Spirakis [24] do not explicitly require the connected backbone constraint, and do not explicitly define the collision model. The models in [16, 18] do not require the connected backbone constraint, and allow modules to enter and leave cells simultaneously, even in orthogonal directions. Similarly, [21] relaxes the free-space constraint of the convex transition move, allowing a module to move through two diagonally adjacent static modules. However, the authors disallow chain moves as shown in Figure 1(b), so that the cells involved in individual slide moves in the same transformation are disjoint. The same is true for [14, 15] where the paths of transformations at any given time stamp must be disjoint.

We define the skeleton of a configuration $C$ as a valid subconfiguration $S$ such that: $C\subset N[S]$ (every module of $C$ is either contained in $S$ or edge-adjacent to a module of $S$); and cycles in the dual graph of $S$ are pairwise disjoint with length at most 4. We call a module in $S$ (resp., not in $S$) a skeleton (resp., nonskeleton) module. In Figure 6(a), skeleton modules are highlighted with an internal square and the perimeter of the skeleton is shown in red. Note that any set of nonskeleton modules is free.

On a high level, we can compute a skeleton $S$ of a given configuration $C$ as follows. Think of $S$ as a subset of $C$, initialized as the empty set. Modules of $C$ are then algorithmically added to $S$ until it satisfies the definition of a skeleton. First, all modules with even $x$-coordinate are added to $S$, then all modules with odd $x$-coordinate with no east and west neighbors. Next modules are added to $S$ until it is a connected subconfiguration of $C$ (see magenta squares in Figure 6(a)). This might introduce large cycles (greater than length 4) to $S$. These cycles are broken via removal of modules from $S$ or exchanging adjacent modules. We show that careful execution of these steps will build $S$ into a skeleton of $C$.

Equipped with a skeleton $S$, we now consider its dual graph. Contracting every cycle in the dual of $S$ to a single vertex renders a max-degree-4 tree where each node is either a cell or a 4-cycle. We refer to the nodes of this tree as nodes of $S$ and abuse notation by referring to $S$ as a tree. Let $r$ be the root node of $S$, arbitrarily chosen. For every nonskeleton module, we assign an adjacent module of $S$ as its support. We define the subskeleton rooted at $c$ (denoted $S_c$) as the subconfiguration containing $c$ and its descendant nodes. The set $S_c^{\ast }$ contains the modules in $S_c$ and the nonskeleton modules supported by modules in $S_c$. The weight of a subskeleton $S_c$ is defined as $|S_c^{\ast }|$. By definition, $S_r^{\ast }=C$ and $|S_r^{\ast }|=n$.

Using this, we locate a module $h\in S$ (highlighted with a red marker in Figures 6(a) and 6(b)) such that $|S_h^{\ast }|\in \mathrm{\Theta }(P)$. Afterwards, we “thicken” $S_h^{\ast }$ into a structure called the exoskeleton.

An exoskeleton is made from three types of modules: core, shell, and tail modules; depicted respectively in dark gray, purple and pink in the figures. Recall that we wish to make the neighborhood of $S_h$ is full. The core modules occupy the positions originally occupied by the skeleton $S_h$, the shell modules are the ones “coating” the skeleton, and the tail modules are “leftover” modules in the neighborhood of a leaf. We recursively thicken $S_h$ by applying this process to its smaller subtrees, effectively converting tail or core modules at the leaves into a shell module near the root. If the core modules cover the entire subtree of $S_h$, it may take a linear number of transformations to move a module from a leaf to the root. Instead, we allow empty positions inside the exoskeleton which permits us to “teleport” a module from a leaf to the root in $𝒪(1)$ transformations. Although some of the positions are empty, the structure remains connected due to its shell and the fact that these empty positions are well separated (in tree metric along $S_h$, see Property 4 below).

Formally, we define an exoskeleton $X_c$ as follows. The core $\overline{X_c}$ of $X_c$ are positions in the lattice (not necessarily full) that form a subtree of $S_c$ containing $c$ (since we recursively “shave off” leaves to make material for the shell). Note that $\overline{X_c}$, unlike $S_c$, is not a subgraph of the configuration’s dual graph because of the empty positions. In our figures, we highlight core cells with an internal circle. Let $ℒ$ be the set of positions corresponding to the leaves of $\overline{X_c}$. We call $N^{\ast }(\overline{X_c}\setminus ℒ)\setminus ℒ$ the shell of $X_c$ (recall $N^{\ast }(S)$ is the open neighborhood under vertex-adjacency). The following must hold:

1. 1.

   All modules in $X_c$ are in the neighborhood of its core. ($|\overline{X_c}|\ge 2$, and $X_c\subset N^{\ast }\left[\overline{X_c}\right]$.)

2. 2.

   The leaves are occupied. ($ℒ\subset X_c$.)

3. 3.

   All cells in the shell are occupied. ($N^{\ast }(\overline{X_c}\setminus ℒ)\setminus ℒ\subset X_c$.)

4. 4.

   The depth (in $\overline{X_c}$) of every empty cell is congruent to $k$ (mod 4) for a fixed $k\in \{0,1,2,3\}$.

The modules that are in $N^{\ast }(\mathrm{\ell })$, for a leaf $\mathrm{\ell }\in ℒ$, and not in the shell or core of $X_c$ are called the tail modules of $\mathrm{\ell }$. By definition, a module in $X_c$ is either in the shell, in the core, or is a tail module. Shell modules protect the connectivity of $X_c$, allowing us to place empty positions in the core wherever necessary to expand the exoskeleton constant time.

We show that $S_h$ can be reconfigured into an exoskeleton $X_h$ in $𝒪(P)$ transformations, thereby inductively establishing Lemma 9. To this end, we first prove Lemma 7, demonstrating how small skeletons (lighter than 9) are turned into exoskeletons. In doing so, we obtain Corollary 8, which settles the base case of our induction. Lemma 7 will also be pivotal in the inductive step. All that this lemma does is take a subskeleton of weight $\le 9$ and transform it into a $3\times 3$ square, a minimal instance of an exoskeleton $(|X_c|=2)$.

At first glance, the lemma might seem overly complicated, since without any obstacle, modules can freely move along the perimeter of $S$ (see Figure 8(a)). However, nonlocal pieces of the skeleton (connected subsets $S_1$ and $S_2$ of $S$ are local if $S\cap N^{\ast }(S_1\cup S_2)$ is connected) previously converted to exoskeletons can interfere when processing later subskeletons. Figures 8(b) and 8(c) show a configuration before and after two nonlocal pieces of the skeleton were converted into exoskeletons. Modules in the working subskeleton $S_c$ might be part of the shell of another exoskeleton, making their movement dangerous (potentially disconnecting the nonlocal exoskeletons). We try to leave such modules in their place, changing their membership from $S_c^{\ast }$ to the shell of the exoskeleton.

By applying Lemma 7 a constant number of times in appropriate subskeletons, we eventually obtain a solid $3\times 3$ square from which we can construct an exoskeleton.

Corollary 8 provides the base case of our induction for Lemma 9. We now establish some routines for the inductive step. We assume there is a module $d\in S_h$ so that for every child $c$ of $d$, $S_c^{\ast }$ was reconfigured to an exoskeleton $X_c$ satisfying Property 4 with $k=0$. If $N^{\ast }[d]$ is full, we can finish by making $d$ the root of the exoskeleton, effectively merging the children exoskeletons. Note that this will necessarily happen if $d$ had degree 4 and is not part of a 4-cycle. Thus, assume that there is an empty position $e\in N^{\ast }[d]$. We apply a routine Inchworm-Push that fills $e$ with local moves, using a module initially in the core of the exoskeleton $X_c$ (making that cell empty). The routine Inchworm-Pull then moves core modules higher (in tree metric) pushing empty positions deeper until they “exit” the exoskeleton at leaves. Again, ignoring nonlocal interactions, these operations are straightforward. However, in the general case, these interactions mandate extra care.

• $\mathrm{■}$

  Inchworm-Push: Let $c$ be a child of $d$, and $p$ be the parent of $d$. Require that $N^{\ast }[c]$ is full. We branch into cases. (i) If $c$, $d$, and $p$ are collinear, there is a path $\pi$ in $N^{\ast }(d)$ from $c$ to $e$ going through only occupied cells, see Figure 9(a); (ii) If $c$, $d$ and $p$ form a bend, there is a path $\pi$ in $N^{\ast }[d]$ from $c$ to $e$ going through $d$ and at most one nonskeleton module, see Figures 9(b) and 9(c); (iii) In analogous cases to (i–ii), if a node in $\{c,d,p\}$ is a 4-cycle, there is a path $\pi$ in $N^{\ast }(d)$ from a module in $c$ to $e$ going through one module in the shell of $X_d$, depicted in Figure 9(d). For all cases, move the modules along $\pi$ making $e$ occupied and $c$ empty. This requires at most two transformations since there is at most one collision along $\pi$ and we can decompose $\pi$ into two paths with no collisions.

• $\mathrm{■}$

  Inchworm-Pull: The operation consists of four stages, each involving at most two transformations. For every empty cell $p$ in the core, select one of its children $q$ arbitrarily, and let $x(q)$ be its $x$-coordinate. Move the module from $q$ to $p$ in stage $j\in \{1,2,3,4\}$ if $x(q)\equiv j(mod4)$. Figure 10(a) gives two examples, in one of which $p$ is a 4-cycle (that takes two transformations). If $q$ is a leaf, if there is a tail module of $q$ that is originally in $S_c^{\ast }$ and not in another exoskeleton, move such a module to $q$, visualized in Figures 10(b) and 10(c). If there are no more tail modules we can update $\overline{X_c}$ by deleting $q$ which causes the tail module that just moved to become a shell module, see Figure 10(b), or causes two shell modules to become tail modules as in Figure 10(c).

The reason we stagger the moves into four stages in Inchworm-Pull is to guarantee that the configuration contains enough static modules around a move. Otherwise, performing all moves in a single transformation might disconnect the configuration, as shown in Figure 10(d). In the full version [5], we argue that Inchworm-Push and Inchworm-Pull preserve connectivity and require only $𝒪(1)$ transformations. To establish local connectivity of the static modules in the neighborhood of each move, we rely on Properties 3–4.

If a subskeleton of $S_d$ does not contain an exoskeleton, we can apply Corollary 8. If, after that, $S_d$ is not the core of an exoskeleton $X_d$, we apply induction. Let $Q$ be the set containing the children of $d$. For every child $c\in Q$ with $|S_c^{\ast }|\ge 9$ we can get an exoskeleton $X_c$ in $𝒪(|S_c^{\ast }|)$ transformations by inductive hypothesis. For every child $c\in Q$ with , we apply Lemma 7 that either results in an exoskeleton $X_c$, or results in deleting $c$ from $S$ “compacting” all its modules in $N^{\ast }[c]\cap N^{\ast }[d]$. If after that $N^{\ast }[d]$ is not full, $N^{\ast }[d]$ contains at most three empty cells if $d$ is a degree-2 bend in $S$, at most two empty cells if $d$ is a “straight” degree-2 in $S$, or at most 1 empty cell if $d$ has degree 3. (Note that if $d$ has degree 4 and is not a 4-cycle, then $N^{\ast }[d]$ is full.) For each of these empty cells, we can fill them by applying Inchworm-Push followed by at most four applications of Inchworm-Pull to ensure that $N^{\ast }[c]$ is full for all children $c$ of $d$ while maintaining Property 4. This takes at most $𝒪(1)$ transformations. When $N^{\ast }[d]$ is full, the configuration contains an exoskeleton $X_d$ except for the “4-arity” of the empty positions (Property 4). That can be resolved by applying Inchworm-Pull to $X_c$ at most three times for each child $c$ of $d$. $◀$

By Lemma 6, we can choose an appropriately heavy node $d$ of $S$ to obtain:

We define a scaffold structure composed of meta-modules, each consisting of eight modules occupying the open vertex-neighborhood of a common center cell $v$, i.e., one in every cell of $N^{\ast }(v)$ as shown in Figure 12(a). A sweep line $\mathrm{\ell }\subset C$ is then a valid subconfiguration formed by the union of $h$ disjoint meta-modules $M_1,\mathrm{\dots },M_h$ with identical $x$-coordinates such that $\mathrm{\ell }$ spans the full height of the bounding box of $C\setminus \mathrm{\ell }$. Let $v_i$ now refer to the center cell of $M_i$, such that exactly if , see Figures 12(b) and 12(c).

For each meta-module $M$ in a sweep line $\mathrm{\ell }\subseteq C$, we define as its east and west strips as the cells which share a $y$-coordinate with one of its modules and are located within the bounding box of the full configuration $C$. We denote these by $\text{e}(M)$ and $\text{w}(M)$, respectively, and refer to their union for $\mathrm{\ell }$, e.g., $\text{w}(\mathrm{\ell })$. We use these to define the following characteristics.

A sweep line $\mathrm{\ell }$ is clean exactly if every meta-module $M_i$ either has an empty center cell $v_i$, or its respective west strip is fully occupied, i.e, $\text{w}(M_i)\subseteq C$. See Figure 12(b) for an illustration. Analogously, we call $\mathrm{\ell }$ solid if all center cells of its meta-modules are occupied.

Furthermore, we say that is $\mathrm{\ell }$ a separator if for every meta-module $M_i$ in $\mathrm{\ell }$:

1. 1.

   The east strip $\text{e}(M_i)$ does not contain modules unless all cells in $\text{w}(M_i)$ are full.

2. 2.

   The modules in $\text{e}(M_i)$ are located in its $x$-minimal cells, thus forming a $3$ cell tall rectangle with at most two additional “loose” modules.

We start by transforming part of the exoskeleton from Phase (II) into meta-modules that form a sweep line at the eastern boundary of $B$.

This gives us a separator sweep line $\mathrm{\ell }$ that is not necessarily clean or solid, located at the east edge of the configuration’s bounding box $B$. Our goal is to move $\mathrm{\ell }$ towards the west edge of $B$ while maintaining its separator property, compacting all encountered modules into $3$-tall strips in the process. We define two procedures that suffice to reach this goal.

Intuitively, the Advance operation provides a schedule that translates a sweep line by one unit to the west, and the Clean operation replaces a given sweep line with a clean one. To efficiently parallelize these operations, we split the sweep line into leading and trailing meta-modules such that $M_i$ is trailing exactly if $i$ is odd, and leading otherwise. At any given time, either the leading or the trailing meta-modules are active, but never both.

By repeatedly alternating between the Advance and Clean operations, we create a configuration with a clean separator sweep line that has an empty west half-space, see Figure 13.

We first argue the Clean operation can be performed in constantly many transformations. Let $M_i$ be an active meta-module with an occupied center cell. On a high-level, we consider a rectangle induced by occupied cells in west direction within its strip. It is easy to see that we can fill an empty position immediately adjacent to this rectangle, while also cleaning the center cell of $M_i$ by at most two subsequent transformations. By doing this for leading and trailing meta-modules separately, we conclude the following lemma.

It remains to argue that the same is true of the Advance operation. For this, we consider the three positions immediately west of an active meta-module, and distinguish eight cases based on occupied and empty cells. For all of them, we define local transformation schedules that enable us to move a meta-module one step to the east. Thus, we obtain:

After no more than $𝒪(P)$ many iterations consisting of Clean+Advance, we obtain a state in which $\text{w}(\mathrm{\ell })\cap C=\mathrm{\varnothing }$. The separator property implies that the modules in $\text{e}(\mathrm{\ell })$ form $3$-wide, horizontal stacks. It remains to show that we can make this configuration $3$-scaled.

To simplify our arguments, assume that $n$ is a multiple of nine. In the general case, $n$ can exceed a multiple of nine by at most $8$ modules. We can place these at the south-west corner of the extended bounding box $B^{\prime }$ and locally ensure the existence of a connected backbone during each transformation.

On a high level, we achieve this by filling the center cells of all meta-modules and balancing the remaining modules between their east strips such that each contains a multiple of nine. Having constructed a $3$-scaled configuration, we can arbitrarily reconfigure due to Theorem 4 before applying Phases (I-III) in reverse to obtain our target configuration.