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

Nos travaux de recherches présentés dans ce manuscrit ont pour objectif, l'optimisation des performances des algorithmes de suivi des formants. Pour ce faire, nous avons commencé par l'analyse des différentes techniques existantes utilisées dans le suivi automatique des formants. Cette analyse nous a permis de constater que l'estimation automatique des formants reste délicate malgré l'emploi de diverses techniques complexes. Vue la non disponibilité des bases de données de référence en langue arabe, nous avons élaboré un corpus phonétiquement équilibré en langue arabe tout en élaborant un étiquetage manuel phonétique et formantique. Ensuite, nous avons présenté nos deux nouvelles approches de suivi de formants dont la première est basée sur l'estimation des crêtes de Fourier (maxima de spectrogramme) ou des crêtes d'ondelettes (maxima de scalogramme) en utilisant comme contrainte de suivi le calcul de centre de gravité de la combinaison des fréquences candidates pour chaque formant, tandis que la deuxième approche de suivi est basée sur la programmation dynamique combinée avec le filtrage de Kalman. Finalement, nous avons fait une étude exploratrice en utilisant notre corpus étiqueté manuellement comme référence pour évaluer quantitativement nos deux nouvelles approches par rapport à d'autres méthodes automatiques de suivi de formants. Nous avons testé la première approche par détection des crêtes ondelette, utilisant le calcul de centre de gravité, sur des signaux synthétiques ensuite sur des signaux réels de notre corpus étiqueté en testant trois types d'ondelettes complexes (CMOR, SHAN et FBSP). Suite à ces différents tests, il apparaît que le suivi de formants et la résolution des scalogrammes donnés par les ondelettes CMOR et FBSP sont meilleurs qu'avec l'ondelette SHAN. Afin d'évaluer quantitativement nos deux approches, nous avons calculé la différence moyenne absolue et l'écart type normalisée. Nous avons fait plusieurs tests avec différents locuteurs (masculins et féminins) sur les différentes voyelles longues et courtes et la parole continue en prenant les signaux étiquetés issus de la base élaborée comme référence. Les résultats de suivi ont été ensuite comparés à ceux de la méthode par crêtes de Fourier en utilisant le calcul de centre de gravité, de l'analyse LPC combinée à des bancs de filtres de Mustafa Kamran et de l'analyse LPC dans le logiciel Praat. D'après les résultats obtenus sur les voyelles /a/ et /A/, nous avons constaté que le suivi fait par la méthode ondelette avec CMOR est globalement meilleur que celui des autres méthodes Praat et Fourier. Cette méthode donne donc un suivi de formants (F1, F2 et F3) pertinent et plus proche de suivi référence. Les résultats des méthodes Fourier et ondelette sont très proches dans certains cas puisque toutes les deux présentent moins d'erreurs que la méthode Praat pour les cinq locuteurs masculins ce qui n'est pas le cas pour les autres voyelles où il y a des erreurs qui se présentent parfois sur F2 et parfois sur F3. D'après les résultats obtenus sur la parole continue, nous avons constaté que dans le cas des locuteurs masculins, les résultats des deux nouvelles approches sont notamment meilleurs que ceux de la méthode LPC de Mustafa Kamran et ceux de Praat même si elles présentent souvent quelques erreurs sur F3. Elles sont aussi très proches de la méthode par détection de crêtes de Fourier utilisant le calcul de centre de gravité. Les résultats obtenus dans le cas des locutrices féminins confirment la tendance observée sur les locuteurs / Our research work presented in this thesis aims the optimization of the performance of formant tracking algorithms. We began by analyzing different existing techniques used in the automatic formant tracking. This analysis showed that the automatic formant estimation remains difficult despite the use of complex techniques. For the non-availability of database as reference in Arabic, we have developed a phonetically balanced corpus in Arabic while developing a manual phonetic and formant tracking labeling. Then we presented our two new automatic formant tracking approaches which are based on the estimation of Fourier ridges (local maxima of spectrogram) or wavelet ridges (local maxima of scalogram) using as a tracking constraint the calculation of center of gravity of a set of candidate frequencies for each formant, while the second tracking approach is based on dynamic programming combined with Kalman filtering. Finally, we made an exploratory study using manually labeled corpus as a reference to quantify our two new approaches compared to other automatic formant tracking methods. We tested the first approach based on wavelet ridges detection, using the calculation of the center of gravity on synthetic signals and then on real signals issued from our database by testing three types of complex wavelets (CMOR, SHAN and FBSP). Following these tests, it appears that formant tracking and scalogram resolution given by CMOR and FBSP wavelets are better than the SHAN wavelet. To quantitatively evaluate our two approaches, we calculated the absolute difference average and standard deviation. We made several tests with different speakers (male and female) on various long and short vowels and continuous speech signals issued from our database using it as a reference. The formant tracking results are compared to those of Fourier ridges method calculating the center of gravity, LPC analysis combined with filter banks method of Kamran.M and LPC analysis integrated in Praat software. According to the results of the vowels / a / and / A /, we found that formant tracking by the method with wavelet CMOR is generally better than other methods. Therefore, this method provides a correct formant tracking (F1, F2 and F3) and closer to the reference. The results of Fourier and wavelet methods are very similar in some cases since both have fewer errors than the method Praat. These results are proven for the five male speakers which is not the case for the other vowels where there are some errors which are present sometimes in F2 and sometimes in F3. According to the results obtained on continuous speech, we found that in the case of male speakers, the result of both approaches are particularly better than those of Kamran.M method and those of Praat even if they are often few errors in F3. They are also very close to the Fourier ridges method using the calculation of center of gravity. The results obtained in the case of female speakers confirm the trend observed over the male speakers

