Problèmes de Plus Sûr et Plus Court Chemin Stochastique - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Problèmes de Plus Sûr et Plus Court Chemin Stochastique

Résumé

Résoudre de manière optimale des problèmes de Plus Court Chemin Stochastique (SSP en anglais) nécessite en général qu'il existe au moins une politique qui atteint le but avec probabilité 1 depuis l'état initial. Cette condition est très forte et empêche de résoudre de nombreux problèmes intéressants, par exemple où toutes les politiques possibles atteignent des états "culs-de-sac" avec une probabilité strictement positive. Nous introduisons un critère d'optimisation duale plus général et plus riche, qui minimise le coût moyen (non pondéré) des seuls chemins menant au but parmi toutes les politiques qui maximisent la probabilité d'atteindre le but. Nous présentons des équations de mise à jour de la politique sous la forme de la programmation dynamique pour ce nouveau critère dual. Ces équations sont différentes des équations standards de Bellman, mais elles produisent la même solution s'il existe une politique menant au but avec probabilité 1 depuis l'état initial. Nous démontrons que nos équations convergent en horizon infini sans aucune condition sur la structure du problème ni sur ses politiques, ce qui étend de fait la classe des problèmes de Plus Court Chemin Stochastique qui peuvent être résolus. Nous montrons expérimentalement que notre critère dual fournit des solutions bien fondées à des SSP qui n'ont pas de solution avec le critère standard, et que le fait d'utiliser un facteur d'actualisation avec ce dernier fournit certes des politiques solutions, mais qui ne sont pas optimales au regard du critère dual.
Fichier principal
Vignette du fichier
16.pdf (324.32 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00736210 , version 1 (27-09-2012)

Identifiants

  • HAL Id : hal-00736210 , version 1

Citer

Florent Teichteil-Königsbuch. Problèmes de Plus Sûr et Plus Court Chemin Stochastique. Journées Francophones sur la planification, la décision et l'apprentissage pour le contrôle des systèmes - JFPDA 2012, May 2012, Villers-lès-Nancy, France. 16 p. ⟨hal-00736210⟩

Collections

ONERA JFPDA2012
72 Consultations
106 Téléchargements

Partager

Gmail Facebook X LinkedIn More