Search

In this thesis, using Markov decision models, we investigate high-level decision-making (task-level planning) for robotics in two aspects: robot-robot collaboration and human-robot collaboration.In robot-robot collaboration (RRC), we study the decision problems of multiple robots involved to achieve a shared goal collaboratively, and we use the decentralized partially observable Markov decision process (Dec-POMDP) framework to model such RRC problems. Then, we propose two novel algorithms for solving Dec-POMDPs. The first algorithm (Inf-JESP) finds Nash equilibrium solutions by iteratively building the best-response policy for each agent until no improvement can be made. To handle infinite-horizon Dec-POMDPs, we represent each agent's policy using a finite-state controller. The second algorithm (MC-JESP) extends Inf-JESP with generative models, which enables us to scale up to large problems. Through experiments, we demonstrate our methods are competitive with existing Dec-POMDP solvers.In human-robot collaboration (HRC), we can only control the robot, and the robot faces uncertain human objectives and induced behaviors. Therefore, we attempt to address the challenge of deriving robot policies in HRC, which are robust to the uncertainties about human behaviors. In this direction, we discuss possible mental models that can be used to model humans in an HRC task. We propose a general approach to derive, automatically and without prior knowledge, a model of human behaviors based on the assumption that the human could also control the robot. From here, we then design two algorithms for computing robust robot policies relying on solving a robot POMDP, whose state contains the human's internal state. The first algorithm operates offline and gives a complete robot policy that can be used during the robot's execution. The second algorithm is an online method, i.e., it plans the robot's action at each time step during execution. Compared with the offline approach, the online method only requires a generative model and thus can scale up to large problems. Experiments with synthetic and real humans are conducted in a simulated environment to evaluate these algorithms. We observe that our methods can provide robust robot decisions despite the uncertainties over human objectives and behaviors.In this thesis, our research for RRC provides a foundation for building best-response policies in a partially observable and multi-agent setting, which serves as an important intermediate step for addressing HRC problems. Moreover, we provide more flexible algorithms using generative models in each contribution, and we believe this will facilitate applying our contributions to real-world applications.; Dans cette thèse, nous nous intéressons à la prise de décision haut niveau (planification de tâches) pour la robotique à l'aide de modèles de prise de décision markoviens et sous deux aspects : la collaboration robot-robot et la collaboration homme-robot. Dans le cadre de la collaboration robot-robot (RRC), nous étudions les problèmes de décision de plusieurs robots devant atteindre un objectif commun de manière collaborative, et nous utilisons le cadre des processus de décision markoviens partiellement observables et décentralisés (Dec-POMDP) pour modéliser de tels problèmes. Nous proposons deux nouveaux algorithmes pour résoudre les Dec-POMDP. Le premier algorithme (Inf-JESP) trouve des équilibres de Nash en construisant itérativement pour chaque agent la politique meilleure réponse aux autres agents jusqu'à ce qu'aucune amélioration ne soit possible. Pour traiter les Dec-POMDP à horizon infini, nous représentons la politique de chaque agent à l'aide d'un contrôleur à états finis. Le deuxième algorithme (MC-JESP) étend Inf-JESP avec des modèles génératifs, ce qui nous permet de passer à l'échelle pour des grands problèmes. Nous démontrons expérimentalement que nos méthodes sont compétitives par rapport aux solveurs Dec-POMDP existants. Dans le cadre de la collaboration homme-robot (HRC), nous ne pouvons contrôler que le comportement du robot, lequel doit faire face à des objectifs humains et à des comportements induits incertains. Nous cherchons ainsi à dériver des politiques de robot qui sont robustes aux incertitudes sur les comportements humains. Pour cela, nous discutons des modèles mentaux qui peuvent être utilisés pour modéliser le comportement humain dans une telle tâche collaborative. Nous décrivons ensuite une approche générale pour dériver, automatiquement et sans connaissance préalable, un modèle de comportements humains basé sur l'hypothèse que l'humain contrôle aussi le robot. À partir de là, nous proposons deux algorithmes pour calculer des politiques robustes pour le robot en se basant sur la résolution d'un POMDP dont l'état contient l'état interne de l'humain. Le premier algorithme fonctionne hors ligne et fournit une politique complète qui peut être utilisée par le robot pendant son exécution. Le deuxième algorithme est une méthode en ligne, c'est-à-dire qu'il décide de l'action du robot à chaque pas de temps au cours de l'exécution. Par rapport à l'approche hors ligne, la méthode en ligne ne nécessite qu'un modèle génératif et peut donc s'adapter à de grands problèmes. Des expériences avec des humains synthétiques et réels sont menées dans un environnement simulé pour évaluer ces algorithmes. Nous observons que nos méthodes peuvent fournir des décisions robustes pour des robots collaboratifs malgré les incertitudes sur les objectifs et les comportements humains. Dans cette thèse, notre recherche sur la collaboration robot-robot fournit une base pour construire des politiques meilleure réponse dans un cadre partiellement observable et multi-agent, base qui sert d'étape intermédiaire importante pour aborder les problèmes de collaboration homme-robot. De plus, pour chaque contribution, nous fournissons des algorithmes plus flexibles utilisant des modèles génératifs dont nous pensons qu'ils faciliteront la mise en œuvre de nos contributions à des applications du monde réel.

