• Daniela Rus, left, and Kyle Gilpin.

    Photo: M. Scott Brauer

    Full Screen
  • To test their algorithm, the researchers designed and built a system of 'smart pebbles' — cubes about 10 millimeters to an edge, with processors and magnets built in.

    Photo: M. Scott Brauer

    Full Screen
  • Daniela Rus, left, and Kyle Gilpin.

    Photo: M. Scott Brauer

    Full Screen

Self-sculpting sand

New algorithms could enable heaps of ‘smart sand’ that can assume any shape, allowing spontaneous formation of new tools or duplication of broken mechanical parts.


Press Contact

Caroline McCall
Email: newsoffice@mit.edu
Phone: 617-253-2700
MIT News Office

Media Resources

3 images for download

Access Media

Media can only be downloaded from the desktop version of this website.

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.

Best of 2012

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 MIT’s Computer Science and Artificial Intelligence Laboratory. At the IEEE International Conference on Robotics and Automation in May — the world’s premier robotics conference — 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 millimeters 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 three-dimensional 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.

Inside the robot pebbles
To attach to each other, to communicate and to share power, the cubes use 'electropermanent magnets,' materials whose magnetism can be switched on and off with jolts of electricity. Each cube has magnets — recognizable by the reddish wires wrapped around them — on four of its six faces.
Photo: M. Scott Brauer

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 two-dimensional case. Picture each grain of sand as a square in a two-dimensional 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 — lead 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, two-dimensional 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 three-dimensional block of cubes, too, by treating each layer of the block as its own two-dimensional 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-millimeter 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.”


Topics: Algorithms, Computer Science and Artificial Intelligence Laboratory (CSAIL), Distributed, Programmable matter, Reconfigurable robots, Research, Robots

Comments

Easily solved and yes this is an actual solution to their problem, yawn. do{ Send signal to each layer to number itself [layer, 0] straight down the whole structure single block in middle. 1..n layers. (numbering 0,0 block basically) } Each block do { If you have number given to you assign the numbers on your layer, giving them the layer they are on(though not needed) all blocks going left, right, forward back on the grid are given the same numbers for every grid. } Once each block has its number its easy as you know what to send next to each layer sequentially is the map, bang bang bang all the way down. Each map of each layer will have exactly the same numbering scheme for every block on it. And if you have to ask what numbers to put into the grid, omg youre really stupid...ever heard of x,y grid. This blkock is 1 along and 2 up, 2 along 2 up...can it be any easier...I mean i ask you. Signal transmission is then sent efficiently to each and every block of what faces to
Signal transmission is then sent efficiently to each and every block of what faces to kill magneticm too. Then once the WHOLE mass has its instructions an BEGIN command is send to the lowest layer first going up until the top layer recieves its BEGIN COMMAND at which point you have your tool. Each layer also sending the signal to the block below it as well just to remove isolated individuals who dont get signal.
(In reference to this supposedly "easily solved" problem) "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."
Really cool! This is a great first step, but have you managed to get the cubes to do this out of simulation? If so, could you post a video of them in action? Thanks, and great work!
I interviewed Kyle Gilpin at ICRA 2010 about his work with the robot pebble, which is the "grain" in the "smart sand" http://bit.ly/feGLLF This interview is part of the Flexible Elements podcast series, focusing on Self-reconfiguring modular robotics, at IT Conversations http://bit.ly/eZwV8e
Is the actual algorithm available? I don't want to sound like I'm offering another "actual solution...yawn", but having support for a 'conjugate' seems like it breaks automatism of the grains. If you have knowledge of points a distance away, the shape can be duplicated fairly directly (invert-invert-clean up). But I imagine it is doable with a little language based on the state of the sides (a la Conway's Life) and a stack.
Any block.face that detects an object next to it generates a "0" signal on the opposite face. Other faces will have a "1" signal. Any block.face that detects a "0" signal adjacent to in (on the neighbouring block) will also generate a "0" on the opposite face. So the first bit is either 0 or 1, with 0 indicating that it is part of a chain touching part of the object to be copied. The remainin g bits of the byte of data are the layer number, wih each block adding 1 to the layer number it read from the adjacent block. Blocks that start in a corner will have two (or possibly three) faces that are touching, and will this cause the 3 opposite faces to generate their "0" signals. When the layer number reaches the required count (for the total object size) then the outer-most blocks will will generate a "1" instead of a "0". Blocks that see only a "1" signal on all six faces will switch off their magnets when the sand is required to fall away.
Step 1: sand forms a mould around the object. Step 2: use a "smart scalpel" to cut the mould in two and remove the base object. Step 3: re-join the mould Step 4: use the smart scalpel to open a small access hole/ Step 5: fill with smart sand to create the copy object. Only sand that is in contac with a mould wall will turn off the relevant magnet, otherwise all magnets will be on. Step 6: remove the mould (by switching off magnets) You may be able to do this with one type of sand, but it is proably easier to use two types (mould sand and filler sand).
You cheated, you watched the video. Only the smart scalpel is so smart that it fills a virtual mould instead of fiddling with the mould. Only one type of sand needed.
You may be interested in this sequence from a feature film in which our job was to create "smart cubes" that appear to organize with individual and mass intelligence to build up 2 of the main characters and to facilitate transformations between characters. We did around 100 of these types of shots in the film. It was exciting for us to see this starting to happen in the real world of MIT! http://www.youtube.com/watch?v=fMis7LPZE9M&context=C4ec7528ADvjVQa1PpcFNKYehDAzVa3RuUt-CDoeEgJijXnoDEUCA=
As they say in the philosophy department, "For every complex human problem there is a simple solution ... and it is wrong."
Sadly, I can't watch the video unless I log on from home - which I have not done yet. So I didn't cheat, One of the main points in the original article was explaining that they needed too much storage for the sand. My approach only needs a dozen bytes per grain, rather than 32k. Sand with 32k is a lot smarter than sand with 12 or 16 bytes, but if you want to make the grains small then my approach seems to have merit (in my biased view). I'll try and watch the video from home soon.
Truncated octahedra would seem to be an ideal shape for these. They form a nice uniform honeycomb with some faces 90degrees and 180 for strength and a better roll-off edge than a cube for the transition to a new grouping. Seems like a cube would have a hard time pushing itself off of one face onto a neighboring face at transition time. What other shapes are being considered?
I would like to speak to the author of this article would someone call me to discuss a application idea.
M12345, if your solution is so simple that it bores you, perhaps that is because you live in a digital world of make-believe with 'solutions' that do not apply to the real-world. Deal with the real world and soon your presumptuous attitude will be properly adjusted. Just try to find real-world objects, like tie rods, that conveniently displace sand in an ordered, layer-by-layer, row-by-row, column-by-column fashion. While you engage in that search, I'll go take a long nap (yawn). After one puts a real object (like a tie-rod) in a box of small 'sand' cubes, the cubes near the object become disordered. Some of cubes make contact with others along edges, some only at points. There are no convenient layers. Assigning these jumbled particles to a virtual matrix is more complex than going "bang bang bang all the way down." That might explain why your 'actual' solution is so soporific - it is trivial when compared to the real-world. I look forward to your real solution. :-)
How about just putting "'sand' computer chips" on current real world items with an algorithim already tailored to that item so when you place that item in the sand, it just reads the copy data. So instead of figuring out how to load shapes into each sand you just have to teach the sand how to read, and all the "books" are just put on items from their manufacturers, and then u could just place the chip in the sand and duplicate the real item? or am i misunderstanding what you mean by not enough storage space that you dont have enough to store the "reading" information on the sand.
Back to the top