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
7ème Journées Francophones Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA 2012), May 2012, NANCY, France
Liste complète des métadonnées

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

https://hal-onera.archives-ouvertes.fr/hal-01060414
Contributeur : Alain Broc <>
Soumis le : mercredi 3 septembre 2014 - 15:31:46
Dernière modification le : mercredi 28 mars 2018 - 14:16:10
Document(s) archivé(s) le : jeudi 4 décembre 2014 - 11:27:48

Fichier

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

Identifiants

  • HAL Id : hal-01060414, version 1

Collections

Citation

F. Teichteil-Königsbuch. Problèmes de Plus Sûr et Plus Court Chemin Stochastique.. 7ème Journées Francophones Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA 2012), May 2012, NANCY, France. 〈hal-01060414〉

Partager

Métriques

Consultations de la notice

79

Téléchargements de fichiers

158