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.

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.

A identificação de regiões cromossômicas, ou blocos de dependência dentro do genoma humano, que são transmitidas em conjunto para seus descendentes (haplótipos) tem sido um desafio e alvo de várias iniciativas de pesquisa, muitas delas utilizando dados de plataformas de marcadores moleculares do tipo SNP (Single Nucleotide Polymorphisms - SNPs), com alta densidade dentro do DNA humano. Este trabalho faz uso de uma modelagem estocástica de campos Markovianos de alcance variável, em uma amostra estratificada de diferentes populações, para encontrar blocos de SNPs, independentes entre si, estruturando assim o genoma em regiões ilhadas de dependência. Foram utilizados dados públicos de SNPs de diferentes populações mundiais (projeto HapMap), além de uma amostra da população brasileira. As regiões de dependência configuram janelas de influência as quais foram usadas para caracterizar as diferentes populações de acordo com sua ancestralidade e os resultados obtidos mostraram que as janelas da população brasileira têm, em média, tamanho maior, evidenciando a sua história recente de miscigenação. É também proposta uma otimização da função de verossimilhança do problema para obter as janelas de consenso maximais de todas as populações. Dada uma determinada janela de consenso, uma medida de distância apropriada para variáveis categóricas, é adotada para medir sua homogeneidade/heterogeneidade. Janelas homogêneas foram identificadas na região HLA (Human Leukocyte Antigen) do genoma, a qual está associada à resposta imunológica. O tamanho médio dessas janelas foi maior do que a média encontrada no restante do cromossomo, confirmando a alta dependência existente nesta região, considerada como bastante conservada na evolução humana. Finalmente, considerando a distribuição dos SNPs entre as populações nas janelas mais heterogêneas, a Análise de Correspondência foi aplicada na construção de um classificador capaz de determinar o percentual relativo de ancestralidade de um indivíduo, o qual, submetido à validação, obteve uma eficiência de 90% de acerto da população originária. / The identification of chromosome regions, or dependency blocks in the human genome, that are transmitted together to offspring (haploids) has been a challenge and object of several research initiatives, many of them using platforms of molecular markers such as SNP (Single Nucleotide Polymorphisms), with high density inside the human DNA. This work makes use of a stochastic modeling of Markov random fields, in a stratified sample of different populations, to find SNPs blocks, independent of each other, thus structuring the genome in stranded regions of dependency. Public data from different worldwide populations were used (HapMap project), beyond a Brazilian population. The dependence regions constitute windows of influence which were used to characterize the different populations according of their ancestry and the results showed that the Brazilian populations windows have, on average, a bigger size, showing their recent history of admixture. It is also proposed an optimization of likelihood function of the problem for the maximal windows of consensus from all populations. Given a particular window of consensus, a distance measure appropriated to categorical variables, it is adopted to evaluate its homogeneity/heterogeneity. Homogeneous windows were identified within region of genome called HLA (Human Leukocyte Antigen), which is associated with the immune response. The average size of these windows was bigger than the average found in the rest of the chromosome, confirming the high dependence verified in this region, considered highly conserved in the human evolution. Finally, considering the distribution of the SNPs among the populations in the most heterogeneous windows, the Correspondence Analysis was applied to build a classifier able to determine, for a given individual, the ancestry proportion from each population considered, which, submitted to a validation, obtained a 90% accuracy of the original population.

Neste trabalho estudamos um controlador denominado rastreador linear quadrático (RLQ) com custo médio de longo prazo (CMLP) para sistemas lineares com saltos markovianos (SLSM). Mostramos que o conceito de detetabilidade uniforme, juntamente com a hipótese de que o regulador linear quadrático associado ao RLQ tenha custo uniformemente limitado, são suficientes para que o controle obtido seja estabilizante em um certo sentido. A partir deste resultado, e considerando as mesmas hipóteses, demonstramos a existência do CMLP. Com isto, estendemos os resultados dispostos na literatura desde que consideramos um sistema variante no tempo e uma estrutura mais geral para a cadeia deMarkov. Além disto, avaliamos a aplicação deste controlador no planejamento da operação de um sistema hidrotérmico. Para isto, utilizamos o sistema de usinas do rio São Francisco, em dois casos de estudo, para comparar o desempenho do controlador estudado em relação à solução ótima para o problema, encontrada com o uso da programação dinâmica estocástica, e em relação à solução obtida via programação dinâmica determinística. Os resultados sugerem que o RLQ pode representar uma alternativa interessante para o problema de planejamento hidrotérmico / In the present work we study the reference tracking controller (RTC) for the long run average cost (LRAC) problem for Markov jump linear systems. We show that uniform detectability and an hypothesis that the linear quadratic regulator associated with the RTC has uniformly bounded cost, together, are sufficient conditions for the obtained control be exponentially stabilizing in a certain sense. This result allows us to demonstrate the existence of the LTAC under the same hypotheses. The results can be regarded as an extension of previous works, since we have considered a more general framework with time-varying systems and quite general Markov chains. As an applicatioin, we consider the operational planning of hydrothermal systems. We have considered some power plants of the Sao Francisco river, in two different scenarios, and we have compared the performances of the RTC and standard controls obtained by deterministic and stochastic dynamic programming, indicating that the RTC may be an interesting alternative for the hydrothermal planning problem

