IEEE Robotics & Automation Magazine - September 2010 - 51

Theorem 2
The self-assembly algorithm prevents the formation of holes in
the lattice.

Proof
By Theorem 1, the self-assembly algorithm never creates gaps
with more than two neighbors, so the algorithm can never create a gap with four neighbors-the definition of a hole.
n
While the algorithm presented here has pertained to a 2-D
system, the extension to 3-D is straightforward. Instead of a 2D vector pointing back to the root module, each module will
have a 3-D vector and will need to check for neighbors in
three directions. Likewise, the 3-D algorithm guarantees that a
gap with more than three neighbors will never be created,
which implies that holes will never be created.
Self-Disassembly
Once the initial block of material has been assembled, self-disassembly by subtraction proceeds through four basic stages:
model formation, virtual sculpting, shape distribution, and disassembly. After self-assembly is complete, each module knows
its location within the initial structure. In the first stage, model
formation, each module, as evidence of its existence in the
initial structure, sends a reflection message containing its position back to the root module. The root does not store these
messages but forwards them to a graphical-user interface (GUI)
running on a PC. The GUI builds a virtual model representing
the initial arrangement of modules in the physical structure.
Using this GUI model, the user drives the virtual-sculpting stage
by selecting which modules should be included in the final
shape. During the entire shape-formation process, the PC is the
only entity that stores the entire shape description. After this
sculpting process is complete, the PC program generates a
sequence of inclusion messages. During the shape-distribution
stage, the GUI transmits these inclusion messages to the root
module. The structure then propagates these inclusion messages to their proper destinations. As with the localization
process, the messages only contain local information. During
the disassembly phase, the modules not designated to be in the
final structure disconnect from their neighbors to reveal the
shape the user sculpted previously. Each of the self-disassembly
phases is dependent on a distributed, localized message passing
algorithms executing on each module. Figure 13 shows a dog

0:00

(a)

being formed through the self-disassembly of a block of 27
Miche modules. As shown by the progression of time in the
frames, most modules disconnect quickly and fall away under
gravity's influence in less than 5 s. Others get stuck or disconnect but still rest on top of other modules. These must be
removed by vibrating the structure or by hand.
When self-assembly and self-disassembly are combined to
form structures, the resulting shapes cannot contain internal
cavities. Not only does the self-assembly algorithm, in its mission to form a close-packed lattice, avoid introducing holes, the
self-disassembly process has no way to remove unnecessary
modules from the interior of a structure if no exit hole exists.
Additionally, as one may suspect, if the modules being removed
from an initial block to form the final structure have a narrow or
convoluted exit path, it is unlikely that they will be able to exit
from the structure. In future work, we plan to examine how
the self-assembly process can be modified to accommodate the
formation of holes in the finished structure through a series of
repeated self-assembly and self-disassembly iterations.
Experiments
We have experimentally tested both the self-assembly and
self-disassembly algorithms. We use a collection of 17 modules
that was described in the "Hardware for Self-Assembly and
Disassembly" section. In 3-D, we imagine shaking a bag full of
modules to drive the self-assembly process. The 2-D analog is
an inclined vibration table. As shown in Figure 14, we built a
custom-vibration table that provides the stochastic forces necessary to move and align the modules. The frequency and
amplitude of the vibration can be controlled, as can the tilt of
the table. The perimeter of the table is surrounded by a low
barrier that prevents modules from falling off.
In our experiments, we anchored one module, the root, in
a corner of the vibration table at coordinates (0,0). The root
module provides the power and communication link between
the system and the user. Then, we tilted the table 4° in both
the x- and y-directions to bias the movement of all free modules toward the root module located at (0,0).
Using 16 randomly arranged modules (in addition to the
fixed-root module), we first tested the self-assembly algorithms
in a series of 13 trials. A progression of still images from one of
these trials is shown in Figure 15. Initially, the connectors on
each module are deactivated, and they are only turned on when

0:03

0:01

(b)

(c)

0:37

0:05

(d)

(e)

Figure 13. A dog-shaped structure can be self-disassembled from an initial configuration of 27 suspended Miche modules (each
45-mm per side). (Picture courtesy of Daniela Rus, Distributed Robotics Laboratory at MIT.)
SEPTEMBER 2010

IEEE Robotics & Automation Magazine

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2010