Rice University, Department of Computer Science
What is a "Swarm"?
As robots become more and more useful, multiple robots working together on a single task will become commonplace. Many of the most useful applications of robots are particularly well-suited to this "swarm" approach. Groups of robots can perform these tasks more efficiently, and can perform them in fundamentally different ways than robots working individually. However, swarms of robots are difficult to program and coordinate. My work focuses on developing software and programming techniques applicable to large swarms of robots, with populations in the 10 to 10,000 range. Software is evaluated on the 100-robot iRobot swarm.
Applications of Robot Swarms
There are many applications for swarms of robots. Multiple vacuum cleaner robots might need to share maps of areas where they've previously cleaned. A swarm of mars rovers might need to disperse throughout the environment to locate promising areas, while maintaining communications with each other. Robots used for earthquake rescue might come in three flavors: thousands of cockroach-sized scouts to infiltrate the debris and locate survivors, a few dozen rat-sized structural engineers to get near the scene and solve the "pick-up-sticks" problem of getting the rubble off, and a few brontosaurus-sized heavy-lifters to carry out the rescue plan.
In all these applications, individual robots must work independently, only communicating with other nearby robots. It is either too expensive (robot vacuums need to be very cheap), too far (it takes 15 minutes for messages to get to Mars), or impossible (radio control signals cannot penetrate into earthquake ruble) to control all of the robots from a centralized location. However, a distributed control system can let robots interact with other nearby robots, cooperating amongst themselves to accomplish their mission.
Software from Insects?
The main goal of my research is to understand how to use local interactions between nearby robots to produce large-scale group behaviors from the entire swarm. This idea is not new, in fact it is almost 65 million years old. Ants, bees, and termites are beautifully engineered examples of this kind of software in use. These insects do not use centralized communication, there is no strict hierarchy, and no one in charge.
However, developing swarm software from the "top down", i.e. by starting with the group application and trying to determine the individual behaviors that it arises from, is very difficult. Instead, I am developing a library of "group behavior building blocks" that can be combined to form larger, more complex applications. The robots use these behaviors to communicate, cooperate, and move relative to each other. Some behaviors are simple, like following, dispersing, and counting. Some are more complex, like dynamic task assignment, temporal synchronization, and gradient tree navigation. There are currently about forty of these behaviors. They are designed to produce predictable outcomes when used individually, or when combined with other library behaviors, allowing group applications to be constructed much more easily.
Robots are going to be an important part of the future. Once robots are useful, groups of robots are the next step, and will have tremendous potential to benefit mankind. Software designed to run on large groups of robots is the key needed to unlock this potential.
The behaviors described below are primitive building blocks for building more complicated swarm applications. Their inner workings are described in detail in my Master's Thesis.
matchOrientation (3,661,KB mpg)
matchOrientation (3,661,KB mpg)
beaconNavigation (3,071 KB mpg)
The pictures above show how a long-range ISIS beacon can be used with the matchHeadingToRobot behavior to guide the robots in along global heading. The robots are trying to move "north". As the beacon is rotated, all the robots change their direction accordingly. If the heading of the beacon is kept constant, the robots can use it like a compass to determine their absolute heading. Multiple beacons can be used to cover the entire workspace.
orbitRobot (4,027 KB mpg)
This video clip shows a group of robots orbiting a reference robot. The reference robot is the one with the tall black antenna.
disperseFromSource (3,702 KB mpg)
This video clip shows the disperseFromSource behavior in action.
disperseUniformly (4,363 KB mpg)
disperseUniformly-2 (4,010 KB mpg)
These video clips show the disperseUniformly behavior in action. For the keen of eye, robots that are near walls are flashing their blue light; robots in the interior are flashing their green light.
followTheLeader (20,903 KB mpg)
This video clip shows the followTheLeader behavior in action. Constant handshaking between successive robots keeps the line robust. If a robot does not respond, another is recruited to take its place. The chain breaks in image four, re-forms in image five, and is stable in the final image.
navigateGradient (4,948 KB mpg)
This video clip shows the navigateGradient behavior in action. The source robot is wearing a small flag and is highlighted in green in the bottom center of the images. The active robot is highlighted in red.
clusterOnSource (4,635 KB mpg)
This video clip shows the clusterOnSource behavior in action.
clusterIntoGroups (3,298 KB mpg)
This video clip shows the clusterIntoGroups behavior in action. There are three groups, red, green, and blue. Each group elects a leader, and robots use the navigateGradient behavior to move towards the leader of each group. Once robots are grouped, entire groups move away from other nearby groups.
counting (8,010 KB mpg)
This video clip shows the counting behavior in action.
dockToCharger (3,629 KB mpg)
This video clip shows the dockToCharger behavior in action.
SwarmTrek-DarkRoom (31,251 KB avi)
This video clip shows the Swarm dispersing into a large room.
SwarmTrek-WalkThrough (2,718 KB mpg)
This video clip shows a walk-through of a dispersed Swarm.
SwarmTrek-clusterWithBreadCrumbs (8,688 KB avi)
This video clip shows the clusterWithBreadCrumbs behavior pulling the swarm out of the large room.