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.
Type de document :
Communication dans un congrès
Olivier Buffet. 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, 2012
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00736210
Contributeur : Olivier Buffet <>
Soumis le : jeudi 27 septembre 2012 - 17:40:37
Dernière modification le : mercredi 13 décembre 2017 - 09:03:09
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 17:56:23

Fichier

16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00736210, version 1

Collections

Citation

Florent Teichteil-Königsbuch. Problèmes de Plus Sûr et Plus Court Chemin Stochastique. Olivier Buffet. 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, 2012. 〈hal-00736210〉

Partager

Métriques

Consultations de la notice

109

Téléchargements de fichiers

59