[Home bibliotech]
Home > Les thèses en ligne de l'INP

Recherche en ligne pour les Processus Décisionnels de Markov : application à la maintenance d’une constellation de satellites.

Péret, Laurent (2004) Recherche en ligne pour les Processus Décisionnels de Markov : application à la maintenance d’une constellation de satellites. (On-line search for Markov Decision Processes : application to the maintenance of a constellation of satellites.)

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
3.12 Mo

Abstract

La résolution de Processus Décisionnels de Markov de grande dimension est habituellement basée sur le calcul hors ligne d'une approximation de la fonction de valeur optimale. Cette fonction de valeur est ensuite exploitée en ligne pour définir une politique a priori. Toutefois, quand l'espace d'états est très vaste et qu'aucune représentation structurée efficace n'est connue, le calcul d'une bonne approximation de la fonction de valeur optimale s'avère souvent être une tâche difficile. Nous proposons dans cette thèse une approche alternative reposant sur la simulation stochastique du processus décisionnel depuis chaque état courant sur un certain horizon de raisonnement. Cette approche conduit à la définition en ligne d'une politique stochastique en remplacement de la politique a priori traditionnelle. Nous proposons en particulier deux algorithmes baptisés "Focused Reinforcement Learning" et "Controlled Rollout" pour contrôler l'allocation en ligne des simulations. Notre démarche a été validée sur une application proposée par le Centre National d'Etudes Spatiales concernant la maintenance d'une constellation de 32 satellites en orbite basse. L'objectif est de pallier efficacement les pannes affectant les satellites, qui, en raison de l'hostilité du milieu spatial, sont relativement fréquentes. L'usage conjugué de méthodes d'optimisation hors ligne et de nos techniques de recherche en ligne a permis une diminution significative des coûts simulés de maintenance. ABSTRACT : Solving complex Markov Decision Processes usually requires an off-line approximation of an approximate value function. The greedy policy defined by this value function is then exploited on-line. When the state space is huge the computation of a good approximate value function is often a hard task, especially when no efficiently structured representation is known. In this thesis, we propose an alternative approach based on the stochastic simulation of the decision process from each current state over some reasoning horizon. This approach defines a stochastic policy which replaces the standard greedy policy. We propose two algorithms to monitor the on-line allocation of simulations. Our approach was applied to a problem proposed by the French Space Agency concerning the maintenance of a constellation of 32 satellites in low orbit. The actions to be taken are the preparation and the launching of satellites. As satellites failures are costly and quite frequent, the objective is to find an efficient policy to efficiently replace them. We have developed diverse simulation-based techniques to improve the maintenance policy. The best of these techniques combining off-line optimisation and on-line search have shown an improvement of the performance of the maintenance policy 26%.

Department:Unité de Biométrie et Intelligence Artificielle - UBIA (Castanet-Tolosan, France)
Directeur de thèse:Garcia, Frédérick
Uncontrolled Keywords:Processus décisionnels de Markov - Apprentissage par renforcement - Optimisation stochastique - Recherche dans les graphes - Constellations de satellites
Subjects:Computer science > Computer systems
Deposited On:13 May 2005

Archive Staff Only: edit this record


Contacts | Infos légales | Plan du site | Intranet

(c)INP de Toulouse 2012 - Tous droits réservés. -  INP Communication