Ant foraging and minimal paths in simple graphs

Ants are known to be able to find paths of minimal length between the nest and food sources. The deposit of pheromones while they search for food and their chemotactical response to them has been proposed as a crucial element in the mechanism for finding minimal paths. We investigate both individual and collective behavior of ants in some simple networks representing basic mazes. The character of the graphs considered is such that it allows a fully rigorous mathematical treatment via analysis of some markovian processes in terms of which the evolution can be represented. Our analytical and computational results show that in order for the ants to follow shortest paths between nest and food, it is necessary to superimpose to the ants' random walk the chemotactic reinforcement. It is also needed a certain degree of persistence so that ants tend to move preferably without changing their direction much. It is also important the number of ants, since we will show that the speed for finding minimal paths increases very fast with it.
Comment: 39 pages, 13 figures