via Northwestern University
For self-driving vehicles to become an everyday reality, they need to safely and flawlessly navigate one another without crashing or causing unnecessary traffic jams.
To help make this possible, Northwestern University researchers have developed the first decentralized algorithm with a collision-free, deadlock-free guarantee.
The researchers tested the algorithm in a simulation of 1,024 robots and on a swarm of 100 real robots in the laboratory. The robots 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 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 paper will be published later this month in the journal IEEE Transactions on Robotics. Rubenstein is the Lisa Wissner-Slivka and Benjamin Slivka Professor in Computer Science and Mechanical Engineering in Northwestern’s McCormick School of Engineering. He’s also a member of Northwestern’s Center for Robotics and Biosystems.
The advantage of a swarm of small robots — versus one large robot or a swarm with one lead robot — is the lack of a centralized control, which can quickly become a central point of failure. Rubenstein’s decentralized algorithm acts as a fail-safe.
“If the system is centralized and a robot stops working, then the entire system fails,” Rubenstein said. “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.”
Still, the robots need to coordinate in order to avoid collisions and deadlock. To do this, the 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, each robot uses sensors to communicate with its neighbors, 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 said. “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 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.”
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. Rubenstein imagines that his algorithm could be used in fleets of driverless cars and in automated warehouses.
“Large companies have warehouses with hundreds of robots doing tasks similar to what our robots do in the lab,” he 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.”
The Latest Updates from Bing News & Google News
Go deeper with Bing News on:
- Caesar Network perfects the traditional consensus algorithm and reshapes the trust mechanismon November 20, 2020 at 2:58 pm
It is still centralized mode in value exchange, which is resulted from the lack of trust mechanism of Internet itself. From the emergence of blockchain in 2019, human gradually transformed from ...
- Fetch.AI launches blockchain-based AI smart-city infrastructure in Munichon November 20, 2020 at 3:41 am
Fetch.ai and Datarella predict mass implementation of Munich’s smart-city infrastructure will reduce CO2 emissions by 34,000 tonnes per year.
- Hello Interoperability! Journey to the Mass Adoption of Decentralized Finance.on November 19, 2020 at 1:00 pm
Now that interoperability is no longer a problem, we have to embark on a new journey - the journey to mass adoption of decentralized finance.
- TomiEX Announces Launch of Decentralized Exchange Operating on Delegated Proof-of-Stake Algorithmon November 16, 2020 at 1:02 am
LONDON, Nov. 16, 2020 /PRNewswire/ -- The TomiEX exchange has announced that it is launching a decentralized environment for its platform on the basis of the delegated Proof-of-Stake algorithm.
- TomiEX Announces Launch of Decentralized Exchange Operating on Delegated Proof-of-Stake Algorithmon November 16, 2020 at 1:01 am
The TomiEX exchange has announced that it is launching a decentralized environment for its platform on the basis of the delegated Proof-of-Stake algorithm. The new platform launched by the TomiEX ...
Go deeper with Google Headlines on:
Go deeper with Bing News on:
- Self-Assembling Robot Swarms to Form Bridges and Buildings: The Future of Constructionon November 21, 2020 at 8:40 am
Researchers at MIT and the US Army are working on robot swarms, a bunch of mechanical metamaterials that can assemble to form any structure. The concept is simple—you open a box, and a bunch of ...
- Researchers are developing robot swarms that turn into buildings, vehicles, and moreon November 19, 2020 at 1:31 pm
There are two schools of thought when it comes to building bridges. There’s the traditional way involving humans assembling materials to create a unique structure. And then there’s the way MIT and the ...
- Army, MIT explore materials for transforming robots made of robotson November 19, 2020 at 9:18 am
Scientists from the US Army and MIT's Center for Bits and Atoms created a new way to link materials with unique mechanical properties, opening up the possibility of future military robots made of ...
- Swarms of Gloryon November 17, 2020 at 10:28 pm
Sooner or later, swarms of autonomous weapons are likely to transform militaries. But how long will they take to transform our relationship to weapons and armed violence?
- Jocasta: How Ultron's Robot Wife Evolved Into an Avengers Revolutionaryon November 15, 2020 at 5:31 pm
Jocasta is a former member of The Avengers and served as part of the Robot Revolution, but her road to heroism was not easy for the bride of Ultron.