Par rapport aux différentes composantes du MCO (Maintien en Conditions Opérationnelles) d’un système industriel, ces travaux de thèse, initiés dans le cadre d'un partenariat entre l'INRETS et le CRAN, portent plus spécifiquement sur le processus de maintenance dans un contexte applicatif dédié à la maintenance des voies ferrées. En effet, les exploitants ferroviaires, ayant pour priorité d’améliorer sans cesse la sécurité et le bien-être des passagers, cherchent actuellement à faire évoluer leur politique de maintenance, d’une politique essentiellement corrective ou exécutée à intervalles de temps prédéterminés, vers une politique plus conditionnelle voire prévisionnelle et à moindre coût. Dans cette nouvelle dimension, la maintenance des rails ne doit plus être limitée à la seule vision du composant (portion de rail) siège de la défaillance mais à l'étude du système dans sa globalité (système à n-composants). Les décisions relatives à la maintenance ne sont donc plus isolées de leur contexte et s'inscrivent dans un continuum Surveillance - Diagnostic - Aide à la décision. Face à ce besoin industriel et aux enjeux scientifiques qui s’y réfèrent, notre contribution porte premièrement sur une approche originale de diagnostic (approche hybride) qui se base sur une fusion de deux sources d'informations de natures différentes : Approche Locale (capteur à courants de Foucault) et Approche Globale. Dans ce cadre, les RBD ont été utilisés pour développer des modèles stochastiques facilitant la classification des points singuliers de la voie. La fusion entre ces modèles et l’approche basée sur le traitement des données mesurées en un point précis du rail a été réalisée par fusion bayésienne naïve. Le résultat de cette fusion est repris comme point d’entrée du processus d’aide à la décision, pour lequel nous avons proposé, deuxièmement, une méthode générique pour l’optimisation de la maintenance conditionnelle des systèmes à N-composants. Cette proposition se base sur une combinaison des réseaux bayésiens dynamiques et des MDP (Markov Decision Processes) afin de pouvoir modéliser les systèmes à N-composants de façon factorisée. Notre démarche a été illustrée d’abord par un exemple académique pour mettre en évidence sa faisabilité puis elle a été appliquée dans le cadre de l’optimisation de la maintenance des défauts surfaciques du rail. / Compared to the various activities of “Keeping the Operational Conditions” of an industrial system, these PhD, initiated in the framework of a partnership between the INRETS and CRAN, is focusing on the maintenance process with an application context dedicated to the maintenance of the railway. Railway firms, with the priority of improving the safety and welfare of passengers, are seeking to adjust their maintenance policy which is nowadays primarily corrective or executed at a predetermined time interval, to a more conditional or predictive planning with a minimum of costs. In this new context, rails maintenance should no longer be limited to the vision of the isolated component (portion of rail), but to the study of the whole system failure (N-components system). Therefore, maintenance decisions are no longer isolated from their context and exist on a continuum Surveillance - Diagnostic - Decision making. In response to these industrial needs and its scientific issues, our contribution focuses first on an original approach of diagnosis (hybrid approach), which is based on a fusion of two different information sources: Local Approach (sensor eddy currents) and Global Approach. RBD have been used to develop probabilistic models to for the classification of singular points of the track. The fusion between these models and the local approach was produced by naive Bayes fusion method. The result of this fusion constitutes the input of decision making process, for which we have proposed, secondly, a generic methodology for optimizing conditional based maintenance of N-components systems. Our approach is based on a combination of dynamic Bayesian networks and MDP (Markov Decision Processes) to be able to model N-components systems in a factored way. This new proposal was illustrated by a first instance academic to highlight its feasibility then it has been applied in the framework of the optimization of maintenance of the surface defects rail.

