Connect with us

Hi, what are you looking for?

swarming robot algorithm

Autonomous Vehicles

Algorithm Could Prevent Autonomous Cars From Bumping Into Things — Like Other Cars

Researchers at Northwestern University have created an algorithm that keeps robots from bumping into each other. It could be used in autonomous cars and automated warehouses.

Researchers at Northwestern University have devised an algorithm that keeps robots from bumping into each other. The program could help autonomous cars avoid traffic jams and make automated warehouses operate more efficiently. Here’s the abstract of the study published February 17 in the journal IEEE Transactions on Robotics.

The task of shape formation in robot swarms can often be reduced to two tasks—assigning goal locations to each robot and creating a collision-free path to that goal. In this article, we present a distributed algorithm that solves these tasks concurrently, enabling a swarm of robots to move and form a shape quickly and without collision. A user can specify a desired shape as an image, send that to a swarm of identically programmed robots, and the swarm will move all robots to goal locations within the desired shape. This algorithm was executed on a swarm of up to 1024 simulated robots and a swarm of 100 real robots, showing that it reliably converges to all robots forming the shape.

“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,” the researchers say. “To help make this possible, [we] have developed the first decentralized algorithm with a collision-free, deadlock-free guarantee.”

The algorithm has been successfully tested in a simulation of 1,024 robots and in a swarm of 100 real robots in the laboratory. The robots reliably, safely, and efficiently converged to form a predetermined shape in less than a minute. Check out the video below in which the robots form the letters NU to celebrate their prowess.

“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,” says lead researcher Michael Rubenstein. “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 advantage of using a swarm of small robots instead of 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. “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. If one robot fails in a swarm, the swarm can still accomplish the task,” Rubenstein says.

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

The algorithm limits how far away each robot can communicate with other robots. “Each robot can only sense three or four of its closest neighbors,” Rubenstein explains. “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.”

Using the algorithm, 100 robots can coordinate to form a shape within a minute. In some previous approaches, the same process could take as much as an 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 says. “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 principle relies on the robots being connected to each other over a wireless network instead of using radar, cameras, and ultrasonic sensors the way most self-driving systems do today. Connected cars can also interface with traffic signals to speed traffic flow in places where congestion is a common problem. Perhaps an algorithm such as this could make Level 5 autonomous cars feasible sooner than expected.

Sign up for daily news updates from CleanTechnica on email. Or follow us on Google News!

Have a tip for CleanTechnica, want to advertise, or want to suggest a guest for our CleanTech Talk podcast? Contact us here.

Former Tesla Battery Expert Leading Lyten Into New Lithium-Sulfur Battery Era — Podcast:

I don't like paywalls. You don't like paywalls. Who likes paywalls? Here at CleanTechnica, we implemented a limited paywall for a while, but it always felt wrong — and it was always tough to decide what we should put behind there. In theory, your most exclusive and best content goes behind a paywall. But then fewer people read it! We just don't like paywalls, and so we've decided to ditch ours. Unfortunately, the media business is still a tough, cut-throat business with tiny margins. It's a never-ending Olympic challenge to stay above water or even perhaps — gasp — grow. So ...
If you like what we do and want to support us, please chip in a bit monthly via PayPal or Patreon to help our team do what we do! Thank you!
Written By

Steve writes about the interface between technology and sustainability from his home in Florida or anywhere else The Force may lead him. He is proud to be "woke" and doesn't really give a damn why the glass broke. He believes passionately in what Socrates said 3000 years ago: "The secret to change is to focus all of your energy not on fighting the old but on building the new."


You May Also Like

Autonomous Vehicles

I read the book titled Killing Sophia — Consciousness, Empathy, and Reason in the Age of Intelligent Robots by Thomas Telving, with whom I...

Autonomous Vehicles

Want to run a robotaxi in Seattle? You'll need $5 million in insurance!

Autonomous Vehicles

GM's Robotaxi Service Starts Work in Tesla's Back Yard

Clean Power

Solar power is sending robots off to duty on harbor clean-up and other environmental chores.

Copyright © 2023 CleanTechnica. The content produced by this site is for entertainment purposes only. Opinions and comments published on this site may not be sanctioned by and do not necessarily represent the views of CleanTechnica, its owners, sponsors, affiliates, or subsidiaries.