Nav: Home

Swarming robots avoid collisions, traffic jams

February 24, 2020

EVANSTON, Ill. -- 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 in Northwestern's McCormick School of Engineering.

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."
-end-
The study, "Shape formation in homogenous swarms using local task swapping," was supported by the Alfred P. Sloan Foundation. Hanlin Wang, a Ph.D. candidate in Rubenstein's laboratory, is the paper's first author.

More news at Northwestern Now
Find experts on our Faculty Experts Hub
Follow @NUSources for expert perspectives

Northwestern University

Related Robots Articles:

Robots popular with older adults
A new study by psychologists from the University of Jena (Germany) does not confirm that robot skepticism among elder people is often suspected in science.
Showing robots how to do your chores
By observing humans, robots learn to perform complex tasks, such as setting a table.
Designing better nursing care with robots
Robots are becoming an increasingly important part of human care, according to researchers based in Japan.
Darn you, R2! When can we blame robots?
A recent study finds that people are likely to blame robots for workplace accidents, but only if they believe the robots are autonomous.
Robots need a new philosophy to get a grip
Robots need to know the reason why they are doing a job if they are to effectively and safely work alongside people in the near future.
How can robots land like birds?
Birds can perch on a wide variety of surfaces, thick or thin, rough or slick.
Soft robots for all
Each year, soft robots gain new abilities. They can jump, squirm, and grip.
The robots that dementia caregivers want: robots for joy, robots for sorrow
A team of scientists spent six months co-designing robots with informal caregivers for people with dementia, such as family members.
Faster robots demoralize co-workers
A Cornell University-led team has found that when robots are beating humans in contests for cash prizes, people consider themselves less competent and expend slightly less effort -- and they tend to dislike the robots.
Increasing skepticism against robots
In Europe, people are more reserved regarding robots than they were five years ago.
More Robots News and Robots Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

Listen Again: Reinvention
Change is hard, but it's also an opportunity to discover and reimagine what you thought you knew. From our economy, to music, to even ourselves–this hour TED speakers explore the power of reinvention. Guests include OK Go lead singer Damian Kulash Jr., former college gymnastics coach Valorie Kondos Field, Stockton Mayor Michael Tubbs, and entrepreneur Nick Hanauer.
Now Playing: Science for the People

#562 Superbug to Bedside
By now we're all good and scared about antibiotic resistance, one of the many things coming to get us all. But there's good news, sort of. News antibiotics are coming out! How do they get tested? What does that kind of a trial look like and how does it happen? Host Bethany Brookeshire talks with Matt McCarthy, author of "Superbugs: The Race to Stop an Epidemic", about the ins and outs of testing a new antibiotic in the hospital.
Now Playing: Radiolab

Dispatch 6: Strange Times
Covid has disrupted the most basic routines of our days and nights. But in the middle of a conversation about how to fight the virus, we find a place impervious to the stalled plans and frenetic demands of the outside world. It's a very different kind of front line, where urgent work means moving slow, and time is marked out in tiny pre-planned steps. Then, on a walk through the woods, we consider how the tempo of our lives affects our minds and discover how the beats of biology shape our bodies. This episode was produced with help from Molly Webster and Tracie Hunte. Support Radiolab today at Radiolab.org/donate.