Nesta tese consideramos uma nova classe de sistemas markovianos de partículas com infinitas componentes interagentes. O sistema representa a evolução temporal dos potenciais de membrana de um conjunto infinito de neurônios interagentes. Provamos a existência e unicidade do processo construindo um pseudo-algoritmo de simulação perfeita e mostrando que este algoritmo roda em um número finito de passos quase certamente. Estudamos também o comportamento do sistema quando consideramos apenas um conjunto finito de neurônios. Neste caso, construímos um procedimento de simulação perfeita para o acoplamento entre o processo limitado a um conjunto finito de neurônios e o processo que considera todos os neurônios do sistema. Como consequência encontramos um limitante superior para a probabilidade de discrepância entre os processos. / We consider a new class of interacting particle systems with a countable number of interacting components. The system represents the time evolution of the membrane potentials of an infinite set of interacting neurons. We prove the existence and uniqueness of the process, by the construction of a perfect simulation procedure. We show that this algorithm is successful, that is, we show that the number of steps of the algorithm is finite almost surely. We also study the behaviour of the system when we consider only a finite number of neurons. In this case, we construct a perfect simulation procedure for the coupling of the process with a finite number of neurons and the process with a infinite number of neurons. As a consequence we obtain an upper bound for the error we make when sampling from a finite set of neurons instead of the infinite set of neurons.