Dans l’état de l’art actuel, la reconnaissance de symboles signifie généralement la reconnaissance des symboles isolés. Cependant, ces méthodes de reconnaissance de symboles isolés ne sont pas toujours adaptés pour résoudre les problèmes du monde réel. Dans le cas des documents composites qui contiennent des éléments textuels et graphiques, on doit être capable d’extraire et de formaliser les liens qui existent entre les images et le texte environnant, afin d’exploiter les informations incorporées dans ces documents.Liés à ce contexte, nous avons d’abord introduit une méthode de reconnaissance graphique basée sur la programmation dynamique et la mise en correspondance de caractéristiques issues de la transformée de Radon. Cette méthode permet d’exploiter la propriété de cette transformée pour inclure à la fois le contour et la structure interne des formes sans utiliser de techniques de compression de la représentation du motif dans un seul vecteur et qui pourrait passer à côté d’informations importantes. La méthode surpasse en performances les descripteurs de forme de l’état de l’art, mais reste principalement adapté pour la reconnaissance de symboles isolés seulement. Nous l’avons donc intégrée dans une approche complètement nouvelle pour la reconnaissance de symboles basé sur la description spatio-structurelle d’un «vocabulaire» de primitives visuelles extraites. La méthode est basée sur les relations spatiales entre des paires de types étiquetés de ce vocabulaire (dont certains peuvent être caractérisés avec le descripteur mentionné précédemment), qui sont ensuite utilisées comme base pour construire un graphe relationnel attribué (ARG) qui décrit des symboles. Grâce à notre étiquetage des types d’attribut, nous évitons le problème classique NP-difficile d’appariement de graphes. Nous effectuons une comparaison exhaustive avec d’autres modèles de relations spatiales ainsi qu’avec l’état de l’art des approches pour la reconnaissance des graphismes afin de prouver que notre approche combine efficacement les descripteurs statistiques structurels et globaux et les surpasse de manière significative.Dans la dernière partie de cette thèse, nous présentons une approche de type sac de caractéristiques utilisant les relations spatiales, où chaque paire possible primitives visuelles est indexée par sa configuration topologique et les types visuels de ses composants. Ceci fournit un moyen de récupérer les symboles isolés ainsi que d’importantes parties connues de symboles en appliquant soit un symbole isolée comme une requête soit une collection de relations entre les primitives visuelles. Finalement, ceci ouvre des perspectives vers des processus de reconnaissance de symboles fondés sur le langage naturel / In the current state-of-the-art, symbol recognition usually means recognising isolated symbols. However, isolated symbol recognition methods are not always suitable for solving real-world problems. In case of composite documents that contain textual and graphical elements, one needs to be able to extract and formalise the links that exist between the images and the surrounding text, in order to exploit the information embedded in those documents.Related to this context, we first introduce a method for graphics recognition based on dynamic programming matching of the Radon features. This method allows to exploit the Radon Transform property to include both boundary and internal structure of shapes without compressing the pattern representation into a single vector that may miss information. The method outperforms all major set of state-of-the-art of shape descriptors but remains mainly suited for isolated symbol recognition only. We therefore integrate it in a completely new approach for symbol recognition based on the spatio-structural description of a ‘vocabulary’ of extracted visual primitives. The method is based on spatial relations between pairs of labelled vocabulary types (some of which can be characterised with the previously mentioned descriptor), which are further used as a basis for building an attributed relational graph (ARG) to describe symbols. Thanks to our labelling of attribute types, we avoid the general NP-hard graph matching problem. We provide a comprehensive comparison with other spatial relation models as well as state-of-the-art approaches for graphics recognition and prove that our approach effectively combines structural and statistical descriptors together and outperforms them significantly.In the final part of this thesis, we present a Bag-Of-Features (BOFs) approach using spatial relations where every possible pair of individual visual primitives is indexed by its topological configuration and the visual type of its components. This provides a way to retrieve isolated symbols as well as significant known parts of symbols by applying either an isolated symbol as a query or a collection of relations between the important visual primitives. Eventually, it opens perspectives towards natural language based symbol recognition process

