Swarming robots avoid crashes, jams using algorithm developed by Northwestern University researchers

February 26, 2020 | AUVSI News

Northwestern University researchers have developed what they are calling the “first decentralized algorithm with a collision-free, deadlock-free guarantee.”

The algorithm could potentially one day help self-driving vehicles navigate one another safely and flawlessly without crashing or causing unnecessary traffic jams, but for now, it is helping robots avoid crashes and jams. The algorithm was tested in a simulation of 1,024 robots and on a swarm of 100 real robots in the laboratory. In less than a minute, the robots reliably, safely and efficiently converged to form a pre-determined shape, as you can see below:

“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,” says Northwestern’s Michael Rubenstein, who led 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.”

According to the researchers, a swarm of small robots is more advantageous than one large robot or a swarm with one lead robot because of the lack of a centralized control, which can quickly become a central point of failure. The decentralized algorithm acts as a fail-safe.

“If the system is centralized and a robot stops working, then the entire system fails,” Rubenstein explains. “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.”

To avoid collisions and deadlock, the robots still need to coordinate, so to do this, the algorithm views the ground beneath the robots as a grid. Each robot is aware of where it sits on the ground thanks to the use of technology similar to GPS.

Each robot uses sensors to communicate with its neighbors before deciding where to move. This helps determine 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,” Rubenstein says. “They are careful and reserve a space ahead of time.”

Despite all of the careful coordination, though, the robots can still communicate and move quickly to form a shape, which is accomplished by keeping the robots near-sighted.

“Each robot can only sense three or four of its closest neighbors,” Rubenstein explains. “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.”

For example, in Rubenstein’s swarm, 100 robots can coordinate to form a shape within a minute. This could take a full hour in some previous approaches.

This algorithm could potentially be used in fleets of driverless cars and in automated warehouses, Rubenstein imagines.

“Large companies have warehouses with hundreds of robots doing tasks similar to what our robots do in the lab,” Rubenstein says. “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.”

The study, “Shape formation in homogenous swarms using local task swapping,” will be published in the journal IEEE Transactions on Robotics later this month.

Below: Northwestern University researchers have developed the first decentralized algorithm with a collision-free, deadlock-free guarantee. Using the algorithm, robots reliably, safely and efficiently converged to form a pre-determined shape in less than a minute. Photo: Northwestern University