Life in Wireframe

We come back to ant algorithms and now focus on where it can be applied. The most classic problem in computional mathematics is the traveling salesman problem. The problem is simple, but yet solving it is not.

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

It's described in mathematics as a NP-complete problem, but I'll leave it up to you if you want to go down that road finding out exactly what that means. Anyone can connect every city with a single line, but how do you know if it's the shortest route? If you read the first article about ant algorithms you should get a "aha!" experince right about now. Ant algorithms or as it is also called ant optimization is perfect for these kind of problems.

Having a set of cities and X amount of ants with one task - visit each city once, you will achieve your goal simply by using the same stigmergy as when the ants collect food for their colony. The trail pattern will go from (2) to (3) and ending up as (4) as the pheromone decreases in strength on the trails with the longer distance. No real calculation, just nature finding its way.

If you are more interested in this technique and what it can do I recommend taking a look here for further studies. It's all about optimizations =)

- Tobias

Yes you read it. Ants are a good example of emergent behaivor.

Have you ever been to the woods? If so, have you ever stumbled on a ant trail? How could these little creatures with almost no brain be able to find their way from the colony, get food and find their way back again. Well, simple realy ... if you can't think it, see it than smell it - pheromones. Ants use the environment to communicate with eachother and leave local pheromone tracks when wandering about. This is called Stigmergy. Notice "local" pheromone, because a pheromone does not say anything about where the food is or where the colony is. In mathematical terms, it's just a variable with a value.

We can embody a simple set of rules which is geneticly inprinted in a "farmer" ant. When it finds food it releases a pheromone when trying to find its way back to the colony. It's follows pheromone released by searching ants, the stronger the pheromone the closer to the colony(more ants). The pheromone it releases by it self (1) is attracting other ants which leads to that more ants finds the foodsource. They than also try to find their way back to the colony, creatinga trail in the process. When finaly finding the colony and again sets of finding food it has a pheromone trail to follow back to the food, consisting of pheromones by other ants.

Hence, the ants does not know where the colony or the food is. They are simple following the pheromones. The stigmergy happens to solve the task "given" to the ants. But, and this is a big but, the pheromone left by each ant decreases in in strength by time. This makes it possible for ants to determine if a trail is "hot" or "cold". Otherwise the trail would not just be one trail, it would be many since the ants can't determine which way is the shortest between the foodsource and the colony. The trail would look like (2) in the picture, well somewhat simplified anyway. Since the pheromone decreases over time the longer trails gets lower pheromone strength the ants will more and more follow the path with shorter distance between the foodsource and the colony (3).


So, simply by following pheromones the ants form a more complex situation than anticipated. Not strictly emergent as Boids, but still a algorithm engineered by nature. This may also explain why ant colonies all of a sudden are deserted. Maybe it's simply because the food started to be so far away that all ants scattered about to god knows where and started a new colony. How exactly would be fun to speculate, but some other time ...

- Tobias