No description available.

Face à l'augmentation du prix du carburant et des exigences légales rigoureuses sur les émissions de gaz à effet de serre ces dernières années, les fabricants de camions doivent s'interroger davantage sur les nouvelles mesures techniques pour être plus compétitifs sur le marché. Dans ce contexte, l'électromobilité est l'une des approches les plus prometteuses pour répondre aux exigences ci-dessus, où sa solution principale est l'hybridation électrique du groupe motopropulseur. Parallèlement à cette solution, une autre solution technique de l'électromobilité, l'électrification auxiliaire qui apparaît récemment, devient aussi une solution attrayante non seulement pour le milieu universitaire, mais aussi pour les entreprises de l'automobile. Cependant, l'intégration de ces deux solutions dans un véhicule peut donner lieu à un problème de commande du système beaucoup plus compliqué, notamment en terme de gestion de l'énergie. L'objectif de ce travail est de concevoir une approche appropriée pour la conception de la commande auxiliaire électrifiée, qui peut gérer d'une part la stratégie de commande du groupe motopropulseur hybride électrique et, d'autre part, améliorer l'efficacité énergétique globale du véhicule. Tout d'abord, le travail se concentre sur un seul auxiliaire électrifié typique - le système d'alimentation en air. Pour ce cas simple, la modélisation et le contrôle à base d'énergie basés sur le contrôle prédictif (MPC) sont développés afin de minimiser la consommation d'énergie / l'efficacité de cet auxiliaire le long d'un cycle de conduite. En soulignant les difficultés à atteindre l'objectif en matière d'efficacité énergétique en considérant uniquement des unités auxiliaires, l'approche se concentre ensuite sur l'analyse d'impact du système auxiliaire sur l'efficacité énergétique globale du véhicule. La première étape de cette analyse propose une méthode générale pour simplifier le contrôleur de groupe motopropulseur de HEV / PHEVs. Ensuite, une méthode basée sur l'optimisation est présentée et appliquée sur un modèle de véhicule simplifié, qui contient le contrôleur de groupe motopropulseur simple obtenu à partir de l'étape ci-dessus. Cette méthode d'optimisation, qui est un contrôle en mode hors connexion et basée sur la méthode de programmation dynamique, permet de déterminer l'économie d'énergie maximale réalisable du véhicule lors de l'application d'une stratégie de contrôle avancée sur le système auxiliaire électrifié. De plus, certaines idées / règles pour concevoir le contrôle auxiliaire sont également tirées des résultats obtenus avec la méthode ci-dessus. Pour une mise en oeuvre en ligne de ces concepts, un contrôle multi-agent est finalement adopté pour la commande du système auxiliaire électrifié (EAS). Sur la base des résultats de l'étape d'analyse d'impact et d'un modèle simple de l'EAS, trois paramètres de contrôle pour l'EAS (centralisé, hiérarchisé et distribué) sont étudiés et discutés. Enfin, différents algorithmes pour ces paramètres de contrôle sont fournis, puis comparés pour indiquer les avantages et les limites de chaque algorithme. / Facing to the increase of fuel price and stringent legal requirements on the greenhouse gas emission in recent years, truck manufacturers have to investi-gate more on new technical measures to be more competitive on the market. Within this context, electromobility rises as one of the most promising approaches to answer to above requirements, where its principle solution is the electric hybridization of powertrain. In parallel with this solution, another technical solution of electromobility- the auxiliary electrification that appears recently becomes also an attractive solution for not only the academic community but also the automotive companies. However, the integration of these two solutions together in a vehicle can give rise to a much more complicated system control problem, especially in term of energy management. The objective of this work is to figure out an appropriate approach for designing the electrified auxiliary control, which can cope with the control strategy of the electric hybrid powertrain on one hand, and can improve the overall energy efficiency of the vehicle on the other hand. Firstly, the work focuses on only one typical electrified auxiliary- the air supply system. For this simple case, energy-based modeling and control based on predictive control (MPC) are developed in order to minimize the energy consumption/efficiency of this auxiliary along a driving cycle. By pointing out the difficulties for reaching the target on the energy efficiency when considering only auxiliary units, the approach focuses then on the impact analysis of the auxiliary system on the overall vehicle‘s energy efficiency. The first step of this analysis proposes a general method to simplify the powertrain controller of HEV/PHEVs. Then, an optimization-based method is presented and applied on a simplified vehicle model, which contains the simple powertrain controller obtained from the above step. This optimization method, which is an offline con-trol and based on the dynamic programming method, allows us to determine the maximal achievable energy saving of the vehicle when applying an advanced control strategy on the electrified auxiliary system. Additionally, some ideas/rules for designing the auxiliary control are drawn as well from the results obtained with the above method. Toward an online implementation of these concepts, a multi-agent based control is finally adopted for controlling the electrified auxiliary system (EAS). Based on the results of the impact analysis step and a simple model of the EAS, three control settings for the EAS (centralized, hierarchical, and distributed) are studied and discussed. Finally, different algorithms for these control settings are provided, and then compared to point out the advantages and limitations of each algorithm.

