Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements

Programmable matter is made of many small, identical robotic modules that can change the properties of matter, such as its shape, color, or density, in a programmable way [19]. In this paper, we consider the reconfiguration dynamics of the geometric amoebot model [7, 8, 9] from a centralized perspective. In the distributed version of this model, a set of $n$ robots (called amoebots) is placed on a triangular grid. Each amoebot can communicate with its neighboring amoebots and move by expanding into an empty adjacent node and then contracting into it. Since movement and communication happen locally from node to node, many problems in this model have a natural lower bound of $\mathrm{\Omega }(D)$ rounds, where $D$ is the diameter of the structure.

To overcome this limitation, previous work introduced the joint movement extension [15]. This extension allows multiple amoebots to move together in a coordinated way, e.g., an amoebot can push or pull other amoebots while expanding or contracting, which enables large parts of the structure to move in parallel. This raises an important question: Can we reconfigure an amoebot structure much faster using joint movements? By “faster” we mean running in sublinear parallel time (measured in discrete rounds), or, if possible, even in polylogarithmic or constant time. In this paper, we are interested in whether this is in principle feasible, thus we naturally focus on the centralized reconfiguration dynamics of the model.

Actuation operations that can globally affect the structure are sometimes called linear-strength operations, representing the property that they have sufficient strength to displace up to a linear-sized set. Although such operations may be a strict assumption to make in some systems, they have been incorporated in a variety of theoretical models [2, 3, 4, 5, 13, 20] and are reasonable in several real-world contexts like micro- and nano-robotic systems in low-viscosity environments, DNA nanotechnology, and programmable matter where a single local operation can directly cause reconfiguration of the entire system. They also form a simple theoretical abstraction for dynamics that, in practice, could be implemented by joint movements, with multiple robots jointly bearing the load of a linear-strength operation. We use the terms move and movement to refer to actuation operations throughout the paper.

Aloupis et al. [4, 5] studied a model of a modular robot system known as crystalline robots [18]. The 2D version of the crystalline model represents modules as squares on a 2D grid, forming a connected shape of modules attached to adjacent modules. Each individual module can expand and contract, by extending one of its faces one unit out and retracting it back at some later point. Due to modules being attached to each other, up to linear-size components can move due to a module’s expansion or contraction. In [5], they gave a universal centralized reconfiguration algorithm for the crystalline model that, for any pair of connected shapes $S_I,S_F$ of the same number of modules $n$, can transform $S_I$ into $S_F$ in $O(\log n)$ rounds. Note that in the crystalline model reconfiguration of some classes of shapes is impossible without metamodules (or other assumptions), and these algorithms essentially rely on the use of metamodules.

Recent work has showed that joint movements in the geometric amoebot model can also be very powerful when additional assumptions such as metamodules are used [15]. However, it is still unclear how powerful the model is on its own, without relying on extra assumptions. In this paper, we study the centralized reconfiguration problem in the geometric amoebot model with joint movements, without relying on such additional assumptions, thus focusing on the limits of the model dynamics themselves.

We consider centralized algorithms, where a global scheduler knows the full structure and decides the movements of all amoebots in each round. This allows us to focus on the main question: How fast can reconfiguration be in principle? Given two classes of amoebot structures, the goal is to design sequences of movements that reconfigure every structure from one class into some structure of the other class. An algorithm in this context is a formal description of these sequences of movements for all structures in the source class.

Our main result is the first within-the-model universal sublinear-time reconfiguration algorithm. We show that any connected amoebot structure can be reconfigured into a line segment in $O(\sqrt{n}\log n)$ rounds. Since any two connected structures with the same number of amoebots can both be reconfigured into a line segment, and every reconfiguration is reversible, this immediately implies that we can reconfigure any structure into any other structure within the same asymptotic bound. Therefore, we obtain universal reconfiguration in $O(\sqrt{n}\log n)$ rounds. This answers an open question on whether large-scale reconfiguration can be achieved in sublinear time without additional assumptions [15]. We also present an algorithm that reconfigures spiral structures into a line segment in constant time. This result shows that non-trivial subclasses of paths can be reconfigured extremely fast within the model. We hope that this can serve as a foundational step toward polylogarithmic or even constant-time universal reconfiguration, which is left as a central open question.

