To make self-driving vehicles a reality and to bring them on roads, they need to be able to safely and flawlessly navigate traffic without collisions or jams. Northwestern University researchers have made this possible by developing the first decentralized algorithm with a collision-free guarantee.

The algorithm was tested in a simulation of 1,024 robots and in a throng of 100 real robots by the researchers in the laboratory. The robots carefully and efficiently followed to form a command shape.

 “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,” said 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.” Rubenstein, the professor who led the study is the Lisa Wissner-Slivka and Benjamin Slivka Professor in Computer Science and Mechanical Engineering in Northwestern’s McCormick School of Engineering and a member of Northwestern’s Center for Robotics and Biosystems. The paper will be published in the journal IEEE Transactions on Robotics later this month.

Rubenstein algorithm is decentralized and not centralized which makes it foolproof and safer. “If the system is centralized and a robot stops working, then the entire system fails,” Rubenstein said. “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.”

But still, to move effortlessly, the robots need to communicate with each other so as not to collide and for this, the algorithm divides the ground below in grids and by using a GPS type technology the robot knows where to go - where the grid is empty and no other robot is moving to that spot.

 “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 said. “They are careful and reserve a space ahead of time.”  

These robots interact locally to make decisions and hence do not need a central command body. This system according to Rubenstein can be very effective in driver-less cars as well as in warehouses with many robots working at the same time.