How do you prevent autonomous cars from crashing into each other, or causing unnecessary traffic jams? Northwestern University researchers believe intelligent decentralized swarm robots can provide 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. This exercise could take a full hour in some previous approaches.
“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,” said Michael Rubenstein, the Lisa Wissner-Slivka and Benjamin Slivka Professor in Computer Science in Northwestern’s McCormick School of Engineering. He is lead author of the paper that will be published later this month in the journal IEEE Transactions on Robotics, according to a 24 February release.
Why decentralized swarm robots?
The entire system fails if it is centralized and a robot stops working. In a decentralized system, however, there is no leader telling all the other robots what to do, allowing each robot to make its own decisions. Hence, “if one robot fails in a swarm, the swarm can still accomplish the task,” explains Rubenstein.
The robots need to coordinate to avoid collisions and deadlock. To do this, the algorithm views the ground beneath the robots as a grid. Each robot is aware of where it sits on the grid using technology similar to GPS.
“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.”
Rubenstein accomplishes seamless coordination 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.”
Swarm intelligence
Swarm intelligence deals with the study of self-organizing processes—both in nature and in artificial systems.
Researchers have been focusing on applying swarm intelligence techniques to the control of large groups of cooperating autonomous robots.
Ant colony optimization, for instance, has been applied to a large number of difficult discrete optimization problems including the travelling salesman problem (finding the shortest, cheapest route), scheduling, vehicle routing, etc., as well as to routing in telecommunication networks.
Similar examples
For instance, iRobot built the diminutive Ember–a mobile robotic platform that can work in a group to establish a wireless network anywhere–a decade ago. The pocket-sized tank was part of DARPA’s LANdroid program that aimed to create a fleet of these bots for less than $100.
On 22 May 2012, SHOAL, a pan-European information, communications and technology (ICT) project, part funded by the European Union, said it had successfully developed and delivered intelligent robotic fish capable of working together to detect and identify pollution in ports and other aquatic areas.
In 2014, Radhika Nagpal, Fred Kavli professor of computer science at the Harvard School of Engineering and Applied Sciences (SEAS) developed the first 1000-robot flash mob, assembled at Harvard University.
The autonomous robots arranged themselves into vast, complex shapes with the help of simple programmed rules.
Nagpal’s research group made news in Feb. 2014, too, with a group of termite-inspired robots that can collaboratively perform construction tasks using simple forms of coordination.
The Kilobots also correct their own mistakes. If a traffic jam forms or a robot moves off-course—errors that become much more common in a large group—nearby robots sense the problem and cooperate to fix it.
The kilobot robot design and software, originally created in Nagpal’s group at Harvard, were made available open-source for non-commercial use. The Kilobots have also been licensed by Harvard’s Office of Technology Development to K-Team, a manufacturer of small mobile robots.
Going forward
More recently, a group of experts wants to study the brain waves and eye movements of people playing a video game to build an advanced AI that could coordinate the actions of military robots.
The study of 25 video game players will include real-time strategy games such as StarCraft, Stellaris and Company of Heroes, according to a 10 Feb. report.
