Optimation par colonies de fournis d'un essaim de patrouilleurs pour la surveillance de zone

François Charpillet 1 Fabrice Lauri 2
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : RÉSUMÉ. Patrouiller dans un environnement implique une équipe d'agents dont le but consiste à visiter continuellement et aussi fréquemment que possible les lieux les plus pertinents. Afin d'obtenir des performances optimales, il est alors primordial que les agents coordonnent leurs actions. De nombreux domaines peuvent être concernés par ce problème, comme la robotique, la simulation ou les jeux vidéo. Nous adoptons dans cet article une approche d'optimisation basée sur les colonies de fourmis pour traiter ce problème. Deux algorithmes sont proposés, dans lesquels des colonies de fourmis sont engagées dans une compétition pour découvrir la meilleure stratégie de patrouille multi-agent. Les résultats expérimentaux montrent que, sur quatre des six graphes étudiés, l'une de nos techniques est significativement meilleure que la technique d'apprentissage par renforcement proposée par Santana. ABSTRACT. Patrolling an environment involves a team of agents whose goal usually consists of continuously visiting its most relevant areas as frequently as possible. For such a task, agents have to coordinate their actions in order to achieve optimal performance. A wide range of applications can be dealt with this problem, from computer network management to vehicle routing. The Ant Colony Optimization is adopted here as the solution approach to this problem. Two novel ACO algorithms are proposed here, in which several ants' colonies try to discover the best multi-agent patrolling strategy. Experimental results show that, for four out of the six evaluated graphs, one of our techniques significantly outperforms the reinforcement learning technique proposed by Santana, irrespective of the number of the involved patrolling agents.
Type de document :
Article dans une revue
Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, Lavoisier, 2007, 22 (1)
Liste complète des métadonnées

https://hal.inria.fr/inria-00175666
Contributeur : François Charpillet <>
Soumis le : samedi 29 septembre 2007 - 15:02:09
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51

Identifiants

  • HAL Id : inria-00175666, version 1

Citation

François Charpillet, Fabrice Lauri. Optimation par colonies de fournis d'un essaim de patrouilleurs pour la surveillance de zone. Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, Lavoisier, 2007, 22 (1). 〈inria-00175666〉

Partager

Métriques

Consultations de la notice

252