Spelling suggestions: "subject:"markovien"" "subject:"anmarkovian""
51 |
Contributions to Simulation-based High-dimensional Sequential Decision Making / Contributions sur la prise de décision séquentielle basée sur des simulations dans des environnements complexes de grande dimensionHoock, Jean-Baptiste 10 April 2013 (has links)
Ma thèse s'intitule « Contributions sur la prise de décision séquentielle basée sur des simulations dans des environnements complexes de grande dimension ». Le cadre de la thèse s'articule autour du jeu, de la planification et des processus de décision markovien. Un agent interagit avec son environnement en prenant successivement des décisions. L'agent part d'un état initial jusqu'à un état final dans lequel il ne peut plus prendre de décision. A chaque pas de temps, l'agent reçoit une observation de l'état de l'environnement. A partir de cette observation et de ses connaissances, il prend une décision qui modifie l'état de l'environnement. L'agent reçoit en conséquence une récompense et une nouvelle observation. Le but est de maximiser la somme des récompenses obtenues lors d'une simulation qui part d'un état initial jusqu'à un état final. La politique de l'agent est la fonction qui, à partir de l'historique des observations, retourne une décision. Nous travaillons dans un contexte où (i) le nombre d'états est immense, (ii) les récompenses apportent peu d'information, (iii) la probabilité d'atteindre rapidement un bon état final est faible et (iv) les connaissances a priori de l'environnement sont soit inexistantes soit difficilement exploitables. Les 2 applications présentées dans cette thèse répondent à ces contraintes : le jeu de Go et le simulateur 3D du projet européen MASH (Massive Sets of Heuristics). Afin de prendre une décision satisfaisante dans ce contexte, plusieurs solutions sont apportées :1. simuler en utilisant le compromis exploration/exploitation (MCTS)2. réduire la complexité du problème par des recherches locales (GoldenEye)3. construire une politique qui s'auto-améliore (RBGP)4. apprendre des connaissances a priori (CluVo+GMCTS) L'algorithme Monte-Carlo Tree Search (MCTS) est un algorithme qui a révolutionné le jeu de Go. A partir d'un modèle de l'environnement, MCTS construit itérativement un arbre des possibles de façon asymétrique en faisant des simulations de Monte-Carlo et dont le point de départ est l'observation courante de l'agent. L'agent alterne entre l'exploration du modèle en prenant de nouvelles décisions et l'exploitation des décisions qui obtiennent statistiquement une bonne récompense cumulée. Nous discutons de 2 moyens pour améliorer MCTS : la parallélisation et l'ajout de connaissances a priori. La parallélisation ne résout pas certaines faiblesses de MCTS ; notamment certains problèmes locaux restent des verrous. Nous proposons un algorithme (GoldenEye) qui se découpe en 2 parties : détection d'un problème local et ensuite sa résolution. L'algorithme de résolution réutilise des principes de MCTS et fait ses preuves sur une base classique de problèmes difficiles. L'ajout de connaissances à la main est laborieuse et ennuyeuse. Nous proposons une méthode appelée Racing-based Genetic Programming (RBGP) pour ajouter automatiquement de la connaissance. Le point fort de cet algorithme est qu'il valide rigoureusement l'ajout d'une connaissance a priori et il peut être utilisé non pas pour optimiser un algorithme mais pour construire une politique. Dans certaines applications telles que MASH, les simulations sont coûteuses en temps et il n'y a ni connaissance a priori ni modèle de l'environnement; l'algorithme Monte-Carlo Tree Search est donc inapplicable. Pour rendre MCTS applicable dans MASH, nous proposons une méthode pour apprendre des connaissances a priori (CluVo). Nous utilisons ensuite ces connaissances pour améliorer la rapidité de l'apprentissage de l'agent et aussi pour construire un modèle. A partir de ce modèle, nous utilisons une version adaptée de Monte-Carlo Tree Search (GMCTS). Cette méthode résout de difficiles problématiques MASH et donne de bons résultats dans une application dont le but est d'améliorer un tirage de lettres. / My thesis is entitled "Contributions to Simulation-based High-dimensional Sequential Decision Making". The context of the thesis is about games, planning and Markov Decision Processes. An agent interacts with its environment by successively making decisions. The agent starts from an initial state until a final state in which the agent can not make decision anymore. At each timestep, the agent receives an observation of the state of the environment. From this observation and its knowledge, the agent makes a decision which modifies the state of the environment. Then, the agent receives a reward and a new observation. The goal is to maximize the sum of rewards obtained during a simulation from an initial state to a final state. The policy of the agent is the function which, from the history of observations, returns a decision. We work in a context where (i) the number of states is huge, (ii) reward carries little information, (iii) the probability to reach quickly a good final state is weak and (iv) prior knowledge is either nonexistent or hardly exploitable. Both applications described in this thesis present these constraints : the game of Go and a 3D simulator of the european project MASH (Massive Sets of Heuristics). In order to take a satisfying decision in this context, several solutions are brought : 1. Simulating with the compromise exploration/exploitation (MCTS) 2. Reducing the complexity by local solving (GoldenEye) 3. Building a policy which improves itself (RBGP) 4. Learning prior knowledge (CluVo+GMCTS) Monte-Carlo Tree Search (MCTS) is the state of the art for the game of Go. From a model of the environment, MCTS builds incrementally and asymetrically a tree of possible futures by performing Monte-Carlo simulations. The tree starts from the current observation of the agent. The agent switches between the exploration of the model and the exploitation of decisions which statistically give a good cumulative reward. We discuss 2 ways for improving MCTS : the parallelization and the addition of prior knowledge. The parallelization does not solve some weaknesses of MCTS; in particular some local problems remain challenges. We propose an algorithm (GoldenEye) which is composed of 2 parts : detection of a local problem and then its resolution. The algorithm of resolution reuses some concepts of MCTS and it solves difficult problems of a classical database. The addition of prior knowledge by hand is laborious and boring. We propose a method called Racing-based Genetic Programming (RBGP) in order to add automatically prior knowledge. The strong point is that RBGP rigorously validates the addition of a prior knowledge and RBGP can be used for building a policy (instead of only optimizing an algorithm). In some applications such as MASH, simulations are too expensive in time and there is no prior knowledge and no model of the environment; therefore Monte-Carlo Tree Search can not be used. So that MCTS becomes usable in this context, we propose a method for learning prior knowledge (CluVo). Then we use pieces of prior knowledge for improving the rapidity of learning of the agent and for building a model, too. We use from this model an adapted version of Monte-Carlo Tree Search (GMCTS). This method solves difficult problems of MASH and gives good results in an application to a word game.
|
52 |
Vers le vol à voile longue distance pour drones autonomes / Towards Vision-Based Autonomous Cross-Country Soaring for UAVsStolle, Martin Tobias 03 April 2017 (has links)
Les petit drones à voilure fixe rendent services aux secteurs de la recherche, de l'armée et de l'industrie, mais souffrent toujours de portée et de charge utile limitées. Le vol thermique permet de réduire la consommation d'énergie. Cependant,sans télédétection d'ascendances, un drone ne peut bénéficier d'une ascendance qu'en la rencontrant par hasard. Dans cette thèse, un nouveau cadre pour le vol à voile longue distance autonome est élaboré, permettant à un drone planeur de localiser visuellement des ascendances sous-cumulus et d’en récolter l'énergie de manière efficace. S'appuyant sur le filtre de Kalman non parfumé, une méthode de vision monoculaire est établie pour l'estimation des paramètres d’ascendances. Sa capacité de fournir des estimations convergentes et cohérentes est évaluée par des simulations Monte Carlo. Les incertitudes de modèle, le bruit de traitement de l'image et les trajectoires de l'observateur peuvent dégrader ces estimés. Par conséquent, un deuxième axe de cette thèse est la conception d'un planificateur de trajectoire robuste basé sur des cartes d'ascendances. Le planificateur fait le compromis entre le temps de vol et le risque d’un atterrissage forcé dans les champs tout en tenant compte des incertitudes d'estimation dans le processus de prise de décision. Il est illustré que la charge de calcul du planificateur de trajectoire proposé est réalisable sur une plate-forme informatique peu coûteuse. Les algorithmes proposés d’estimation ainsi que de planification sont évalués conjointement dans un simulateur de vol à 6 axes, mettant en évidence des améliorations significatives par rapport aux vols à voile longue distance autonomes actuels. / Small fixed-wing Unmanned Aerial Vehicles (UAVs) provide utility to research, military, and industrial sectors at comparablyreasonable cost, but still suffer from both limited operational ranges and payload capacities. Thermal soaring flight for UAVsoffers a significant potential to reduce the energy consumption. However, without remote sensing of updrafts, a glider UAVcan only benefit from an updraft when encountering it by chance. In this thesis, a new framework for autonomous cross-country soaring is elaborated, enabling a glider UAV to visually localize sub-cumulus thermal updrafts and to efficiently gain energy from them.Relying on the Unscented Kalman Filter, a monocular vision-based method is established, for remotely estimatingsub-cumulus updraft parameters. Its capability of providing convergent and consistent state estimates is assessed relyingon Monte Carlo Simulations. Model uncertainties, image processing noise, and poor observer trajectories can degrade theestimated updraft parameters. Therefore, a second focus of this thesis is the design of a robust probabilistic path plannerfor map-based autonomous cross-country soaring. The proposed path planner balances between the flight time and theoutlanding risk by taking into account the estimation uncertainties in the decision making process. The suggested updraftestimation and path planning algorithms are jointly assessed in a 6 Degrees Of Freedom simulator, highlighting significantperformance improvements with respect to state of the art approaches in autonomous cross-country soaring while it is alsoshown that the path planner is implementable on a low-cost computer platform.
|
53 |
Processus stochastiques et systèmes désordonnés : autour du mouvement Brownien / Stochastic processes and disordered systems : around Brownian motionDelorme, Mathieu 02 November 2016 (has links)
Dans cette thèse, on étudie des processus stochastiques issus de la physique statistique. Le mouvement Brownien fractionnaire, objet central des premiers chapitres, généralise le mouvement Brownien aux cas où la mémoire est importante pour la dynamique. Ces effets de mémoire apparaissent par exemple dans les systèmes complexes et la diffusion anormale. L’absence de la propriété de Markov rend difficile l’étude probabiliste du processus. On développe une approche perturbative autour du mouvement Brownien pour obtenir de nouveaux résultats, sur des observables liées aux statistiques des extrêmes. En plus de leurs applications physiques, on explore les liens de ces résultats avec des objets mathématiques, comme les lois de Lévy et la constante de Pickands. / In this thesis, we study stochastic processes appearing in different areas of statistical physics: Firstly, fractional Brownian motion is a generalization of the well-known Brownian motion to include memory. Memory effects appear for example in complex systems and anomalous diffusion, and are difficult to treat analytically, due to the absence of the Markov property. We develop a perturbative expansion around standard Brownian motion to obtain new results for this case. We focus on observables related to extreme-value statistics, with links to mathematical objects: Levy’s arcsine laws and Pickands’ constant. Secondly, the model of elastic interfaces in disordered media is investigated. We consider the case of a Brownian random disorder force. We study avalanches, i.e. the response of the system to a kick, for which several distributions of observables are calculated analytically. To do so, the initial stochastic equation is solved using a deterministic non-linear instanton equation. Avalanche observables are characterized by power-law distributions at small-scale with universal exponents, for which we give new results.
|
54 |
Quelques contributions à l'étude de modèles bivariés de dégradation et de choc en fiabilité / Some contributions to study of bivariate models for deterioration and shocks in reliabilityPham, Hai Ha 15 October 2013 (has links)
La thèse est consacrée à l'étude de modèles bivariés en Fabilité, qui tiennent compte de différents types de dépendance entre composants. Dans un premier temps, nous nous intéressons au cas d'un système formé de deux composants, dont la dégradation est modélisée par un processus de Lévy croissant bivarié (subordinateur bivarié). Sous cette hypothèse, eux études sont faites : l'une sous l'hypothèse de surveillance continue et de réparation parfaite du système, l'autre sous une hypothèse d'inspections périodiques et de réparation imparfaite. Dans un deuxième temps, la thèse est consacrée à un autre modèle de survie bivarié, sous influence d'un environnement stochastique stressant ponctuel. La dépendance entre composants est ici induite par un environnement stressant commun, qui induit des détériorations différentes sur chacun des composants (augmentation du taux de panne pour l'un, du niveau de détérioration pour l'autre). Pour chacun des modèles étudiés, nos résultats montrent l'importance de la prise en compte de la dépendance entre les composants d'un système. / The thesis is devoted to the study of bivariate models in reliability, which take into account several types of dependence between components. As a first step, we are interested in a two-component system with accumulating deterioration modeled by a bivariate increasing Lévy process (bivariate subordinator). Under this hypothesis, two different studies are made : one under the assumption of continuous monitoring and perfect repair, the other one under the assumption of periodic inspections and imperfect repair. In a second step, the thesis is devoted to the study of another bivariate survivalmodel, under the influence of a stochastic and stressful environment. The dependence between components is here induced by the common stressful environment, with different incidence on the two components (increment of failure rate for one, of deterioration level for the other). For each of the studied models, our results show the importance of taking into account the dependence between the components of a system.
|
55 |
Monte Carlo Tree Search for Continuous and Stochastic Sequential Decision Making Problems / Monte Carlo Tree Search pour les problèmes de décision séquentielle en milieu continus et stochastiquesCouetoux, Adrien 30 September 2013 (has links)
Dans cette thèse, nous avons étudié les problèmes de décisions séquentielles, avec comme application la gestion de stocks d'énergie. Traditionnellement, ces problèmes sont résolus par programmation dynamique stochastique. Mais la grande dimension, et la non convexité du problème, amènent à faire des simplifications sur le modèle pour pouvoir faire fonctionner ces méthodes.Nous avons donc étudié une méthode alternative, qui ne requiert pas de simplifications du modèle: Monte Carlo Tree Search (MCTS). Nous avons commencé par étendre le MCTS classique (qui s’applique aux domaines finis et déterministes) aux domaines continus et stochastiques. Pour cela, nous avons utilisé la méthode de Double Progressive Widening (DPW), qui permet de gérer le ratio entre largeur et profondeur de l’arbre, à l’aide de deux méta paramètres. Nous avons aussi proposé une heuristique nommée Blind Value (BV) pour améliorer la recherche de nouvelles actions, en utilisant l’information donnée par les simulations passées. D’autre part, nous avons étendu l’heuristique RAVE aux domaines continus. Enfin, nous avons proposé deux nouvelles méthodes pour faire remonter l’information dans l’arbre, qui ont beaucoup amélioré la vitesse de convergence sur deux cas tests.Une part importante de notre travail a été de proposer une façon de mêler MCTS avec des heuristiques rapides pré-existantes. C’est une idée particulièrement intéressante dans le cas de la gestion d’énergie, car ces problèmes sont pour le moment résolus de manière approchée. Nous avons montré comment utiliser Direct Policy Search (DPS) pour rechercher une politique par défaut efficace, qui est ensuite utilisée à l’intérieur de MCTS. Les résultats expérimentaux sont très encourageants.Nous avons aussi appliqué MCTS à des processus markoviens partiellement observables (POMDP), avec comme exemple le jeu de démineur. Dans ce cas, les algorithmes actuels ne sont pas optimaux, et notre approche l’est, en transformant le POMDP en MDP, par un changement de vecteur d’état.Enfin, nous avons utilisé MCTS dans un cadre de méta-bandit, pour résoudre des problèmes d’investissement. Le choix d’investissement est fait par des algorithmes de bandits à bras multiples, tandis que l’évaluation de chaque bras est faite par MCTS.Une des conclusions importantes de ces travaux est que MCTS en continu a besoin de très peu d’hypothèses (uniquement un modèle génératif du problème), converge vers l’optimum, et peut facilement améliorer des méthodes suboptimales existantes. / In this thesis, we study sequential decision making problems, with a focus on the unit commitment problem. Traditionally solved by dynamic programming methods, this problem is still a challenge, due to its high dimension and to the sacrifices made on the accuracy of the model to apply state of the art methods. We investigate on the applicability of Monte Carlo Tree Search methods for this problem, and other problems that are single player, stochastic and continuous sequential decision making problems. We started by extending the traditional finite state MCTS to continuous domains, with a method called Double Progressive Widening (DPW). This method relies on two hyper parameters, and determines the ratio between width and depth in the nodes of the tree. We developed a heuristic called Blind Value (BV) to improve the exploration of new actions, using the information from past simulations. We also extended the RAVE heuristic to continuous domain. Finally, we proposed two new ways of backing up information through the tree, that improved the convergence speed considerably on two test cases.An important part of our work was to propose a way to mix MCTS with existing powerful heuristics, with the application to energy management in mind. We did so by proposing a framework that allows to learn a good default policy by Direct Policy Search (DPS), and to include it in MCTS. The experimental results are very positive.To extend the reach of MCTS, we showed how it could be used to solve Partially Observable Markovian Decision Processes, with an application to game of Mine Sweeper, for which no consistent method had been proposed before.Finally, we used MCTS in a meta-bandit framework to solve energy investment problems: the investment decision was handled by classical bandit algorithms, while the evaluation of each investment was done by MCTS.The most important take away is that continuous MCTS has almost no assumption (besides the need for a generative model), is consistent, and can easily improve existing suboptimal solvers by using a method similar to what we proposed with DPS.
|
56 |
Apprentissage Intelligent des Robots Mobiles dans la Navigation Autonome / Intelligent Mobile Robot Learning in Autonomous NavigationXia, Chen 24 November 2015 (has links)
Les robots modernes sont appelés à effectuer des opérations ou tâches complexes et la capacité de navigation autonome dans un environnement dynamique est un besoin essentiel pour les robots mobiles. Dans l’objectif de soulager de la fastidieuse tâche de préprogrammer un robot manuellement, cette thèse contribue à la conception de commande intelligente afin de réaliser l’apprentissage des robots mobiles durant la navigation autonome. D’abord, nous considérons l’apprentissage des robots via des démonstrations d’experts. Nous proposons d’utiliser un réseau de neurones pour apprendre hors-ligne une politique de commande à partir de données utiles extraites d’expertises. Ensuite, nous nous intéressons à l’apprentissage sans démonstrations d’experts. Nous utilisons l’apprentissage par renforcement afin que le robot puisse optimiser une stratégie de commande pendant le processus d’interaction avec l’environnement inconnu. Un réseau de neurones est également incorporé et une généralisation rapide permet à l’apprentissage de converger en un certain nombre d’épisodes inférieur à la littérature. Enfin, nous étudions l’apprentissage par fonction de récompenses potentielles compte rendu des démonstrations d’experts optimaux ou non-optimaux. Nous proposons un algorithme basé sur l’apprentissage inverse par renforcement. Une représentation non-linéaire de la politique est désignée et la méthode du max-margin est appliquée permettant d’affiner les récompenses et de générer la politique de commande. Les trois méthodes proposées sont évaluées sur des robots mobiles afin de leurs permettre d’acquérir les compétences de navigation autonome dans des environnements dynamiques et inconnus / Modern robots are designed for assisting or replacing human beings to perform complicated planning and control operations, and the capability of autonomous navigation in a dynamic environment is an essential requirement for mobile robots. In order to alleviate the tedious task of manually programming a robot, this dissertation contributes to the design of intelligent robot control to endow mobile robots with a learning ability in autonomous navigation tasks. First, we consider the robot learning from expert demonstrations. A neural network framework is proposed as the inference mechanism to learn a policy offline from the dataset extracted from experts. Then we are interested in the robot self-learning ability without expert demonstrations. We apply reinforcement learning techniques to acquire and optimize a control strategy during the interaction process between the learning robot and the unknown environment. A neural network is also incorporated to allow a fast generalization, and it helps the learning to converge in a number of episodes that is greatly smaller than the traditional methods. Finally, we study the robot learning of the potential rewards underneath the states from optimal or suboptimal expert demonstrations. We propose an algorithm based on inverse reinforcement learning. A nonlinear policy representation is designed and the max-margin method is applied to refine the rewards and generate an optimal control policy. The three proposed methods have been successfully implemented on the autonomous navigation tasks for mobile robots in unknown and dynamic environments.
|
57 |
Mise en place d'un modèle de fuite multi-états en secteur hydraulique partiellement instrumenté / Mastering losses on drinking water networkClaudio, Karim 19 December 2014 (has links)
L’évolution de l’équipement des réseaux d’eau potable a considérablement amélioré le pilotage de ces derniers. Le telérelevé des compteurs d’eau est sans doute la technologie qui a créé la plus grande avancée ces dernières années dans la gestion de l’eau, tant pour l’opérateur que pour l’usager. Cette technologie a permis de passer d’une information le plus souvent annuelle sur les consommations (suite à la relève manuelle des compteurs d’eau) à une information infra-journalière. Mais le télérelevé, aussi performant soit-il, a un inconvénient : son coût. L’instrumentation complète d’un réseau engendre des investissements que certains opérateurs ne peuvent se permettre. Ainsi la création d’un échantillon de compteurs à équiper permet d’estimer la consommation totale d’un réseau tout en minimisant les coûts d’investissement. Cet échantillon doit être construit de façon intelligente de sorte que l’imprécision liée à l’estimation ne nuise pas à l’évaluation des consommations. Une connaissance précise sur les consommations d’eau permet de quantifier les volumes perdus en réseau. Mais, même dans le cas d’une évaluation exacte des pertes, cela ne peut pas suffire à éliminer toutes les fuites sur le réseau. En effet, si le réseau de distribution d’eau potable est majoritairement enterré, donc invisible, il en va de même pour les fuites. Une fraction des fuites est invisible et même indétectable par les techniques actuelles de recherche de fuites, et donc irréparable. La construction d’un modèle de fuite multi-états permet de décomposer le débit de fuite suivant les différents stades d’apparition d’une fuite : invisible et indétectable, invisible mais détectable par la recherche de fuite et enfin visible en surface. Ce modèle, de type semi-markovien, prend en compte les contraintes opérationnelles, notamment le fait que nous disposons de données de panel. La décomposition du débit de fuite permet de fait une meilleure gestion du réseau en ciblant et adaptant les actions de lutte contre les fuites à mettre en place en fonction de l’état de dégradation du réseau. / The evolution of equipment on drinking water networks has considerably bettered the monitoring of these lasts. Automatic meter reading (AMR) is clearly the technology which has brought the major progress these last years in water management, as for the operator and the end-users. This technology has allowed passing from an annual information on water consumption (thanks to the manual meter reading) toan infra-daily information. But as efficient as AMR can be, it has one main inconvenient : its cost. A complete network instrumentation generates capital expenditures that some operators can’t allowed themselves. The constitution of a sample of meters to equip enables then to estimate the network total consumption while minimizing the investments. This sample has to be built smartly so the inaccuracy of the estimator shouldn’t be harmful to the consumption estimation. A precise knowledge on water consumption allowsquantifying the water lost volumes on the network. But even an exact assessment of losses is still not enough to eliminate all the leaks on the network. Indeed, if the water distribution network is buried, and so invisible, so do the leaks. A fraction of leaks are invisible and even undetectable by the current technologies of leakage control, and so these leaks are un-reparable. The construction of a multi-state model enables us to decompose the leakage flow according to the different stages of appearance of a leak : invisible and undetectable, invisible but detectable with leakage control and finally detectable. This semi-Markovian model takes into account operational constrains, in particular the fact that we dispose of panel data. The leakage flow decomposition allows a better network monitoring but targeting and adapting the action of leakage reduction to set up according to the degradation state of the network.
|
58 |
Contrôle adaptatif des feux de signalisation dans les carrefours : modélisation du système de trafic dynamique et approches de résolution / Adaptative traffic signal control at intersections : dynamic traffic system modeling and algorithmsYin, Biao 11 December 2015 (has links)
La régulation adaptative des feux de signalisation est un problème très important. Beaucoup de chercheurs travaillent continuellement afin de résoudre les problémes liés à l’embouteillage dans les intersections urbaines. Il devient par conséquent très utile d’employer des algorithmes intelligents afin d’améliorer les performances de régulation et la qualité du service. Dans cette thèse, nous essayons d'étudier ce problème d’une part à travers une modèlisation microscopique et dynamique en temps discret, et d’autre part en explorant plusieurs approches de résoltion pour une intersection isolée ainsi que pour un réseau distribué d'intersections.La première partie se concentre sur la modélisation dynamique des problèmes des feux de signalisation ainsi que de la charge du réseau d’intersections. Le mode de la “séquence de phase adaptative” (APS) dans un plan de feux est d'abord considéré. Quant à la modélisation du contrôle des feux aux intersections, elle est formulée grâce à un processus décisionnel de markov (MDP). En particulier, la notion de “l'état du système accordable” est alors proposée pour la coordination du réseau de trafic. En outre, un nouveau modèle de “véhicule-suiveur” est proposé pour l'environnement de trafic. En se basant sur la modélisation proposée, les méthodes de contrôle des feux dans cette thèse comportent des algorithmes optimaux et quasi-optimaux. Deux algorithmes exacts de résolution basées sur la programmation dynamique (DP) sont alors étudiés et les résultats montrent certaines limites de cette solution DP surtout dans quelques cas complexes où l'espace d'états est assez important. En raison de l’importance du temps d’execution de l'algorithme DP et du manque d'information du modèle (notamment l’information exacte relative à l’arrivée des véhicules à l’intersection), nous avons opté pour un algorithme de programmation dynamique approximative (ADP). Enfin, un algorithme quasi-optimal utilisant l'ADP combinée à la méthode d’amélioration RLS-TD (λ) est choisi. Dans les simulations, en particulier avec l'intégration du mode de phase APS, l'algorithme proposé montre de bons résultats notamment en terme de performance et d'efficacité de calcul. / Adaptive traffic signal control is a decision making optimization problem. People address this crucial problem constantly in order to solve the traffic congestion at urban intersections. It is very popular to use intelligent algorithms to improve control performances, such as traffic delay. In the thesis, we try to study this problem comprehensively with a microscopic and dynamic model in discrete-time, and investigate the related algorithms both for isolated intersection and distributed network control. At first, we focus on dynamic modeling for adaptive traffic signal control and network loading problems. The proposed adaptive phase sequence (APS) mode is highlighted as one of the signal phase control mechanisms. As for the modeling of signal control at intersections, problems are fundamentally formulated by Markov decision process (MDP), especially the concept of tunable system state is proposed for the traffic network coordination. Moreover, a new vehicle-following model supports for the network loading environment.Based on the model, signal control methods in the thesis are studied by optimal and near-optimal algorithms in turn. Two exact DP algorithms are investigated and results show some limitations of DP solution when large state space appears in complex cases. Because of the computational burden and unknown model information in dynamic programming (DP), it is suggested to use an approximate dynamic programming (ADP). Finally, the online near-optimal algorithm using ADP with RLS-TD(λ) is confirmed. In simulation experiments, especially with the integration of APS, the proposed algorithm indicates a great advantage in performance measures and computation efficiency.
|
59 |
Les processus additifs markoviens et leurs applications en finance mathématiqueMomeya Ouabo, Romuald Hervé 05 1900 (has links)
Cette thèse porte sur les questions d'évaluation et de couverture des options
dans un modèle exponentiel-Lévy avec changements de régime. Un tel modèle est
construit sur un processus additif markovien un peu comme le modèle de Black-
Scholes est basé sur un mouvement Brownien. Du fait de l'existence de plusieurs
sources d'aléa, nous sommes en présence d'un marché incomplet et ce fait rend
inopérant les développements théoriques initiés par Black et Scholes et Merton
dans le cadre d'un marché complet.
Nous montrons dans cette thèse que l'utilisation de certains résultats de la théorie
des processus additifs markoviens permet d'apporter des solutions aux problèmes
d'évaluation et de couverture des options. Notamment, nous arrivons à caracté-
riser la mesure martingale qui minimise l'entropie relative à la mesure de probabilit
é historique ; aussi nous dérivons explicitement sous certaines conditions,
le portefeuille optimal qui permet à un agent de minimiser localement le risque
quadratique associé. Par ailleurs, dans une perspective plus pratique nous caract
érisons le prix d'une option Européenne comme l'unique solution de viscosité
d'un système d'équations intégro-di érentielles non-linéaires. Il s'agit là d'un premier
pas pour la construction des schémas numériques pour approcher ledit prix. / This thesis focuses on the pricing and hedging problems of financial derivatives in
a Markov-modulated exponential-Lévy model. Such model is built on a Markov
additive process as much as the Black-Scholes model is based on Brownian motion.
Since there exist many sources of randomness, we are dealing with an incomplete
market and this makes inoperative techniques initiated by Black, Scholes and
Merton in the context of a complete market.
We show that, by using some results of the theory of Markov additive processes it
is possible to provide solutions to the previous problems. In particular, we characterize
the martingale measure which minimizes the relative entropy with respect
to the physical probability measure. Also under some conditions, we derive explicitly
the optimal portfolio which allows an agent to minimize the local quadratic
risk associated. Furthermore, in a more practical perspective we characterize the
price of a European type option as the unique viscosity solution of a system of
nonlinear integro-di erential equations. This is a rst step towards the construction
of e ective numerical schemes to approximate options price.
|
60 |
Dynamique et contrôle de systèmes quantiques ouvertsChenel, Aurélie 16 July 2014 (has links) (PDF)
L'étude des effets quantiques, comme les cohérences quantiques, et leur exploitation en contrôle par impulsion laser constituent encore un défi numérique pour les systèmes de grande taille. Pour réduire la dimensionnalité du problème, la dynamique dissipative se focalise sur un sous-espace quantique dénommé 'système', qui inclut les degrés de liberté les plus importants. Le système est couplé à un bain thermique d'oscillateurs harmoniques. L'outil essentiel de la dynamique dissipative est la densité spectrale du bain, qui contient toutes les informations sur le bain et sur l'interaction entre le système et le bain. Plusieurs stratégies complémentaires existent. Nous adoptons une équation maîtresse quantique non-markovienne pour décrire l'évolution de la matrice densité associée au système. Cette approche, développée par C. Meier et D.J. Tannor, est perturbative en fonction du couplage entre le système et le bain, mais pas en fonction de l'interaction avec un champ laser. Le but est de confronter cette méthodologie à des systèmes réalistes calibrés par des calculs de structure électronique ab initio. Une première étude porte sur la modélisation du transfert d'électron ultrarapide à une hétérojonction oligothiophène-fullerène, présente dans des cellules photovoltaïques organiques. La description du problème en fonction d'une coordonnée brownienne permet de contourner la limitation du régime perturbatif. Le transfert de charge est plus rapide mais moins complet lorsque la distance R entre les fragments oligothiophène et fullerène augmente. La méthode de dynamique quantique décrite ci-dessus est ensuite combinée à la Théorie du Contrôle Optimal (OCT), et appliquée au contrôle d'une isomérisation, le réarrangement de Cope, dans le contexte des réactions de Diels-Alder. La prise en compte de la dissipation dès l'étape d'optimisation du champ permet à l'algorithme de contrôle de contrer la décohérence induite par l'environnement et conduit à un meilleur rendement. La comparaison de modèles à une et deux dimensions montre que le contrôle trouve un mécanisme adapté au modèle utilisé. En deux dimensions, il agit activement sur les deux coordonnées du modèle. En une dimension, le décohérence est minimisée par une accélération du passage par les états délocalisés situés au-dessus de la barrière de potentiel.
|
Page generated in 0.0367 seconds