Nous étudions les jeux ramifiés introduits par Mio pour définir la sémantique du μ-calcul modal stochastique. Ces jeux stochastiques infinis à information imparfaite joués tour à tour par deux joueurs forment une sous-classe des jeux infinis à somme nulle. Elles étendent les jeux de Gale- Stewart en ce que chaque partie peut se scinder en sous-parties qui se déroulent indépendamment et simultanément. En conséquence, chaque partie a une structure arborescente, contrairement à la structure linéaire des parties des jeux de Gale-Stewart.Dans cette thèse, nous étudions les jeux ramifiés réguliers. Ceux-ci ont pour caractéristique d’avoir leurs ensembles gagnants régulières, c’est à dire, des ensembles d’arbres infinis reconnus par automates finis d’arbres. Nous nous intéressons aux problèmes de détermination, de calcul des valeurs de jeux ramifiés réguliers et de calcul effectif de la mesure d’un ensemble régulier d’arbres. De plus, nous utilisons des données réelles pour présenter comment on peut employer des techniques de la théorie des jeux stochastiques en pratique. Nous proposons une procédure générale qui à partir d’une série temporelle crée un modèle réactif capable de prédire l’évolution du système. Ce modèle facilite aussi les choix des stratégies permettant d’atteindre certains objectifs prédéfinis. La procédure nous sert ensuite à créer un jeux basé sur les processus décisionnels de Markov. Le jeu obtenu peut être utilisé pour prédire et contrôler le niveau d’infestation d’un verger expérimental., We study a class of games introduced by Mio to capture the probabilistic μ-calculi called branching games. They are a subclass of stochastic two-player zero-sum turn-based infinite-time games of imperfect information. Branching games extend Gale-Stewart games by allowing players to split the execution of a play into new concurrent sub-games that continue their execution independently. In consequence, the play of a branching game has a tree-like structure, as opposed to linearly structured plays of Gale-Stewart games.In this thesis, we focus our attention on regular branching games. Those are the branching games whose pay-off functions are the indicator functions of regular sets of infinite trees, i.e. the sets recognisable by finite tree automata. We study the problems of determinacy, game value computability and the related problem of computing a measure of a regular set of infinite trees.Moreover, we use real-life data to show how to incorporate game-theoretic techniques in practice. We propose a general procedure that given a time series of data extracts a reactive model that can be used to predict the evolution of the system and advise on the strategies to achieve predefined goals. We use the procedure to create a game based on Markov decision processes that is used to predict and control level of pest in a tropical fruit farm.

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.; 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., 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.

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([lambda]). 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([lambda])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, 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([lambda]). 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([lambda])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

