A Thousand Kilobots Self-Assemble Into Complex Shapes

posted in: Robotics News | 0

Photo: Michael Rubenstein/Harvard University

When Harvard roboticists first introduced their Kilobots in 2011, they’d only made 25 of them. When we next saw the robots in 2013, they’d made 100. Now the researchers have built one thousand of them. That’s a whole kilo of Kilobots, and probably the most robots that have ever been in the same place at the same time, ever [UPDATE: Some readers wrote in to say they disagree that this is the most robots in the same place at the same time ever. Rod Brooks says he was once in a warehouse in China with more than a thousand Roombas in storage. “Admittedly, they are in boxes rather than out running around and cooperating,” he says, “but it was a lot of robots!” Another reader claims that SRI has more than 1024 microrobots operating simultaneously. If you know of other massive robot swarms like that, let us know.]

The researchers—Michael Rubenstein, Alejandro Cornejo, and Professor Radhika Nagpal of Harvard’s Self-Organizing Systems Research Group—describe their thousand-robot swarm in a paper published today in Science (they actually built 1024 robots, apparently following the computer science definition of “kilo”).

Despite their menacing name (KILL-O-BOTS!) and the robot swarm nightmares they may induce in some people, these little guys are harmless. Each Kilobot [pictured below] is a small, cheap-ish ($14) device that can move around by vibrating their legs and communicate with other robots with infrared transmitters and receivers.

Photo: Michael Rubenstein/Harvard University

Two things are key to doing useful stuff with a swarm of robots like this. Thing one is having a lot of them, and one thousand most definitely qualifies as A LOT of them. In fact, researchers working on swarm robotics often rely on computer simulations (because digital robots are cheap!). When they built actual robots, their “swarm” consists of five robots or so. Maybe ten. Or a hundred, in rare cases.

But a thousand Kilobots—that’s a swarm. There are so many robots here that the importance of any individual robot is close to zero, which is a big part of the point of a swarm in the first place: robots can screw up, robots can break down, but there are so many of them that it just doesn’t matter, because their collective behavior prevails.

The second thing about swarm robotics is that you need the software and infrastructure to manage and control a huge number of robots. With a thousand robots, tasks that are trivial with a few robots rapidly scale to impossible. Charging is one example. Imagine if you had to manually plug 1000 robots to their chargers. For their Kilobots, the Harvard researchers solve this problem by sandwiching them between two metal sheets and passing a current through them. Similarly, you can rapidly program the robots by beaming infrared signals on them. And because you can do these operations (charging and programming) for all the robots at once, even if you increase the size of the swarm, the time required remains the same.

So once you’ve got your robots, and your charging, and your programming, what can you do? This:

In biological systems, swarms organize and control themselves based on a set of very simple rules. With fish, for example, the rules are to stay close to the fish in front of you while turning towards your nearest neighbor to the side. With the Kilobots, the algorithm that they use to create shapes are based on a similarly simple set of capabilities:

  • Edge-following, where a robot can move along the edge of a group by measuring distances from robots on the edge
  • Gradient formation, where a source robot can generate a gradient value message that increments as it propagates through the swarm, giving each robot a geodesic distance from the source
  • Localization, where the robots can form a local coordinate system using communication with, and measured distances to, neighbors

Of these capabilities, the localization is both the trickiest and most important. The robots talk to each other by bouncing infrared light off of the surface that they operate on. They can tell how far away they are from other robots by measuring how much the brightness of the infrared light changes: the dimmer the light, the farther away they are. But they have no information about where exactly the light is coming from. So, to localize, they depend on an initial “seed” group of robots to define the origin of a coordinate system, and then subsequent robots can localize based on the relative brightness of the infrared pulses coming from at least three other robots that have already been localized.

 
Image: Harvard University/Science
Collective self-assembly algorithm: Top left: A user-specified shape is given to robots in the form of a picture. Top right: The algorithm relies on three primitive collective behaviors: edge-following, gradient formation, and localization. Bottom: The self-assembly process by which a group of robots forms the user-defined shape.

Once the robots localize themselves, the procedure for forming an arbitrary shape is relatively straightforward: robots start to move around the perimeter of the swarm until they detect that they’ve entered the area where the shape will be formed. Then, each robot continues to move around the edge of whatever other robots are already in the shape until it detects that it’s about to exit the shape, or until it bumps into the previous robot. And that’s it: robots just keep moving, following these simple rules, until the shape is created.

With 1000 robots, you have to figure that they’re not all going to do exactly what they’re supposed to do all the time, which is why the researchers had to build as much flexibility as possible into the system. Lots of things can go wrong, from robots accidentally shoving other robots to robots breaking down for whatever reason. In these cases, more relatively simple rules allow the swarm as a whole to form the desired shape. A stalled robot might direct other robots to go around it, while a shoved robot might have to reposition itself. Individual robots don’t necessarily have the sensors to determine when bad things like this happen, but through interacting with their neighbors and looking for patterns in the sensor data, the swarm as a whole is much more resilient.

Photo: Michael Rubenstein/Harvard University

Now that there are a thousand of these robots out there running around, what’s next? We’re fixated on these two sentences (the very first one and the very last one) from the Science paper:

“In nature, groups of thousands, millions, or trillions of individual elements can self-assemble into a wide variety of forms, purely through local interaction.”

“This motivates new investigations into advanced collective algorithms capable of detecting malfunctioning robots and recovering from large-scale external damages, as well as new robot designs that, like army ants, can physically attach to each other to form stable self-assemblages.”

Okay, so if I’m putting these two things together correctly, what the researchers are saying is that they’re going to create a trillion Kilobots (trilobots?) that will form self-assembling structures that cannot be destroyed. Ever. By anything.