MIT scientists have coded a series of algorithms that could ultimately facilitate the design of "smart sand" capable of assuming any shape.
This would allow the spontaneous formation of new tools or duplication of broken mechanical parts.
Sound like science fiction? Well, engineers have already tested the algorithms on somewhat larger particles - cubes approximately 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 leverages a subtractive method - similar to stone carving - rather than an additive method, akin to snapping LEGO blocks together.
Essentially, a heap of smart sand is analogous to the rough block of stone that a sculptor begins with. Individual grains would pass messages back and forth and selectively attach to each other to form a three-dimensional object, while 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.
The next step? How does one develop efficient algorithms that do not waste any information at the level of communication and at the level of storage.
"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,” explained Professor Daniela Rus. "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... We'd like to not have to know ahead of time what our block looks like."
Conveying shape information to the heap with a simple physical model - such as the tiny footstool - helps address both of these problems. To understand how the 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.
As Rus and her student Kyle Gilpin explain, 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.
Of course, 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 said. "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. However, unlike permanent magnets, they can be turned on and off. And, as opposed to 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. In addition, each pebble is equipped with a tiny microprocessor, which can store 32 kilobytes of program code and has 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." However, Gilpin and Rus performed computer simulations showing that their algorithm would work with a three-dimensional block of cubes as well, 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.
Obviously, true smart sand 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. 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," said Wood.
"Still, it would take quite a lot of engineering to do that, of course... That's a well-posed but very difficult set of engineering challenges that they could continue to address in the future."