Made available in DSpace on 2014-06-12T17:41:40Z (GMT). No. of bitstreams: 2 arquivo7328_1.pdf: 3505785 bytes, checksum: 08ba0b4fd9e921becd50bfdf276c052f (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta dissertação trata de sistemas reparáveis que sofrem reparo imperfeito, utilizando uma classe de modelos de processos estocásticos conhecida como Processo de Renovação Generalizado (PRG), a qual permite inserir uma maior flexibilidade quanto ao tratamento de diversos níveis de reparo. Para tanto, é proposto um modelo utilizando processos Markovianos não homogêneos para analisar o comportamento dinâmico de sistemas complexos, utilizando o PRG para modelar as probabilidades de transição para estados falhos. Os parâmetros destas distribuições são estimados a partir de um outro modelo proposto de inferência Bayesiana para solução das equações do PRG, considerando a situação de escassez de dados de falha, com múltiplos modos de falha, tempos incertos de ocorrência de falha e censura na amostra. Os modelos propostos permitiram obter diversos indicadores de desempenho de confiabilidade, como disponibilidade, níveis de incerteza acerca dos parâmetros do PRG, além permitir quantificar a eficácia da manutenção em seus reparos, por exemplo. Como exemplo de aplicação dos modelos propostos, foram coletados dados reais de operação de uma válvula do tipo PCV, situada em diferentes estações de redução de pressão de gás natural, sujeita à manutenção corretiva e preventiva

Este trabalho foi motivado pela necessidade de considerar comportamento estocástico durante o planejamento da produção de sistemas de manufatura, ou seja, o que produzir e em que ordem. Estes sistemas possuem um comportamento estocástico geralmente não considerado no planejamento da produção. O principal objetivo deste trabalho foi obter um método que modelasse sistemas de manufatura e representasse seu comportamento estocástico durante o planejamento de produção destes sistemas. Como os métodos que eram ideais para planejamento não forneciam a modelagem adequada dos sistemas, e os com modelagem adequada não forneciam a capacidade de planejamento necessária, decidiu-se combinar dois métodos para atingir o objetivo desejado. Decidiu-se modelar os sistemas em rede de Petri e convertê-los em processos de decisão markovianos, e então realizar o planejamento com o ultimo. Para que fosse possível modelar as probabilidades envolvidas nos processos, foi proposto um tipo especial de rede de Petri, nomeada rede de Petri fatorada. Utilizando este tipo de rede de Petri, foi desenvolvido o método de conversão em processos de decisão markovianos. A conversão ocorreu com sucesso, conforme testes que mostraram que planos podem ser produzidos utilizando-se algoritmos de ponta para processos de decisão markovianos. / The present work was motivated by the need to consider stochastic behavior when planning the production mix in a manufacturing system. These systems are exposed to stochastic behavior that is usually not considered during production planning. The main goal of this work was to obtain a method to model manufacturing systems and to represent their stochastic behavior when planning the production for these systems. Because the methods that were suitable for planning were not adequate for modeling the systems and vice-versa, two methods were combined to achieve the main goal. It was decided to model the systems in Petri nets and to convert them into Markov decision processes, to do the planning with the latter. In order to represent probabilities in the process, a special type of Petri nets, named Factored Petri nets, were proposed. Using this kind of Petri nets, a conversion method into Markov decision processes was developed. The conversion is successful as tests showed that plans can be produced within seconds using state-of-art algorithms for Markov decision processes.

Este trabalho foi motivado pela necessidade de considerar comportamento estocástico durante o planejamento da produção de sistemas de manufatura, ou seja, o que produzir e em que ordem. Estes sistemas possuem um comportamento estocástico geralmente não considerado no planejamento da produção. O principal objetivo deste trabalho foi obter um método que modelasse sistemas de manufatura e representasse seu comportamento estocástico durante o planejamento de produção destes sistemas. Como os métodos que eram ideais para planejamento não forneciam a modelagem adequada dos sistemas, e os com modelagem adequada não forneciam a capacidade de planejamento necessária, decidiu-se combinar dois métodos para atingir o objetivo desejado. Decidiu-se modelar os sistemas em rede de Petri e convertê-los em processos de decisão markovianos, e então realizar o planejamento com o ultimo. Para que fosse possível modelar as probabilidades envolvidas nos processos, foi proposto um tipo especial de rede de Petri, nomeada rede de Petri fatorada. Utilizando este tipo de rede de Petri, foi desenvolvido o método de conversão em processos de decisão markovianos. A conversão ocorreu com sucesso, conforme testes que mostraram que planos podem ser produzidos utilizando-se algoritmos de ponta para processos de decisão markovianos. / The present work was motivated by the need to consider stochastic behavior when planning the production mix in a manufacturing system. These systems are exposed to stochastic behavior that is usually not considered during production planning. The main goal of this work was to obtain a method to model manufacturing systems and to represent their stochastic behavior when planning the production for these systems. Because the methods that were suitable for planning were not adequate for modeling the systems and vice-versa, two methods were combined to achieve the main goal. It was decided to model the systems in Petri nets and to convert them into Markov decision processes, to do the planning with the latter. In order to represent probabilities in the process, a special type of Petri nets, named Factored Petri nets, were proposed. Using this kind of Petri nets, a conversion method into Markov decision processes was developed. The conversion is successful as tests showed that plans can be produced within seconds using state-of-art algorithms for Markov decision processes.

Em problemas de tomada de decisão sequencial modelados como Processos de Decisão Markovianos (MDP) pode não ser possível obter uma medida exata para as probabilidades de transição de estados. Visando resolver esta situação os Processos de Decisão Markovianos com Probabilidades Imprecisas (Markov Decision Processes with Imprecise Transition Probabilities, MDP-IPs) foram introduzidos. Porém, enquanto estes MDP-IPs se mostram como um arcabouço robusto para aplicações de planejamento no mundo real, suas soluções consomem muito tempo na prática. Em trabalhos anteriores, buscando melhorar estas soluções foram propostos algoritmos de programação dinâmica síncrona eficientes para resolver MDP-IPs com uma representação fatorada para as funções de transição probabilística e recompensa, chamados de MDP-IP fatorados. Entretanto quando o estado inicial de um problema do Caminho mais Curto Estocástico (Stochastic Shortest Path MDP, SSP MDP) é dado, estas soluções não utilizam esta informação. Neste trabalho será introduzido o problema do Caminho mais Curto Estocástico com Probabilidades Imprecisas (Stochastic Shortest Path MDP-IP, SSP MDP-IP) tanto em sua forma enumerativa, quanto na fatorada. Um algoritmo de programação dinâmica assíncrona para SSP MDP-IP enumerativos com probabilidades dadas por intervalos foi proposto por Buffet e Aberdeen (2005). Entretanto, em geral um problema é dado de forma fatorada, i.e., em termos de variáveis de estado e nesse caso, mesmo se for assumida a imprecisão dada por intervalos sobre as variáveis, ele não poderá ser mais aplicado, pois as probabilidades de transição conjuntas serão multilineares. Assim, será mostrado que os SSP MDP-IPs fatorados são mais expressivos que os enumerativos e que a mudança do SSP MDP-IP enumerativo para o caso geral de um SSP MDP-IPs fatorado leva a uma mudança de resolução da função objetivo do Bellman backup de uma função linear para uma não-linear. Também serão propostos algoritmos enumerativos, chamados de RTDP-IP (Real-time Dynamic Programming with Imprecise Transition Probabilities), LRTDP-IP (Labeled Real-time Dynamic Programming with Imprecise Transition Probabilities), SSiPP-IP (Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) e LSSiPP-IP (Labeled Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) e fatorados chamados factRTDP-IP (factored RTDP-IP) e factLRTDP-IP (factored LRTDP-IP). Eles serão avaliados em relação aos algoritmos de programação dinâmica síncrona em termos de tempo de convergência da solução e de escalabilidade. / In sequential decision making problems modelled as Markov Decision Processes (MDP) we may not have the state transition probabilities. To solve this issue, the framework based in Markov Decision Processes with Imprecise Transition Probabilities (MDP-IPs) is introduced. Therefore, while MDP-IPs is a robust framework to use in real world planning problems, its solutions are time-consuming in practice. In previous works, efficient algorithms based in synchronous dynamic programming to solve MDP-IPs with factored representations of the probabilistic transition function and reward function, called factored MDP-IPs. However, given a initial state of a system, modeled as a Stochastic Shortest Path MDP (SSP MDP), solutions does not use this information. In this work we introduce the Stochastic Shortest Path MDP-IPs (SSP MDP-IPs) in enumerative form and in factored form. An efficient asynchronous dynamic programming solution for SSP MDP-IPs with enumerated states has been proposed by Buffet e Aberdeen (2005) before which is restricted to interval-based imprecision. Nevertheless, in general the problem is given in a factored form, i.e., in terms of state variables and in this case even if we assume interval-based imprecision over the variables, the previous solution is no longer applicable since we have multilinear parameterized joint transition probabilities. In this work we show that the innocuous change from the enumerated SSP MDP-IP cases to the general case of factored SSP MDP-IPs leads to a switch from a linear to nonlinear objectives in the Bellman backup. Also we propose assynchronous dynamic programming enumerative algorithms, called RTDP-IP (Real-time Dynamic Programming with Imprecise Transition Probabilities), LRTDP-IP (Labeled Real-time Dynamic Programming with Imprecise Transition Probabilities), SSiPP-IP (Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) and LSSiPP-IP (Labeled Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities), and factored algorithms called factRTDP-IP (factored RTDP-IP) and factLRTDP-IP (factored LRTDP-IP). There algorithms will be evaluated with the synchronous dynamic programming algorithms previously proposed in terms of convergence time and scalability.

Neste trabalho foi estudado um problema de controle de sistemas lineares com saltos Markovianos sem observação da variável de salto, que pode ser escrito como um problema de otimização de considerável complexidade. As contribuições para a área estão divididas em três aspectos. Um dos avanços foi a elaboração de um contraexemplo para a conjectura de que há somente um mínimo local isolado para o problema. Além disso, foi estudado o problema de otimização intermediário, que consiste em fixar todas as variáveis do problema exceto duas matrizes de ganhos, e os resultados indicam que, com uma pequena alteração na formulação, este é um problema biquadrático. Por fim, novos algoritmos foram elaborados a partir de um método disponível na literatura, chamado de método Variacional, adaptando-o para atualizar os ganhos aos pares, levando a problemas intermediários biquadráticos. Três métodos foram implementados para a resolução destes problemas: dois métodos clássicos de descida, Newton e Gradiente, e uma adaptação do próprio método Variacional. Para a análise dos resultados foram utilizados exemplos gerados aleatoriamente a partir do Gerador de SLSM, que pode ser encontrado na literatura, e o método Variacional como referência para comparação com os métodos propostos / This work addresses a control problem arising in linear systems with Markov jumps without observation of the jump variable and advances in three different aspects. First, it is presented a counterexample to the conjecture that states about the uniqueness of local minimum. Second, the intermediary optimization problem, which sets all the variables of the problem except two arrays of gains, was studied and the results suggested that a slight modification in the formulation makes the intermediary problem a biquadratic one. Finally, new algorithms were developed based on a method available in the literature, which is frequently referred to as the Variational method, adapting it to update the gains in pairs, leading to biquadratic intermediary problems. Three methods were implemented to solve these intermediary problems: two classical descent methods, Newton and Gradient, and an adaptation of the Variational method. To evaluate the performance of the proposed methods, randomly generated examples were used and the Variational method was set as reference for comparing the results

Em geral, quando modelamos problemas de planejamento probabilístico do mundo real, usando o arcabouço de Processos de Decisão Markovianos (MDPs), é difícil obter uma estimativa exata das probabilidades de transição. A incerteza surge naturalmente na especificação de um domínio, por exemplo, durante a aquisição das probabilidades de transição a partir de um especialista ou de dados observados através de técnicas de amostragem, ou ainda de distribuições de transição não estacionárias decorrentes do conhecimento insuficiente do domínio. Com o objetivo de se determinar uma política robusta, dada a incerteza nas transições de estado, Processos de Decisão Markovianos com Probabilidades Imprecisas (MDP-IPs) têm sido usados para modelar esses cenários. Infelizmente, apesar de existirem diversos algoritmos de solução para MDP-IPs, muitas vezes eles exigem chamadas externas de rotinas de otimização que podem ser extremamente custosas. Para resolver esta deficiência, nesta tese, introduzimos o MDP-IP fatorado e propomos métodos eficientes de programação matemática e programação dinâmica que permitem explorar a estrutura de um domínio de aplicação. O método baseado em programação matemática propõe soluções aproximadas eficientes para MDP-IPs fatorados, estendendo abordagens anteriores de programação linear para MDPs fatorados. Essa proposta, baseada numa formulação multilinear para aproximações robustas da função valor de estados, explora a representação fatorada de um MDP-IP, reduzindo em ordens de magnitude o tempo consumido em relação às abordagens não-fatoradas previamente propostas. O segundo método proposto, baseado em programação dinâmica, resolve o gargalo computacional existente nas soluções de programação dinâmica para MDP-IPs propostas na literatura: a necessidade de resolver múltiplos problemas de otimização não-linear. Assim, mostramos como representar a função valor de maneira compacta usando uma nova estrutura de dados chamada de Diagramas de Decisão Algébrica Parametrizados, e como aplicar técnicas de aproximação para reduzir drasticamente a sobrecarga computacional das chamadas a um otimizador não-linear, produzindo soluções ótimas aproximadas com erro limitado. Nossos resultados mostram uma melhoria de tempo e até duas ordens de magnitude em comparação às abordagens tradicionais enumerativas baseadas em programação dinâmica e uma melhoria de tempo de até uma ordem de magnitude sobre a extensão de técnicas de iteração de valor aproximadas para MDPs fatorados. Além disso, produzimos o menor erro de todos os algoritmos de aproximação avaliados. / When modeling real-world decision-theoretic planning problems with the framework of Markov Decision Processes(MDPs), it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, uncertainty arises in the specification of transitions due to elicitation of MDP transition models from an expert or data, or non-stationary transition distributions arising from insuficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, Markov Decision Processes with Imprecise Transition Probabilities (MDP-IPs) have been introduced. Unfortunately, while various solutions exist for MDP-IPs, they often require external calls to optimization routines and thus can be extremely time-consuming in practice. To address this deficiency, we introduce the factored MDP-IP and propose eficient mathematical programming and dynamic programming methods to exploit its structure. First, we derive eficient approximate solutions for Factored MDP-IPs based on mathematical programming resulting in a multilinear formulation for robust maximin linear-value approximations in Factored MDP-IPs. By exploiting factored structure in MDP-IPs we are able to demonstrate orders of magnitude reduction in solution time over standard exact non-factored approaches. Second, noting that the key computational bottleneck in the dynamic programming solution of factored MDP-IPs is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional at dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-IPs while producing the lowest error among all approximation algorithm evaluated.

Neste trabalho foi estudado um problema de controle de sistemas lineares com saltos Markovianos sem observação da variável de salto, que pode ser escrito como um problema de otimização de considerável complexidade. As contribuições para a área estão divididas em três aspectos. Um dos avanços foi a elaboração de um contraexemplo para a conjectura de que há somente um mínimo local isolado para o problema. Além disso, foi estudado o problema de otimização intermediário, que consiste em fixar todas as variáveis do problema exceto duas matrizes de ganhos, e os resultados indicam que, com uma pequena alteração na formulação, este é um problema biquadrático. Por fim, novos algoritmos foram elaborados a partir de um método disponível na literatura, chamado de método Variacional, adaptando-o para atualizar os ganhos aos pares, levando a problemas intermediários biquadráticos. Três métodos foram implementados para a resolução destes problemas: dois métodos clássicos de descida, Newton e Gradiente, e uma adaptação do próprio método Variacional. Para a análise dos resultados foram utilizados exemplos gerados aleatoriamente a partir do Gerador de SLSM, que pode ser encontrado na literatura, e o método Variacional como referência para comparação com os métodos propostos / This work addresses a control problem arising in linear systems with Markov jumps without observation of the jump variable and advances in three different aspects. First, it is presented a counterexample to the conjecture that states about the uniqueness of local minimum. Second, the intermediary optimization problem, which sets all the variables of the problem except two arrays of gains, was studied and the results suggested that a slight modification in the formulation makes the intermediary problem a biquadratic one. Finally, new algorithms were developed based on a method available in the literature, which is frequently referred to as the Variational method, adapting it to update the gains in pairs, leading to biquadratic intermediary problems. Three methods were implemented to solve these intermediary problems: two classical descent methods, Newton and Gradient, and an adaptation of the Variational method. To evaluate the performance of the proposed methods, randomly generated examples were used and the Variational method was set as reference for comparing the results

Made available in DSpace on 2015-03-04T18:50:48Z (GMT). No. of bitstreams: 1 Apresentacao.pdf: 199708 bytes, checksum: ce3c2b5e9db17dddd7a2684d9e5cac8b (MD5) Previous issue date: 2006-07-14 / O processo de Fleming-Viot é um processo de Markov cujo espaço de estado é um conjunto de medidas de propabilidade. As funções-amostras do processo representam as prováveis possibilidades de transformação das freqüencias de tipos genéticos presentes numa população ao longo do tempo. Obtido como solução de um problema de martingala bem posto para um operador linear construído de forma a modelar diversas características importantes no estudo da genética populacional, como mutação, seleção, deriva genética, entre outras, o processo de Fleming-Viot permite, por meio de uma abordagem matemática unificadora, tratar problemas de complexidade variada. No presente trabalho, estudamos s processs de Fleming-Viot com saltos, introduzidos por Hiraba. Interpretamos biologicamente esse saltos como mudanças abruptas que podem ocorrer, num curto espaço de tempo, durante a evolução de uma população de indivíduos, causadas por epidemias, desastres naturais ou outras catástrofes, e que levam a descontinuidades nas frequências dos tipos gênicos. Apresentamos uma forma de incluir um fator de seleção no processo com saltos, através da aplicação de uma transformação de medida do tipo Girsanov. Em seguida, fazemos uma análise do comportamento assintótico do processo utilizando técnicas de dualidade e acoplamento.

Submitted by Maria Cristina (library@lncc.br) on 2018-06-27T12:31:36Z No. of bitstreams: 1 Dissertacao_final_Fortia.pdf: 758629 bytes, checksum: 6b31d1df1ed8f464b298cce7e1ee4180 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2018-06-27T12:31:54Z (GMT) No. of bitstreams: 1 Dissertacao_final_Fortia.pdf: 758629 bytes, checksum: 6b31d1df1ed8f464b298cce7e1ee4180 (MD5) / Made available in DSpace on 2018-06-27T12:32:06Z (GMT). No. of bitstreams: 1 Dissertacao_final_Fortia.pdf: 758629 bytes, checksum: 6b31d1df1ed8f464b298cce7e1ee4180 (MD5) Previous issue date: 2017-02-24 / Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ) / Stochastic differential equations with Markovian jump parameters constitute one of the most important class of hybrid dynamical systems, which has been extensively used for the modeling of dynamical systems which are subject to abrupt changes in their structure. The abrupt changes can be due, for instance, to abrupt environmental disturbances, component failure, volatility in economic systems, changes in subsystems interconnections, abrupt changes in the operation of a nonlinear plant, etc. This can be found, for instance, in aircraft control systems, robot systems, large flexible structure for space station, etc. We shall be particularly interested in the linear class which is dubbed in the literature as the class of Markov jump linear systems (MJLS). The jump mechanism is modeled by a Markov process, which is also known in the literature as the operation mode. The dissertation address the filtering problem of the operation mode for the class of MJLS. Previous result in the literature on this problem has been obtained by Wonham, which has shown the existence of an optimal nonlinear filter for this problem. The main hindrance with Wonham’s result, in the context of the control problem with partial observation of operation mode, is that it introduces a great deal of nonlinearity in the Hamilton-Jacobi- Belman equation, which makes it difficult to get an explicit closed solution for the control problem. Motivated by this, the main contribution of this dissertation is to devise an optimal linear filter for the mode operation, which we believe could be more favorable in the solution of the control problem with partial observations. In addition, relying on Murayama’s stochastic numerical method and the results of Yuan and Mao, we carry out simulation of Wonham’s filter, and the one devised in the dissertation, in order to compare their performances. / As equações diferenciais estocáticas com salto Markoviano constituem uma das clases de sistemas dinâmicos híbridos mais importantes, e tem sido muito usados para modelar sistemas sujeitos a mudanças abruptas na sua estructura. Essas mudanças podem ser devido a, por exemplo, perturbações ambientais, falhas em componentes, volatilidade em sistemas econômicos, mudanças em interconexões de subsistemas, mudanças abruptas em operações de plantas não lineares, etc. Estas falhas podem ser encontradas em sistemas de controle para aeronaves, sistemas robóticos, estructuras grandes e flexíveis em estações espaciais, etc. Nós estamos especialmente interessados na clase de sistemas lineares que é referenciada na literatura como sistemas lineares com salto Markoviano (SLSM). O mecanismo de salto é modelado por um processo de Markov, que é conhecido na literatura como modo de operação do sistema. Essa dissertação visa o problema de filtragem para o modo de operação do sistema linear com salto. Na literatura pode-se encontrar resultados já obtidos para esse problema como é o caso do filtro ótimo não linear deduzido por Wonham. Mas no contexto de controle ótimo com observações parciais do modo de operação, o filtro de Wonham introduz não linearidades na equação de Hamilton-Jacobi-Belman, fazendo com que seja muito complexo obter uma solução fechada para o problema de controle. A principal motivação desta dissertação é deduzir o filtro ótimo linear para o modo de operação, já que esta pode ser uma solução mais favorável para o problema de controle ótimo. Finalmente, usando o método numérico para equações diferenciais estocásticas de Euler-Murayama e o resultado de Yuan e Mao, realizamos a simulação do filtro de Wonham tal como o filtro deduzido neste trabalho, com o objetivo de comparar as respectivas performances.