Cette thèse porte sur la prise de décision distribuée dans des<br />systèmes multi-agents agissant sous incertitude (les colonies de<br />robots autonomes par exemple). Les processus décisionnels de Markov<br />Décentralisés décrivent un formalisme mathématique permettant de<br />modéliser et de résoudre de tels problèmes. Leur utilisation pour la<br />planification des tâches dans des applications réelles pose<br />toutefois quelques difficultés. Le modèle usuel des DEC-MDPs ne<br />permet par exemple pas la prise en compte de contraintes sur l'exécution des tâches. De plus,<br />la complexité de leur résolution est telle qu'il est difficile de déterminer une solution optimale excepté pour de <br />petits problèmes.<br /><br />Le travail que nous présentons dans cette thèse a pour premier objectif<br />d'adapter le modèle des DEC-MDPs afin de proposer une modélisation<br />adéquate du temps et des actions, et de permettre la représentation de<br />problèmes réels. Nous décrivons ainsi une nouvelle classe de<br />DEC-MDPs : les OC-DEC-MDPs (DEC-MDP avec Coût Occasionné). Dans un second temps,<br />nous nous intéressons à leur résolution. Nous proposons différents<br />algorithmes procédant à la planification des tâches de chaque agent<br />en vue d'une prise de décision décentralisée et autonome, en accord<br />avec les contraintes du problème. Afin de développer des algorithmes<br />efficaces et de traiter des problèmes de taille importante, nous recherchons une<br />approximation de la solution optimale. Nous procédons<br />également à un découpage du problème initial en un ensemble de MDPs,<br />et introduisons la notion de coût occasionné afin de tenir compte<br />des interactions entre les agents et de calculer des politiques<br />coopératives.

Les processus décisionnels de Markov (MDP) sont un formalisme mathématique des domaines de l'intelligence artificielle telle que la planification, l'apprentissage automatique, l'apprentissage par renforcement... Résoudre un MDP permet d'identifier la stratégie (politique) optimale d'un agent en interaction avec un environnement stochastique. Lorsque la taille de ce système est très grande il devient difficile de résoudre ces processus par les moyens classiques. Cette thèse porte sur la résolution des MDP de grande taille. Elle étudie certaines méthodes de résolutions: comme les abstractions et les méthodes dites de projection. Elle montre les limites de certaines abstractions et identifie certaines structures "les bisimulations" qui peuvent s'avérer intéressantes pour une résolution approchée du problème. Cette thèse s'est également intéressée à une méthode de projection l'algorithme Least square temporal difference LSTD(λ). Une estimation de la borne sur la vitesse de convergence de cet algorithme a été établie avec une mise en valeur du rôle joué par le paramètre [lambda]. Cette analyse a été étendue pour déduire une borne de performance pour l'algorithme Least square non stationary policy iteration LS(λ)NSPI en estimant la borne d'erreur entre la valeur calculée à une itération fixée et la valeur sous la politique optimale qu'on cherche à identifier / Markov Decision Processes (MDP) are a mathematical formalism of many domains of artifical intelligence such as planning, machine learning, reinforcement learning... Solving an MDP means finding the optimal strategy or policy of an agent interacting in a stochastic environment. When the size of this system becomes very large it becomes hard to solve this problem with classical methods. This thesis deals with the resolution of MDPs with large state space. It studies some resolution methods such as: abstractions and the projection methods. It shows the limits of some approachs and identifies some structures that may be interesting for the MDP resolution. This thesis focuses also on projection methods, the Least square temporal difference algorithm LSTD(λ). An estimate of the rate of the convergence of this algorithm has been derived with an emphasis on the role played by the parameter [lambda]. This analysis has then been generalized to the case of Least square non stationary policy iteration LS(λ)NSPI . We compute a performance bound for LS([lambda])NSPI by bounding the error between the value computed given a fixed iteration and the value computed under the optimal policy, that we aim to determine

