[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Thèse soutenue

Le problème du plus court chemin stochastique et ses variantes : fondements et applications à l'optimisation de stratégie dans le sport

FR  |  
EN
Auteur / Autrice : Matthieu Guillot
Direction : Gautier Stauffer
Type : Thèse de doctorat
Discipline(s) : Mathématiques et informatique
Date : Soutenance le 03/07/2020
Etablissement(s) : Université Grenoble Alpes
Ecole(s) doctorale(s) : École doctorale Mathématiques, sciences et technologies de l'information, informatique (Grenoble ; 1995-....)
Partenaire(s) de recherche : Laboratoire : Sciences pour la conception, l'optimisation et la production (Grenoble, Isère, France)
Jury : Président / Présidente : Nadia Brauner
Examinateurs / Examinatrices : Louis Esperet, Bruno Scherrer
Rapporteur / Rapporteuse : Jörg Rambau, François Clautiaux

Résumé

FR  |  
EN

Un parcours de golf est composé de dix-huit trous. Sur chaque trou, le problème du golfeur est de déplacer la balle d'un point de départ prédéfini jusqu'au drapeau en un minimum de coups. Sous certaines hypothèses, ce problème peut se modéliser comme un problème de plus court chemin stochastique (PCCS). Le problème du PCCS est un processus de Markov particulier dans lequel un agent évolue dynamiquement dans un ensemble fini d'états. En chaque état, l'agent choisis une action, induisant un coût, qui le mène en un autre état en suivant une distribution de probabilité connue. Il existe également un état `puits' particulier dans lequel, une fois atteint, on reste avec une probabilité un et un coût de zéro. Le but de l'agent est, depuis un état initial, d'atteindre l'état puits en un coût moyen minimal. Dans un premier chapitre, nous étudions de manière théorique le problème du PCCS. Après avoir redéfini un cadre d'étude dans lequel nous avons affaibli les hypothèses d'existence d'une solution optimale, nous avons prouvé que les algorithmes classiques de résolution convergent dans ce nouveau cadre. Nous avons également défini un nouvel algorithme de résolution basé sur l'algorithme primal-dual. Dans le deuxième chapitre, nous détaillons la modélisation du problème d'optimisation de stratégies au golf en un problème de PCCS. Grâce à la base de données Shotlink, nous définissons des `clones numériques' de joueurs que nous pouvons faire jouer artificiellement sur différents parcours de golf afin de prédire les scores des joueurs. Nous avons appliqué ce modèle à deux compétitions : le master d'Augusta en 2017 et la Ryder Cup en 2018. Dans un troisième et dernier chapitre, nous étudions l'extension naturelle à deux joueurs du problème du PCCS : les jeux de plus courts chemins stochastiques. Nous étudions particulièrement les formulations programmation linéaire de ces jeux et de deux cas particuliers de ceux-ci.