Feb 25 2020
Self-driving vehicles can turn out to be a day-to-day reality only if they can flawlessly and safely navigate one another without crashing or leading to any unnecessary traffic jams.
One hundred small robots line up in the laboratory. Image Credit: Northwestern University.
To achieve this, researchers at Northwestern University have created the first-ever decentralized algorithm with a deadlock-free, collision-free guarantee.
The team tested the algorithm through a simulation of 1,024 robots and on a swarm of 100 real robots in the laboratory. The robots efficiently, reliably, and safely converged to form a predefined shape within a minute.
“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,” stated Michael Rubenstein from Northwestern University, who headed the study. “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.”
The study will be published in the IEEE Transactions on Robotics journal later this month. Rubenstein is the Lisa Wissner-Slivka and Benjamin Slivka Professor in Computer Science and Mechanical Engineering in Northwestern’s McCormick School of Engineering. In addition, he is a member of Northwestern’s Center for Robotics and Biosystems.
The benefit of a swarm of tiny robots, as opposed to a single huge robot or a swarm with one lead robot, is the absence of centralized control, which can instantly turn into a central point of failure. The decentralized algorithm developed by Rubenstein serves as a fail-safe.
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.
Michael Rubenstein, Lisa Wissner-Slivka and Benjamin Slivka Professor in Computer Science and Mechanical Engineering, McCormick School of Engineering, Northwestern University
However, the robots must coordinate to prevent deadlock and collisions. To achieve this, the algorithm visualizes the ground below the robots as a grid. Through technology analogous to GPS, each robot knows where it is positioned on the grid.
Prior to arriving at a decision of where to move, each robot makes use of sensors to communicate with its neighbors, ascertaining whether or not adjacent spaces within the grid are occupied or vacant.
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. They are careful and reserve a space ahead of time.
Michael Rubenstein, Lisa Wissner-Slivka and Benjamin Slivka Professor in Computer Science and Mechanical Engineering, McCormick School of Engineering, Northwestern University
Using this cautious coordination, the robots can communicate and move quickly to form a shape. The team has achieved this by keeping the robots near-sighted.
“Each robot can only sense three or four of its closest neighbors,” explained 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.”
In Rubenstein’s swarm, for instance, 100 robots can coordinate and form a shape in less than a minute. In some earlier methods, it could need nearly an hour. Rubenstein considers that his algorithm could be applied to fleets of cars without drivers, as well as in automated warehouses.
Large companies have warehouses with hundreds of robots doing tasks similar to what our robots do in the lab. They need to make sure their robots don’t collide but do move as quickly as possible to reach the spot where they eventually give an object to a human.
Michael Rubenstein, Lisa Wissner-Slivka and Benjamin Slivka Professor in Computer Science and Mechanical Engineering, McCormick School of Engineering, Northwestern University
The study, titled “Shape formation in homogenous swarms using local task swapping,” was funded by the Alfred P. Sloan Foundation. The first author of the paper is Hanlin Wang, a Ph.D. candidate in Rubenstein’s laboratory.
Swarming robots avoid collisions, traffic jams
One hundred small robots swarm together to self-assemble to form “NU.” A new algorithm prevents the robots from colliding and getting stuck in traffic jams. Someday, this algorithm could make fleets of autonomous vehicles more reliable, safe, and efficient. Video Credit: Northwestern University.