Analyse théorique du problème de la patrouille multi-agent en utilisant le cadre des processus décisionnels de Markov

Fabrice Lauri 1 François Charpillet 1 Daniel Szer 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : Patrouiller implique habituellement une équipe d'agents dont le but consiste à visiter aussi fréquemment que possible les zones stratégiques d'un environnement. Pour une telle tâche, les agents impliqués doivent coordonner leurs actions afin d'atteindre des performances optimales. Les recherches actuelles sur le problème de la patrouille multi-agent (ou PPMA) considère généralement que l'environnement est réduit à un graphe métrique. Sous cette hypothèse, ce problème peut donc concerner une large gamme d'applications, telles que la gestion d'un réseau informatique, les jeux vidéo ou la détermination d'itinéraires de véhicules. Dans cet article, nous concentrons notre attention sur des instances particulières de ce problème. Nous considérons uniquement le pire cas où tous les agents commencent à patrouiller à partir d'un noeud donné. Nous formulons le problème de la patrouille multi-agent à l'aide d'un processus décisionnel de Markov (PDM). Trouver une politique optimale de patrouille se réduira alors à résoudre ce PDM. Nous prouvons d'une part que les stratégies multi-agents optimales sont nécessairement cycliques. D'autre part, nous avons montré que déterminer une stratégie de patrouille multi-agent consiste à trouver deux politiques à horizon ni. Un algorithme meilleur d'abord est utilisé pour déterminer une telle politique. Les résultats expérimentaux montrent que, pour toutes les congurations testées, notre approche améliore substantiellement ceux obtenus avec la méthode d'apprentissage par renforcement proposée par Santana et al..
Type de document :
Communication dans un congrès
Journées Francophones Planification, Décision, Apprentissage - JFPDA'2006, May 2006, Toulouse/France, 2006
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-00104432
Contributeur : Daniel Szer <>
Soumis le : vendredi 6 octobre 2006 - 15:25:50
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50
Document(s) archivé(s) le : jeudi 20 septembre 2012 - 11:26:31

Identifiants

  • HAL Id : inria-00104432, version 1

Collections

Citation

Fabrice Lauri, François Charpillet, Daniel Szer. Analyse théorique du problème de la patrouille multi-agent en utilisant le cadre des processus décisionnels de Markov. Journées Francophones Planification, Décision, Apprentissage - JFPDA'2006, May 2006, Toulouse/France, 2006. 〈inria-00104432〉

Partager

Métriques

Consultations de la notice

252

Téléchargements de fichiers

135