Reconﬁguration of 3D Crystalline Robots Using
O(log n) Parallel Moves ∗
Greg Aloupis†
S´ebastien Collette‡
Erik D. Demaine§
Stefan Langerman¶
Vera Sacrist´an∥
Stefanie Wuhrer∗∗
November 5, 2021
Abstract
We consider the theoretical model of Crystalline robots, which have been
introduced and prototyped by the robotics community. These robots con-
sist of independently manipulable unit-square atoms that can extend/contract
arms on each side and attach/detach from neighbors. These operations suf-
ﬁce to reconﬁgure between any two given (connected) shapes. The worst-
case number of sequential moves required to transform one connected con-
ﬁguration to another is known to be Θ(n). However, in principle, atoms
can all move simultaneously. We develop a parallel algorithm for reconﬁg-
uration that runs in only O(log n) parallel steps, although the total number
of operations increases slightly to Θ(n log n). The result is the ﬁrst (the-
oretically) almost-instantaneous universally reconﬁgurable robot built from
simple units.
∗This result, constrained to 2D, was presented by the authors at the 19th International Symposium
on Algorithms and Computation [3].
†Universit´e Libre de Bruxelles. aloupis.greg@gmail.com
‡Universit´e Libre de Bruxelles. Charg´e de Recherches du FRS-FNRS. secollet@ulb.ac.be
§Massachusetts Institute of Technology. edemaine@mit.edu Partially supported by NSF CA-
REER award CCF-0347776, DOE grant DE-FG02-04ER25647, and AFOSR grant FA9550-07-1-
0538.
¶Universit´e Libre de Bruxelles. Maˆıtre de Recherches du FRS-FNRS. slanger@ulb.ac.be
∥Universitat Polit`ecnica de Catalunya. vera.sacristan@upc.edu Partially supported by projects
MEC MTM2006-01267 and Gen. Cat. DGR 2009SGR1040.
∗∗Carleton University. stefanie.wuhrer@gmail.com
1
arXiv:0908.2440v1  [cs.CG]  17 Aug 2009
1
Introduction
In this paper, we consider homogeneous self-reconﬁguring modular robots com-
posed of unit-cube atoms arranged in a grid conﬁguration. Each atom is equipped
with mechanisms allowing it to extend each face out one unit and later retract it
back. Furthermore, the faces can attach/detach to faces of adjacent atoms. At all
times, the atoms should form a connected conﬁguration. When groups of atoms
perform the four basic atom operations (expand, contract, attach, detach) in a coor-
dinated way, the atoms move relative to one another, resulting in a reconﬁguration
of the robot. Fig. 1 shows an example of such a reconﬁguration. Each atom is
depicted as a square, with a T-shaped arm on each side.
Figure 1: Example of reconﬁguring Crystalline atoms: the top row of atoms is able
to shift to the left, using the bottom row of atoms as a ﬁxed base.
The robotics community has implemented this model in two prototype systems:
Crystalline atoms [4, 11] and Telecube atoms [12]. In the Crystalline model, the
default state for atoms is expanded, while in the Telecube model, the default state is
contracted. Thus Fig. 1 reconﬁgures a Crystalline robot, or an expanded Telecube
robot.
To ensure connectedness of the conﬁguration space, atoms must be arranged in
modules, which are groups of k×k×k atoms. Any value k ≥2 sufﬁces for univer-
sal reconﬁgurability [2, 13]. Here the collection of atoms composing a robot must
remain connected in the sense that its module graph (where vertices correspond to
modules and edges correspond to attached modules) is connected.
The complexity of a reconﬁguration algorithm can be measured by the num-
ber of parallel steps performed (“makespan”), as well as the total number of atom
operations (“work”). In a parallel step, many atoms may perform moves simul-
taneously. The number of parallel steps is typically the most signiﬁcant factor in
overall reconﬁguration time, because the mechanical actions (expansion, contrac-
tion, attachment, detachment) are the slowest part of the system.
Our main contribution in this paper is a reconﬁguration algorithm that, given a
source robot S and a target robot T, each composed of n atoms arranged in k×k×k
modules for some constant k, reconﬁgures S into T in O(log n) parallel steps and
a total of O(n log n) atom operations.
A central assumption in our algorithm is that one atom, by contracting or ex-
panding, can pull or push all n atoms (linear strength). Thus our algorithm cer-
tainly tests the structural limits of a modular robot, but on the other hand this as-
2
sumption enables us to achieve reconﬁguration times that are likely asymptotically
optimal.
The main idea of our parallel algorithm is to reconﬁgure the given robot into a
canonical form, by recursively dividing the plane into a hierarchy of cube-shaped
cells and employing a divide-and-conquer technique to merge adjacent cells. Each
merge creates a cell containing a simple structure using a constant number of
moves. This structure, which ﬁlls the perimeter of a cell as much as possible,
can be decomposed into a constant number of rectangular components. Because
the steps to merge cells of the same level can be executed in parallel, the total num-
ber of parallel steps used to reconﬁgure any conﬁguration to a simple structure is
O(log n). The entire reconﬁguration takes place in the smallest box with side 2h
that contains the initial conﬁguration, where h is an integer.
We choose to describe our algorithm in terms of the naturally expanded mod-
ules of Crystalline robots. Of course, this immediately implies reconﬁgurability in
the naturally contracted Telecube model, by adding one step at the beginning and
end in which all atoms expand and contract in parallel. We also expect that the
individual constructions in our algorithm can be modiﬁed to directly work in the
Telecube model as well.
In sections 3–5 we focus on 2D Crystalline atoms. In this case, our algorithm
effectively uses modules of 4×4 atoms, but for clarity and brevity assumes that
atoms initially appear in blocks of 32×32. Reducing the module size leads to more
complicated basic operations that we have designed for use on large rectangular
components. On the other hand, reducing the initial block size leads to a larger
number of possible shapes that we must consider during the merge of cells. We
have designed (though not rigorously analyzed) a range of algorithms for 2×2
modules with decreasing restrictions on block size. This is discussed in our con-
cluding remarks (section 7). However, the bulk of this paper focuses on the version
that is easiest to describe.
In section 6 we describe how to extend our algorithm from 2D to 3D. Although
the technique used is the same, there are a few subtle differences that we address,
while attempting to avoid repetition. The block size and/or module size increase
slightly, depending on the chosen extension approach.
2
Related Work
Robots designed with a unique purpose can be very efﬁcient but may lack versa-
tility in the sense that they may not efﬁciently perform tasks other than the ones
they were initially designed for. Furthermore, problems can occur when the robots
actuate in an environment different from that originally envisaged.
3
For this reason, research on self-reconﬁguring robots is active in the robots
community. These robots can self-reconﬁgure in order to adapt to unknown envi-
ronments and perform unknown tasks. Modular robots can self-organize to repair
or replace damaged structures, transport pieces of machinery or manipulate objects
in inaccessible locations. Their adaptability allows them to climb over obstacles,
maneuver into narrow passages, and change shape to adapt to their environment.
In addition, their modularity enables auto-repairing when one unit fails and, of
course, allows locomotion. Two of the main goals in this ﬁeld are to construct new
self-reconﬁguring systems and to design efﬁcient algorithms for their autonomous
reconﬁguration.
Several models have been proposed, most of which have been prototyped.
Crystalline robots are an example of a (cube) lattice model. Alternative models in-
clude hexagonal lattice robots [9], 3-dimensional rectangular grid robots [7], chain
robots such as Polybot [14], and mixed (chain and lattice) models as M-Tran [16].
For a survey on the large range of modular robot prototypes, as well as for an
outlook on the future goals and prospects of the ﬁeld, see [8, 15].
A O(n2)-time sequential algorithm for reconﬁguring general classes of lattice-
based robotic models was given in [6], and it was also shown that this number of
individual atom moves is sometimes required. The ﬁrst reconﬁguration algorithm
speciﬁcally proposed for Crystalline robots was the melt-grow algorithm [11]. It
reconﬁgures one shape to another by constructing a strip of modules as an interme-
diate step. This is done in O(n2) steps. The algorithm is not in-place; the additional
area used is O(n), in terms of the unit-volume of a module. The PAC-MAN algo-
rithm [5] and its variant [13] are in-place, have a more parallelized nature, but still
use O(n2) steps. In fact, for each of these algorithms there exist simple instances
that require Ω(n2) steps.
A linear-time parallel algorithm for reconﬁguring within the bounding box of
source and target is given in [2]. The total number of individual moves is also
linear. No restrictions are made concerning physical properties of the robots. For
example, O(n) strength is required, since modules can carry towers and push large
masses during certain operations.
However, it turns out that if the strength of each atom is restricted to O(1), i.e.
one atom can only pull or push a ﬁxed number of other atoms, any Crystalline robot
can still be reconﬁgured in-place, using O(n) parallel steps [1]. Unavoidably, the
total number of individual moves is O(n2). This is shown to be worst-case optimal.
When O(1) strength is required but velocities are allowed to grow arbitrarily
over time, reconﬁguration takes Θ(√n) steps [10]. Note that this is for 2D robots
and the third dimension is used as an intermediate.
In this paper, we do not restrict the strength or maximum velocity of each robot.
In this model, we can reconﬁgure any shape using O(log n) parallel steps.
4
3
Deﬁnitions
Since we will ﬁrst focus on 2D reconﬁgurations (in sections 4 and 5), our basic
deﬁnitions given here will be for 2D as well. In section 6 we will describe how
these deﬁnitions can be extended if necessary.
We will mainly deal with modules, not atoms, which can be viewed as lying on
their own square lattice somewhat coarser than the atom lattice. Refer to Fig. 2 for
examples of the following notions. In all ﬁgures, modules are depicted as squares
unless mentioned otherwise. A module is a node if it has exactly one neighbor (a
leaf node), more than two neighbors (a branching node), or exactly two neighbors
not collinear with the node (a bending node). A branch is a straight path of (non-
node) modules between two nodes (including the nodes themselves). A cell is a
square of module positions (aligned with the module lattice), some of which may
be occupied by modules. The boundary of a cell consists of all module positions
touching the cell’s border. For cells of sufﬁcient size the near-boundary consists
of all module positions adjacent to the cell’s boundary. If a branch lies entirely in
the boundary of a cell, we call it a side-branch. The conﬁguration within a cell
is a ring if the entire cell’s boundary is occupied by modules, and all remaining
modules within the cell are arranged at the bottom of the cell, ﬁlling row by row
from left to right. The conﬁguration within a cell is sparse if it contains only
side-branches. A backbone is a set of branches forming a path that connects two
opposite edges of a cell.
(a)
(b)
(c)
Figure 2: Deﬁnitions; modules are depicted by squares. (a) A ring. (b) A sparse
cell with ﬁve side-branches and shaded near-boundary. (c) A shaded backbone and
eight nodes.
4
Elementary Moves That Use O(1) Parallel Steps
Throughout this paper, whenever we describe a move, it is implied that we do not
disconnect the robot and that no collisions occur.
We ﬁrst describe three basic module moves (slide, compress, k-tunnel) that are
used in [2]. We omit a detailed description of how to implement these moves in
terms of individual atom operations. A compression pushes one module m1 into
5
the space of an adjacent module m2. The atoms of m1 literally ﬁll the spaces
between those of m2 (see Fig 3). Thus we see that two modules can occupy the
same position in the module lattice. Any part of the robot attached to m1 will be
displaced by one unit along the same direction. A decompression is the inverse of
a compression.
(a)
(b)
Figure 3: Result of compressing two adjacent 4×4 modules into one lattice cell.
A slide moves a module to an adjacent position, using two substrate modules.
See Fig. 4a. The k-tunnel move compresses a leaf module into the robot, and
decompresses another module out into a leaf position. See Fig. 4b. An entire path
of modules between the two leaves is involved in this move. Within each branch in
this path, modules shift in the direction of the compression, and essentially transfer
the compression to the next bend. Any modules attached to the branches will also
shift. This issue is addressed later on. The parameter k denotes the number of
branches (or bends) in the path between the two leaf modules. The move takes
O(k) parallel steps, but in our uses k will always be a small constant.
(a)
(b)
Figure 4: (a) Slide move; (b) Tunnel move.
We now proceed to describe new basic moves that form the cornerstones of our
reconﬁguration algorithm.
4.1
Staircase Move
The staircase move transforms a rectangle of k1×k2 modules to one of dimensions
k2 × k1, both sharing the same lower-left corner C. Connectivity to the rest of the
robot is maintained through the module at C, and thus that module cannot move.
Without loss of generality, we can assume that k1 ≥k2; otherwise, we invert the
6
sequence of operations described.
First, we move every row of modules to the right using a slide move with
respect to the row immediately below, as in Fig. 5(b). Second, we move every
column that does not touch the top or bottom border of the bounding box down
using a slide move, as in Fig. 5(c). Finally, we move every row to the left using a
slide move, as in Fig. 5(d). Note that the sliding motions of each step are executed
in parallel. Also, each operation can be done at the atom-level, as was shown in
Fig. 1. Thus the move works even if k2 = 1.
k1
k2
k2
k1 + k22
k2
k1
(a)
(b)
(c)
(d)
Figure 5: Staircase move in three parallel steps. The shaded module maintains
connectivity to the rest of the robot.
If we require that the transformation between rectangles takes place within the
bounding box of the source and target conﬁgurations, we can modify the above
procedure as follows. Ideally, every row of modules would slide to the right as
illustrated in Fig. 5(b). We partially perform this step but do not slide the top rows
that would emerge from the k1 × k1 square originating at C. Thus we get a shape
partially resembling Fig. 5(b), but with a dimension k2 square appended on top of
it. Now we slide the diagonal structure downwards, including the lower-right half
of the extra square (i.e., slide down everything below the diagonal starting at C).
At this point we have a shape similar to Fig. 5(c) except that the empty region in the
lower right corner of the ﬁgure is actually occupied, and there is a “lower-left half”
of a dimension k2 square sticking out above that corner. Next, with a parallel slide
to the left, we ﬁll the empty region on the left but create a symmetric empty region
at the far right. This leaves us with a rectangle exactly as we want it, except that at
the far right we have a shape that is the lower left portion of a square (of height 2
times that of the rectangle). We want to transport the top 1/4 of that shapes’ mass
(i.e., the part that is above our target rectangle) into the the gap in the lower-right.
That’s easily done with a few more slides.
4.2
Elevator Move
The elevator move transports a rectangle of modules by k units between two verti-
cal strips, each at least two atoms wide. Figure 6(a) shows the initial conﬁguration
7
in which a rectangle is to be transported vertically downward. First we detach the
top half T of the rectangle from the bottom half B. Furthermore, B detaches from
the vertical strip on the right. Let R be the rightmost vertical column of k atoms
along the left strip, together with the atoms to the left of B. We detach R to its left,
except at the very bottom, and detach R above, thus creating a corner with B. Then
we contract R vertically, thereby pulling B downward half way. This is shown in
Figure 6(b), in which, however, we have let R be a vertical column of modules
instead of atoms, due to the large width of the shape. Thus far, T has maintained
the connectivity of the robot. Afterward, B attaches to the right vertical strip and
detaches from R, which is now free to expand and re-attach to the top, as in Fig-
ure 6(c). Now R detaches from the bottom and contracts upwards. It re-connects
to B at the bottom, as in Figure 6(d). In the last step, shown in Figure 6(e), B
detaches from the right side, and R expands, thereby moving B all the way to the
bottom. At this point, B has reached its target position. It now assumes the role of
maintaining connectivity, and the process can be repeated for T.
(a)
(b)
(c)
(d)
(e)
Figure 6: Elevator move in O(1) parallel steps.
4.3
Corner Pop
Consider a rectangle R of k1 × k2 module units, where without loss of generality
k1 ≤k2. Let R be empty except for a strip V of modules on its left border and a
strip H along the bottom. The strips form a corner, as shown in Figure 7(a).
The corner pop moves the modules in R to the upper and right borders of R.
During this corner pop, the modules at the top-left and bottom-right corners of R
do not move. It is assumed that only these positions connect to modules outside R.
Thus, this operation preserves the connectivity of the robot.
Assume that we have 4×4 modules, so that we can use our easy staircase op-
eration. We ﬁrst create two staircases of height k1/2 at the two ends of H, as in
Figure 7(b). This shifts the middle of H upward. Next, we use the lower half of V
to create a staircase of width k1/2. Simultaneously, the rightmost staircase of H
also moves so that it ends up on the right border of B, as in Figure 7(c). We move
the two remaining staircases upward, as in Figure 7(d). Finally, we clean up the
two extra atoms that protrude using a 2-tunnel move and a 3-tunnel.
8
(a)
(b)
(c)
(d)
(e)
Figure 7: Popping a corner in O(1) parallel steps. The shaded modules maintain
connectivity to the rest of the robot.
4.4
Parallel Tunnel Move
The parallel tunnel move takes as input a horizontal row H of modules together
with, on the row immediately above, several smaller horizontal components that
have no other connections. The top components are absorbed into H, after which
H extends horizontally. Alternatively, the absorbed mass can be pushed out any-
where else on top of H, provided the target space is free. This move allows us to
merge an arbitrary number of strips in the top row in O(1) time.
The idea is to take all odd lattice positions along H and perform 1-tunnel
moves, i.e., absorb modules from above and compress them under even positions.
Then decompressing them all in parallel just expands H horizontally. Any mod-
ules remaining on top will shift over during the expansion, since they are attached
to H. A gap will remain to the right of each such module, so we can repeat one
more time to complete the move.
Figure 8 illustrates half of the absorption of one 4×4 module into H. Note
that groups of 4 atoms move separately (they can be considered to be temporary
smaller modules).
5
Reconﬁguration
In this section we show how to reconﬁgure a given robot to a canonical form with
O(log n) parallel steps. Here we assume that the initial and ﬁnal conﬁgurations of
the robot consist of blocks of 32×32 atoms. However we will split blocks to use
modules of 4×4 atoms in the intermediate conﬁgurations. Recall that the boundary
has a width of four atoms.
Our divide-and-conquer algorithm proceeds as follows. Let the initial robot
be placed on a grid of unit blocks (of 32×32 atoms). On this grid we construct
a minimal square cell of side length 2h that contains the initial robot (length is
measured in block units). We recursively divide the cell into four subcells of length
2h−1. As a base case, we take subcells of 2×2 blocks (i.e., containing 16×16
module lattice positions).
9
(a)
(b)
(c)
(d)
Figure 8: Parallel tunnel move. Three 4 × 4 modules are involved.
In parallel, we reconﬁgure each subcell within the same recursive depth, so
that the resulting shape is easy to handle. Thus, by merging subcells, in O(log n)
iterations we will have created a simple shape in our original square. Consider a
cell M. We will use the inductive hypothesis that after merging its subcells, M
will become a ring if there are enough modules, or sparse otherwise. Furthermore,
if two points on the boundary of M were initially connected, the new conﬁguration
will ensure connectivity via the shortest path through its boundary.
In the base case of our induction, M has length 2. Thus we have to merge four
subcells, each of which is empty or full. We will obtain a ring if there is at least
one full subcell. One such subcell contains 64 modules, which sufﬁce to cover the
boundary of M. Reconﬁguration can be done by tunneling each interior module
iteratively (or by the lemmas that will follow). Thus our hypothesis is preserved.
Lemma 1. Consider a cell M. If any subcell of M contained a backbone in the
original conﬁguration, then there are enough modules to create a ring in M. There
are also enough modules if a path originally connected two subcell sides that be-
long to the boundary of M but are not adjacent.
Proof. Consider the eight exterior sides of subcells of M as shown in Figure 9(a).
Let each of the sides Mi have length c (i.e., c modules ﬁll the side of a subcell).
The total number of modules in the boundary of M is 8c −4. A subcell backbone
contains at least 8c modules and therefore sufﬁces to cover the boundary.
10
Without loss of generality, suppose that a path begins on M1 and ends at any
side other than M1, M8, M2. Then we have enough modules to make a ring in M,
by similar counting as above. In fact to avoid having enough modules, such a path
would have to remain within the lower two subcells.
Lemma 2. Let S1 and S2 be adjacent sparse subcells at the top of cell M. In the
original robot, there can be no path from the top border of M to the other subcells
(see Figure 9(b)).
Proof. A path from the top to the middle of M in the initial robot would contain
enough modules to make both S1 and S2 rings. By the pigeon-hole principle, one
of the two subcells cannot be sparse.
M1
M2
M3
M4
M5
M6
M7
M8
M
S1
S2
(a)
(b)
Figure 9: Connectivity issues, in Lemmas 1 and 2.
Lemma 3. All side-branches along the common border of two cells that are rings
or sparse can be merged into at most two pieces per side, with O(1) moves. Fur-
thermore each side-branch touches one end of the border.
Proof. If one cell is a ring then the other side can use it as a platform for a parallel
tunnel move that will merge its side-branches into one piece. Otherwise, for each
connected component of side-branches (of which there are at most two; one per
corner) do the following.
Denote the two sides of the border by A and B. Absorb as much as possible
from A to B by sliding modules from A across the border into vacant module lattice
positions. Thus the component has one side-branch in B. Shift (parallel tunnel)
the remainder of A towards the corner that the connected component attaches to,
using B as a platform. Thus A becomes one side-branch. Now (either by a pop or
by parallel-tunnel) bring back material from B to A to restore the original numbers
in each cell. Thus each connected component consists of at most one side-branch
from A and one from B.
11
Lemma 4. Suppose B is a boundary side of a cell that has been processed accord-
ing to Lemma 3. Let A be a branch that is in the near-boundary adjacent to B,
and has no connectivity purpose. We can absorb A into B, or B can be ﬁlled, with
O(1) moves.
Proof. By Lemma 3, B contains at most two side-branches, each attached to a
corner. If no modules in B are adjacent to A, we can use a 1-tunnel to move one
node (endpoint) of A into the position in B that is adjacent to the other node of A.
Then the rest of A can slide into B. Otherwise, if A is adjacent to a side-branch in
B, as in Figure 10(a), we do the following. Absorb parts of A into empty positions
of B, as in Figure 10(b). Thus we create a side-branch B1 which can be used as a
platform to be extended by performing a parallel tunnel move on what remains of
A. If the extension causes B1 to reach a corner or join to another side-branch in B,
then B is full; see Figure 10(c).
For sparse cells, by repeatedly applying Lemma 4 and staircaising the remain-
der of A to the near-boundary side adjacent to B, we obtain the following:
Corollary 5. If a branch A is positioned in the near-boundary of a sparse cell,
either A can be fully absorbed into the boundary, or the cell will become a ring.
(a)
(b)
(c)
Figure 10: Absorbing a near-boundary branch into the boundary of a cell.
Let a merged cell contain four subcells that satisfy our induction hypothesis.
That is, they are either rings or sparse, and connectivity is ensured via shortest paths
along their boundaries. A merged cell becomes well-merged if it is reconﬁgured to
satisfy the induction hypothesis.
Lemma 6. Let M be a merged cell containing three or four subcell rings. Then
M can become a ring using O(1) moves. Thus M becomes well-merged.
Proof. First consider the case where M consists of four rings. The outer ring
structure is already in place. Use elevator moves to transfer any internal material
from the top two subcells as far down as possible. The resulting interior structure
on either side of the internal vertical subcell borders is a monotone terrain with
at most two height changes. Furthermore each height change is by one unit. The
internal borders can be staircased and incorporated into these terrains, which can
12
then be merged easily with parallel tunneling and sliding. There still may be a large
height difference between the left and right sides. In other words, one side has an
extra rectangle of modules. To even things out, we slide half of the rectangle over
and then use two staircase moves.
Second consider the case where M consists of three rings and a sparse subcell
S. We can quickly modify the “direction” of the interior structure in any ring with
a couple of staircase moves, so without loss of generality let S be at the top-left of
M. If the interior sides of S contain side-branches, we can staircase them to the
near-boundary and then apply Corollary 5, to redistribute them to exterior sides or
obtain a fourth ring. In the former case, we are free to staircase the full sides of
subcells adjacent to S in order to ﬁll the boundary of M (again using Corollary 5).
Further redistribution is nearly identical to the four ring case.
Lemma 7. If exactly two subcells of a merged cell M are rings, then M can
become well-merged using O(1) moves.
Proof. If the two sparse subcells are adjacent, then there is no critical connectivity
maintained through their common border, by Lemma 2.
Apply Corollary 5 to move side-branches in the sparse subcells to the boundary
of M. There is only one module that possibly cannot be moved, in the case of two
rings that exist in a diagonal conﬁguration and must be connected. If a new ring
is created, we apply Lemma 6. Now the only branches along interior borders of
subcells belong to the two rings, with the possible exception of one module at the
middle of M. We can use corner pops and/or staircase moves and Corollary 5 to
move the interior ring sides to the boundary of M while maintaining connectivity.
This happens regardless of the relative position of the rings or the presence of the
extra module.
What remains is to maintain our shortest path requirement, if we still do not
have a ring in M. In this case, by Lemma 1 we know that there was no initial
backbone in M. Thus each connected component of robot within M “covers” at
most one corner (in other words there is at least one module gap per side).
Note that the modules in the two subrings alone nearly sufﬁce to create a ring
in M. Four modules are missing. We can remove a strip of width 2 from positions
where we wish to have a gap in the boundary of M, and use parallel-tunneling to
position this material in the current gaps. Essentially we create a temporary ring of
width 2. Then the remaining material can be moved.
Lemma 8. If exactly one subcell S of a merged cell M is a ring, then M can
become well-merged using O(1) moves.
Proof. Without loss of generality let S be at the bottom-left of M. By Lemma 2,
in the original robot there was no path from the top border of M leading to either
13
of the bottom subcells. The same holds for the right border of M and the two left
subcells. Therefore the two interior borders between the three sparse subcells do
not preserve any connectivity. We may use Corollary 5 to move branches from
those interior borders to the boundary of M. Finally we can do the same for the
interior sides of S.
We may have to redistribute excess internal material from within S. If M
has become a ring, this is easy and has been discussed previously. Otherwise, we
can apply Corollary 5 to each full row of the internal ring structure. This can be
required at most eight times before a ring is created.
Our shortest path connectivity requirement is preserved directly, by the fact
that the internal borders where not necessary for connectivity.
Lemma 9. If no subcell of a merged cell M is a ring, then M can become well-
merged using O(1) moves.
Proof. By Lemma 2, we know that in the original robot conﬁguration no path ex-
isted from a side of M to either of the two subcells furthest from it. Therefore
all disjoint subgraphs maintained connectivity between at most two adjacent ex-
ternal sides of subcells. More speciﬁcally, the ﬁrst type of allowed path connects
points that are separated by a corner of M but are also inside the same subcell.
By induction we assume that these points are already connected along the external
boundary of their subcell. The second type connects points that are on the same
border side of M (possibly adjacent subcells). Again by induction we know that
they are already connected along the boundary of M. Therefore our shortest path
requirement is preserved.
All that remains is to remove excess material from inner borders of subcells.
This material consists of one or two branches per border, each of which is con-
nected to the boundary of M. If any such border B does not connect the boundary
of M to the mid-point of M (i.e., to a path on another interior border), then any
module along B can be moved to the boundary of M (with staircasing, and absorb-
ing via parallel tunnel). Along any inner border we can absorb modules from one
cell’s boundary to gaps in its adjacent one. Any remaining material can be sent to
the boundary of M.
So, without loss of generality, assume that we have at least one full inner bor-
der. In fact if there is one it can be removed, and if there are only two forming
a bend, they too can be eliminated. The only non-trivial case involves a straight
path through the middle of M, that may also have one or two straight branches (a
T-shape or a cross). Let the straight path be vertical. If we cannot just cut the path
in two and collapse, this means that the path is critical for connectivity. If the crit-
ical connection is between points on opposite sides of M, then we know that there
14
must be at least three more side lengths of thin blobs in M. Moreover, because we
have no subrings, that initial backbone must zig-zag through the current vertical
connection (avoiding to make a backbone in any subring). We might have to argue
here that parts of the initial backbone always remain connected. This would imply
that we can simply elevator the vertical connecting path over to the boundary.
Theorem 10. Any source robot S can be reconﬁgured into any target robot T with
O(n log n) atom operations in O(log n) parallel steps, if S and T are constructed
with blocks of 32×32 atoms.
Proof. Every cell retains the modules that it initially contained and does not inter-
fere with the conﬁguration of the robot outside the cell, until it is time to merge with
its neighbors. A temporary exception to this occurs during Lemma 3. Therefore
that step should be performed in a way so that no interference occurs (i.e., perform
only this operation during one time step). At every time step, we merge groups of
four cells, which by induction are either rings or sparse. By Lemmas 6–9, these
four cells merge into a ring or sparse cell. Thus we construct a ring or sparse cell
in O(log n) parallel time steps.
We show that the total number of operations is O(n log n). Each subcell con-
taining m atoms can involve O(m) parallel operations per time step. Because there
are O(1) time steps per level in the recursion, and all mi sum to n, the total number
of operations per recursion level is O(n).
Now consider the bounding box B of S. We construct the smallest square B2
of side length 2h that contains S and has the same lower-left corner as B. Our
recursive algorithm takes place within B2. Now consider the last merge of subcells
in our algorithm. The lower-left subcell L could not have contained S, because this
would imply that B2 = L. Therefore there must have been a path in S from the left
side of B2 leading to the two rightmost subcells (or from bottom to two topmost).
This implies that S will become a ring (not sparse).
Because a ring of speciﬁc side length has a unique shape as a function of the
number of modules it contains, the resulting ring in B2 serves as a canonical form
between S and T.
6
Generalization to Three Dimensions
We now discuss how to extend the 2D result to 3D. The main concepts are similar,
so we focus on the few technical differences.
In 3D, our reconﬁguration takes place in a cube of side length 2h. We recur-
sively divide space into cubes with side lengths divided by 2. The boundary of
the cell consists of all module positions that touch an edge of the cell. As in 2D,
15
a branch that lies entirely in the boundary of a cell is a side-branch. The near-
boundary of a cell consists of all module positions that are face-connected to the
boundary.
If we manage to ﬁll the boundary of a cell with modules, it is called a ring.
Excess modules ﬁll the cell from bottom to top, analogous to 2D. The entire bottom
horizontal square layer must be ﬁlled in order to progress higher. A 3D sparse cell
has modules only on edges (in fact this means that every side-branch can be made
to connect to a corner, by a temporary trading argument, just like in 2D, Lemma 3).
When we merge 8 subcells, we use the inductive assumption that they are empty,
sparse or rings.
6.1
Block size and shortest paths
In 2D, the block size was determined in Lemma 1, where the minimum length of a
subcell backbone was compared to the circumference of a cell. Recall that the ﬁrst
part of Lemma 1 states that if a subcell contains a backbone then a cell becomes a
ring. This is a result of the factor of 8 ratio between the cross-section of 2D blocks
and modules. In other words, a path made of blocks is 8 modules wide.
If we want this statement of Lemma 1 to apply in 3D, it sufﬁces to set the mul-
tiplicative factor at 24; If subcells have side length c (which is also the minimum
length of their backbone), then the number of modules in a 3D ring is 24c−16.
Therefore the cross-section of a backbone should be at least 5×5 modules. In
other words, we establish that a block should be at least 5×5×5 modules.
A 3D analog of the second statement of Lemma 1 also holds. Paths in the
original conﬁguration can only connect adjacent subcell sides (if a ring cannot be
formed).
Let P be a path beginning on an exterior face F of a subcell, without loss of
generality, the front-left face on the top of the cell. Assume that the entire cell does
not have enough modules to make a ring. Then P can only connect to the other top
faces, or to the external vertical faces of its own subcell, or to their neighbors to
the left and right. In other words, it can connect to any of the legal faces deﬁned as
the faces touched by one of F’s corners. A path to any other external face would
contradict our assumption.
Consider a subset Z of the robot within a cell, where every path in this subset
has the property described above. Z can be substituted with a different connected
set of modules that runs along the exterior of the cell and maintains connectivity
with every position outside of the cell. This can be established with a projection
argument.
16
Similar to 2D, any path of the original robot, within a cell that does not become
a ring, can be replaced with a shortest path along the boundary.
6.2
Connectivity of rings and sparse cells
In a 2D cell, a connectivity point was any position on the boundary (since any
such position could potentially be connected to an adjacent cell). Such positions
were never tampered with. However in 3D we do not wish to leave modules in
the interior of cell faces. We have shown that the internal connectivity of a sparse
cell can be maintained by pushing modules to the boundary. However we have not
addressed the issue of connectivity to adjacent cells.
We now argue that in two adjacent cells “sharing” face F, no modules need to
be inside F to preserve connectivity.
Suppose without loss of generality that the two cells are side-by-side (F is
vertical). If at least one of the cells is a ring, the claim is easy to prove: recall that,
by Lemma 1, the paths of a sparse cell can be replaced with paths that only traverse
the boundary. Now notice that the side-branches of the sparse cell A that are in the
interior of F can be moved anywhere, since they don’t affect connectivity. On the
one hand if they connect to other modules within A, this happens along the surface
of A, which means through a path that touches the adjacent ring. Thus there is an
alternate path from any module in the ring to the remaining modules of A. On the
other hand if side-branches of A are simply “islands” in the interior of F, then they
clearly have no connectivity purpose between the cells and they don’t critically
connect any modules from the ring cell. Thus they can just be swept to a corner.
Now suppose that both adjacent cells are sparse. Note that an initial path from
the top of the (union of the) two cells to the bottom would contain enough modules
to make at least one of them a ring (by pigeon-hole, as in Lemma 2). If the cells
have side-length 2c, the path would contain at least 50c modules, at least half of
which are in one of the cells. This exceeds the 24c−16 bound given previously.
This means that we can avoid having to shortcut through F. Now, with no con-
nectivity requirement between opposite edges of F, we can essentially look at the
union of the two sides of F (one in each cell) and treat it as the 2D case; all paths
can be substituted with new paths along the perimeter of a square.
We have established that, when we are to merge 8 subcells, we can assume that
all modules are on the subcell edges. In fact, in a sparse cell, all paths are shortest
paths along the edges. At this point, we can proceed with a description of how to
merge while preserving connectivity.
17
6.3
Module size and merging
Consider any given branch b, made of 8×8×8 modules. We could consider b as
consisting of four quarters, corresponding to branches of 4×4×4 modules. One
such component could be stripped away and moved about, say in a sparse cell,
using standard 2D moves (see Lemma 4) to reach any desired position in O(1)
time. Clearly it is not crucial for connectivity, since the remaining three quarters
are in place. Thus if we wish to displace b to a new position c, where c replaces the
connectivity role of b, we can use this doubling trick to move b in parts.
We use the term “doubling” instead of “quadrupling” because the trick only
technically requires double the module size (volume) used in basic-moves. How-
ever, it is conceptually easier to strip away sub-branches of cross-section 4×4 (even
if this must be done 4 times), rather than working with something like 6×6×6 that
technically sufﬁces for our argument.
Consider 8 subcells about to be merged into cell C. If we use the doubling
trick, it is easy to replace the existing paths in C with new ones that only use the
perimeter of C.
After this, for each face F of C, we push modules that are in the interior of F
towards the edges, while making sure we don’t lose connectivity with the newly
merged cell adjacent to F. This may involve some trading of modules (between F
and its adjacent counterpart), as in Lemma 3.
The main advantage of the doubling trick is that it allows us to avoid explicitly
considering how to move around the modules on the internal borders of the subcells
of C. Note that the underlying idea was also used in 2D, in the last paragraph of
the proof of Lemma 7. However, recall that in 2D we also had to argue why certain
connections along internal borders were not critical (Lemmas 8 and 9).
Without the double-module trick, we would probably have to increase the block
size to follow the method used for 2D. This would involve stronger pigeon-hole
arguments. For instance, suppose that a subcell has side length c. If it is a ring,
it contains at least 12c−16 modules. The top four subcells would contain 48c−64
modules. Now consider an initial path (of blocks) running from the top of the cell
to one of the bottom subcells. Its length is at least c. If the cross-section of the path
is at least 7×7 modules, then the path must contain more modules than four rings.
Thus the pigeon-hole principle tells us that one of these subcells must end up as a
ring.
Then, as in 2D, we can argue that there are no critical connections along in-
ternal borders, whenever fewer than two subcell rings exist. Note that two subcell
rings contain nearly enough modules to make the entire cell a ring. Only 16 mod-
18
ules are missing. Thus we could repeat the arguments of Lemmas 7, 8, 9.
We conclude that by using modules and blocks of constant size (either 8×8×8 and
5×5×5 respectively, or 4×4×4 and 7×7×7), we can reconﬁgure 3D Crystalline
robots in O(log n) parallel steps.
7
Discussion
The number of atoms in our modules and initial blocks can be reduced. By using
2×2 modules instead of 4×4, some of our basic operations become relatively com-
plicated. For example, the staircase move cannot be implemented via sliding, but
instead involves a form of parallel tunneling to break off strips that are one module
wide, and then using those as carrying tools, etc. Corner pops also become partic-
ularly unattractive. Reducing the block size has the result that we can no longer
rely only on rings and sparse cells to maintain the connectivity of any robot. In 2D,
we obtain a small set of orthogonal shortcut trees that must be taken into consider-
ation when merging cells. We expect that the same holds in 3D, although we have
not attempted to compute the necessary set of shortcut types. We conjecture that
reconﬁguration can take place with minimal modules (2 atoms in each dimension)
and no block restriction.
Our algorithm can be implemented in O(n log n) time. Each subcell contains
a constant number of rectangular components, so determining their relative conﬁg-
uration and series of motions should require constant time. We also claim that our
results extend to the case of labeled robots. This would involve a type of merge-
sort using staircase moves, once a straight path of modules is constructed using our
algorithm.
We have not determined if O(log n) steps are worst-case optimal. Such a lower
bound can be given for labeled robots, by a simple Kolmogorov argument: there
exist permutations that contain Θ(n log n) bits of information. Each parallel move
can be encoded in O(n) bits (for each robot in order, which sides perform which
operations), so we need Ω(log n) steps.
References
[1] G. Aloupis, S. Collette, M. Damian, E. D. Demaine, D. El-Khechen, R. Flat-
land, S. Langerman, J. O’Rourke, V. Pinciu, S. Ramaswami, V. Sacrist´an,
and S. Wuhrer. Realistic reconﬁguration of Crystalline and Telecube robots.
In 8th International Workshop on the Algorithmic Foundations of Robotics
(WAFR), 2008.
19
[2] G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langer-
man, J. O’Rourke, S. Ramaswami, V. Sacrist´an, and S. Wuhrer. Linear recon-
ﬁguration of cube-style modular robots. Computational Geometry - Theory
and Applications, 42(6–7):652–663, 2009.
[3] G. Aloupis, S. Collette, E. D. Demaine, S. Langerman, V. Sacrist´an, and
S. Wuhrer. Reconﬁguration of cube-style modular robots using O(log n) par-
allel moves. In Proc. Intl. Symp. on Algorithms and Computation (ISAAC
2008), volume 5369 of LNCS, 2008.
[4] Z. Butler, R. Fitch, and D. Rus. Distributed control for unit-compressible
robots: Goal-recognition, locomotion and splitting. IEEE/ASME Trans. on
Mechatronics, 7(4):418–430, 2002.
[5] Z. Butler and D. Rus.
Distributed planning and control for modular
robots with unit-compressible modules. Intl. Journal of Robotics Research,
22(9):699–715, 2003.
[6] G. Chirikjian, A. Pamecha, and I. Ebert-Uphoff. Evaluating efﬁciency of
self-reconﬁguration in a class of modular robots. Journal of Robotic Systems,
13(5):317–338, 1996.
[7] K. Hosokawa, T. Tsujimori, T. Fujii, H. Kaetsu, H. Asama, Y. Kuroda, and
I. Endo. Self-organizing collective robots with morphogenesis in a vertical
plane. In Proceedings of the IEEE International Conference on Robotics and
Automation (ICRA), pages 2858–2863, 1998.
[8] S. Murata and H. Kurokawa. Self-reconﬁgurable robots: Shape-changing
cellular robots can exceed conventional robot ﬂexibility. IEEE Robotics &
Automation Magazine, 14(1):43–52, 2007.
[9] A. Pamecha, C. Chiang, D. Stein, and G. Chirikjian. Design and implementa-
tion of metamorphic robots. In Proceedings of the ASME Design Engineering
Technical Conference and Computers in Engineering Conference, 1996.
[10] J. H. Reif and S. Slee.
Optimal kinodynamic motion planning for self-
reconﬁgurable robots between arbitrary 2D conﬁgurations. In Robotics: Sci-
ence and Systems Conference, Georgia Institute of Technology, 2007.
[11] D. Rus and M. Vona. Crystalline robots: Self-reconﬁguration with compress-
ible unit modules. Autonomous Robots, 10(1):107–124, 2001.
20
[12] J. W. Suh, S. B. Homans, and M. Yim. Telecubes: Mechanical design of a
module for self-reconﬁgurable robotics. In Proc. of the IEEE Intl. Conf. on
Robotics and Automation, pages 4095–4101, 2002.
[13] S. Vassilvitskii, M. Yim, and J. Suh. A complete, local and parallel recon-
ﬁguration algorithm for cube style modular robots. In Proc. of the IEEE Intl.
Conf. on Robotics and Automation, pages 117–122, 2002.
[14] M. Yim, D. G. Duff, and K. D. Roufas. Polybot: a modular reconﬁgurable
robot. In Proc. of the 2000 IEEE International Conference on Robotics and
Automation, pages 514–520, 2000.
[15] M. Yim, W.-M. Shen, B. Salemi, D. Rus, M. Moll, H. Lipson, E. Klavins, and
G. S. Chirikjian. Modular self-reconﬁgurable robots systems: Challenges
and opportunities for the future. IEEE Robotics & Automation Magazine,
14(1):43–52, 2007.
[16] E. Yoshida, S. Murata, A. Kamimura, K. Tomita, H. Kurokawa, and S. Kokaji.
A self-reconﬁgurable modular robot: Reconﬁguration planning and experi-
ments. The International Journal of Robotics Research, 21(10-11):903–915,
2002.
21