For self-driving vehicles to become an everyday reality, they need to safely and flawlessly navigate one another without crashing or causing unnecessary traffic jams. To help make this possible, researchers have developed the first decentralized algorithm with a collisionfree, deadlock-free guarantee.
The researchers tested the algorithm in a simulation of 1,024 robots and on a swarm of 100 real robots in the laboratory. The robots reliably, safely, and efficiently converged to form a pre-deter-mined shape in less than a minute.
The advantage of a swarm of small robots — versus one large robot or a swarm with one lead robot — is the lack of a centralized control, which can quickly become a central point of failure. The decentralized algorithm acts as a failsafe. If the system is centralized and a robot stops working, the entire system fails. In a decentralized system, however, there is no leader telling 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.
Still, the robots need to coordinate in order to avoid collisions and deadlock. To do this, the algorithm views the ground beneath the robots as a grid. Using technology similar to GPS, each robot is aware of where it sits on the grid. Before making a decision about where to move, each robot uses sensors to communicate with its neighbors, determining whether or not nearby spaces within the grid are vacant or occupied.
The robots refuse to move to a spot until that spot is free and until they know that no other robots are moving to that same spot. Even with careful coordination, the robots are still able to communicate and move swiftly to form a shape. This is accomplished by keeping the robots near-sighted so that each robot can only sense three or four of its closest neighbors. They cannot see across the whole swarm, which makes it easier to scale the system. The robots interact locally to make decisions without global information.
In the test swarm, for example, 100 robots coordinated to form a shape within a minute. In some previous approaches, it could take a full hour. The algorithm could be used in fleets of driverless cars and in automated warehouses where hundreds of robots are doing tasks similar to what robots do in the lab.