Newswise — Algae bloom, birds flock, and insects swarm. This en masse behavior by individual organisms can provide separate and collective good, such as improving chances of successful mating propagation or providing security. Now, researchers have harnessed the self-organization skills required to reap the benefits of natural swarms for robotic applications in artificial intelligence, computing, search and rescue, and much more.
They published their method on Aug. 3 in Intelligent Computing.
“Designing a set of rules that, once executed by a swarm of robots, results in a specific desired behavior is particularly challenging,” said corresponding author Marco Dorigo, professor in the artificial intelligence laboratory, named IRIDIA, of the Université Libre de Bruxelles, Belgium. “The behavior of the swarm is not a one-to-one map with simple rules executed by individual robots, but rather results from the complex interactions of many robots executing the same set of rules.”
In other words, the robots must work together to achieve the sum goal of discrete contributions. The issue, according to Dorigo and his co-authors Dr. Valentini and Prof. Hamann, is that conventional design for individual units to achieve a collective goal is bottom up, requiring trial-and-error refinements that can be costly.
“To tackle this challenge, we propose a novel global-to-local design approach,” Dorigo said. “Our key idea is to compose a heterogenous swarm using groups of behaviorally different agents such that the resulting swarm behavior approximates a user input representing the behavior of the entire swarm.”
This composition involves selecting individual agents with predetermined behaviors that the researchers know will work together to achieve the target collective behavior. They lose the ability to locally program individual units, but according to Valentini, Hamann and Dorigo, the trade-off is worth it. They pointed to the example of a surveillance task, where a swarm may need to monitor a facility that requires more internal monitoring during the day and more external monitoring at night.
“The user provides a description of the desired swarm allocations as a probability distribution over the space of all possible swarm allocations — more agents inside during the day, more outside at night or vice versa,” Valentini said.
The user would define the target behavior by changing the number and position of distribution’s modes, with each mode corresponding a specific allocation, such as 80% of agents inside, 20% outside during the day and 30% inside, 70% outside at night. This allows the swarm to change behavior periodically and autonomously, predetermined by the set modes, as circumstances change.
“While it is hard to find the exact control rules for robots so that the swarm behaves as we wish, a desired swarm behavior can be obtained by combining different sets of control rules that we already understand,” Dorigo said. “Swarm behaviors can be designed macroscopically by mixing robots of different pre-defined rule sets.”
This isn’t the first time Dorigo has turned to nature to improve computer science approaches. He previously developed the ant colony optimization algorithm, based on how ants navigate between their colonies and food sources, to solve difficult computing problems that involve finding a good approximation of an optimal path on a graph. While Dorigo first proposed this approach for a relatively simple problem, it has since evolved as a means to address a variety of problems. Dorigo said he plans to take the swarm methodology in a similar direction.
“Our immediate next step is to demonstrate the validity of our methodology across a larger set of swarm behaviors and move beyond task allocation,” Dorigo said. “Our ultimate goal is to understand what makes this possible, formalizing a generic theory to allow researchers and engineers to design swarm behaviors without going through the painstaking trial-and-error process.”
Gabriele Valentini, scientific collaborator of IRIDIA, and Heiko Hamann, professor in the Institute of Computer Engineering at the University of Lübeck, Germany, co-authored this paper.
The European Research Council and the Belgian Fonds de la Recherche Scientifique partially supported this work.