MIT News magazine

New algorithms could lead to self-sculpting “smart sand”
June 19, 2012

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.”

### DeepMind’s cofounder: Generative AI is just a phase. What’s next is interactive AI.

“This is a profound moment in the history of technology,” says Mustafa Suleyman.

New variants will pose a challenge, but early signs suggest the shots will still boost antibody responses.

### Human-plus-AI solutions mitigate security threats

With the right human oversight, emerging technologies like artificial intelligence can help keep business and customer data secure

### Next slide, please: A brief history of the corporate presentation

From million-dollar slide shows to Steve Jobs’s introduction of the iPhone, a bit of show business never hurt plain old business.

### Stay connected

Illustration by Rose Wong

## Get the latest updates fromMIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!