Cette thèse, intitulée "Contributions à l’apprentissage par renforcement inverse", fournit trois contributions majeures au domaine. La première est une méthode d’estimation de l’attribut moyen, une quantité exploitée par la grande majorité des approches constituant l’état de l’art. Elle a permis d’étendre ces approches au cadre batch et off-policy. La seconde contribution majeure est un algorithme d’apprentissage par renforcement inverse, structured classification for inverse reinforcement learning (SCIRL), qui relâche une contrainte standard du domaine, la résolution répétée d’un processus décisionnel de Markov en introduisant la structure temporelle (par le biais de l’attribut moyen) de ce processus dans un algorithme de classification structurée. Les garanties théoriques qui lui sont attachées et ses bonnes performances en pratique ont permis sa présentation dans une conférence internationale prestigieuse : NIPS. Enfin, la troisième contribution est constituée par la méthode cascaded supervised learning for inverse reinforcement learning (CSI) consistant à apprendre le comportement de l’expert par une méthode supervisée puis à introduire la structure temporelle du MDP par une régression mettant en jeu la fonction de score du classifieur utilisé. Cette méthode offre des garanties théoriques de même nature que celles de SCIRL tout en présentant l’aventage d’utiliser des composants standards pour la classification et la régression, ce qui simplifie la mise en œuvre. Ce travail sera présenté dans une autre conférence internationale prestigieuse : ECML.

This thesis, "Contributions à l'apprentissage par renforcement inverse", brings three major contributions to the community. The first one is a method for estimating the feature expectation, a quantity involved in most of state-of-the-art approaches which were thus extended to a batch off-policy setting. The second major contribution is an Inverse Reinforcement Learning algorithm, structured classification for inverse reinforcement learning (SCIRL), which relaxes a standard constraint in the field, the repeated solving of a Markov Decision Process, by introducing the temporal structure (using the feature expectation) of this process into a structured margin classification algorithm. The afferent theoritical guarantee and the good empirical performance it exhibited allowed it to be presentend in a good international conference: NIPS. Finally, the third contribution is cascaded supervised learning for inverse reinforcement learning (CSI) a method consisting in learning the expert's behavior via a supervised learning approach, and then introducing the temporal structure of the MDP via a regression involving the score function of the classifier. This method presents the same type of theoretical guarantee as SCIRL, but uses standard components for classification and regression, which makes its use simpler. This work will be presented in another good international conference: ECML, Cette thèse, intitulée "Contributions à l'apprentissage par renforcement inverse", fournit trois contributions majeures au domaine. La première est une méthode d'estimation de l'attribut moyen, une quantité exploitée par la grande majorité des approches constituant l'état de l'art. Elle a permis d'étendre ces approches au cadre batch et off-policy. La seconde contribution majeure est un algorithme d'apprentissage par renforcement inverse, structured classification for inverse reinforcement learning (SCIRL), qui relâche une contrainte standard du domaine, la résolution répétée d'un processus décisionnel de Markov en introduisant la structure temporelle (par le biais de l'attribut moyen) de ce processus dans un algorithme de classification structurée. Les garanties théoriques qui lui sont attachées et ses bonnes performances en pratique ont permis sa présentation dans une conférence internationale prestigieuse : NIPS. Enfin, la troisième contribution est constituée par la méthode cascaded supervised learning for inverse reinforcement learning (CSI) consistant à apprendre le comportement de l'expert par une méthode supervisée puis à introduire la structure temporelle du MDP par une régression mettant en jeu la fonction de score du classifieur utilisé. Cette méthode offre des garanties théoriques de même nature que celle de SCIRL tout en présentant l'avantage d'utiliser des composants standards pour la classification et la régression, ce qui simplifie la mise en oeuvre. Ce travail sera présenté dans une autre conférence internationale prestigieuse : ECML

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 λ Policy Iteration (LSλPI), adds to LSPI an idea of λ-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λ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 Lőrincz, 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.

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 λ Policy Iteration (LSλPI), adds to LSPI an idea of λ-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λ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 Lőrincz, 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.

Rapport stage master; This paper considers the problem of longitudinal control of a linear platoon and proposes a new approach based on reinforcement learning. So far, different approaches have been proposed in the literature. Among them global and near-to-near approaches are often opposed. While the global approach needs that each vehicle acquires the global state of the platoon, the near-to-near approach only needs local information that each vehicle can get through its on-board sensors. This former approach does not need communication infrastructure and is therefore more robust. This paper proposes an approach in which the control law defining the behavior of each vehicle is automatically learnt using a simple reinforcement learning algorithm (Q-learning). A simulator based on a kinematic model defining the dynamic of each vehicle in the platoon permits through an exploration and exploitation process, to obtain an optimal policy for each vehicle in the platoon. Although Q-learning is based on a discrete representation of states and actions, we demonstrated that this technique makes it possible to build efficient controllers when compared to traditional approaches. A comparison with other longitudinal platooning algorithms is presented and it demonstrates the relevancy of our approach. Furthermore, we show that such a controller can be safe as it can be proven to be collision free.

