One of a number of benefits promised by a future in which cars drive themselves is less congestion, with advanced autonomous vehicles being so adept at navigating the streets that they not only avoid slamming into each other, but keep traffic flowing much more smoothly than humans ever could. Researchers at Northwestern University have come up with a novel control algorithm they say offers this type of traffic-free guarantee, demonstrating its capabilities via a swarm of tiny robots that can safely and swiftly assemble into desired shapes within 60 seconds.
The Northwestern University scientists describe their new control software as the first decentralized algorithm with a collision- and deadlock-free guarantee. This leverages the benefits of working with swarms of small robots where there is no centralized control, rather than a pack with a lead robot or a single larger robot, spreading the risk of failure across the entire fleet and shoring up the dependability of the system.
"If the system is centralized and a robot stops working, then the entire system fails," says 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 views the terrain as a grid, and each of the robots is equipped with GPS-like sensors to know where they are on the grid at any given time. Other sensors enable the robots to identify nearby robots and know whether spaces on the grid are available or occupied by a neighbor.
"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."
This near-sighted approach enables the robots to move far more quickly to form a desired shape. In the team's experiments, 100 robots were able to assemble into a pre-determined formation within a minute, while its says previous approaches have required up to one hour. They also tested out the approach in simulations involving more than 1,000 robots, with the virtual machines safely and efficiently moving into formation.
"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 Northwestern's Michael Rubenstein, who led the study. "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."
The research was published in the journal IEEE Transactions on Robotics, while you can see the swarms in action in the video below.
Source: Northwestern University