Overall, our results show that joint movements can greatly increase the reconfiguration efficiency of programmable matter structures, i.e., how quickly a structure can be reconfigured into another. While the original amoebot model is limited by diameter-based lower bounds, as we show, coordinated parallel motion enables significantly faster global reconfiguration.

In this section, we formally present the model and the problem statement. In Section 2.1, we present the geometric amoebot model with joint movements. In Section 2.2, we define the reconfiguration problem and the classes of amoebot structures considered in this paper.

In this section, we present basic movement primitives: the tunneling, shearing, parallelogram, triangle, and trapezoid primitive. These are core components in our reconfiguration algorithms. Due to space constraints, we omit the description of the implementation of these primitives and refer to the full version.

In the tunneling primitive, originally defined in [10], we move a chain of amoebots along a path by constantly performing handovers.¹¹1In previous work, the primitive is defined for spanning forests and is therefore called the spanning forest primitive. Since we only need the simpler case of a path, we refer to [7, 10] for the general case. We will use this primitive to “tunnel” an amoebot from one end to the other end without changing the structure of the remaining chain. In general, it may take up to $O(n)$ rounds to tunnel the amoebot through the chain. We call a chain that alternates between contracted and expanded amoebots alternating. On alternating chains, the primitive only requires $3$ rounds (see Figure 4). Note that the primitive actually moves all amoebots along the path without changing the order. However, since the amoebots are identical, the outcome is equivalent to a real tunneling. By construction, we obtain the following lemma.

We perform all remaining primitives on substructures of the amoebot structure. Other parts of the amoebot structure may be connected to that substructure at specific amoebots which we call connection points. Each primitive has two of these connection points. As the parts are not necessarily connected without the substructure, we must keep it connected at all times. With the exception of the shearing primitive, we maintain the relative position between those connection points.

In the shearing primitive, we shear a line segment of amoebots to another axis.²²2This primitive is similar to the realignment primitive of [15]. In fact, both primitives use the same intermediate structure. This allows us to switch between all structures of both primitives. We emphasize that this is not a rotation of the line segment since the attached parts of the amoebot structure are not rotated with the line segment. The endpoints of the line serve as the connection points.

Consider a parallelogram where only the two sides incident to an obtuse corner are occupied by amoebots. The amoebots at the acute corners serve as the connection points. The goal of the parallelogram primitive is to move the amoebots to the other two sides without leaving the parallelogram and without changing the relative positions of the connection points at any time. Note that these sides require the same number of amoebots as the initially occupied sides.

Consider an equilateral triangle where only two sides (w.l.o.g., the legs) are occupied by amoebots. The amoebots at the corners incident to the unoccupied side (i.e., the base) serve as the connection points. The goal of the triangle primitive is to occupy the base and one of the legs without leaving the triangle and without changing the relative positions of the connection points at any time. Note that any two sides of the triangle require the same number of amoebots since the triangle is equilateral.

Finally, consider a trapezoid where the shorter base and the legs are occupied by amoebots. The amoebots at the acute corners serve as the connection points. Let a node on the longer base be given. We will call it the starting point. The goal of the trapezoid primitive is to occupy the longer base and a path between the bases starting from the starting point, which may consist of up to $2$ segments, without leaving the trapezoid and without changing the relative positions of the connection points at any time. Note that the shorter base and both legs require the same number of amoebots as the longer base and one leg. Furthermore, the path between the legs requires the same number of amoebots as one leg. Hence, we have the exact number of amoebots for this reconfiguration.

Both our universal reconfiguration algorithm and our constant-time Spiral2Line algorithm make use of monotone structures as intermediate structures. In the following, we present our Monotone2LineSegment algorithm. W.l.o.g., we assume that the amoebot structure is $y$-monotone. By definition, each column is a $y$-segment. We first remove all bonds between adjacent columns except for one arbitrary horizontal bond. If there is no such bond, we shift the right column up by one position in a preprocessing phase (see Figure 5).

