Prevention of Ant Mills in Pheromone-Based Search Algorithm for Robot Swarms

Abstract

Computer scientists use animal-based phenomenon as source of inspiration to develop swarm algorithm and simulate their behaviors. One example is ants foraging. For finding food the ants are moving randomly in any direction. After they found food, they spread pheromones to make it easy for other ants to find it. The more ants, the better the pheromone trail. This pheromone-based search algorithm should increase the efficiency of food delivery. However, this phenomenon includes a problem termed ant mill, which is well known. An ant mill is happening when many ants are spreading their pheromones in a closed area. This causes an overlapping of the pheromones and creates a circle trail. Consequently, the ants move in a never-ending loop without ever reaching the food source. The result is starvation and death. In this paper, we take a closer look at three types of search algorithms. Especially pheromone-based searching algorithm, which creates ant mills and provide a solution to overcome them. Our evaluation shows that a pheromone-based search algorithm with ant mill prevention brings a significantly better food delivery.