Mathematical Modeling and Convergence Analysis of Trail Formation

Sameena Shah, Ravi Kothari, Jayadeva, Suresh Chandra

An ant deposits pheromone along the path that it travels and is more likely to choose a path with a higher concentration of pheromone. The sensing and dropping of pheromone makes it easy to understand the trail forming behavior of ants. The reinforcement tendency of pheromone following behavior ensures selection of the shortest path from a set of paths. The reinforcement tendency 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 \textit{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 understanding how to build scalable systems that evolve to solve complex problems (e.g. point covering or the traveling salesman problem) without the necessity of central command-and-control.

Subjects: 1.2 Artificial Life; 7.1 Multi-Agent Systems

Submitted: Apr 14, 2008


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.