Algorithm keeps robots on task

US researchers say they have developed the first decentralised algorithm that can stop robots colliding when they are working together – or just going about their business in the same space.

The obvious potential is with self-driving vehicles or coordinating robots in large warehouses. For now, Michael Rubenstein and colleagues at Northwestern University have succeeded with a simulation of 1024 robots and a swarm of 100 real ones in the laboratory.

Credit: Northwestern University.

All reliably, safely and efficiently converged to form a pre-determined shape in less than a minute, the researchers report in a paper in the journal IEEE Transactions on Robotics. 

In many situations a fleet of a swarm of small robots is better than large one, because if one fails the others can complete the task. The trick is to avoid collisions and gridlock.

To do this, Rubenstein says, the new algorithm views the ground beneath the robots as a grid. By using technology similar to GPS, each robot is aware of where it sits on the grid.

Before making a decision about where to move, a robot uses sensors to communicate with its neighbours, determining whether or not nearby spaces within the grid are vacant or occupied.

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

Even with all this careful coordination, the robots are still able to communicate and move swiftly to form a shape. Rubenstein accomplishes this 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 robots interact locally to make decisions without global information.”

In Rubenstein’s swarm, for example, 100 robots can coordinate to form a shape within a minute. In some previous approaches, it could take a full hour.