Mathematical Modeling and Convergence Analysis of Trail Formation

Abstract

An ant deposits pheromone along the path that it travels and is more likely to choose a path with a higher con-centration of pheromone. The sensing and dropping of pheromone makes it easy to understand the trail form-ing behavior of ants. The reinforcement tendency of pheromone following behavior ensures selection of the shortest path from a set of paths. The reinforcement ten-dency of pheromone following behavior also ensures a biased selection of the initially followed paths over a path, which is shorter but discovered through chance at a later point in time. Under what conditions and limits can this initial bias be reversed? In this paper, we answer this question based on a theoretical analysis of the trail forming behavior of ants. We believe our results to contribute to the overall area of understand-ing how to build scalable systems that evolve to solve complex problems (e.g. point covering or the travel-ing salesman problem) without the necessity of central command-and-control.