To test their algorithm, the researchers designed and built a system of ‘smart pebbles’—cubes about 10 mm to an edge, with processors and magnets built in. Image: M. Scott Brauer |
Imagine
that you have a big box of sand in which you bury a tiny model of a footstool.
A few seconds later, you reach into the box and pull out a full-size footstool:
The sand has assembled itself into a large-scale replica of the model.
That
may sound like a scene from a Harry Potter novel, but it’s the vision animating
a research project at the Distributed Robotics Laboratory (DRL) at Massachusetts
Institute of Technology’s (MIT) Computer Science and Artificial Intelligence
Laboratory. At the IEEE International Conference on Robotics and Automation in
May, DRL researchers will present a paper describing algorithms that could
enable such “smart sand.” They also describe experiments in which they tested
the algorithms on somewhat larger particles—cubes about 10 mm to an edge, with
rudimentary microprocessors inside and very unusual magnets on four of their
sides.
Unlike
many other approaches to reconfigurable robots, smart sand uses a subtractive
method, akin to stone carving, rather than an additive method, akin to snapping
LEGO blocks together. A heap of smart sand would be analogous to the rough
block of stone that a sculptor begins with. The individual grains would pass
messages back and forth and selectively attach to each other to form a 3D
object; the grains not necessary to build that object would simply fall away.
When the object had served its purpose, it would be returned to the heap. Its
constituent grains would detach from each other, becoming free to participate
in the formation of a new shape.
Distributed intelligence
Algorithmically, the main challenge in developing smart sand is that the
individual grains would have very few computational resources. “How do you
develop efficient algorithms that do not waste any information at the level of
communication and at the level of storage?” asks Daniela Rus, a professor of
computer science and engineering at MIT and a co-author on the new paper,
together with her student Kyle Gilpin. If every grain could simply store a digital
map of the object to be assembled, “then I can come up with an algorithm in a
very easy way,” Rus says. “But we would like to solve the problem without that
requirement, because that requirement is simply unrealistic when you’re talking
about modules at this scale.” Furthermore, Rus says, from one run to the next,
the grains in the heap will be jumbled together in a completely different way. “We’d like to not have to know ahead of time what our block looks like,” Rus
says.
Conveying
shape information to the heap with a simple physical model—such as the tiny
footstool—helps address both of these problems. To get a sense of how the
researchers’ algorithm works, it’s probably easiest to consider the 2D case. Picture
each grain of sand as a square in a 2D grid. Now imagine that some of the
squares—say, in the shape of a footstool—are missing. That’s where the physical
model is embedded.
According
to Gilpin-author on the new paper, the grains first pass messages to each other
to determine which have missing neighbors. (In the grid model, each square
could have eight neighbors.) Grains with missing neighbors are in one of two
places: The perimeter of the heap or the perimeter of the embedded shape.
Once
the grains surrounding the embedded shape identify themselves, they simply pass
messages to other grains a fixed distance away, which in turn identify
themselves as defining the perimeter of the duplicate. If the duplicate is
supposed to be 10 times the size of the original, each square surrounding the
embedded shape will map to 10 squares of the duplicate’s perimeter. Once the
perimeter of the duplicate is established, the grains outside it can disconnect
from their neighbors.
Rapid prototyping
The same algorithm can be varied to produce multiple, similarly sized copies of
a sample shape, or to produce a single, large copy of a large object. “Say the
tire rod in your car has sheared,” Gilpin says. “You could duct tape it back
together, put it into your system, and get a new one.”
The
cubes—or “smart pebbles”—that Gilpin and Rus built to test their algorithm
enact the simplified, 2D version of the system. Four faces of each cube are
studded with so-called electropermanent magnets, materials that can be
magnetized or demagnetized with a single electric pulse. Unlike permanent
magnets, they can be turned on and off; unlike electromagnets, they don’t
require a constant current to maintain their magnetism. The pebbles use the
magnets not only to connect to each other but also to communicate and to share
power. Each pebble also has a tiny microprocessor, which can store just 32
kilobytes of program code and has only two kilobytes of working memory.
The
pebbles have magnets on only four faces, Gilpin explains, because, with the
addition of the microprocessor and circuitry to regulate power, “there just
wasn’t room for two more magnets.” But Gilpin and Rus performed computer
simulations showing that their algorithm would work with a 3D block of cubes,
too, by treating each layer of the block as its own 2D grid. The cubes
discarded from the final shape would simply disconnect from the cubes above and
below them as well as those next to them.
True
smart sand, of course, would require grains much smaller than 10-mm cubes. But
according to Robert Wood, an associate professor of electrical engineering at Harvard University, that’s not an insurmountable
obstacle. “Take the core functionalities of their pebbles,” says Wood, who
directs Harvard’s Microrobotics Laboratory. “They have the ability to latch
onto their neighbors; they have the ability to talk to their neighbors; they
have the ability to do some computation. Those are all things that are
certainly feasible to think about doing in smaller packages.”
“It
would take quite a lot of engineering to do that, of course,” Wood cautions. “That’s a well-posed but very difficult set of engineering challenges that they
could continue to address in the future.”
