Skip to Main content Skip to Navigation
Conference papers

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..
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00104432
Contributor : Daniel Szer <>
Submitted on : Friday, October 6, 2006 - 3:25:50 PM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM
Long-term archiving on: : Thursday, September 20, 2012 - 11:26:31 AM

Identifiers

  • 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. ⟨inria-00104432⟩

Share

Metrics

Record views

297

Files downloads

257