Esta dissertação desenvolve filtro de informação, algoritmos array para estimador do erro médio mínimo quadrático para sistemas lineares sujeitos a saltos Markovianos e algoritmos array rápidos para filtragem de sistemas singulares convencionais. Exemplos numéricos serão apresentados para mostrarem as vantagens dos algoritmos array deduzidos. Parte dos resultados obtidos nesta pesquisa serão publicados no seguinte artigo: Terra et al. (2007). Terra, M. H., Ishihara, J. Y. and Jesus, G. Q. (2007). Information filtering and array algorithms for discrete-time Markovian jump linear systems. Proceedings of the American Control Conference ACC07. / This dissertation develops information filter and array algorithms for linear minimum mean square error estimator (LMMSE) of discrete-time Markovian jump linear systems (MJLSs) and fast array algorithms for filtering of standard singular systems. Numerical examples to show the advantage of the array algorithms are presented. Some results obtained in this research are published in the following paper: Terra et al. (2007). Terra, M. H., Ishihara, J. Y. and Jesus, G. Q. (2007). Information filtering and array algorithms for discrete-time Markovian jump linear systems. Proceedings of the American Control Conference ACC07.

Nesta tese de doutorado são apresentados sistemas globais de estimativa baseados em modelos Markovianos aplicados na área de reabilitação robótica. Os sistemas propostos foram desenvolvidos para estimar as posições angulares dos elos de exoesqueletos para membros inferiores, desenvolvidos para reabilitação motora em pacientes que sofreram Acidente Vascular Cerebral (AVC) ou lesão medular. Filtros baseados no filtro de Kalman, um nominal e outro considerando incertezas no modelo, foram utilizados em estratégias de fusão de dados de sensores provenientes de sensores inerciais, possibilitando estimativas de posicionamentos angulares. Algoritmos genéticos são utilizados na otimização dos filtros, ajustando as matrizes de peso destes. Em oposição as modelagens tradicionais, via estimativa local, utilizando somente uma unidade inercial para cada modelo, propõe-se um sistema global de estimativa, obtendo-se a melhor informação de cada sensor combinando-os em um modelo Markoviano. Resultados experimentais com um exoesqueleto foram utilizados para comparar a abordagem Markoviana às convencionais. / In this thesis are presented global estimation systems based on Markov models applied in robotic rehabilitation area. The proposed systems have been developed to estimate the angular positions of the exoskeletons for lower limbs, designed to provide motor rehabilitation of stroke and spinal cord injured people. Filters based on the Kalman filter, one nominal and other considering uncertainties in the model, were used in sensor data fusion strategies from inertial sensors, to estimate angular positions. Genetic algorithms are used to the optimization of filters, tuning the weighting matrices. In opposition to these modelling via local estimation, using only one inertial unit, we also chose a global modelling getting the best information from each sensor, combining them in a Markov model. Experimental results with an exoskeleton were used to compare the Markovian approach to conventional.

Este estudo considera o modelo de controle ótimo estocástico sob um critério de média-variância para sistemas lineares a tempo discreto sujeitos a saltos Markovianos e ruídos multiplicativos sob dois critérios. Inicialmente, consideramos como critério de desempenho a minimização multiperíodo de uma combinação entre a média e a variância da saída do sistema sem restrições. Em seguida, consideramos o critério de minimização multiperíodo da variância da saída do sistema ao longo do tempo com restrições sobre o valor esperado mínimo. Condições necessárias e suficientes explícitas para a existência de um controle ótimo são determinadas generalizando resultados anteriores existentes na literatura. O controle ótimo é escrito como uma realimentação de estado adicionado de um termo constante. Esta solução é obtida através de um conjunto de equações generalizadas a diferenças de Riccati interconectadas com um conjunto de equações lineares recursivas. Como aplicação, apresentamos alguns exemplos numéricos práticos para um problema de seleção de portfólio multiperíodo com mudança de regime, incluindo uma estratégia de ALM (Asset and Liability Management). Neste problema, deseja-se obter a melhor alocação de portfólio de forma a otimizar seu desempenho entre risco e retorno em cada passo de tempo até o nal do horizonte de investimento e sob um dos dois critérios citados acima. / In this work we consider the stochastic optimal control problem of discrete-time linear systems subject to Markov jumps and multiplicative noise under two criterions. First, we consider an unconstrained multiperiod mean-variance trade-off performance criterion. In the sequence, we consider a multiperiod minimum variance criterion subject to constraints on the minimum expected output along the time. We present explicit necessary and sufficient conditions for the existence of an optimal control strategy for the problems, generalizing previous results in the literature. The optimal control law is written as a state feedback added with a deterministic sequence. This solution is derived from a set of coupled generalized Riccati difference equations interconnected with a set of coupled linear recursive equations. As an application, we present some practical numerical examples on a multiperiod portfolio selection problem with regime switching, including an Asset and Liability Management strategy. In this problem it is desired to nd the best portfolio allocation in order to optimize its risk-return performance in every time step along the investment horizon, under one of the two criterions stated above.In this work we consider the stochastic optimal control problem of discrete-time linear systems subject to Markov jumps and multiplicative noise under two criterions. First, we consider an unconstrained multiperiod mean-variance trade-off performance criterion. In the sequence, we consider a multiperiod minimum variance criterion subject to constraints on the minimum expected output along the time. We present explicit necessary and sufficient conditions for the existence of an optimal control strategy for the problems, generalizing previous results in the literature. The optimal control law is written as a state feedback added with a deterministic sequence. This solution is derived from a set of coupled generalized Riccati difference equations interconnected with a set of coupled linear recursive equations. As an application, we present some practical numerical examples on a multiperiod portfolio selection problem with regime switching, including an Asset and Liability Management strategy. In this problem it is desired to nd the best portfolio allocation in order to optimize its risk-return performance in every time step along the investment horizon, under one of the two criterions stated above.

