New algorithm could help self-driving cars avoid collisions, traffic jams

The first decentralized algorithm with a collision-free, deadlock-free guarantee.

As the use of driverless cars is getting closer and closer to become an everyday reality, the need for a way to drive them safely and prevent traffic jams and accidents is imperative.

To solve this problem, the researchers at Northwestern University (NU) have devised a new algorithm with a collision-free, deadlock-free guarantee. The team demonstrated the control algorithm on the swarm of 1,024 tiny robots and on 100 real robots in the laboratory. The robots in this experiment were able to safely and efficiently coordinate and move to form a pre-determined shape in less than a minute.

One of the benefits of using tiny robots instead of large robots is that they do not require centralized control, which can quickly become a central point of failure.

If the system is centralized and a robot stops working, then the entire system fails,” said Northwestern’s Michael Rubenstein, who led the study. “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.

The team’s algorithm examines the ground beneath the robots as a grid to prevent accidents. Each robot is equipped with GPS-like technology, which helps them be aware of where it sits on the grid at any given time. Other sensors allow the robot to communicate with nearby robots before it makes a decision to move and to identify vacant or occupied spaces in the grid.

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

Researchers believe the algorithm can be used in cars to prevent accidents and traffic jams. “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,” Rubenstein said. “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.”

It can also be used in automated warehouses with hundreds of robots doing tasks. The research was published in the IEEE Journal of Transactions on Robotics.



See stories of the future in your inbox every morning.

New Inventions