Prise de décision en temps-réel pour des POMDP de grande taille
Cet article présente une méthode d'approximation pour les POMDP qui est basée sur une recherche en profondeur pour la planification dans un environnement temps-réel dynamique. L'idée de base de notre approche, appelée RTBSS, est d'éviter de calculer des politiques complètes pour des POMDP. Cette approche est spécialement utile pour des environnements temps-réel où l'espace d'états est trop grand pour que l'on puisse considérer les algorithmes de résolution hors lignes des POMDP. À cet effet, nous proposons une approche en ligne pour calculer à chaque cycle, l'action qui maximise l'utilité espérée de l'agent. Nous commençons par présenter tout le formalisme à la base de notre méthode. Par la suite, nous présentons les résultats expérimentaux obtenus sur trois environnements. Mentionnons par ailleurs que cette approche a été implémentée avec succès pour la compétition mondiale de la RoboCupRescue en 2004 où nous nous sommes classés en deuxième position.
This paper presents a POMDP approximation method, called RTBSS, which is based on a look-ahead search in order to plan in a real-time dynamic environment. The basis of our approach is to avoid computing full policies in POMDP problems. Our approach is especially motivated by real-time environments where the state space is too large to consider traditional offline algorithms. We then proceed with an online approach to find at each step, the action that maximizes the agent expected utility. To this end, we present the formalism behind our approach. Then, we present how the approach was applied on three different environments. Let us mention finally that this approach was successfully implemented for the RoboCupRescue 2004 international competition where we finished second.
S.PAQUET, L.TOBIN, B.CHAIB-DRAA
POMDP, temps-réel, prise de décision.
POMDP, real-time, decision making.
Français
|
