Skip to Main content Skip to Navigation
Conference papers

Self-Organization of Patrolling-Ant Algorithms

Arnaud Glad 1 Olivier Buffet 1 Olivier Simonin 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We consider here multi-agent patrolling as the task for a group of agents to repeatedly visit all the cells of a discrete environment. Wagner et al. (1999) have introduced patrolling ant algorithms, where each agent can only mark and move according to its local perception of the environment. Among various results, it has been experimentally observed that for some algorithms the agents often self-organize in stable cycles which are near optimal in terms of visit frequency. This property is particularly interesting as it guarantees the long-term performance of the patrol. The present paper focuses on the convergence behavior of a typical ant-based algorithm, EVAW. The main contribution of this paper is to theoretically prove that the group of agents self-organizes in cycles under certain hypotheses. These hypotheses rely on some implementation details that allow to control the predictability of the system. In addition to these qualitative results on the convergence behavior, we aim at experimentally evaluating its characteristics. This led us to a second contribution: an algorithm that detects steady states. Finally, we propose an improved behavior that dramatically speeds up the self-organization and allows us to experiment on larger problems (both in terms of size and number of agents).
Complete list of metadatas
Contributor : Olivier Buffet <>
Submitted on : Tuesday, November 3, 2009 - 3:16:09 PM
Last modification on : Thursday, January 11, 2018 - 6:19:50 AM




Arnaud Glad, Olivier Buffet, Olivier Simonin, François Charpillet. Self-Organization of Patrolling-Ant Algorithms. Third IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'09), Sep 2009, San Francisco, United States. pp.61-70, ⟨10.1109/SASO.2009.39⟩. ⟨inria-00429571⟩



Record views