National audience; Dans le cadre du contrôle optimal stochastique, nous proposons une manière modifiée de mettre en oeuvre l'algorithme λ-Policy Iteration (Bertsekas & Tsitsiklis, 1996), une méthode qui généralise Value Iteration et Policy Iteration en introduisant un paramètre λ. Nous montrons que cette version modifiée, qui est analogue à Modified Policy Iteration, généralise tous ces algorithmes et converge vers la fonction de valeur optimale. En nous appuyant sur des arguments analytiques et expérimentaux, nous mettons en évidence le fait que lorsque l'algorithme est appliqué de manière exacte, le paramètre λ ne permet pas d'améliorer la vitesse de convergence de manière significative.

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.; 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., 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.

La complexité des problèmes de décision dans l'incertain dépendant du temps provient sou-vent de l'interaction de plusieurs processus concurrents. Les Processus Décisionnels Semi-Markoviens Généralisés (GSMDP) consituent un formalisme efficace et élégant pour représenter à la fois les aspects de concurrence d'événements et d'actions et d'incertitude. Nous proposons un formalisme GSMDP étendu à un temps observable et un espace d'états hybride. Sur cette base, nous introduisons un nouvel algorithme inspiré de l'itération de la politique approchée afin de construire des politiques efficaces. Cet algorithme repose sur une exploration guidée par la simulation et utilise les techniques d'appren-tissage à vecteurs supports. Nous illustrons cet algorithme sur un exemple et en proposons une version améliorée qui compense sa principale faiblesse.

This thesis deals with decision-theoretic autonomous agents. This work consists in constructing a control system for a resource-bounded agent evolving in a uncertain environment. Such agents must be able to control their resources consumption during a mission. The first part of this thesis introduces the concept of planning under uncertainty in general, and Markov decision processes (MDP) in particular, for the control. Solving techniques of large MDPs are presented. In this control system, we consider resource-bounded agents adopting progressive reasoning as a specific resource-bounded reasoning with anytime behavior. We call progressive processing units (PRU) the task structure which allows the agent to adapt the quality of their accomplishment to the available resources. Each PRU defines a multi-level hierarchy task, to better accomplish the mission.This thesis presents two extensions of the progressive reasoning : the control of multiple resources and an adaptive control system that faces changes during the mission. Firstly, algorithms are presented to avoid combinatorial explosion due to the multiple resources. Secondly, a value function approximation algorithm permits to quickly obtain a control system when the mission suddenly changes. Promising experimental results have been obtained and illustrated on a real robot., Cette thèse se situe dans le cadre de la décision pour un agentrationnel et autonome. Le travail consiste à élaborer un système decontrôle intelligent pour un agent évoluant dans un environnementincertain. L'agent doit pouvoir contrôler sa consommation de ressourcesau cours d'une mission prédéfinie. La première partie de cette thèseintroduit le concept de planification sous incertitude. Une présentationdes processus décisionnels de Markov (MDP) précède un état de l'art surles techniques de résolution de MDP de grande taille.Ce système de contrôle de ressources s'appuie sur le raisonnementprogressif. Le raisonnement progressif permet de modéliser un ensemblede tâches sous forme d'unités de raisonnement progressif (ou PRUs).Chaque PRU définit des niveaux de réalisation pour une tâche donnée,donnant lieu à des qualités croissantes de réalisation. Chaque niveauest lui-même composé de modules dont un seul sera retenu pour saréalisation. Choisir un module plutôt qu'un autre permet à l'agent defaire un compromis entre la qualité de la tâche accomplie et lesressources consommées.Cette thèse présente deux extensions du raisonnement progressif : laprise en compte de ressources multiples et l'adaptation à un changementde mission. Premièrement, des algorithmes sont présentés pour faire faceà l'explosion combinatoire due à l'introduction de nouvelles ressources.Deuxièmement, l'élaboration d'un algorithme d'approximation de fonctionde valeur permet d'obtenir rapidement un système de contrôle pours'adapter à un éventuel changement de mission. Une expérience estfinalement menée sur un robot réel qui contre ses ressources grâce auraisonnement progressif.

