Swarm of Robots Forms Complex Shapes Without Centralized Control
Swarms of small, inexpensive robots are a compelling research area in robotics. With a swarm, you can often accomplish tasks that would be impractical (or impossible) for larger robots to do, in a way that's much more resilient and cost effective than larger robots could ever be.
The tricky thing is getting a swarm of robots to work together to do what you want them to do, especially if what you want them to do is a task that's complicated or highly structured. It's not too bad if you have some kind of controller that can see all the robots at once and tell them where to go, but that's a luxury that you're not likely to find outside of a robotics lab.
Researchers at Northwestern University, in Evanston, have been working on a way to provide decentralized control for a swarm of 100 identically programmed small robots, which allows them to collectively work out a way to transition from one shape to another without running into each other even a little bit.
The process that the robots use to figure out where to go seems like it should be mostly straightforward: They're given a shape to form, so each robot picks its goal location (where it wants to end up as part of the shape), and then plans a path to get from where it is to where it needs to go, following a grid pattern to make things a little easier. But using this method, you immediately run into two problems: First, since there's no central control, you may end up with two (or more) robots with the same goal; and second, there's no way for any single robot to path plan all the way to its goal in a way that it can be certain won't run into another robot.
To solve these problems, the robots are all talking to each other as they move, not just to avoid colliding with its friends, but also to figure out where its friends are going and whether it might be worth swapping destinations. Since the robots are all the same, they don't really care where exactly they end up, as long as all of the goal positions are filled up. And if one robot talks to another robot and they agree that a goal swap would result in both of them having to move less, they go ahead and swap. The algorithm makes sure that all goal positions are filled eventually, and also helps robots avoid running into each other through judicious use of a "wait" command.
What's novel about this approach is that despite the fully distributed nature of the algorithm, it's also provably correct, and will result in the guaranteed formation of an entire shape without collisions or deadlocks. As far as the researchers know, it's the first algorithm to do this.What's really novel about this approach is that despite the fully distributed nature of the algorithm, it's also provably correct, and will result in the guaranteed formation of an entire shape without collisions or deadlocks. As far as the researchers know, it's the first algorithm to do this. And it means that since it's effective with no centralized control at all, you can think of "the swarm" as a sort of Borg-like collective entity of its own, which is pretty cool.
The Northwestern researchers behind this are Michael Rubenstein, assistant professor of electrical engineering and computer science, and his PhD student Hanlin Wang. You might remember Mike from his work on Kilobots at Harvard, which we wrote about in 2011, 2013, and again in 2014, when Mike and his fellow researchers managed to put together a thousand (!) of them. As awesome as it is to have a thousand robots, when you start thinking about what it takes to charge, fix, and modify them, a thousand robots (a thousand robots!), it makes sense why they've updated the platform a bit (now called Coachbot) and reduced the swarm size to 100 physical robots, making up the rest in simulation.
These robots, we're told, are "much better behaved."
Image: Northwestern University The hardware used by the researchers in their experiments. 1. The Coachbot V2.0 mobile robots (height of 12 cm and a diameter of 10 cm) are equipped with a localization system based on the HTC Vive (a), Raspberry Pi b+ computer (b), electronics motherboard (c), and rechargeable battery (d). The robot arena used in experiments has an overhead camera only used for recording videos (e) and an overhead HTC Vive base station (f). The experiments relied on a swarm of 100 robots (g). 2. The Coachbot V2.0 swarm communication network consists of an ethernet connection between the base station and a Wi-Fi router (green link), TCP/IP connections (blue links), and layer 2 broadcasting connections (black links). 3. A swarm of 100 robots. 4. The robots recharge their batteries by connecting to two metal strips attached to the wall.
For more details on this work, we spoke with Mike Rubenstein via email.
IEEE Spectrum: Why switch to the new hardware platform instead of Kilobots?
Mike Rubenstein: We wanted to make a platform more capable and extendable than Kilobot, and improve on lessons learned with Kilobot. These robots have far better locomotion capabilities that Kilobot, and include absolute position sensing, which makes operating the robots easier. They have truly "hands free" operations. For example with Kilobot to start an experiment you had to place the robots in their starting position by hand (sometimes taking an hour or two), while with these robots, a user just specifies a set of positions for all the robots and presses the "go" button. With Kilobot it was also hard to see what the state of all the robots were, for example it was difficult to see if 999 robots are powered on or 1000 robots are powered on. These new robots send state information back to a user display, making it easy to understand the full state of the swarm.
How much of a constraint is grid-ifying the goal points and motion planning?
The grid constraint obviously makes motion less efficient as they must move in Manhattan-type paths, not straight line paths, so most of the time they move a bit farther. The reason we constrain the motions to move in a discrete grid is that it makes the robot algorithm less computationally complex and reasoning about collisions and deadlock becomes a lot easier, which allowed us to provide guarantees that the shape will form successfully.
Image: Northwestern University Still images of a 100 robot shape formation experiment. The robots start in a random configuration, and move to form the desired "N" shape. Once this shape is formed, they then form the shape "U." The entire sequence is fully autonomous. (a) T = 0 s; (b) T = 20 s; (c) T = 64 s; (d) T = 72 s; (e) T = 80 s; (f) T = 112 s.
Can you tell us about those couple of lonely wandering robots at the end of the simulated "N" formation in the video?
In our algorithm, we don't assign goal locations to all the robots at the start, they have to figure out on their own which robot goes where. The last few robots you pointed out happened to be far away from the goal location the swarm figured they should have. Instead of having that robot move around the whole shape to its goal, you see a subset of robots all shift over by one to make room for the robot in the shape closer to its current position.
What are some examples of ways in which this research could be applied to real-world useful swarms of robots?
One example could be the shape formation in modular self-reconfigurable robots. The hope is that this shape formation algorithm could allow these self-reconfigurable systems to automatically change their shape in a simple and reliable way. Another example could be warehouse robots, where robots need to move to assigned goals to pick up items. This algorithm would help them move quickly and reliably.
What are you working on next?
I'm looking at trying to understand how to enable large groups of simple individuals to behave in a controlled and reliable way as a group. I've started looking at this question in a wide range of settings; from swarms of ground robots, to reconfigurable robots that attach together by melting conductive plastic, to swarms of flying vehicles, to satellite swarms.
"Shape Formation in Homogeneous Swarms Using Local Task Swapping," by Hanlin Wang and Michael Rubenstein from Northwestern, is published in IEEE Transactions on Robotics. < Back to IEEE Journal Watch