En microrobotique, la commande des systèmes est délicate car les phénomènes physiques liés à l'échelle microscopique sont complexes. Les méthodes dites d'apprentissage par renforcement constituent une approche intéressante car elles permettent d'établir une stratégie de commande sans connaissance \emph(a priori) sur le système. Au vu des grandes dimensions des espaces d'états des systèmes étudiés, nous avons développé une approche parallèle qui s'inspire à la fois des architectures comportementales et de l'apprentissage par renforcement. Cette architecture, basée sur la parallélisation de l'algorithme du Q-Learning, permet de réduire la complexité du système et d'accélérer l'apprentissage. Sur une application simple de labyrinthe, les résultats obtenus sont bons mais le temps d'apprentissage est trop long pour envisager la commande d'un système réel. Le Q-Learning a alors été remplacé par l'algorithme du Dyna-Q que nous avons adapté à la commande de systèmes non déterministes en ajoutant un historique des dernières transitions. Cette architecture, baptisée Dyna-Q parallèle, permet non seulement d'améliorer la vitesse de convergence, mais aussi de trouver de meilleures stratégies de contrôle. Les expérimentations sur le système de manipulation montrent que l'apprentissage est alors possible en temps réel et sans utiliser de simulation. La fonction de coordination des comportements est efficace si les obstacles sont relativement éloignés les uns des autres. Si ce n'est pas le cas, cette fonction peut créer des maxima locaux qui entraînent temporairement le système dans un cycle. Nous avons donc élaboré une autre fonction de coordination qui synthétise un modèle plus global du système à partir du modèle de transition construit par le Dyna-Q. Cette nouvelle fonction de coordination permet de sortir très efficacement des maxima locaux à condition que la fonction de mise en correspondance utilisée par l'architecture soit robuste.

Cette thèse étudie l'utilisation d'algorithmes connexionnistes pour résoudre des problèmes d'apprentissage par renforcement. Les algorithmes connexionnistes sont inspirés de la manière dont le cerveau traite l'information : ils impliquent un grand nombre d'unités simples fortement interconnectées, manipulant des informations numériques de manière distribuée et massivement parallèle. L'apprentissage par renforcement est une théorie computationnelle qui permet de décrire l'interaction entre un agent et un environnement : elle permet de formaliser précisément le problème consistant à atteindre un certain nombre de buts via l'interaction.<br /><br />Nous avons considéré trois problèmes de complexité croissante et montré qu'ils admettaient des solutions algorithmiques connexionnistes : 1) L'apprentissage par renforcement dans un petit espace d'états : nous nous appuyons sur un algorithme de la littérature pour construire un réseau connexionniste ; les paramètres du problème sont stockés par les poids des unités et des connexions et le calcul du plan est le résultat d'une activité distribuée dans le réseau. 2) L'apprentissage d'une représentation pour approximer un problème d'apprentissage par renforcement ayant un grand espace d'états : nous automatisons le procédé consistant à construire une partition de l'espace d'états pour approximer un problème de grande taille. 3) L'auto-organisation en modules spécialisés pour approximer plusieurs problèmes d'apprentissage par renforcement ayant un grand espace d'états : nous proposons d'exploiter le principe "diviser pour régner" et montrons comment plusieurs tâches peuvent être réparties efficacement sur un petit nombre de modules fonctionnels spécialisés.

