It’s never too late to learn about the birds and the bees. Particularly when they can help enhance surveillance photos, quickly sort through military reports and even enable individual robots to navigate within an army of fellow automatons.
The secret behind these new research efforts derives from the basic rules of what’s known as swarm intelligence, a scientific framework inspired by the way in which birds flock together, social insects swarm and dust particles swirl in the air.
By understanding and correctly applying the rules that animals or particles use to identify and align themselves with their neighbors, Oak Ridge National Laboratory computational scientist Xiaohui Cui said swarm intelligence can yield very fast, though often approximate, solutions. Even so, for an application like identifying the best evacuation route out of a city during an emergency, “getting something quickly is perhaps more important than making sure it’s the absolute best system possible,” said Jesse St. Charles, a University of Tennessee at Chattanooga graduate student working with Cui.
The ability to quickly cluster similar entities using minimal resources also could be a boon for military analysts tasked with searching through thousands of field reports for ones relevant to a specific course of action. To that end, Cui and St. Charles are working with both the U.S. Navy and Air Force to help them better organize their documents.
The bird-flocking research underlying the duo’s current effort was initiated by other scientists in the mid-’80s, mainly as a way to produce more realistic video games. From that early work, three basic rules emerged.
“The separation rule basically keeps the birds from colliding with each other. So as they get closer, there should be a stronger repulsive force,” said St. Charles, who introduced his project earlier this year during a presentation at the annual conference of the American Association for the Advancement of Science. The second, and complementary, rule is known as the cohesion rule. “It says, ‘I don’t want to get too far away from my neighbors,’ ” he said. For the third, or alignment rule, birds gauge where their neighbors are flying and then align themselves with the group’s average heading.
A few years ago, Cui added a fourth rule, which states that birds should only flock with the same species. For their database-sorting algorithm to work, documents should likewise clump only with those that are similar enough to be considered, say, another mallard instead of a Canada goose. To determine whether documents really are birds of a feather, a database is first stripped of non-meaningful words and word endings. Each raw document is then analyzed for the frequency of remaining terms, resulting in an ID that its neighboring documents can use to assess their relatedness.
“What we’ve done is set up a virtual two-dimensional space like a game board,” St. Charles said. “We randomly position these documents at the beginning, and randomly assign them a direction to fly in. Each document will fly in whatever direction for a small distance. And they will ask, ‘Who is nearby me?’ They look at their neighbors and then apply the four rules to the documents by them.”
After a few hundred steps around the board, similar documents find each other and become locked in the same flocking pattern. And because they don’t have to apply the rules to every document in the database, St. Charles said, the system is much speedier than other aggregators.
On average, the duo deals with about 3,000 to 10,000 documents and normally ends up with around eight to 10 main clusters. The system also preserves indirect relationships that might be lost with other methods requiring a document that pertains to airlines, defense contracts and Senate policy to be stored under a single subject heading.
Aladdin Ayesh, coordinator for the Intelligent Mobile Robots and Creative Computing Research Group at De Montfort University in the United Kingdom, said his team’s innovation relies instead on a simple swarm intelligence that treats every pixel of a digital photo like a member of a swirling mass of particles, with a specific speed and direction.
With each new position, every pixel essentially uses a set of rules to look at where it is, where it might go next, and whether a new direction will leave it better or worse off in relation to its neighbors. By repeating that basic decision-making process many times, the pixels organize themselves in a way that enhances a whole image by improving its contrast.
“The good thing about this type of algorithm is that the particle only has a velocity and a direction and you only have rules that tell the particle where to move and rules that tell it what is a good position or bad position,” Ayesh said. Again, the simplicity means the computation can be done with limited resources.
He and two collaborators at Jordan’s Al-Balqa Applied University found that, at best, their contrast-sharpening method can outperform other techniques. At worst, the strategy they published in a recent issue of the International Journal of Innovative Computing and Applications was roughly equivalent, but only required a fraction of the computational energy. Eventually, Ayesh said, it could be incorporated into a suite of photo-editing applications or called upon to search for items of interest within grainy surveillance videos, especially items that might otherwise blend in with the foreground or background.
For another project, Ayesh and a graduate student assembled a group of firefighting robots and sent them off in the direction of a blaze (in a simulator, anyway). As with the project by Cui and St. Charles, the robots were governed by flocking rules that kept them from venturing too close or too far away from each other while moving in the same general heading. Varying the rule definitions led to different group behaviors. Tweaking the group’s relative cohesion, for example, changed whether a lost or stuck robot effectively delayed the entire team.
Eventually, the researchers found that a group of about 50 robots worked best for a task that might, in real life, require the rapid deployment of a search-and-rescue or firefighting team that wouldn’t be undermined by the loss of a few units. Encouragingly, when the scientists imported their control and communication software into a handful of real robots, the system worked as expected. In addition, Ayesh said the research could help with the kind of computer vision advances necessary for firefighting robots to correctly identify fellow members while choosing where to aim a stream of water.
Influencing neighbors’ behavior
Tucker Balch, an associate professor in Interactive and Intelligent Computing at Georgia Institute of Technology in Atlanta, said flock-based applications such as finding similar documents in a database work by distributing little bits of intelligence across large areas. “The key insight there is really to convert the problem from a centralized compare-everything-to-everything problem into a decentralized approach,” Balch said. “They’re ascribing to each paper a little bit of autonomy.”
As with the method’s original inspirations, “the general idea is that each insect or animal can perceive and react to what it sees locally,” said Balch, who co-directs Georgia Tech’s “Borg Lab,” an interdisciplinary effort named in honor of the collective-minded villains of “Star Trek” fame.
No individual fully grasps the entire problem, whether the task is to defend a hive or migrate in a coordinated fashion, he said. But by acting on its own senses within its immediate surroundings, each animal influences its neighbors’ behavior. Magnified across a large flock or swarm, “you get a global behavior of the whole system that can appear intelligent.”
In other words, the sum is greater than its parts.
The end result isn’t guaranteed to be the best solution, he cautioned. “The idea is that you get a fairly good solution fairly quickly, as opposed to no solution or maybe the optimal solution but it takes a long, long time.” Even so, for many applications, he said, “you need a fast solution, not necessarily the optimal solution.”
Unlike the famous “I Love Lucy” episode when Lucy and Ethel’s assembly line job wrapping chocolates ends in a comical disaster, the collective intelligence of wasps has inspired other researchers to develop a formulation that efficiently assigns cars to different painting stations as they continuously roll off the assembly line.
And like Ayesh’s bird-inspired simulation of firefighting robots, Balch said animal-based solutions lack a central point of failure — a fatal weakness of the droid-controlling ship on “Star Wars Episode I: The Phantom Menace,” which is finally torpedoed by Anakin Skywalker, the movie’s young hero. The result? An entire droid army falls over.