Swarming Raspberry Pi Robots Get a No-Collision, No-Deadlock Guarantee Through New Algorithm
By communicating with nearby neighbors, Northwestern's robots form shapes without collisions or deadlocks.
Researchers from Northwestern University have developed a swarm of Raspberry Pi-powered robots capable of avoiding collisions and jams using a novel decentralized algorithm — and they're promising a deadlock-free guarantee.
"If you have many autonomous vehicles on the road, you don’t want them to collide with one another or get stuck in a deadlock," explains study lead Michael Rubenstein. "By understanding how to control our swarm robots to form shapes, we can understand how to control fleets of autonomous vehicles as they interact with each other.
"If the system is centralized and a robot stops working, then the entire system fails. In a decentralized system, there is no leader telling all the other robots what to do. Each robot makes its own decisions. If one robot fails in a swarm, the swarm can still accomplish the task."
Rubenstein's team claims to have developed an algorithm for decentralized autonomous robot coordination which comes with a no-collision, no-deadlock guarantee — and has been proven in simulation for 1,024 robots and in the lab with 100 real-life 3D-printed wheeled robots each powered by a Raspberry Pi 3 Model B+ single-board computer.
Each robot is able to track its own location, and before making a move communicates with its immediate neighbors to find out whether its target location is vacant or occupied. If the location is free, the robot can place a reservation — guaranteeing that it'll still be empty when it arrives.
The trick to keeping things ticking along quickly: Short-sightedness. "Each robot can only sense three or four of its closest neighbors," says Rubenstein. "They can’t see across the whole swarm, which makes it easier to scale the system. The robots interact locally to make decisions without global information."
The team's paper is due to be published in the journal IEEE Transactions on Robotics; more information is available on the Northwestern University website and over on IEEE Spectrum.