Ce travail contribue à la théorie de la décision possibiliste et plus précisément à la prise de décision séquentielle dans le cadre de la théorie des possibilités, à la fois au niveau théorique et pratique. Bien qu'attrayante pour sa capacité à résoudre les problèmes de décision qualitatifs, la théorie de la décision possibiliste souffre d'un inconvénient important : les critères d'utilité qualitatives possibilistes comparent les actions avec les opérateurs min et max, ce qui entraîne un effet de noyade. Pour surmonter ce manque de pouvoir décisionnel, plusieurs raffinements ont été proposés dans la littérature. Les raffinements lexicographiques sont particulièrement intéressants puisqu'ils permettent de bénéficier de l'arrière-plan de l'utilité espérée, tout en restant "qualitatifs". Cependant, ces raffinements ne sont définis que pour les problèmes de décision non séquentiels. Dans cette thèse, nous présentons des résultats sur l'extension des raffinements lexicographiques aux problèmes de décision séquentiels, en particulier aux Arbres de Décision et aux Processus Décisionnels de Markov possibilistes. Cela aboutit à des nouveaux algorithmes de planification plus "décisifs" que leurs contreparties possibilistes. Dans un premier temps, nous présentons des relations de préférence lexicographiques optimistes et pessimistes entre les politiques avec et sans utilités intermédiaires, qui raffinent respectivement les utilités possibilistes optimistes et pessimistes. Nous prouvons que les critères proposés satisfont le principe de l'efficacité de Pareto ainsi que la propriété de monotonie stricte. Cette dernière garantit la possibilité d'application d'un algorithme de programmation dynamique pour calculer des politiques optimales. Nous étudions tout d'abord l'optimisation lexicographique des politiques dans les Arbres de Décision possibilistes et les Processus Décisionnels de Markov à horizon fini. Nous fournissons des adaptations de l'algorithme de programmation dynamique qui calculent une politique optimale en temps polynomial. Ces algorithmes sont basés sur la comparaison lexicographique des matrices de trajectoires associées aux sous-politiques. Ce travail algorithmique est complété par une étude expérimentale qui montre la faisabilité et l'intérêt de l'approche proposée. Ensuite, nous prouvons que les critères lexicographiques bénéficient toujours d'une fondation en termes d'utilité espérée, et qu'ils peuvent être capturés par des utilités espérées infinitésimales. La dernière partie de notre travail est consacrée à l'optimisation des politiques dans les Processus Décisionnels de Markov (éventuellement infinis) stationnaires. Nous proposons un algorithme d'itération de la valeur pour le calcul des politiques optimales lexicographiques. De plus, nous étendons ces résultats au cas de l'horizon infini. La taille des matrices augmentant exponentiellement (ce qui est particulièrement problématique dans le cas de l'horizon infini), nous proposons un algorithme d'approximation qui se limite à la partie la plus intéressante de chaque matrice de trajectoires, à savoir les premières lignes et colonnes. Enfin, nous rapportons des résultats expérimentaux qui prouvent l'efficacité des algorithmes basés sur la troncation des matrices. / This work contributes to possibilistic decision theory and more specifically to sequential decision-making under possibilistic uncertainty, at both the theoretical and practical levels. Even though appealing for its ability to handle qualitative decision problems, possibilisitic decision theory suffers from an important drawback: qualitative possibilistic utility criteria compare acts through min and max operators, which leads to a drowning effect. To overcome this lack of decision power, several refinements have been proposed in the literature. Lexicographic refinements are particularly appealing since they allow to benefit from the expected utility background, while remaining "qualitative". However, these refinements are defined for the non-sequential decision problems only. In this thesis, we present results on the extension of the lexicographic preference relations to sequential decision problems, in particular, to possibilistic Decision trees and Markov Decision Processes. This leads to new planning algorithms that are more "decisive" than their original possibilistic counterparts. We first present optimistic and pessimistic lexicographic preference relations between policies with and without intermediate utilities that refine the optimistic and pessimistic qualitative utilities respectively. We prove that these new proposed criteria satisfy the principle of Pareto efficiency as well as the property of strict monotonicity. This latter guarantees that dynamic programming algorithm can be used for calculating lexicographic optimal policies. Considering the problem of policy optimization in possibilistic decision trees and finite-horizon Markov decision processes, we provide adaptations of dynamic programming algorithm that calculate lexicographic optimal policy in polynomial time. These algorithms are based on the lexicographic comparison of the matrices of trajectories associated to the sub-policies. This algorithmic work is completed with an experimental study that shows the feasibility and the interest of the proposed approach. Then we prove that the lexicographic criteria still benefit from an Expected Utility grounding, and can be represented by infinitesimal expected utilities. The last part of our work is devoted to policy optimization in (possibly infinite) stationary Markov Decision Processes. We propose a value iteration algorithm for the computation of lexicographic optimal policies. We extend these results to the infinite-horizon case. Since the size of the matrices increases exponentially (which is especially problematic in the infinite-horizon case), we thus propose an approximation algorithm which keeps the most interesting part of each matrix of trajectories, namely the first lines and columns. Finally, we reports experimental results that show the effectiveness of the algorithms based on the cutting of the matrices.

Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), ajoute à LSPI un concept venant de [lambda]-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LS[lambda]PI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lorincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008 / This thesis studies policy iteration methods with linear approximation of the value function for large state space problems in the reinforcement learning context. We first introduce a unified algorithm that generalizes the main stochastic optimal control methods. We show the convergence of this unified algorithm to the optimal value function in the tabular case, and a performance bound in the approximate case when the value function is estimated. We then extend the literature of second-order linear approximation algorithms by proposing a generalization of Least-Squares Policy Iteration (LSPI) (Lagoudakis and Parr, 2003). Our new algorithm, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), adds to LSPI an idea of [lambda]-Policy Iteration (Bertsekas and Ioffe, 1996): the damped (or optimistic) evaluation of the value function, which allows to reduce the variance of the estimation to improve the sampling efficiency. Thus, LS[lambda]PI offers a bias-variance trade-off that may improve the estimation of the value function and the performance of the policy obtained. In a second part, we study in depth the game of Tetris, a benchmark application that several works from the literature attempt to solve. Tetris is a difficult problem because of its structure and its large state space. We provide the first full review of the literature that includes reinforcement learning works, evolutionary methods that directly explore the policy space and handwritten controllers. We observe that reinforcement learning is less successful on this problem than direct policy search approaches such as the cross-entropy method (Szita et Lorincz, 2006). We finally show how we built a controller that outperforms the previously known best controllers, and shortly discuss how it allowed us to win the Tetris event of the 2008 Reinforcement Learning Competition

Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), ajoute à LSPI un concept venant de λ-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LSλPI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lőrincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008.

