Soutenance de thèse de Matthieu Guillot (OC) le 03 juillet à 9h00 en amphi Gosse - Site Viallet - Grenoble INP

Les membres du jury :
 

• Nadia Brauner : Présidente
• Gautier Stauffer : Directeur de thèse
• François Clautiaux : Rapporteur
• Jörg Rambau : Rapporteur
• Louis Esperet : Examinateur
• Bruno Scherrer : Examinateur

Résumé :

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.

Abstract :

A golf course consists of eighteen holes. On each hole, the golfer has to move the ball from the tee to the flag in a minimum number of shots. Under some assumptions, the golfer's problem can be modeled as a stochastic shortest path problem (SSP). SSP problem is a special case of Markov Decision Processes in which an agent evolves dynamically in a finite set of states. In each state, the agent chooses an action that leads him to another state following a known probability distribution. This action induces a cost. There exists a `sink node' in which the agent, once in it, stays with probability one and a cost zero. The goal of the agent is to reach the sink node with a minimum expected cost. In the first chapter, we study the SSP problem theoretically. We define a new framework in which the assumptions needed for the existence of an optimal policy are weakened. We prove that the most famous algorithm still converge in this setting. We also define a new algorithm to solve exactly the problem based on the primal-dual algorithm. In the second chapter we detail the golfer's problem model as a SSP. Thanks to the Shotlink database, we create `numerical clones' of players and simulate theses clones on different golf course in order to predict professional golfer's scores. We apply our model on two competitions: the master of Augusta in 2017 and the Ryder Cup in 2018. In the third chapter, we study the 2-player natural extension of SSP problem: the stochastic shortest path games. We study two special cases, and in particular linear programming formulation of these games.