Newly Developed Algorithm Could Prevent Autonomous Cars from Bumping Into Each Other

Researchers have developed a novel algorithm that may allow collision-free transportation in autonomous vehicles, an advance which they claim can help self-driving cars navigate each other without crashing, or causing traffic jams. The study, published in the journal IEEE Transactions on Robotics, tested the algorithm in a simulation of 1,024 robots, and on a swarm of 100 real robots, and reported that the bots reliably, safely, and efficiently converged to form a pre-determined shape in less than a minute.

"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 Michael Rubenstein, study lead author from Northwestern University in the US. "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 said.

According to the researchers, the advantage of a swarm of small robots -- versus one large robot, or a collective of bots with one lead -- is the lack of centralised control. The new algorithm, the scientists said, allows for decentralised swarms, and acts as a fail-safe, the study noted. "If the system is centralized and a robot stops working, then the entire system fails. In a decentralized system, there is no leader telling all the other robots what to do. Each robot makes its own decisions," Rubenstein explained.

"If one robot fails in a swarm, the swarm can still accomplish the task," he added. The researchers said the robots need to coordinate in order to avoid collisions, and for achieving this, the algorithm views the ground beneath the robots as a grid. Using technology that is similar to the Global Positioning System (GPS) which enables location tracking in mobile phones, each robot is aware of where it sits on the grid, the study noted.

In this set up, the scientists said, individual robots use sensors to communicate with their neighbours before making a decision about where to move. The robots then determine whether or not nearby spaces within the grid are vacant or occupied, they explained. "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. They are careful and reserve a space ahead of time," Rubenstein said.

The robots then communicate and move swiftly to form a shape, the study noted. According to Rubenstein, this is achieved by keeping the robots near-sighted. "Each robot can only sense three or four of its closest neighbours. They can't see across the whole swarm, which makes it easier to scale the system," the Northwestern University scientist explained.

"The robots interact locally to make decisions without global information," he added. In the swarm engineered by the researchers, 100 robots can coordinate to form a shape within a minute, the study noted. In earlier approaches, this could take a full hour, they said. "Large companies have warehouses with hundreds of robots doing tasks similar to what our robots do in the lab," Rubenstein said. "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," he added.