Durant leur évolution, les génomes accumulent des mutations pouvant affecter d’un nucléotide à plusieurs gènes. Les modifications au niveau du nombre et de l’organisation des gènes dans les génomes sont dues à des mutations globales, telles que les duplications, les pertes et les réarrangements. En comparant les ordres de gènes des génomes, il est possible d’inférer les événements évolutifs les plus fréquents, le contenu en gènes des espèces ancestrales ainsi que les histoires évolutives ayant menées aux ordres observés. Dans cette thèse, nous nous intéressons au développement de nouvelles méthodes algorithmiques, par approche d’alignement, afin d’analyser ces différents aspects de l’évolution des génomes. Nous nous intéressons à la comparaison de deux ou d’un ensemble de génomes reliés par une phylogénie, en tenant compte des mutations globales. Pour commencer, nous étudions la complexité théorique de plusieurs variantes du problème de l’alignement de deux ordres de gènes par duplications et pertes, ainsi que de l’approximabilité de ces problèmes. Nous rappelons ensuite les algorithmes exacts, en temps exponentiel, existants, et développons des heuristiques efficaces. Nous proposons, dans un premier temps, DLAlign, une heuristique quadratique pour le problème d’alignement de deux ordres de gènes par duplications et pertes. Ensuite, nous présentons, OrthoAlign, une extension de DLAlign, qui considère, en plus des duplications et pertes, les réarrangements et les substitutions. Nous abordons également le problème de l’alignement phylogénétique de génomes. Pour commencer, l’heuristique OrthoAlign est adaptée afin de permettre l’inférence de génomes ancestraux au noeuds internes d’un arbre phylogénétique. Nous proposons enfin, MultiOrthoAlign, une heuristique plus robuste, basée sur la médiane, pour l’inférence de génomes ancestraux et d’histoires évolutives d’un ensemble de génomes représentés aux feuilles d’un arbre phylogénétique. / During the evolution process, genomes accumulate mutations that may affect the genome at different levels, ranging from one base to the overall gene content. Global mutations affecting gene content and organization are mainly duplications, losses and rearrangements. By comparing gene orders, it is possible to infer the most frequent events, the gene content in the ancestral genomes and the evolutionary histories of the observed gene orders. In this thesis, we are interested in developing new algorithmic methods based on an alignment approach for comparing two or a set of genomes represented as gene orders and related through a phylogenetic tree, based on global mutations. We study the theoretical complexity and the approximability of different variants of the two gene orders alignment problem by duplications and losses. Then, we present the existing exact exponential time algorithms, and develop efficient heuristics for these problems. First, we developed DLAlign, a quadratic time heuristic for the two gene orders alignment problem by duplications and losses. Then, we developed OrthoAlign, a generalization of DLAlign, accounting for most genome-wide evolutionary events such as duplications, losses, rearrangements and substitutions. We also study the phylogenetic alignment problem. First, we adapt our heuristic OrthoAlign in order to infer ancestral genomes at the internal nodes of a given phylogenetic tree. Finally, we developed MultiOrthoAlign, a more robust heuristic, based on the median problem, for the inference of ancestral genomes and evolutionary histories of extent genomes labeling leaves of a phylogenetic tree.

