This New Algorithm Can Prevent Self-Driving Vehicles From Crashing

Dhir Acharya - Feb 27, 2020

Sometimes, a fleet of robots is better than using one large robot. But the challenge is to avoid collisions, and that's now possible with a new algorithm.

US researchers have developed the first decentralized algorithm that will be able to stop robots from bumping into each other when they work together in the same space.

If the algorithm does work as the researchers say, it will potentially help prevent self-driving vehicles on the road or robots working in large warehouses from crashing. For now, researchers at Northwestern University have successfully simulated 1024 robots and tested 100 real robots in the lab.

100 robots working together without bumping into one another

They were all efficiently, safely, and reliably converged to create a pre-determined shape in under a minute, according to the research report.

In many circumstances, a fleet of small robots work better than one large robot because in case one of them fails, the others can still complete the task. The challenge is to avoid gridlock and collisions.

Michael Rubenstein, a researcher of the team, shares that to achieve this goal, the new algorithm sees the ground underneath the robots as a grid. Using a technology similar to GPS, the robots all know their positions on the grid.

Before deciding where to move, a robot communicates with its neighbors using its sensors, then it determines if a nearby space in the grid is occupied or vacant. It’s stated by the researcher that the robots don’t move to a new spot unless it’s free and if they know the other robots are not moving to that same spot. The robots are careful and they reserve a spot ahead of time.

Despite careful coordination, the robots can still communicate with each other as well as move swiftly to form a pre-determined shape. This is accomplished by keeping them near-sighted. Specifically, each robot can sense three or four closest neighbors only, they cannot see across the entire swarm, making it easier to scale up the system. The interaction to make the decision between the robots happens locally without global information. For instance, in this research, 100 robots can work together and take less than a minute to form a shape while that might take an hour with previous approaches.