Neste trabalho estudamos a estabilidade assintótica de Lagrange para duas classes de sistemas, sob as hipóteses de detetabilidade fraca e de limitação do custo medio a longo prazo. Para sistemas lineares com saltos markovianos com rudo aditivo, a equivalência entre estabilidade e as condições mencionadas sera provada. Para sistemas dinâmicos generalizados, provaremos a estabilidade sob uma condição adicional / In this work we study Lagrange asymptotic stability for two classes of systems, under conditions of weak detectability and boundedness of the long run average cost. For Markov jump linear systems with additive noise, the equivalence between stability and the aforementioned conditions is proved. For generalized dynamical systems, we prove stability under an additional condition

Esta tese trata das propriedades estruturais e do controle de sistemas lineares singulares sujeitos a saltos Markovianos (SLSSM). Três questões fundamentais são consideradas para esta classe de sistemas. A primeira estabelece condições necessárias para que o sistema seja estocasticamente regular em um período de tempo determinado. A segunda trata da estabilidade exponencial estocástica de SLSSM. Equações de Lyapunov acopladas generalizadas são deduzidas para caracterizar estabilidade deste tipo de sistema. Em virtude da complexidade das soluções numéricas dessas equações, cada equação de Lyapunov do conjunto acoplado está em função de duas variáveis desconhecidas, estamos propondo um algoritmo para resolver este problema. A terceira questão diz respeito à síntese de um regulador para este tipo de sistema singular definida em termos de equações algébricas generalizadas de Riccati acopladas. / This thesis deals with the structural features and with the control of singular linear systems with Markovian jump parameters (SLSMJP). Three fundamental questions are considered to this class of systems. The first provides necessary conditions to characterize stochastic regularity in a determined period of time. The second deals with exponential stability of SLSMJP. Coupled generalized Lyapunov Equations are deduced to check the stability of this class of systems. In virtue of the complexity of the numerical solutions of these equations, there exist two unknown variables for each equation of the set of coupled Lyapunov equations, we are proposing an algorithm to solve this problem. The third question is related with the synthesis of a regulator for this class of singular systems defined in terms of coupled algebraic generalized Riccati equations.

Esta tese aborda o problema de regulação para sistemas lineares sujeitos a saltos Markovianos de tempo discreto com matrizes de transição incertas. Considera-se que as incertezas são limitadas em norma e os estados da cadeia de Markov podem não ser completamente observados pelo controlador. No cenário com observação completa dos estados, a solução é deduzida com base em um funcional quadrático dado em termos das probabilidades de transição incertas. Enquanto que no cenário sem observação, a solução é obtida por meio da reformulação do sistema Markoviano como um sistema determinístico, independente da cadeia de Markov. Três modelos são propostos para essa reformulação: um modelo é baseado no primeiro momento do sistema Markoviano, o segundo é obtido a partir da medida de Dirac e resulta em um sistema aumentado, e o terceiro fornece um sistema aumentado singular. Os reguladores recursivos robustos são projetados a partir de critérios de custo quadrático, dados em termos de problemas de otimização restritos. A solução é derivada da técnica de mínimos quadrados regularizados robustos e apresentada em uma estrutura matricial. A recursividade é estabelecida por equações de Riccati, que se assemelham às soluções dos reguladores clássicos, para essa classe de sistemas, quando não estão sujeitos a incertezas. / This thesis deals with regulation problem for discrete-time Markovian jump linear systems with uncertain transition matrix. The uncertainties are assumed to be normbounded type. The states of the Markov chain can not be completely observed by the controller. In the scenario with complete observation of the states, the solution is deduced based on a quadratic functional given in terms of uncertain transition probabilities. While in the scenario without observation, the solution is obtained from reformulation of the Markovian system as a deterministic system, independent of the Markov chain. Three models are proposed for the reformulation process: a model is based on the first moment of the Markovian system, the second is obtained from Dirac measure which results in an augmented system, and the third provides a singular augmented system. Recursive robust regulators are designed from quadratic cost criteria given in terms of constrained optimization problems. The solution is derived from the robust regularized least-square approach, whose framework is given in terms of a matrix structure. The recursiveness is established by Riccati equations which resemble the solutions of standard regulators for this class of systems, when they are not subject to uncertainties.