Proving That Shape-Shifting Robots Can Get A Move On

She soon determined that electromagnets didn’t have enough lifting power to solve the tennis-ball problem. However, her question led to a decade-long research program into the challenges of designing robots that reconfigure themselves to perform different tasks. Most recently, Rus and Dartmouth Robotics Lab researchers developed the first control methods that guarantee such self-reconfigurable robots won’t fall apart as they change shape or move across a surface.

The paper by postdoctoral researcher Zach Butler, graduate student Keith Butler, Rus and visiting professor Kohji Tomita from Japan's National Institute of Advanced Industrial Science and Technology appeared in the September 2004 issue of the International Journal of Robotics Research (IJRR).

"These latest papers show it is possible to develop self-reconfiguration capabilities in a way that has analytical guarantees," said Rus, who moved to MIT in January after 10 years as director of Dartmouth’s Robotics Lab. "Understanding exactly how your system works and when you can trust it and when you can’t is very important." In 2002, Rus received a MacArthur Foundation Fellowship, a so-called "genius award," for her work, which has been supported by National Science Foundation (NSF) awards since 1996.

Robots are usually designed to perform one task very well, whether it’s assembling parts in a factory or vacuuming the living room. But ask those robots to perform another task or even the same task in a new environment, and you’re asking for trouble.

Self-reconfigurable robots, on the other hand, can reshape themselves as their task or environment changes, ideally without human intervention. A walking robot used for search-and-rescue operations would transform into a snake-like form to slither through small spaces in a collapsed building. A rolling robot exploring the surface of Mars would flow like water over a vertical drop or "flow" uphill onto a rock ledge.

However, today's state-of-the-art shape-shifting robots are a long way from living up to that vision. Several research groups around the world are tackling the many significant mechanical and control challenges involved in having a robot change shape.

Over the past decade, assisted by more than 50 Dartmouth undergraduate and graduate students passing through her lab, Rus has made advances on both the mechanical and control fronts. On the mechanical side, she pioneered the design of 3-D shape-shifting robots built out of "expanding cubes," such as the Crystal modules.

Each Crystal module, or "atom," has sides that extend and contract and that use a 'key-in-lock' mechanism to attach to neighboring atoms. The expanding-cube concept is an example of so-called "lattice robots," which can assume a wide variety of 3-D shapes, an advantage over robots whose modules can only form long, thin chains.

Shape-shifting for such lattice robots boils down to exercises in control and planning, which happen at two levels. At one level, the robot must plan how to remodel itself from shape A to shape B. At another level, the robot must also plan the series of shapes needed to accomplish more complicated tasks, such as moving over rough terrain.

Early work in self-reconfiguring robots used centralized methods to control how the pieces reassembled themselves. Today, researchers in the field generally acknowledge the need for distributed methods, in which each robotic module takes at least some control of its own destiny.

"Since we are talking about potentially very large systems, with thousands of individual parts, it’s important to consider distributed control and planning," Rus said. "And parallel and distributed algorithms are hard to guarantee."

The recent IJRR paper and a related paper in the September 2003 IJRR by Butler and Rus provide some of the first distributed methods for generating provably correct steps for both types of control and planning. In other words, robots that reconfigure themselves using these plans won't fall to pieces, in a very literal sense, or get irreversibly stuck as they move from place to place.

The papers present sets of about a dozen rules that instruct lattice robots how to roam over terrain, build tall structures to overcome obstacles or enter closed spaces through small tunnels. Rus and her colleagues analyzed the simpler rule sets for correctness and developed automated methods to prove that the more complicated ones worked. More complex tasks, however, demand more complicated rule sets, and Rus is now investigating ways that would allow robots to learn their own rules.

In addition to the theoretical guarantees, the papers represent a departure from another norm. Often in robotics, a control method is tied to specific hardware, making it more difficult to apply lessons from one robot system to another. Rus's work applies to control and planning for the entire class of lattice robots, of which the Crystal atoms are one example.

"The [latest IJRR] paper is an example of a methodology for developing and proving algorithms and understanding control systems in general," Rus said. "It’s important to learn more general lessons. You get a deeper sense about the self-reconfiguration problem."