Spelling suggestions: "subject:"markovian"" "subject:"markoviano""
111 |
Multiscale description of dynamical processes in magnetic media : from atomistic models to mesoscopic stochastic processes / Simulation multi-échelle des processus dynamiques dans les milieux magnétiques : depuis une modélisation atomistique vers la simulation de processsus mésoscopiques stochastiquesTranchida, Julien 01 December 2016 (has links)
Les propriétés magnétiques détaillées des solides peuvent être vu comme le résultat de l'interaction de plusieurs sous-systèmes: celui des spins effectifs, portant l'aimantation, celui des électrons et celui du réseau crystallin. Différents processus permettent à ces sous-systèmes d'échanger de l'énergie. Parmis ceux-ci, les phénomènes de relaxation jouent un rôle prépondérants. Cependant, la complexité de ces processus en rend leur modélisation ardue. Afin de prendre en compte ces interactions de façon abordable aux calculs, l'approche de Langevin est depuis longtemps appliquée à la dynamique d'aimantation, qui peut être vue comme la réponse collective des spins. Elle consiste à modéliser les interactions entre les trois sous-systèmes par des interactions effectives entre le sous-système d'intérêt, les spins, et un bain thermique, dont seulement la densité de probabilité constituerait une quantité pertinente. Après avoir présenté cette approche, nous verrons en quoi elle permet de bâtir une dynamique atomique de spin. Une fois son implémentation détaillée, cette méthodologie sera appliquée à un exemple tiré de la littérature et basé sur le superparamagnétisme de nanoaimants de fer. / Detailed magnetic properties of solids can be regarded as the result of the interaction between three subsystems: the effective spins, that will be our focus in this thesis, the electrons and the crystalline lattice. These three subsystems exchange energy, in many ways, in particular, through relaxation processes. The nature of these processes remains extremely hard to understand, and even harder to simulate. A practical approach, for performing such simulations, involves adapting the description of random processes by Langevin to the collective dynamics of the spins, usually called the magnetization dynamics. It consists in describing the, complicated, interactions between the subsystems, by the effective interactions of the subsystem of interest, the spins, and a thermal bath, whose probability density is only of relevance. This approach allows us to interpret the results of atomistic spin dynamics simulations in appropriate macroscopic terms. After presenting the numerical implementation of this methodology, a typical study of a magnetic device based on superparamagnetic iron monolayers is presented, as an example. The results are compared to experimental data and allow us to validate the atomistic spin dynamics simulations.
|
112 |
Modelagem e avaliação da extensão da vida útil de plantas industriais / Modelling and evaluation of industrial plants useful life extensionJosé Alberto Avelino da Silva 30 May 2008 (has links)
O envelhecimento de uma instalação industrial provoca o aumento do número de falhas. A probabilidade de falhar é um indicador do momento em que deve ser feita uma parada para manutenção. É desenvolvido um método estatístico, baseado na teoria não-markoviana, para a determinação da variação da probabilidade de falhar em função do tempo de operação, que resulta num sistema de equações diferenciais parciais de natureza
hiperbólica. São apresentadas as soluções por passo-fracionário e Lax-Wendroff com termo fonte. Devido à natureza suave da solução, os dois métodos chegam ao mesmo resultado com erro menor que 10−3. No caso estudado, conclui-se que o colapso do sistema depende principalmente do estado inicial da cadeia de Markov, sendo que os demais estados apresentam pouca influência na probabilidade de falha geral do sistema. / During the useful life of an industrial plant, the failure occurrence follows an exponential distribution. However, the aging process in an industrial plant generates an increase of the failure number. The failure probability is a rating for the maintenance stopping process. In this paper, an statistical method for the assessment of the failure probability as a function of the operational time, based on the non-Markovian theory, is presented. Two maintenance conditions are addressed: In the first one, the old parts are utilized, after the repair this condition being called as good as old; in the second one the old parts are substituted by brand new ones this condition being called as good as new. A non-Markovian system with variable source term is modeled by using hyperbolic partial differential equations. The system of equations is solved using the Lax-Wendroff and fractional-step numerical schemes. The two methods achieve to approximately the same results, due to the smooth behavior of the solution. The main conclusion is that the system collapse depends essentially on the initial state of the Markov chain.
|
113 |
Modelagem e avaliação da extensão da vida útil de plantas industriais / Modelling and evaluation of industrial plants useful life extensionJosé Alberto Avelino da Silva 30 May 2008 (has links)
O envelhecimento de uma instalação industrial provoca o aumento do número de falhas. A probabilidade de falhar é um indicador do momento em que deve ser feita uma parada para manutenção. É desenvolvido um método estatístico, baseado na teoria não-markoviana, para a determinação da variação da probabilidade de falhar em função do tempo de operação, que resulta num sistema de equações diferenciais parciais de natureza
hiperbólica. São apresentadas as soluções por passo-fracionário e Lax-Wendroff com termo fonte. Devido à natureza suave da solução, os dois métodos chegam ao mesmo resultado com erro menor que 10−3. No caso estudado, conclui-se que o colapso do sistema depende principalmente do estado inicial da cadeia de Markov, sendo que os demais estados apresentam pouca influência na probabilidade de falha geral do sistema. / During the useful life of an industrial plant, the failure occurrence follows an exponential distribution. However, the aging process in an industrial plant generates an increase of the failure number. The failure probability is a rating for the maintenance stopping process. In this paper, an statistical method for the assessment of the failure probability as a function of the operational time, based on the non-Markovian theory, is presented. Two maintenance conditions are addressed: In the first one, the old parts are utilized, after the repair this condition being called as good as old; in the second one the old parts are substituted by brand new ones this condition being called as good as new. A non-Markovian system with variable source term is modeled by using hyperbolic partial differential equations. The system of equations is solved using the Lax-Wendroff and fractional-step numerical schemes. The two methods achieve to approximately the same results, due to the smooth behavior of the solution. The main conclusion is that the system collapse depends essentially on the initial state of the Markov chain.
|
114 |
Uma abordagem fuzzy para a estabilização de uma classe de sistemas não-lineares com saltos Markovianos / A fuzzy stabilization approach for a class of Markovian jump nonlinear systemsNatache do Socorro Dias Arrifano 30 April 2004 (has links)
Neste trabalho é apresentada uma abordagem fuzzy para a estabilização de uma classe de sistemas não-lineares com parâmetros descritos por saltos Markovianos. Uma nova modelagem fuzzy de sistemas é formulada para representar esta classe de sistemas na vizinhança de pontos de operação escolhidos. A estrutura deste sistema fuzzy é composta de dois níveis, um para descrição dos saltos Markovianos e outro para descrição das não-linearidades no estado do sistema. Condições suficientes para a estabilização estocástica do sistema fuzzy considerado são derivadas usando uma função de Lyapunov acoplada. O projeto de controle fuzzy é então formulado a partir de um conjunto de desigualdades matriciais lineares. Em adição, um exemplo de aplicação, envolvendo a representação da operação de um sistema elétrico de potência em esquema de co-geração por um sistema com saltos Markovianos, é construído para validação dos resultados. / This work deals with the fuzzy-model-based control design for a class of Markovian jump nonlinear systems. A new fuzzy system modeling is proposed to approximate the dynamics of this class of systems. The structure of the new fuzzy system is composed of two levels, a crisp level which describes the Markovian jumps and a fuzzy level which describes the system nonlinearities. A sufficient condition on the existence of a stochastically stabilizing controller using a Lyapunov function approach is presented. The fuzzy-model-based control design is formulated in terms of a set of linear matrix inequalities. In addition, simulation results for a single-machine infinite-bus power system in cogeneration scheme, whose operation is modeled as an Markovian jump nonlinear system, are presented to illustrate the applicability of the technique.
|
115 |
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.
|
116 |
Quantum dissipative dynamics with a surrogate HamiltonianKoch, Christiane 18 October 2002 (has links)
Diese Dissertation untersucht Quantensysteme in kondensierter Phase, welche mit ihrer Umgebung wechselwirken und durch ultrakurze Laserpulse angeregt werden. Die Zeitskalen der verschiedenen beteiligten Prozessen lassen sich bei solchen Problemen nicht separieren, weshalb die Standardmethoden zur Behandlung offener Quantensysteme nicht angewandt werden können. Die Methode des Surrogate Hamiltonian stellt ein Beispiel neuer Herangehensweisen an dissipative Quantendynamik dar. Die Weiterentwicklung der Methode und ihre Anwendung auf Phänomene, die zur Zeit experimentell untersucht werden, stehen im Mittelpunkt dieser Arbeit. Im ersten Teil der Arbeit werden die einzelnen dissipativen Prozesse klassifiziert und diskutiert. Insbesondere wird ein Modell der Dephasierung in die Methode des Surrogate Hamiltonian eingeführt. Dies ist wichtig für zukünftige Anwendungen der Methode, z.b. auf kohärente Kontrolle oder Quantencomputing. Diesbezüglich hat der Surrogate Hamiltonian einen großen Vorteil gegenüber anderen zur Verfügung stehenden Methoden dadurch, daß er auf dem Spin-Bad, d.h. auf einer vollständig quantenmechanischen Beschreibung der Umgebung, beruht. Im nächsten Schritt wird der Surrogate Hamiltonian auf ein Standardproblem für Ladungstransfer in kondensierter Phase angewandt, zwei nichtadiabatisch gekoppelte harmonische Oszillatoren, die in ein Bad eingebettet sind. Dieses Modell stellt eine große Vereinfachung von z.B. einem Molekül in Lösung dar, es dient hier jedoch als Testbeispiel für die theoretische Beschreibung eines prototypischen Ladungstransferereignisses. Alle qualitativen Merkmale eines solchen Experimentes können wiedergegeben und Defizite früherer Behandlungen identifiziert werden. Ultraschnelle Experimente beobachten Reaktionsdynamik auf der Zeitskala von Femtosekunden. Dies kann besonders gut durch den Surrogate Hamiltonian als einer Methode, die auf einer zeitabhängigen Beschreibung beruht, erfaßt werden. Die Kombination der numerischen Lösung der zeitabhängigen Schrödingergleichung mit der Wignerfunktion, die die Visualisierung eines Quantenzustands im Phasenraum ermöglicht, gestattet es, dem Ladungstransferzyklus intuitiv Schritt für Schritt zu folgen. Der Nutzen des Surrogate Hamiltonian wird weiterhin durch die Verbindung mit der Methode der Filterdiagonalisierung erhöht. Dies gestattet es, aus mit dem Surrogate Hamiltonian nur für relative kurze Zeite konvergierte Erwartungswerten Ergebnisse in der Frequenzdomäne zu erhalten. Der zweite Teil der Arbeit beschäftigt sich mit der theoretischen Beschreibung der laserinduzierten Desorption kleiner Moleküle von Metalloxidoberflächen. Dieses Problem stellt ein Beispiel dar, in dem alle Aspekte mit derselben methodischen Genauigkeit beschrieben werden, d.h. ab initio Potentialflächen werden mit einem mikroskopischen Modell für die Anregungs- und Relaxationsprozesse verbunden. Das Modell für die Wechselwirkung zwischen angeregtem Adsorbat-Substrat-System und Elektron-Loch-Paaren des Substrats beruht auf einer vereinfachten Darstellung der Elektron-Loch-Paare als ein Bad aus Dipolen und auf einer Dipol-Dipol-Wechselwirkung zwischen System und Bad. Alle Parameter können aus Rechnungen zur elektronischen Struktur abgeschätzt werden. Desorptionswahrscheinlichkeiten und Desorptionsgeschwindigkeiten werden unabhängig voneinander im experimentell gefundenen Bereich erhalten. Damit erlaubt der Surrogate Hamiltonian erstmalig eine vollständige Beschreibung der Photodesorptionsdynamik auf ab initio-Basis. / This thesis investigates condensed phase quantum systems which interact with their environment and which are subject to ultrashort laser pulses. For such systems the timescales of the involved processes cannot be separated, and standard approaches to treat open quantum systems fail. The Surrogate Hamiltonian method represents one example of a number of new approaches to address quantum dissipative dynamics. Its further development and application to phenomena under current experimental investigation are presented. The single dissipative processes are classified and discussed in the first part of this thesis. In particular, a model of dephasing is introduced into the Surrogate Hamiltonian method. This is of importance for future work in fields such as coherent control and quantum computing. In regard to these subjects, it is a great advantage of the Surrogate Hamiltonian over other available methods that it relies on a spin, i.e. a fully quantum mechanical description of the bath. The Surrogate Hamiltonian method is applied to a standard model of charge transfer in condensed phase, two nonadiabatically coupled harmonic oscillators immersed in a bath. This model is still an oversimplification of, for example, a molecule in solution, but it serves as testing ground for the theoretical description of a prototypical ultrafast pump-probe experiment. All qualitative features of such an experiment are reproduced and shortcomings of previous treatments are identified. Ultrafast experiments attempt to monitor reaction dynamics on a femtosecond timescale. This can be captured particularly well by the Surrogate Hamiltonian as a method based on a time-dependent picture. The combination of the numerical solution of the time-dependent Schrödinger equation with the phase space visualization given by the Wigner function allows for a step by step following of the sequence of events in a charge transfer cycle in a very intuitive way. The utility of the Surrogate Hamiltonian is furthermore significantly enhanced by the incorporation of the Filter Diagonalization method. This allows to obtain frequency domain results from the dynamics which can be converged within the Surrogate Hamiltonian approach only for comparatively short times. The second part of this thesis is concerned with the theoretical treatment of laser induced desorption of small molecules from oxide surfaces. This is an example which allows for a description of all aspects of the problem with the same level of rigor, i.e. ab initio potential energy surfaces are combined with a microscopic model for the excitation and relaxation processes. This model of the interaction between the excited adsorbate-substrate complex and substrate electron-hole pairs relies on a simplified description of the electron-hole pairs as a bath of dipoles, and a dipole-dipole interaction between system and bath. All parameters are connected to results from electronic structure calculations. The obtained desorption probabilities and desorption velocities are simultaneously found to be in the right range as compared to the experimental results. The Surrogate Hamiltonian approach therefore allows for a complete description of the photodesorption dynamics on an ab initio basis for the first time.
|
117 |
Speckle Analysis of the Excitonic Emission fromQuantum WellsMannarini, Gianandrea 08 June 2005 (has links)
In der vorliegenden Promotionsarbeit werden optische Eigenschaften von Halbleiterquantengräben untersucht, die mit der Ausbildung von Speckle-Mustern in der exzitonischen Emission zusammenhängen. Die in nichtspekulärer Richtung nach resonanter Anregung von Exzitonen ausgestrahlte Emission enthält Informationen über Unordnung und Streuprozesse in der Probe. Im Kapitel "Spektrale Speckle-Analyse" wird gezeigt, dass Speckles zur Bestimmung des koährenten Anteils verwendet werden können. Außerdem kann die innerhalb des inhomogen verbreiterten Ensembles frequenzaufgelöste Lebensdauer der Exzitonen bestimmt werden. Eine mikroskopische Dichtematrixtheorie wird entwickelt und numerisch gelöst. Es wird eine gute Übereinstimmung mit den gemessenen Daten für unterschiedliche Quantengraben-Dicken und Temperaturen gefunden. Im Kapitel "Schrägliegende Speckles" werden Quantengräben mit mechanischer Verzerrung betrachtet. Die Verzerrung führt zu einer ort-abhängigen Änderung der Emissionsenergie in der Ebene des Quantengrabens und das richtungs- und zeitaufgelöste Specklemuster erfährt eine Drehung. Die theoretische Beschreibung des Rayleigh-Spektrums erlaubt es, diese Drehung mit dem lokalen Wert des Gradienten der Exzitonenergie in Beziehung zu setzen. Numerische Simulationen zeigen allerdings, dass dieser Effekt nicht durch eine Bewegung der Exzitonen entlang des Verzerrungs-Gradienten verursacht wird. Im Kapitel "Nicht-Markovsche Exziton-Phonon Dynamik" die Dichtematrixtheorie, wird jenseits der Markovschen Näherung für die Streuung von Exzitonen an akustischen Phononen numerisch gelöst. Das Absorptionsspektrum besteht aus Lorentz-formige Peaks und breiteren Seitenbändern, die aus der nicht-Markovschen Kopplung stammen. Diese Eigenschaften sind vor allem für die stark lokalisierten Zustände auf der Niederenergie-Seite des Spektrums wichtig, und erlauben eine bessere Deutung von Nahfeld-Experimenten. / In this work, optical properties of semiconductor quantum wells (QW) are investigated, which are relevant for the irregular light pattern (speckle pattern) emitted in nonspecular directions by QW after resonant excitation of the exciton states. This emission contains information on disorder and scattering processes in the sample. In Chapter "Spectral Speckle Analysis", it is shown that Speckles can be used for extraction of the coherent part of the emission, the Resonant Rayleigh Scattering. Furthermore, the frequency resolved lifetime of excitons within an inhomogeneously broadened ensemble can be established. A microscopic density matrix theory for excitons interacting with acoustic phonons is developed and numerically solved. Good agreement with the experimental results for different QW sizes and temperatures is found. In Chapter "Sloped Speckles" QW with mechanical strain are considered. The strain leads to a spatially dependent modification of the emission energy and to a tilting of the direction- and time-resolved speckle pattern. The theoretical description of the RRS relates this tilting to the local value of the spatial gradient of the exciton energy. However, numerical simulations make clear that this effect is not due to exciton motion along the strain gradient. In Chapter "Non-Markovian exciton-phonon dynamics" the density matrix theory is numerically solved beyond the Markov approximation for the interaction between excitons and acoustical phonons. The resulting absorption spectrum consists of Lorentzian peaks on top of broader sidebands originating from the non-Markovian coupling. These features are mostly important for the strongly localized states in the low energy side of the spectrum, suggesting a better interpretation of near-field experiments.
|
118 |
Filtragem robusta recursiva para sistemas lineares a tempo discreto com parâmetros sujeitos a saltos Markovianos / Recursive robust filtering for discrete-time Markovian jump linear systemsJesus, Gildson Queiroz de 26 August 2011 (has links)
Este trabalho trata de filtragem robusta para sistemas lineares sujeitos a saltos Markovianos discretos no tempo. Serão desenvolvidas estimativas preditoras e filtradas baseadas em algoritmos recursivos que são úteis para aplicações em tempo real. Serão desenvolvidas duas classes de filtros robustos, uma baseada em uma estratégia do tipo H \'INFINITO\' e a outra baseada no método dos mínimos quadrados regularizados robustos. Além disso, serão desenvolvidos filtros na forma de informação e seus respectivos algoritmos array para estimar esse tipo de sistema. Neste trabalho assume-se que os parâmetros de saltos do sistema Markoviano não são acessíveis. / This work deals with the problem of robust state estimation for discrete-time uncertain linear systems subject to Markovian jumps. Predicted and filtered estimates are developed based on recursive algorithms which are useful in on-line applications. We develop two classes of filters, the first one is based on a H \'INFINITO\' approach and the second one is based on a robust regularized leastsquare method. Moreover, we develop information filter and their respective array algorithms to estimate this kind of system. We assume that the jump parameters of the Markovian system are not acessible.
|
119 |
Extração de preferências por meio de avaliações de comportamentos observados. / Preference elicitation using evaluation over observed behaviours.Silva, Valdinei Freire da 07 April 2009 (has links)
Recentemente, várias tarefas tem sido delegadas a sistemas computacionais, principalmente quando sistemas computacionais são mais confiáveis ou quando as tarefas não são adequadas para seres humanos. O uso de extração de preferências ajuda a realizar a delegação, permitindo que mesmo pessoas leigas possam programar facilmente um sistema computacional com suas preferências. As preferências de uma pessoa são obtidas por meio de respostas para questões específicas, que são formuladas pelo próprio sistema computacional. A pessoa age como um usuário do sistema computacional, enquanto este é visto como um agente que age no lugar da pessoa. A estrutura e contexto das questões são apontadas como fonte de variações das respostas do usuário, e tais variações podem impossibilitar a factibilidade da extração de preferências. Uma forma de evitar tais variações é questionar um usuário sobre a sua preferência entre dois comportamentos observados por ele. A questão de avaliar relativamente comportamentos observados é mais simples e transparente ao usuário, diminuindo as possíveis variações, mas pode não ser fácil para o agente interpretar tais avaliações. Se existem divergências entre as percepções do agente e do usuário, o agente pode ficar impossibilitado de aprender as preferências do usuário. As avaliações são geradas com base nas percepções do usuário, mas tudo que um agente pode fazer é relacionar tais avaliações às suas próprias percepções. Um outro problema é que questões, que são expostas ao usuário por meio de comportamentos demonstrados, são agora restritas pela dinâmica do ambiente e um comportamento não pode ser escolhido arbitrariamente. O comportamento deve ser factível e uma política de ação deve ser executada no ambiente para que um comportamento seja demonstrado. Enquanto o primeiro problema influencia a inferência de como o usuário avalia comportamentos, o segundo problema influencia quão rápido e acurado o processo de aprendizado pode ser feito. Esta tese propõe o problema de Extração de Preferências com base em Comportamentos Observados utilizando o arcabouço de Processos Markovianos de Decisão, desenvolvendo propriedades teóricas em tal arcabouço que viabilizam computacionalmente tal problema. O problema de diferentes percepções é analisado e soluções restritas são desenvolvidas. O problema de demonstração de comportamentos é analisado utilizando formulação de questões com base em políticas estacionárias e replanejamento de políticas, sendo implementados algoritmos com ambas soluções para resolver a extração de preferências em um cenário sob condições restritas. / Recently, computer systems have been delegated to accomplish a variety of tasks, when the computer system can be more reliable or when the task is not suitable or not recommended for a human being. The use of preference elicitation in computational systems helps to improve such delegation, enabling lay people to program easily a computer system with their own preference. The preference of a person is elicited through his answers to specific questions, that the computer system formulates by itself. The person acts as an user of the computer system, whereas the computer system can be seen as an agent that acts in place of the person. The structure and context of the questions have been pointed as sources of variance regarding the users answers, and such variance can jeopardize the feasibility of preference elicitation. An attempt to avoid such variance is asking an user to choose between two behaviours that were observed by himself. Evaluating relatively observed behaviours turn questions more transparent and simpler for the user, decreasing the variance effect, but it might not be easier interpreting such evaluations. If divergences between agents and users perceptions occur, the agent may not be able to learn the users preference. Evaluations are generated regarding users perception, but all an agent can do is to relate such evaluation to his own perception. Another issue is that questions, which are exposed to the user through behaviours, are now constrained by the environment dynamics and a behaviour cannot be chosen arbitrarily, but the behaviour must be feasible and a policy must be executed in order to achieve a behaviour. Whereas the first issue influences the inference regarding users evaluation, the second problem influences how fast and accurate the learning process can be made. This thesis proposes the problem of Preference Elicitation under Evaluations over Observed Behaviours using the Markov Decision Process framework and theoretic properties in such framework are developed in order to turn such problem computationally feasible. The problem o different perceptions is analysed and constraint solutions are developed. The problem of demonstrating a behaviour is considered under the formulation of question based on stationary policies and non-stationary policies. Both type of questions was implemented and tested to solve the preference elicitation in a scenario with constraint conditions.
|
120 |
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.
|
Page generated in 0.0582 seconds