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

12 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

air dissecant said...

black mold exposureblack mold symptoms of exposurewrought iron garden gatesiron garden gates find them herefine thin hair hairstylessearch hair styles for fine thin hairnight vision binocularsbuy night vision binocularslipitor reactionslipitor allergic reactionsluxury beach resort in the philippines

afordable beach resorts in the philippineshomeopathy for eczema.baby eczema.save big with great mineral makeup bargainsmineral makeup wholesalersprodam iphone Apple prodam iphone prahacect iphone manualmanual for P 168 iphonefero 52 binocularsnight vision Fero 52 binocularsThe best night vision binoculars here

night vision binoculars bargainsfree photo albums computer programsfree software to make photo albumsfree tax formsprintable tax forms for free craftmatic air bedcraftmatic air bed adjustable info hereboyd air bedboyd night air bed lowest pricefind air beds in wisconsinbest air beds in wisconsincloud air beds

best cloud inflatable air bedssealy air beds portableportables air bedsrv luggage racksaluminum made rv luggage racksair bed raisedbest form raised air bedsaircraft support equipmentsbest support equipments for aircraftsbed air informercialsbest informercials bed airmattress sized air beds

bestair bed mattress antique doorknobsantique doorknob identification tipsdvd player troubleshootingtroubleshooting with the dvd playerflat panel television lcd vs plasmaflat panel lcd television versus plasma pic the bestThe causes of economic recessionwhat are the causes of economic recessionadjustable bed air foam The best bed air foam

hoof prints antique equestrian printsantique hoof prints equestrian printsBuy air bedadjustablebuy the best adjustable air bedsair beds canadian storesCanadian stores for air beds

migraine causemigraine treatments floridaflorida headache clinicdrying dessicantair drying dessicantdessicant air dryerpediatric asthmaasthma specialistasthma children specialistcarpet cleaning dallas txcarpet cleaners dallascarpet cleaning dallas

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.

Anonymous said...

Fashion lovers from various areas of the globe admire this classiness of such gorgeous exploring flats. [url=http://www.isabelmarantshoes.co.uk/]isabelmarantshoes.co.uk[/url] is a masterpiece of shoe-making. The sneakers isabel marant 2012 have passed away alongside more and more with great and decent popularity. celebrities wearing isabel marant shoes is definitely the major you for sporting activities! [url=http://www.isabelmarantshoes.co.uk/#0325]isabel marant shoe[/url] are always giving surprises to every customer, within new elements adding to the shoes, you can pick the style which is adorned with eye-catching fringe details, low wedge subtly also gained to perfect it's entirety look. We provide you with massive volume designer Also You can buy the top quality and huge [url=http://www.isabelmarantshoes.co.uk/#9305]isabel marant wedge sneakers tumblr[/url].


Name: isabel marant bekket high-top sneaker

SKU: Isabel Marant 13721
Brand: Isabel Marant
site: http://www.isabelmarantshoes.co.uk/sticker-sneakers-c-2.html#81212
Isabel Marant Shoes UK's Mission
sneakers isabel marant 2012
To provide one-stop sercvice and point-to-point trade solution for our worldwide customers.
isabel marant sneakers fall 2012
To reach 100% customer satisfactory.
isabel marant sneaker
To offer cost-effective trade services.
isabel marant betty sneakers uk
To maximize our international buyer's competitiveness and profitability.