Researchers have developed an algorithm that could stop self-driving vehicles from getting in crashes and traffic jams. The team from Northwestern University (NU) claims their invention is “the first decentralized algorithm with a collision-free, deadlock-free guarantee.” The algorithm divides the ground beneath the machines into a grid. The robots learn their position through technology similar to GPS and coordinate their movements through sensors that assess where there’s free space to move. “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,” said Northwestern Engineering’s Michael Rubenstein, who led the study. “They are careful and reserve a space ahead of time.”
Rubenstein’s team tested their algorithm on a swarm of 100 robots set up in their lab. In less than a minute, the robots converged in the shape of the letters “NU.”
Check out how the bots did it in the video below:
To cut out any distractions, the robots were only allowed to sense three or four of their closest neighbors. This restriction on their vision makes the system easier to scale, as the robots can interact locally without needing global information.
From the warehouse to the road
The advantage of a swarm of robots is there’s no centralized controller that can disrupt the whole system. This allows them to work together to accomplish a task — even if one of them breaks down. This gives the system an obvious application in warehouse robots. But Rubenstein believes it could also cut traffic and collisions for self-driving vehicles on the road. “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,” he said.