Swarm Approaches for the Patrolling Problem, Information Propagation vs. Pheromone Evaporation

This paper deals with the multi-agent patrolling problem in unknown environment using two collective approaches exploiting environmental dynamics. After specifying criteria of performances, we define a first algorithm based only on the evaporation of a pheromone dropped by reactive agents (EVAP). Then we present the model CLInG [10] proposed in 2003 which introduces the diffusion of the idleness of areas to visit. We systematically compare by simulations the performances of these two models on growing- complexity environments. The analysis is supplemented by a comparison with the theoretical optimum performances, allowing to identify topologies for which methods are the most adapted.