Let $(v_1,\mathrm{\dots },v_m)$ denote the amoebots of the column from bottom to top. Let $v_{\mathrm{\ell }}$ ($v_r$) be the amoebot connected to the left (right) column if it exists and $v_{\mathrm{\ell }}=v_1$ ($v_r=v_m$) otherwise. Each column applies the following rules until $m=1$ (see Figure 6).

1. 1.

   If , we shear the subsegment $(v_{\mathrm{\ell }},\mathrm{\dots },v_r)$ to align it to the $x$-axis (see Figure 6). We obtain $r-\mathrm{\ell }+1$ new columns. The first column consists of $(v_1,\mathrm{\dots },v_{\mathrm{\ell }})$. For all $i\in \{2,\mathrm{\dots },r-\mathrm{\ell }\}$, the $i$-th column consists of $v_{\mathrm{\ell }-1+i}$. The last column consists of $(v_r,\mathrm{\dots },v_m)$. For each of these columns, $\mathrm{\ell }=r$ holds. Note that if $\mathrm{\ell }=1\wedge r=m$, all resulting columns will consist of a single amoebot, respectively.

2. 2.

   If $\mathrm{\ell }>r$, we shear the subsegment $(v_r,\mathrm{\dots },v_{\mathrm{\ell }})$ twice to first align it to the $y$-axis and then to the $x$-axis (see Figure 6). We obtain $\mathrm{\ell }-r+1$ new columns. The first column consists of $(v_{\mathrm{\ell }},\mathrm{\dots },v_m)$. For all $i\in \{2,\mathrm{\dots },\mathrm{\ell }-r\}$, the $i$-th column consists of $v_{\mathrm{\ell }+1-i}$. The last column consists of $(v_1,\mathrm{\dots },v_r)$. For each of these columns, $\mathrm{\ell }=r$ holds. Note that if $\mathrm{\ell }=m\wedge r=1$, all resulting columns will consist of a single amoebot, respectively.

3. 3.

   If $\mathrm{\ell }=r$, we apply the following subrules.

   1. (a)

      If , we split the column into two columns as follows (see Figure 6). First, $v_{\mathrm{\ell }}$ expands horizontally. Second, $v_{\mathrm{\ell }}$ and $v_{\mathrm{\ell }+1}$ perform a handover. Finally, $v_{\mathrm{\ell }+1}$ contracts again. The left column consists of $(v_1,\mathrm{\dots },v_{\mathrm{\ell }})$. The right column consists of $(v_{\mathrm{\ell }+1},\mathrm{\dots },v_m)$.

   2. (b)

      If $\mathrm{\ell }=1$ and $m$ is odd, we split the column into two columns analogously to Rule 3a (see Figure 6). The left column consists of $v_1$. The right column consists of $(v_2,\mathrm{\dots },v_m)$.

   3. (c)

      If $\mathrm{\ell }=m$ and $m$ is odd, we split the column into two columns analogously to Rules 3a and 3b (see Figure 6). The left column consists of $v_m$. The right column consists of $(v_2,\mathrm{\dots },v_{m-1})$.

   4. (d)

      If $\mathrm{\ell }=1$ and $m$ is even, we split the subsegment $(v_{\mathrm{\ell }},\mathrm{\dots },v_m)$ into two columns with $m/2$ amoebots, respectively, as follows (see Figure 6). For each $i\in \{1,3,\mathrm{\dots },m-1\}$, $v_i$, we perform the following procedure in parallel. In the first round, each $v_i$ expands horizontally. In the second round, each $v_i$ performs a handover with $v_{i+1}$. In the third round, each $v_{i+1}$ contracts. We obtain two columns with $m/2$ amoebots. The left column consists of $(v_1,v_3,\mathrm{\dots },v_{m-1})$. The right column consists of $(v_2,v_4,\mathrm{\dots },v_m)$.

      For subsequent rule applications, we connect all amoebots within the same column with bonds and remove all bonds between those columns except for the topmost horizontal bond. Note that this does not require an additional round.

   5. (e)

      If $\mathrm{\ell }=m$ and $m$ is even, we split the subsegment $(v_{\mathrm{\ell }},\mathrm{\dots },v_m)$ into two columns with $m/2$ amoebots, respectively, analogously to Rules 3d (see Figure 6). The left column consists of $(v_2,v_4,\mathrm{\dots },v_m)$. The right column consists of $(v_1,v_3,\mathrm{\dots },v_{m-1})$.

      For subsequent rule applications, we connect all amoebots within the same column with bonds and remove all bonds between those columns except for the bottommost horizontal bond. Note that this does not require an additional round.

