Autonomous robots: A self-organizing thousand-robot swarm (w/ Video)

Aug 14, 2014
Just as single cells can assemble into complex multicellular organisms, the individual Kilobots can follow simple rules to autonomously assemble into predetermined shapes. The vast scale of this swarm is a milestone in itself. Credit: Photo courtesy of Mike Rubenstein and Science/AAAS.

The first thousand-robot flash mob has assembled at Harvard University.

"Form a sea star shape," directs a computer scientist, sending the command to 1,024 little bots simultaneously via an infrared light. The robots begin to blink at one another and then gradually arrange themselves into a five-pointed star. "Now form the letter K."

The 'K' stands for Kilobots, the name given to these extremely simple robots, each just a few centimeters across, standing on three pin-like legs. Instead of one highly-complex , a "kilo" of robots collaborate, providing a simple platform for the enactment of complex behaviors.

Just as trillions of individual cells can assemble into an intelligent organism, or a thousand starlings can form a great flowing murmuration across the sky, the Kilobots demonstrate how complexity can arise from very simple behaviors performed en masse (see video). To computer scientists, they also represent a significant milestone in the development of collective artificial intelligence (AI).

This self-organizing swarm was created in the lab of Radhika Nagpal, Fred Kavli Professor of Computer Science at the Harvard School of Engineering and Applied Sciences (SEAS) and a Core Faculty Member at the Wyss Institute for Biologically Inspired Engineering at Harvard University. The advance is described in the August 15 issue of Science.

"The beauty of biological systems is that they are elegantly simple—and yet, in , accomplish the seemingly impossible," says Nagpal. "At some level you no longer even see the individuals; you just see the collective as an entity to itself."

"Biological collectives involve enormous numbers of cooperating entities—whether you think of cells or insects or animals—that together accomplish a single task that is a magnitude beyond the scale of any individual," says lead author Michael Rubenstein, a research associate at Harvard SEAS and the Wyss Institute.

He cites, for example, the behavior of a colony of army ants. By linking together, they can form rafts and bridges to cross difficult terrain. Social amoebas do something similar at a microscopic scale: when food is scarce, they join together to create a fruiting body capable of escaping the local environment. In cuttlefish, color changes at the level of individual cells can help the entire organism blend into its surroundings. (And as Nagpal points out—with a smile—a school of fish in the movie Finding Nemo also collaborate when they form the shape of an arrow to point Nemo toward the jet stream.)

This video is not supported by your browser at this time.
A video summary of the Kilobot research. Credit: Michael Rubenstein, Harvard University

"We are especially inspired by systems where individuals can self-assemble together to solve problems," says Nagpal. Her research group made news in February 2014 with a group of termite-inspired robots that can collaboratively perform construction tasks using simple forms of coordination.

But the algorithm that instructs those TERMES robots has not yet been demonstrated in a very large swarm. In fact, only a few robot swarms to date have exceeded 100 individuals, because of the algorithmic limitations on coordinating such large numbers, and the cost and labor involved in fabricating the physical devices.

The research team overcame both of these challenges through thoughtful design.

The Kilobots, a swarm of one thousand simple but collaborative robots. Credit: Photo courtesy of Mike Rubenstein and Science/AAAS.

Most notably, the Kilobots require no micromanagement or intervention once an initial set of instructions has been delivered. Four robots mark the origin of a coordinate system, all the other robots receive a 2D image that they should mimic, and then using very primitive behaviors—following the edge of a group, tracking a distance from the origin, and maintaining a sense of relative location—they take turns moving towards an acceptable position. With coauthor Alejandro Cornejo, a postdoctoral fellow at Harvard SEAS and the Wyss Institute, they demonstrated a mathematical proof that the individual behaviors would lead to the right global result.

The Kilobots also correct their own mistakes. If a traffic jam forms or a robot moves off-course—errors that become much more common in a large group—nearby robots sense the problem and cooperate to fix it.