This thesis deals with distributed multiagent decision-making underuncertainty. We formalize this problem with Decentralized MarkovDecision Processes (DEC-MDP) which extends Markov Decision Processes(MDP) to multi-agent settings. Even if DEC-MDPs describe an expressiveframework for cooperative multiagent decision, they suffer from a highcomplexity and fail to formalize constraints on task execution.Despite the wide variety of approaches to solve DEC-MDPs, computinga solution for large problems remains a serious challenge even forapproximation approaches.We develop an approach that can solve large problems, and that candeal with more complex time and action representations. We thereforedefine a class of DEC-MDP, OC-DEC-MDP, that allows us to considerseveral possible durations for each task taking into accountconstraints on task execution. Having considered the representationof the problems we deal with, we turn to OC-DEC-MDP resolution. Ourpurpose is to develop an efficient planning approach that computeseach agent's policy even for large missions. Given the highcomplexity of finding an optimal solution, we aim at computing anapproximate solution. We also split the multiagent decision probleminto a set of MDPs. For purposes of coordinating the agents, we thenintroduce the notion of Opportunity Cost., Cette thèse porte sur la prise de décision distribuée dans dessystèmes multi-agents agissant sous incertitude (les colonies derobots autonomes par exemple). Les processus décisionnels de MarkovDécentralisés décrivent un formalisme mathématique permettant demodéliser et de résoudre de tels problèmes. Leur utilisation pour laplanification des tâches dans des applications réelles posetoutefois quelques difficultés. Le modèle usuel des DEC-MDPs nepermet par exemple pas la prise en compte de contraintes sur l'exécution des tâches. De plus,la complexité de leur résolution est telle qu'il est difficile de déterminer une solution optimale excepté pour de petits problèmes.Le travail que nous présentons dans cette thèse a pour premier objectifd'adapter le modèle des DEC-MDPs afin de proposer une modélisationadéquate du temps et des actions, et de permettre la représentation deproblèmes réels. Nous décrivons ainsi une nouvelle classe deDEC-MDPs : les OC-DEC-MDPs (DEC-MDP avec Coût Occasionné). Dans un second temps,nous nous intéressons à leur résolution. Nous proposons différentsalgorithmes procédant à la planification des tâches de chaque agenten vue d'une prise de décision décentralisée et autonome, en accordavec les contraintes du problème. Afin de développer des algorithmesefficaces et de traiter des problèmes de taille importante, nous recherchons uneapproximation de la solution optimale. Nous procédonségalement à un découpage du problème initial en un ensemble de MDPs,et introduisons la notion de coût occasionné afin de tenir comptedes interactions entre les agents et de calculer des politiquescoopératives.

De nombreux problèmes de planification s'inscrivent dans un environnement instationnaire. Dans le cadre de la décision dans l'incertain sur horizon infini, pour les problèmes stationnaires à l'infini, on se propose de définir un cadre de modélisation dérivé du modèle SMDP dans lequel la variable temporelle est observable par l'agent. Dans ce cadre, nous développons trois approches de résolution différentes afin de générer des politiques qui en tout état discret du système spécifient l'action optimale à entreprendre en fonction de la date courante.

Nous proposons un nouveau formalisme de représentation des actions et des interactions dans les SMA réactifs inspiré des processus de décision Markoviens décentralisés (DEC-MDP). Ce formalisme appelé Interac-DEC-MDP permet de représenter dans un même cadre homogène les actions individuelles et les interactions directes entre agents. Ainsi il permet de calculer automatiquement les prises de décisions des agents relativement aux actions et aux déclenchements et résolution des interactions par l'introduction de la rationalité au travers de la notion de récompense. Un premier problème simple de partage de ressources impliquant 2 agents a été modélisé selon le formalisme proposé et les comportements des agents ont été construits automatiquement par Q-learning. Les premiers résultats bien qu'obtenus avec des hypothèses limitatives montrent qu'il est possible à partir d'apprentissages simples de construire automatiquement des comportements collectifs pertinents.

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.