Nous analysons un type W de système de l’Assemble-à-commande avec des délais de livraison aléatoires, l'arrivée aléatoire de la demande et des ventes perdues, en temps continu. Nous formulons le problème en tant que processus de décision Markov à l'horizon infini. Nous nous éloignons de l'approche standard en caractérisant une région de l'espace d'état où toutes les propriétés de la fonction de coût tiennent. Nous caractérisons la politique optimale dans cette région. En particulier, nous montrons que, dans l'intérieur de la région récurrente, les composants sont toujours produits. Nous caractérisons également la politique d'allocation de composants optimale qui spécifie si une demande de produit arrivant devrait être remplie. Notre analyse révèle que la politique d'allocation optimale est contre-intuitive. Par exemple, même lorsqu'un produit domine l'autre, en termes de coût/taux de vente perdue, sa demande peut ne pas avoir une priorité absolue par rapport à la demande de l'autre produit. Une telle caractéristique n'a pas été observée dans de nombreux paramètres intégrés de production/inventaire où l'allocation d'inventaire suit une priorité fixe pour satisfaire les exigences. Nous montrons également que la structure de la politique optimale reste la même pour les systèmes à production par lots, les temps de production répartis par Erlang et la demande de produits non unitaire. Enfin, nous proposons des heuristiques efficaces qui peuvent être utilisées comme substitut à la politique optimale ou peuvent être utilisées comme une politique de départ pour les algorithmes communs utilisés pour obtenir une politique optimale dans le but de réduire leur temps de calcul. / We analyze a W-configuration assemble-to-order system with random lead times, random arrival of demand, and lost sales, in continuous time. We formulate the problem as an infinite-horizon Markov decision process. We deviate from the standard approach by first characterizing a region (the recurrent region) of the state space where all properties of the cost function hold. We then characterize the optimal policy within this region. In particular, we show that within the interior of the recurrent region components are always produced. We also characterize the optimal component allocation policy which specifies whether an arriving product demand should be fulfilled. Our analysis reveals that the optimal allocation policy is counter-intuitive. For instance, even when one product dominates the other, in terms of lost sale cost and lost sale cost rate (i.e., demand rate times the lost sale cost), its demand may not have absolute priority over the other product’s demand. Such a feature has not been observed in many integrated production/inventory settings where inventory allocation follows a fixed priority in satisfying demands. We also show that the structure of the optimal policy remains the same for systems with batch production, Erlang distributed production times, and non-unitary product demand. Finally, we propose efficient heuristics that can be either used as a substitute for the optimal policy or can be used as a starting policy for the common algorithms that are used to obtain the optimal policy in an effort to reduce their computational time