To keep the cost of the Kilobot down, each robot moves using two vibrating motors that allow it to slide across a surface on its rigid legs. An infrared transmitter and receiver allow it to communicate with a few of its neighbors and measure their proximity—but the robots are myopic and have no access to a bird's-eye view. These design decisions come with tradeoffs, as Rubenstein explains: "These robots are much simpler than many conventional robots, and as a result, their abilities are more variable and less reliable," he says. "For example, the Kilobots have trouble moving in a straight line, and the accuracy of distance sensing can vary from robot to robot."

Given a two-dimensional image, the Kilobots follow simple rules to form the same shape. Visually, the effect is similar to a flock of birds wheeling across the sky. "At some level you no longer even see the individuals; you just see the collective as an entity to itself," says Radhika Nagpal. Credit: Mike Rubenstein and Science/AAAS.

Yet, at scale, the smart algorithm overcomes these individual limitations and guarantees—both physically and mathematically—that the robots can complete a human-specified task, in this case assembling into a particular shape. That's an important demonstration for the future of distributed robotics, says Nagpal.

"Increasingly, we're going to see large numbers of robots working together, whether its hundreds of robots cooperating to achieve environmental cleanup or a quick disaster response, or millions of self-driving cars on our highways," she says. "Understanding how to design 'good' systems at that scale will be critical."

For now, the Kilobots provide an essential test bed for AI algorithms.

"We can simulate the behavior of large swarms of robots, but a simulation can only go so far," says Nagpal. "The real-world dynamics—the physical interactions and variability—make a difference, and having the Kilobots to test the algorithm on real robots has helped us better understand how to recognize and prevent the failures that occur at these large scales."

The Kilobot robot design and software, originally created in Nagpal's group at Harvard, are available open-source for non-commercial use. The Kilobots have also been licensed by Harvard's Office of Technology Development to K-Team, a manufacturer of small mobile robots.

Explore further: Self-organizing robots: Robotic construction crew needs no foreman (w/ video)

More information: "Programmable self-assembly in a thousand-robot swarm," by M. Rubenstein et al. Science, www.sciencemag.org/lookup/doi/… 1126/science.1254295

add to favorites email to friend print save as pdf

Related Stories

Kilobots bring us one step closer to a robot swarm

Jun 17, 2011

(PhysOrg.com) -- When you think about robots, the odds are that you think about something that is fairly large. Maybe you picture a robot arms bolted to the floor of a factory or if you are feeling particularly ...

Simplicity is key to co-operative robots

Apr 16, 2014

A way of making hundreds—or even thousands—of tiny robots cluster to carry out tasks without using any memory or processing power has been developed by engineers at the University of Sheffield, UK.

Clever copters can learn as they fly (w/ Video)

Jun 26, 2014

(Phys.org) —The research paves the way for robots to work intelligently alongside humans in ways that are currently familiar only through science fiction films. The robots could play important roles in ...

Recommended for you

Flying robots will go where humans can't

Sep 17, 2014

There are many situations where it's impossible, complicated or too time-consuming for humans to enter and carry out operations. Think of contaminated areas following a nuclear accident, or the need to erect ...

Will tomorrow's robots move like snakes?

Sep 16, 2014

Over the last few years, researchers at MIT's Computer Science and Artificial Intelligence Lab (CSAIL) have developed biologically inspired robots designed to fly like falcons, perch like pigeons, and swim ...

User comments : 13

Adjust slider to filter visible comments by rank

Display comments: newest first

ViperSRT3g
not rated yet Aug 14, 2014
As simple as this might be, I think I am too amused by this. Watching the little robots vibrate their way around each other is almost "cute"
LariAnn
1 / 5 (4) Aug 14, 2014
Most notably, the Kilobots require no micromanagement or intervention once an initial set of instructions has been delivered.


And where did the initial set of instructions come from? An intelligent source, not random movement or actions. Does this "prove" that "god" is the source of organization? If anything, it proves that intelligence is the source of organization, not "nothing".
11791
2.5 / 5 (2) Aug 14, 2014
Anybody that names their creation Kilibots has to be a devil.
The term kilobots might turn out to be prophetic
if they get together and attack the human race.
antigoracle
3 / 5 (1) Aug 15, 2014
Hmmm... Kilobots, they may want to reconsider their marketing strategy.
Mike_Massen
5 / 5 (2) Aug 15, 2014
LariAnn went offered this
..Does this "prove" that "god" is the source of organization? If anything, it proves that intelligence is the source of organization, not "nothing".
It might well be that, Eg water is a self organisation of hydrogen & oxygen.