Colloque avec actes et comité de lecture. nationale.; National audience; Nous proposons un nouveau formalisme de représentation des actions et des interactions dans les SMA réactifs inspiré des processus de décision Markovien décentralisés (DEC-MDP). Ce formalisme appelé Interac-DEC-MDP permet de représenter dans un même cadre homogène les actions individuelles et les inter\-actions directes entre agents. Ainsi il permet de calculer automatiquement les prises de décisions des agents relativement aux actions et aux déclenchements et résolution des interactions par l'introduction de la rationalité au travers de la notion de récompense. Un premier problème simple de partage de ressources impliquant 2 agents a été modélisé selon le formalisme proposé et les comportements des agents ont été construits automatiquement par Q-learning. Les premiers résultats bien qu'obtenus avec des hypothèses limitatives montrent qu'il est possible à partir d'apprentissages simples de construire automatiquement des comportements collectifs pertinents.

Article dans revue scientifique avec comité de lecture. nationale.; National audience; 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. Le contrôle optimal est une théorie computationnelle qui permet 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. Si le contrôle optimal caractérise un "but" (l'optimisation d'un critère), l'approche connexionniste suggère, elle, une "manière" de calculer. Nous décrivons plusieurs problématiques s'inscrivant dans le cadre du contrôle optimal et montrons qu'elles admettent des solutions qui sont connexionnistes : 1) Le contrôle optimal et sa variante adaptative (l'apprentissage par renforcement) dans un petit espace d'états 2) L'apprentissage d'une représentation pour approximer le problème de contrôle optimal ayant un grand espace d'états.

This thesis studies the use of connectionist algorithms for solving reinforcement learning problems. Connectionist algorithms are inspired by the way information is processed by the brain: they rely on a large network of highly interconnected simple units, which process numerical information in a distributed and massively parallel way. Reinforcement learning is a computational theory that describes the interaction between an agent and an environment: it enables to precisely formalize goal-directed learning from interaction.We have considered three problems, with increasing complexity, and shown that they can be solved with connectionist algorithms: 1) Reinforcement learning in a small state space: we exploit a well-known algorithm in order to build a connectionist network: the problem's paramaters are stored into weighted units and connections and the planning is the result of a distributed activity in the network. 2) Learning a representation for approximating a reinforcement learning problem with a large state space: we provide an algorithm for automatically building a state space partition in order to approximate a large problem. 3) Self-organization of specialized modules for approximating various reinforcement problems with a large state space: we exploit a ``divide and conquer'' approach and show that various tasks can efficiently be spread over a little number of specialized functional modules.; 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.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.

Stage de DEA. Rapport de stage.; We study the prey-predator problem as a multi-agent system (MAS). We consider an hierarchical approach to searching optimal policies for each agent to capture the prey. In particular, we imagine decomposition of the state-space, and of the "situation" space. In other words, we consider an hierarchy of policies, the agent following the one which is most appropriate for his current state-space and for the situation in that state-space.

Colloque avec actes et comité de lecture. nationale.; National audience; Nous proposons une nouvelle approche de conception d'agents coopératifs à l'aide de processus décisionnels de Markov (MDPs). Cette méthode de conception tire profit de deux propriétés fondamentales de nos agents : la subjectivité et l'empathie. Tandis que la subjectivité s'intéresse aux problèmes de conception de plan réactif dans des conditions de perceptions incomplètes d'un environnement, l'empathie d'un agent permet de prévoir les incertitudes de comportements de ses compères et de coordonner ses actions. Notre travail sur l'étude théorique de convergence des plans réactifs ainsi calculés a montré que les algorithmes convergeaient dans des conditions favorables vers un équilibre de Nash. || In this paper, we propose a new method for designing cooperative MAS using Markov decision processes (MDPs). Our approach is based on two major agents properties : the sujectivity and the empathy. Whereas the subjectivity helps to compute the reactive pol

Colloque avec actes et comité de lecture. internationale.; International audience; This paper proposes a decision­theoric approach for designing a set of situated agents so that they can solve a cooperative problem. The design of each agent's behavior results from solving a decentralized partially observable markov decision process (DEC­POMDP). But, as solving a DEC­POMDP is NEX P­complete, we propose an approximate solution to this problem based on subjectivity and empathy.

