Decentralized algorithm developed for collision-free driving

Posted Feb 27, 2020 by Tim Sandle
Autonomous car technology continues to advance but the risk of crashes remains ever-present. To combat this, researchers have been experimenting with swarming robots, which are designed to teach vehicles to avoid collisions.
A driverless bus was recently tested at Tokyo's Haneda Airport and some driverless taxi service...
A driverless bus was recently tested at Tokyo's Haneda Airport and some driverless taxi services aim to be fully functional in time for the 2020 Olympics
Toshifumi KITAMURA, AFP/File
It is hoped that the newly-developed algorithm will help to control future self-driving cars and play a part in the operation of automated warehouses and robotic systems. This expectation has risen following some successful tests with swarming robots. Swarm robotics refers to the coordination of multiple robots as one system, formed of large numbers of simple physical machines.
To test out the robots, the research team, from Northwestern University, built what is said to be the first decentralized algorithm that comes with a collision-free and deadlock-free guarantee. This algorithm was used to control the robots. To qualify the status, the algorithm was first tried out using a simulation. This exercise modelled what would happen with 1,024 robots.
Following this, the algorithm was assessed by using a swarm of 100 autonomous robots under laboratory conditions. This trial indicated that the robots could reliably, safely and efficiently converge to form any pre-determined shape, coming together from different spatial locations in under one minute.
According to lead scientist Michael Rubenstein there was a key purpose to this exercise: "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."
What is especially important is absence of a centralized control point. By using a decentralized process (where each robot is independent) the risk of there being a central point of failure is removed. With the experiment this means that if an individual robot fails to swarm, the collective still completes its task. Applying this concept to an autonomous car, this means that if one component fails the car will still brake or swerve to avoid a collision.
As to how the robots are coordinated, the algorithm focuses on the ground, viewing this as a grid. the algorithm then uses technology equivalent to GPS to send signals to each robot, so that each individual entity becomes aware of its place on the grid.
To avoid robots from colliding, but also avoiding information overload, each robot has the ability to sense other robots but this is restricted to each individual robot only being able to sense three or four of the closest robots.
The development of the algorithm has been published in the journal IEEE Transactions on Robotics. The research paper is titled "Shape Formation in Homogeneous Swarms Using Local Task Swapping."