Swarm Behavior and Artificial Intelligence, Part 2

Stephen DeAngelis

May 30, 2012

In the first segment of this two-part series on swarm behavior and artificial intelligence, I presented some groundwork for why research in this area is important. In this post, I discuss how this research is being actively applied to real-world challenges. I think that most people are fascinated by what insects working together can accomplish. An article in The Economist asserts, “Mimicking the behaviour of ants, bees and birds started as a poor man’s version of artificial intelligence. It may, though, be the key to the real thing.” [“Riders on a swarm,” 12 August 2010] The article continues:

“One of the bugaboos that authors of science fiction sometimes use to scare their human readers is the idea that ants may develop intelligence and take over the Earth. The purposeful collective activity of ants and other social insects does, indeed, look intelligent on the surface. An illusion, presumably. But it might be a good enough illusion for computer scientists to exploit. The search for artificial intelligence modelled on human brains has been a dismal failure. AI based on ant behaviour, though, is having some success. Ants first captured the attention of software engineers in the early 1990s. A single ant cannot do much on its own, but the colony as a whole solves complex problems such as building a sophisticated nest, maintaining it and filling it with food.”

Although individual members of a colony, hive, or swarm may not be particularly bright, or know the larger purpose behind their individual acts, together they have what scientists are calling “swarm intelligence.” For example, some years ago scientists figured out that ants very quickly figure out the shortest possible route between a food source and their nest by marking and following a chemical trail of pheromones. The article explains:

“When an ant finds food, she takes it back to the nest, leaving behind a pheromone trail that will attract others. The more ants that follow the trail, the stronger it becomes. The pheromones evaporate quickly, however, so once all the food has been collected, the trail soon goes cold. Moreover, this rapid evaporation means long trails are less attractive than short ones, all else being equal. Pheromones thus amplify the limited intelligence of the individual ants into something more powerful.”

The article goes on to note that scientists, like Marco Dorigo, a researcher at the Free University of Brussels, have been able to create “a whole family of algorithms, which have been applied to many practical questions” based upon computer simulations of how ants optimize their activities. One practical application is solving the so-called travelling-salesman problem. The article describes the problem:

“Given a list of cities and their distances apart, the salesman must find the shortest route needed to visit each city once. As the number of cities grows, the problem gets more complicated. A computer trying to solve it will take longer and longer, and suck in more and more processing power. The reason the travelling-salesman problem is so interesting is that many other complex problems, including designing silicon chips and assembling DNA sequences, ultimately come down to a modified version of it.”

The article reports that the results of work conducted by researchers, like Dorigo, have been successfully applied in the field of logistics. It continues:

“Migros, a Swiss supermarket chain, and Barilla, Italy’s leading pasta-maker, both manage their daily deliveries from central warehouses to local retailers using AntRoute. This is a piece of software developed by AntOptima, a spin-off from the Dalle Molle Institute for Artificial Intelligence in Lugano (IDSIA), one of Europe’s leading centres for swarm intelligence. Every morning the software’s ‘ants’ calculate the best routes and delivery sequences, depending on the quantity of cargo, its destinations, delivery windows and available lorries. According to Luca Gambardella, the director of both IDSIA and AntOptima, it takes 15 minutes to produce a delivery plan for 1,200 trucks, even though the plan changes almost every day.”

The article goes on to explain that “ant-like algorithms have also been applied to the problem of routing information through communication networks.” The results have been impressive. According to the article, “In computer simulations and tests on small-scale networks, AntNet has been shown to outperform existing routing protocols.” Finding the shortest route between points is not the only reason that swarms form or behave as they do. The article explains:

“Routing, of both bytes and lorries, is what mathematicians call a discrete problem, with a fixed, albeit large, number of solutions. For continuous problems, with a potentially infinite number of solutions—such as finding the best shape for an aeroplane wing—another type of swarm intelligence works better. Particle swarm optimisation (PSO), which was invented by James Kennedy and Russell Eberhart in the mid 1990s, is inspired more by birds than by insects.”

The article reports that “there are now about 650 tested applications of PSO, ranging from image and video analysis to antenna design, from diagnostic systems in medicine to fault detection in industrial machines.” The article indicates that the algorithms that have been created through swarm research are moving from the virtual to the real word. It continues:

“Dr Dorigo is now working on something that can act as well as think: robots. A swarm of small, cheap robots can achieve through co-operation the same results as individual big, expensive robots—and with more flexibility and robustness; if one robot goes down, the swarm keeps going. … His ‘Swarmanoid’ project … is based on three sorts of small, simple robot, each with a different function, that co-operate in exploring an environment. Eye-bots take a look around and locate interesting objects. Foot-bots then give hand-bots a ride to places identified by the eye-bots. The hand-bots pick up the objects of interest. And they all run home. All this is done without any pre-existing plan or central co-ordination. It relies on interactions between individual robots. According to Dr Dorigo, bot-swarms like this could be used for surveillance and rescue—for example, locating survivors and retrieving valuable goods during a fire.”

If you want a better idea of how robot swarms can work together and the potential they hold, watch the following video of Professor Vijay Kumar’s presentation at TED2012.

The article from The Economist reports that “Dr Dorigo’s group has … developed a system to allow robots to detect when a swarm member is malfunctioning. This was inspired by the way some fireflies synchronise their light emissions so that entire trees flash on and off. The robots do the same, and if one light goes out of synch because of a malfunction the other bots can react quickly, either isolating the maverick so that it cannot cause trouble, or calling back to base to have it withdrawn.” The article states that all of these developments are encouraging but wonders if these interesting developments are getting us any closer to understanding the human mind. It concludes:

“Anyone who is really interested in the question of artificial intelligence cannot help but go back to the human mind and wonder what is going on there—and there are those who think that, far from being an illusion of intelligence, what Dr Dorigo and his fellows have stumbled across may be a good analogue of the process that underlies the real thing. For example, according to Vito Trianni of the Institute of Cognitive Sciences and Technologies, in Rome, the way bees select nesting sites is strikingly like what happens in the brain. Scout bees explore an area in search of suitable sites. When they discover a good location, they return to the nest and perform a waggle dance (similar to the one used to indicate patches of nectar-rich flowers) to recruit other scouts. The higher the perceived quality of the site, the longer the dance and the stronger the recruitment, until enough scouts have been recruited and the rest of the swarm follows. Substitute nerve cells for bees and electric activity for waggle dances, and you have a good description of what happens when a stimulus produces a response in the brain. Proponents of so-called swarm cognition, like Dr Trianni, think the brain might work like a swarm of nerve cells, with no top-down co-ordination. Even complex cognitive functions, such as abstract reasoning and consciousness, they suggest, might simply emerge from local interactions of nerve cells doing their waggle dances. Those who speak of intellectual buzz, then, might be using a metaphor which is more apt than they realise.”

Researchers continue to confirm that complex behaviors can result when a few simple rules are put in place. Studying swarm intelligence may or may not bring us closer to understanding the human mind; but it, undoubtedly, will continue to be studied and new uses for the algorithms that result will surely be found.