We obtain the following theorem.

In the full version, we also show how the Monotone2LineSegment algorithm can be used to reconfigure a star-convex structure into a monotone structure.

In this section, we describe our universal reconfiguration algorithm that reconfigures an arbitrary structure into a line segment. It consists of $3$ subroutines. In the first subroutine, we apply an algorithm (called Arbitrary2Bounded) to reconfigure the structure into a bounded structure. In the second subroutine, we apply an algorithm (called Bounded2Monotone) to reconfigure the bounded structure into a monotone structure. Finally, in the third subroutine, we apply the Monotone2LineSegment algorithm to reconfigure the monotone structure into a line segment. The latter subroutine was presented in Section 4. In the following, we present the other two subroutines.

First, consider the reconfiguration into a bounded structure. W.l.o.g., we will bound the number of rows to $\sqrt{n}$. The idea is to iteratively merge rows with less than $\sqrt{n}$ amoebots with neighboring rows. Each iteration proceeds as follows. We first pair a maximum number of adjacent rows such that each pair has at least one row with less than $\sqrt{n}$ amoebots.

Then, we merge each pair of rows as follows. The merge consists of $3$ phases. In the first phase, each amoebot expands into the other row parallel to the $y$-axis if the node is unoccupied (see Figure 7). Observe that the amoebots that are not able to expand form pairs (see the blue amoebots in Figure 7).

In the second phase, we iteratively move one amoebot of each of these pairs to the next unoccupied position in the row. W.l.o.g., consider the rightmost pair of amoebots and all expanded amoebots to the next unoccupied position to the right (see Figure 8). The idea is to construct an alternating chain from the pair of amoebots to the next unoccupied position. For that, we contract every second amoebot to its bottom node, ensuring the rightmost amoebot remains expanded. This construction guarantees that we can maintain connectivity within the amoebot structure since the participating amoebots can keep at least one bond to each of the initially adjacent nodes (see the gray nodes in Figure 8). Now, we can apply the tunneling primitive to move all amoebots to the right (see Lemma 1). Finally, we expand all contracted amoebots again. We continue with the next iteration if there is another pair of amoebots. Otherwise, we continue to the next phase.

In the third phase, we contract all expanded amoebots again (see Figure 9). This concludes the merge. We obtain the following lemma.

In this section, we present two algorithms to reconfigure a spiral into a line. In Section 6.1, we describe a simple algorithm that preserves the order of the amoebots within the spiral. Preserving the order may be interesting when the amoebots store information. In Section 6.2, we show a faster algorithm that only requires constant time.

In this paper, we have shown how to reconfigure any structure into another in sublinear time. It is still open whether a polylogarithmic time universal reconfiguration algorithm is possible. One way to achieve this could be an algorithm that reconfigures a structure of Arbitrary into a structure of Bounded($\mathrm{polylog}n$), which would reduce the runtime of our universal reconfiguration algorithm to polylogarithmic time. Another way would be an algorithm that reconfigures a structure of Arbitrary into a structure of Rhombical for which we already know how to reconfigure it to any other structure of Rhombical in logarithmic time [5, 15]. We have also presented an algorithm that reconfigures a spiral into a line segment in constant time. It would be interesting to investigate which other classes of structures can be reconfigured into a line segment in constant time.

Furthermore, we left the design of distributed algorithms for future work. Recall that local communication between amoebots leads to a natural lower bound of $\mathrm{\Omega }(D)$, where $D$ is the diameter of the structure. Therefore, other ways of communication are required, e.g., the reconfigurable circuit extension [11] which enables fast global communication between amoebots. Previous work has shown that reconfigurable circuits enable polylogarithmic-time solutions to various stationary problems [6, 11, 16, 17]. Almalki et al. [1] were the first to leverage them for rapid, distributed transformations in the growth model. It is open whether they can also prove of use in the amoebot model with joint movements.