Colloque avec actes et comité de lecture. internationale.; International audience; This paper presents an original algorithm, based on Markov Decision Processes (MDPs), that is used to solve the frequency assignment problem in the field of radiobroadcasting. The results obtained by this algorithm are compared to the best known results obtained by hybrid genetic algorithm, ant colony paradigms and the best operating solution in the field of radiobroadcasting in France.

In the microrobotics field, the control of systems is difficult because the physical phenomena connected to the microscopic scale are complex. The reinforcement learning methods constitute an interesting approach because they allow to draw up a control policy without any knowledge of the system. With regard to the large dimensions of the state spaces of the studied systems, we developed a parallel approach which is inspired by the behaviour-based architectures and by the reinforcement learning. This architecture is based on parallel Q-Learning algorithms. It allows to reduce the system complexity and to speed up the learning process. On the gridworld example, the results are good but the learning time is too long to control a real system. Then, the Q-Learning algorithm was replaced by the Dyna-Q algorithm which we adapted to the control of no deterministic systems by using a chronological account of the last transitions. This architecture, called parallel Dyna-Q, allows to increase the convergence speed and also to find better control policies. The experiments done with the real manipulation system show that the learning is possible in real time without no need of simulations. The behaviours co-ordination function works well if the obstacles are separated from each others. If that is not case, it can create local maxima which trap temporarily the system in a cycle. So, we developed another co-ordination function which creates a more global model of the system from the model of transition built with the Dyna-Q algorithm. This new co-ordination function allows to go out of local maxima if the temporal pattern matching function used by the architecture is sturdy., 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.

Article dans revue scientifique avec comité de lecture.; In this paper, we present a new tool for solving weakly-coupled Markov Decision Processes using decomposition techniques. Using a predefined partition of the MDP, a directed graph is built to decompose the global MDP into small local MDPs which are independently solved. An approximate solution for the global MDP is obtained by combining local solutions. Our approach has been tested on a mobile robotics application. It allows near-optimal solutions to be obtained in significantly reduced time. We also present preliminary results concerning a parallel implantation of our tool.

Colloque avec actes et comité de lecture.; Decomposing an MDP consists in (1) partitioning the state space into regions; (2) solving each region independently; (3) combining the local solutions to generate a global one. In our approach, domain characteristics are used to accurately define how region communicates with each others, which is very important to ensure good quality of the approximate policies obtained. We apply it to mobile robotics planning in indoor environments.

Colloque avec actes et comité de lecture.; Markov Decision Processes have been successfully used in robotics for indoor robot navigation problems. They allow to compute optimal sequences of actions in order to achieve a given goal, accounting for actuators uncertainties. But MDPs are weak to avoid unknown obstacles. At the opposite reactive navigators are particulary a dapted to that, and don't need any prior knowledge about the environment. But they are unable to plan the set of actions that will permit the realization of a given mission. We present a new state aggregation technique for Markov Decision Processes, such that part of the work usually dedicated to the planner is achieved by a reactive navigator. Thus some characteristics of our environments, such as width of corridors, have not to be considered, which allows to cluster states together, si gnificantly reducing the state space. As a consequence, policies are computed faster and are shown to be at least as efficient as optimal ones.

Dans le cadre des problèmes décisionnels de Markov, les deux algorithmes de référence d'apprentissage par renforcement de stratégies optimales sont respectivement le Q-Learning et le R-Learning. Dans nos travaux précédents[?, nous avons adapté ces deux algorithmes au cas particulier des problèmes non stationnaires à horizon fini. Nous présentons ici la méthode de l'équation différentielle ordinaire (ODE) pour les algorithmes adaptatifs controlés comme un outil original d'analyse et de comparaison des algorithmes d'apprentissage par renforcement de type Q-Learning ou R-Learning. Son application en horizon fini permet ainsi de retrouver un théorème de convergence pour le Q-Learning, en faisant apparaître explicitement l'importance de la fonction d'exploration utilisée au cours de l'aprentissage, puis d'expliquer en partie la supériorité des méthodes de type R-Learning observée expérimentalement, à travers une analyse des gains d'apprentissage.