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).
Type de document :
Communication dans un congrès
Third IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'09), Sep 2009, San Francisco, United States. IEEE, pp.61-70, 2009, Proceedings of the third IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'09). 〈10.1109/SASO.2009.39〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00429571
Contributeur : Olivier Buffet <>
Soumis le : mardi 3 novembre 2009 - 15:16:09
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50

Lien texte intégral

Identifiants

Collections

Citation

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. IEEE, pp.61-70, 2009, Proceedings of the third IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'09). 〈10.1109/SASO.2009.39〉. 〈inria-00429571〉

Partager

Métriques

Consultations de la notice

236