Been proven many times you don't need an overall intelligence to exercise large permutations of devices that are exposed to simple rules. Genetic algorithms using the power & speed of modern computers show this routinely. Of course the environment & rules have to be in existence first.

This suggests in our reality that 'god' is none other than an observer of the astronomical number of permutations of physics & chemistry, Eg Amino acids observed in interstellar clouds etc.

Pity all claimed deities are:-
1 Created by men
2 Can't relate well to women
3 Very bad lazy communicators

& all religious works only describe: Status, Punishment & Authority - ie No education !

It seems we are but lonely means to explore all permutations !
grondilu
5 / 5 (1) Aug 15, 2014
Most notably, the Kilobots require no micromanagement or intervention once an initial set of instructions has been delivered.


And where did the initial set of instructions come from? An intelligent source, not random movement or actions. Does this "prove" that "god" is the source of organization? If anything, it proves that intelligence is the source of organization, not "nothing".


This sentence was not intended to imply anything of the sort. It merely pointed out that the robots do not require human supervision while operating. This is a feat not so easy to implement for such small, relatively simple robots. This was not an attempt to disprove God or anything. You're imagining things.
antialias_physorg
5 / 5 (1) Aug 15, 2014
And where did the initial set of instructions come from? An intelligent source, not random movement or actions. Does this "prove" that "god" is the source of organization?

It proves that the environment is the source of organization. The environment provides 'fitness criteria' - and self organization tries to fit to those.
Whether the fitness be "form a specific shape" or "try to avoid pain" or "try to maximize happiness" or simply "survive" is just a matter of degree.
EnricM
not rated yet Aug 15, 2014

Pity all claimed deities are:-
1 Created by men
2 Can't relate well to women
3 Very bad lazy communicators


Wrong, His Noodelity the FSM has Male Strippers too! Thus appealing to any possible permutation of sexual preference!!!

Ramen !
alfie_null
not rated yet Aug 15, 2014
With a nod to LariAnn, I for one, welcome our new overlords, the gray goo.

Seriously, on the mention of the tolerance for defects: it would be interesting to deliberately introduce defects into the system, for instance greater or less control of movement, see how it affects things. Sort of like the converse of adding capabilities. How simple, how incapable can these individual robots be? For different numbers and capabilities, how efficiently do they accomplish a task?

Given a sufficiently complex task, would we see groups within the swarm take on specialized roles?

If there were some reasonable way to do it, running this sort of experiment in 3D would be very interesting.
antialias_physorg
not rated yet Aug 15, 2014
If there were some reasonable way to do it, running this sort of experiment in 3D would be very interesting.

Quadcopters? There's already autonomous flocking demonstrations. The only limit to these seems to be the avialable number of copters - which are getting to be dirt cheap. I guess for 50k you could build 1000 of those.
standfast18
1 / 5 (1) Aug 15, 2014
May God help us all!!
antigoracle
not rated yet Aug 15, 2014
May God help us all!!

We imagine God is our creator and worship Him.
So, perhaps these bots, would worship us as their God.
Although, it's more likely they find atheism and enslave or kill us.
Mike_Massen
not rated yet Aug 16, 2014
standfast18 muttered or is it mumbled with
May God help us all!!
Cool, tell me how please ...

Does he/she/it arbitrarily interfere with physics so some people die whilst others survive with no link correlation with belief, practice, intention or prior communication ?

Substantive evidence of any prior causality definitively related to any claimed deity Please ?

You know, the type of evidence which works, that for example has led to all the technological advances since humans move away for hypnotic faith of the old era - especially medical advances in health to alleviate suffering - the mass suffering the christian god put in place as punishment because a young woman was manipulated by a serpent etc ?

antigoracle added
We imagine God is our creator and worship Him.
Thats the problem, imagination - nil evidence - only inconsistent claims aimed at making us feel better about suffering which has only been alleviated recently when we bypass faith & seek answers !