Smart Pebbles: To test their algorithm, researchers designed tiny cubes with built-in processors and magnets.
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 organized itself into a large-scale replica of the model.
Researchers at MIT’s Computer Science and Artificial Intelligence Laboratory have developed an algorithm that could make such “smart sand” possible. The grains of sand would be tiny computational devices that can pass messages to each other and selectively attach to their neighbors; in their research, the MIT team modeled the grains with cubes measuring about 10 millimeters to an edge. The cubes had rudimentary microprocessors inside and switchable magnetic connectors on four of their sides.
Algorithmically, the main challenge in developing smart sand is that such tiny 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 and a coauthor with her student Kyle Gilpin on a paper presented at the IEEE International Conference on Robotics and Automation in May. Rus and Gilpin’s answer is to convey shape information with a simple physical model.
To see how the algorithm works, picture each grain of sand as a square in a two-dimensional grid. Now imagine that some of the squares—say, forming the shape of a footstool—are missing. That’s where the physical model is embedded.
The grains pass messages to each other to determine which have missing neighbors. Grains with missing neighbors are in one of two places: the perimeter of the sand heap or the perimeter of the embedded shape. Once the grains surrounding the embedded shape identify themselves, they 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 grain surrounding the embedded shape will map to 10 grains of the duplicate’s perimeter. The grains not used to form the duplicate shape detach from their neighbors and simply fall away as the assembled object is lifted from the heap.
The cubes that Gilpin and Rus used in experiments enact this simplified, two-dimensional version of the system. But computer simulations demonstrate that the algorithm would work with a three-dimensional block of cubes, too, by treating each layer of the block as its own two-dimensional grid.
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.”