Saturday, September 23, 2006

Learning from the humble ant

The next time you're outdoors and you see a trail of marching ants, try a little experiment. Place an obstruction asymmetrically in their path, which is steep enough that they can't climb over it, and see what happens. At first, they would spread out equally in both directions to rejoin the trail. Over a period of time, you'll see the longer trail thin out and disappear as all the ants start taking the shorter trail.

What's really remarkable about this is that ants cannot see and cannot talk. That is to say, they lack the sensory organs for sight and sound. So how do they do this job of finding a short route around obstacles to their target food source?

The secret, as with many other things observed in nature, is elegant in its simplicity and inventiveness. Ants have a very good sense of smell, and lay out a class of chemicals called Pheromones to mark their trail. Each ant lays out roughly the same amount of pheromone for a particular food source, and the pheromone evaporates at a constant rate. When an ant moves towards a marked food source, it tends to move in a direction in which it senses a relatively higher concentration of pheromone.

That's all. If you're puzzled as to why I cut the explanation short, take a minute to think about how this would work and then read on. Now, when the obstacle is placed in the path, the ants can no longer sense the correct direction to travel, and they choose at random among the available directions. Ultimately, they would rejoin the trail, but each ant has now laid pheromone along the path it has taken. Initially, there is little to choose from between the two options, but over a period of time, the shorter path, simply by virtue of being shorter, would have a greater number of ants traversing the path back and forth. This means that the evaporating pheromone on the shorter route gets regenerated more often than on the longer route, causing more ants to choose that direction over the other. This further increases the disparity in pheromone level between the two choices, until there is insufficient pheromone on the longer trail to tempt even a single ant to go in that direction.

This kind of a process is called Auto-Catalytic, meaning it speeds itself up. Some time around 1990, an Italian scientist called Marco Dorigo got a brainwave on how to use this ant behaviour to solve combinatorial optimization problems, which are notoriously difficult to solve with conventional mathematical techniques.

What he did was to represent an optimization problem as a set of obstacles in the path of an ant trail. The decision of which direction to take at an obstacle represented the decision of what value to assign to a variable. In other words, if a variable can take four different values, it is like placing an obstacle giving an ant four different paths around it. Each variable in the problem is equivalent to an obstacle on the trail. "Pheromone concentrations" are maintained virtually for each decision at each obstacle.

The generation of a solution is done randomly, with the probability of taking a particular decision being proportional to the virtual pheromone concentration. Then, the "goodness" of the solution is quantified by the objective function, and this is analogous to the distance traveled to reach the food source by that route. If it is a poor solution, it is a long route and the pheromone concentrations along that route are increased by a small value. If it is a good solution, the pheromone concentrations are increased by a higher value; and all the time, pheromone is "evaporated" at a constant rate at every decision point.

It worked. In a way similar to how ants find paths, an algorithm known as Ant Colony Optimization (ACO) was developed and refined, and although it does not always find the globally best solution, it tends to find a good solution for even large problems in reasonably quick time.

In spite of all the nature-defying technological marvels scientists and engineers come up with, there seems to be an infinite depth to the workings of nature from which we learn continually. The ant optimization algorithm is but one in a wide class of algorithms under the banner of Swarm Intelligence, for ants, bees, birds and many other social denizens of nature have unique and innovative ways of doing a plethora of tasks. Computer scientists observe, and come up with smarter algorithms. Engineers observe, and come up with better control system schemes.

How wrong we are, in talking about "humble ants". It's we who are the "humble scientists".

Links for further reading:
Marco Dorigo's page on the behaviour of real ants that inspired ACO
Wikipedia
Marco Dorigo's landmark paper on Ant Systems

10 comments:

Born a Libran said...

Very well written Prashanth. Did you know that auto geochemists are trying to look for viable autocatalytic chemical cycles under prebiotic Earth conditions to be at the heart of the Origin of life? I will try to blog about it some day. I do have the required books for it but havent read them yet. Great post again and a very good start to the science section of the blog.

Prashanth said...

That's quite a mouthful :) and no, I don't have any idea what that means, so I look forward to that post. And thanks!

Born a Libran said...

Well, okay... Prebiotic Earth conditions = conditions on Earth before life. Autocatalytic chemical cycles = Chemical cycles which autocatalyze themselves.

Sakshi said...

"there seems to be an infinite depth to the workings of nature from which we learn continually."
well... Nature did have a million or so years to wrok out the kinks. But you are right, there is so much elegance in nature's maneuvering.

Prashanth said...

Well, I figured out that much by myself... its the connection with the origin of life that I didn't get. I've read the "Primal Soup" theory, and can't identify with this one.

anish said...

Nice blog!!
i had come across an article which is not exacly related to this topic but somewhat close.
ants use internal pedometer

Mary Florence said...

Thanks for this priceless information. This will help me for my english homework as I had to look for any piece of information about any curiosity of ants. Thanks a lot!

Anonymous said...

I really like your blog and i really appreciate the excellent quality content you are posting here for free for your online readers. thanks peace claudia.

Anonymous said...

I don't understand something here. You say that after some time the shortest path, by virtue of being shorter, will be traversed by a greater number of ants. Isn't this at odds with what you just said about the ants initially choosing randomly between the paths? If the choice is random, than there is no bias between the paths, and they'll be traversed by roughly equal numbers of ants. Where exactly does the bias toward the shorter path come from?

Mabelle said...

Quite useful info, thank you for the article.