Algorithm advances driverless vehicles' potential

CHICAGO－Researchers at Northwestern University have developed the first decentralized algorithm which may help self-driving vehicles safely navigate roads with one another without crashing or causing unnecessary traffic jams.

They tested the algorithm in a simulation of 1,024 robots and on a swarm of 100 real robots in the laboratory. Both times, the robots reliably, safely and efficiently converged to form a predetermined shape in less than a minute.

The researchers accomplished this by keeping the robots nearsighted.

"Each robot can only sense three or four of its closest neighbors," says Michael Rubenstein, a professor in computer science and mechanical engineering in NU's McCormick School of Engineering who led the study. "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 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 says.

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. By 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 into that same spot," Rubenstein says. "They are careful and reserve a space ahead of time."

In the swarm, 100 robots can coordinate to form a shape within a minute.

The researchers imagine that this algorithm could be used in fleets of driverless cars and in automated warehouses.

"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 is scheduled to be published soon in the journal IEEE Transactions on Robotics.