Algorithm lets swarms of robots work together to create shapes without colliding

Shape Formation in Homogeneous Swarms Using Local Task Swapping

The idea of swarms of comparatively low-cost robots that are able to work together to pull off feats that single large robots are unable to do is pretty exciting. But getting large numbers of robots to carry out coordinated activities without bumping into one another is hard work. The challenge of achieving this is one reason why swarm robotics remains a work in progress, rather than something that is routinely seen in the real world.

Researchers at Northwestern University, in Evanston, Illinois, recently achieved an impressive demonstration, however. They have developed and tested an algorithm for a decentralized swarm of robots which lets them reliably, safely, and efficiently converge to form a predetermined shape in under a minute. The researchers have shown that their algorithm works both on a simulation of 1,024 robots and on a swarm of 100 real robots in a laboratory. Impressively, the robots are able to perform their shape-throwing without getting in one another’s way. That’s easier said than done.

“The robots are given a set of goal points that represent the shape to be formed and they have to figure out as a group which robot goes to which goal, and how do they get there with no collisions,” Mike Rubenstein, assistant professor of computer science and mechanical engineering, told Digital Trends. “The main idea of the controller is that, whenever a robot senses another robot, they check to see if swapping goal locations will reduce the total distance traveled by the pair. If so, they swap goals. A side effect of this behavior is that they will automatically avoid collisions.”

Robots rearranging themselves into giant shapes, such as letters, sounds like it might have limited usefulness. (Automated cheerleaders at future robot sports games?) However, Rubinstein said that this system could actually be applied in a broad range of possible applications. Scenarios in which robots adhering to a specific formation is important could be useful for everything from teaming up to carry objects to, potentially, forming together like the Power Rangers’ Megazord to establish larger modular self-configurable robots.

“The hope is that by avoiding a centralized system, the swarm behavior can more easily scale to large numbers, and is more robust to individual failures,” he said.

This approach isn’t perfect in every scenario, though. “A centralized approach can usually provide more efficient motion, and is easier to guarantee good behaviour when all the robots are working as desired,” Rubenstein explained. “A more centralized approach would be better in cases of small swarms.”

A paper describing the work was recently published in the journal IEEE Transactions on Robotics.

Editors' Recommendations