L’objectif de ce travail est d’exploiter les potentialités offertes par la conduite coopérative afin de fluidifier le trafic au niveau des intersections isolées. Pour ce faire, nous avons proposé un nouveau système de régulation au sein des intersections en s’inspirant du principe de l’intersection autonome. Nous avons appelé notre système : SVAC (système du véhicule-actionneur coopératif). Il repose sur la possibilité des échanges d’information entre le véhicule et son environnement de conduite.Le SVAC permet une régulation plus précise du trafic puisqu’il se base sur les requêtes de droit de passage envoyées par les véhicules réellement présents dans l’intersection. En outre, grâce à la signalisation à bord, la régulation consiste à définir les séquences de passage des véhicules, ce qui permet de personnaliser la signalisation. Le gain de précision soulève plusieurs obstacles. D’une part, nous nous heurtons systématiquement à l’absence de modèles mathématiques permettant d’aborder le problème. D’autre part, la simple énumération des séquences implique une explosion combinatoire, ce qui ne convient pas à l’application temps-réelle de la régulation des intersections. Pour s’affranchir des deux problématiques nous avons utilisé les réseaux de Petri P-temporisés. Le modèle nous a permis de décrire sous la forme d’équations mathématiques les compteurs des différents évènements observés par les véhicules. Deux objectifs de régulation ont été dégagés après avoir déduit le temps moyen d’attente basé sur la formule de Little. Le premier consiste à vider les intersections au plus tôt. Nous avons proposé un algorithme de programmation dynamique et deux heuristiques. La première heuristique est directement issue de l’analyse des propriétés du problème posé. La deuxième est basée sur l’algorithme de colonies de fourmis. En effet, le problème défini est un cas particulier du problème du voyageur de commerce. Le deuxième objectif de régulation consiste à minimiser instantanément la longueur de la file d’attente. Dans ce cadre, nous avons supposé le fonctionnement à vitesse maximale du réseau de Petri. L’utilisation des contraintes sur les ressources nous a permis de définir des règles simples de régulation en utilisant le mapping.Dans ce mémoire, nous avons utilisé la simulation microscopique basée sur les lois de poursuite pour s’approcher du comportement de conduite. La simulation a servi pour la comparaison des différentes approches proposées dans ce mémoire avec les régulateurs adaptatifs et les intersections autonomes. Dans tous les cas notre approche se distingue par un gain de capacité, ce qui nous a encouragé de reproduire le SVAC à travers un prototype de robots. Cette maquette montre la faisabilité du système au moins pour des applications industrielles. / The aim of this work is to benefit from the potential of the cooperative driving in order to optimize the traffic throughput at isolated intersections. To achieve this objective, we have proposed a new traffic control system for isolated intersections: Cooperative Vehicle-Actuation Signalization (CVAS). The concept of this new system is based on the assumption of the ability of exchanging information between each vehicle and the surrounding vehicles or the nearby infrastructure.The system allows more precise control of the traffic since it determines the right-of-way of each vehicle according to its corresponding data sent by the embedded wireless device. The right-of-way is displayed to the driver by means of the onboard signalization. The control system determines the sequence of the vehicles to be directed through the intersection. For the sake of benefiting the improvement brought by the new system, we face several challenges. On the one hand, we are confronted with the absence of a mathematical model to address the control problem. On the other hand, despite the fact that the optimal passing sequence of vehicles can be found by the simple enumeration of all feasible sequences, the exhaustive search does not fulfill the requirements of the real-time application. To overcome these two problems, we seek help from the P-timed Petri nets. This mathematical modeling tool is able to describe the events observed by the position markers in the form of mathematical equations. Two different objectives of the control have been derived from the Little's formula. The first one aims to minimize the maximum exit time of vehicles present in the intersection. An algorithm of dynamic programming and two heuristics have been proposed to achieve this objective. The first heuristic is based on the analysis of the properties of the control problem. The second heuristic is based on the analogy between the dealt problem and the problem of Traveling Salesman Problem, which can be solved successfully by the algorithm of ant colony system. The second objective of the control is to instantly minimize the queue length. A protocol of relaying the right of way has been determined from the assumption of a Petri net that operates at its maximum speed. This simple protocol of control can be extended to all possible layouts of the isolated intersections by using the technique of “mapping”.In this work, a microscopic model (car-following model) is used to simulate the driving behavior. The simulations show that the CVAS system outperforms the other systems which are popularly used at present. It is even better than some innovative systems based on the technology of the cooperative driving. The good results encouraged us to replicate the system under real conditions through a prototype of NXT robots. The tests of this prototype prove the feasibility of the system at least for industrial applications.

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 compose de trois parties indépendantes portant sur l'application du contrôle stochastique à la finance. Dans la première partie, nous étudions le problème de maximisation de la fonction d'utilité dans un marché incomplet avec défauts et information totale/partielle. Nous utilisons le principe de la programmation dynamique pour pouvoir caractériser la fonction valeur solution du problème. Ensuite, nous utilisons cette caractérisation pour en déduire une EDSR dont la fonction valeur est solution. Nous donnons également une approximation de cette fonction valeur. Dans la seconde partie, nous étudions les EDSR à sauts. En utilisant les résultats de décomposition des processus à sauts liée au grossissement progressif de filtration, nous faisons un lien entre les EDSR à sauts et les EDSR browniennes. Cela nous permet de donner un résultat d'existence, un théorème de comparaison ainsi qu'une décomposition de la formule de Feynman-Kac. Puis nous utilisons ces techniques pour la détermination du prix d'une option européenne dans un marché complet et le prix d'indifférence d'un actif contingent non duplicable dans un marché incomplet. Enfin, dans la troisième partie, nous utilisons la théorie des erreurs pour expliquer le risque de liquidité comme une propriété intrinsèque au marché. Cela nous permet de modéliser la fourchette Bid-Ask. Puis nous résolvons dans ce modèle le problème de liquidation optimale d'un portefeuille en temps discret et déterministe en utilisant la programmation dynamique.