Auto-organisation dans les algorithmes fourmis pour la patrouille multi-agent

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
Résumé : Nous considérons ici la patrouille multi-agent comme la tâche, pour un groupe d'agents, de visiter l'ensemble des cellules d'un environnement de manière répétée et aussi regulièrement que possible. Wagner et al. (1999) ont introduit les algorithmes fourmis pour la patrouille, dans lesquels chaque agent peut seulement marquer son environnement et s'y déplacer en fonction de ses perceptions locales. Parmi divers résultats, il a été observé expérimentalement que, pour certains algorithmes, les agents s'auto-organisent souvent en cycles stables, lesquels sont proche de l'optimum en termes de fréquence de visite. Cette propriété garantie la performance a long terme de la patrouille. Le présent article se focalise sur le comportement de convergence d'un algorithme fourmi typique, EVAW (Wagner et al., 1999; Glad et al., 2008). Notre principale contribution est la preuve théorique de l'auto-organisation du groupe d'agents en cycles sous certaines hypothèses. Ces hypothèses reposent sur certains détails d'implémentation qui permettent de contrôler la prédictibilité du système. En plus de ces résultats qualitatifs sur le comportement de convergence, nous cherchons à évaluer expérimentalement ses caractéristiques. Ceci a amené à une seconde contribution : un algorithme détectant les régimes permanents. Finalement, nous proposons un algorithme amélioré qui accélère fortement le processus d'auto-organisation et nous permet ainsi de conduire des expérimentations sur de plus grands problèmes (en termes de taille et de nombre d'agents).
Type de document :
Communication dans un congrès
Olivier Sigaud. journées francophones planification, décision, apprentissage pour la conduite de systèmes (JFPDA'09), Jun 2009, Paris, France. 14 p, 2009
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00429564
Contributeur : Olivier Buffet <>
Soumis le : mardi 3 novembre 2009 - 18:57:23
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50
Document(s) archivé(s) le : jeudi 17 juin 2010 - 17:47:09

Fichier

jfpda09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00429564, version 1

Collections

Citation

Arnaud Glad, Olivier Buffet, Olivier Simonin, François Charpillet. Auto-organisation dans les algorithmes fourmis pour la patrouille multi-agent. Olivier Sigaud. journées francophones planification, décision, apprentissage pour la conduite de systèmes (JFPDA'09), Jun 2009, Paris, France. 14 p, 2009. 〈inria-00429564〉

Partager

Métriques

Consultations de la notice

315

Téléchargements de fichiers

114