Cette thèse se situe dans le cadre de la décision pour un agent<br />rationnel et autonome. Le travail consiste à élaborer un système de<br />contrôle intelligent pour un agent évoluant dans un environnement<br />incertain. L'agent doit pouvoir contrôler sa consommation de ressources<br />au cours d'une mission prédéfinie. La première partie de cette thèse<br />introduit le concept de planification sous incertitude. Une présentation<br />des processus décisionnels de Markov (MDP) précède un état de l'art sur<br />les techniques de résolution de MDP de grande taille.<br />Ce système de contrôle de ressources s'appuie sur le raisonnement<br />progressif. Le raisonnement progressif permet de modéliser un ensemble<br />de tâches sous forme d'unités de raisonnement progressif (ou PRUs).<br />Chaque PRU définit des niveaux de réalisation pour une tâche donnée,<br />donnant lieu à des qualités croissantes de réalisation. Chaque niveau<br />est lui-même composé de modules dont un seul sera retenu pour sa<br />réalisation. Choisir un module plutôt qu'un autre permet à l'agent de<br />faire un compromis entre la qualité de la tâche accomplie et les<br />ressources consommées.<br /><br />Cette thèse présente deux extensions du raisonnement progressif : la<br />prise en compte de ressources multiples et l'adaptation à un changement<br />de mission. Premièrement, des algorithmes sont présentés pour faire face<br />à l'explosion combinatoire due à l'introduction de nouvelles ressources.<br />Deuxièmement, l'élaboration d'un algorithme d'approximation de fonction<br />de valeur permet d'obtenir rapidement un système de contrôle pour<br />s'adapter à un éventuel changement de mission. Une expérience est<br />finalement menée sur un robot réel qui contre ses ressources grâce au<br />raisonnement progressif.