Academic literature on the topic 'Processos de decisió de Markov'

Os Processos de Decisão de Markov (PDMs) são uma importante ferramenta de planejamento e otimização em ambientes que envolvem incertezas. Contudo a especificação e representação computacional das distribuições de probabilidades subjacentes a PDMs é uma das principais dificuldades de utilização desta ferramenta. Este trabalho propõe duas estratégias para representação destas probabilidades de forma compacta e eficiente. Estas estratégias utilizam redes Bayesianas e regularidades entre os estados e as variáveis. As estratégias apresentadas são especialmente úteis em sistemas onde as variáveis têm muitas categorias e possuem forte inter-relação. Além disso, é apresentada a aplicação destes modelos no gerenciamento de grupos de impressoras (um problema real da indústria e que motivou o desenvolvimento do trabalho) permitindo que estas atuem coletiva e não individualmente. O último tópico discutido é uma análise comparativa da mesma aplicação utilizando Lógica Difusa.<br>Markov Decision Processes (MDPs) are an important tool for planning and optimization in environments under uncertainty. The specification and computational representation of the probability distributions underlying MDPs are central difficulties for their application. This work proposes two strategies for representation of probabilities in a compact and efficient way. These strategies use Bayesian networks and regularities among states and variables. The proposed strategies are particularly useful in systems whose variables have many categories and have strong interrelation. This proposal has been applied to the management of clusters of printers, a real problem that in fact motivated the work. Markov Decision Processes are then used to allow printers to act as a group, and not just individually. The work also presents a comparison between MDPs and Fuzzy Logic in the context of clusters of printers.

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.<br>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.

El sector porquí Espanyol ha sofert recentment profuns canvis degut bàsicament a<br/>l'augment de la competència i al procés de globalització econòmica. Ademes, els<br/>avenços tecnológicos i el grau creixent d'especialització en el sector afavoreixen el<br/>desenvolupament i l'adopció de eienes avançades per a la pressa de decisions. En<br/>aquest context, l'objectiu d'aquesta Tesi ha estat formular i implementar un model<br/>dinàmic estocàstic del comportament productiu d'un remat de truges, basat en<br/>processos de decisió Markovians i capaç d'ésser utilitzat en condicions reals. La<br/>finalitat del model és representar alternatives de maneig reproductiu i de reposició en<br/>explotacins porcines per assistir als grangers, tècnics i gerents en la pressa de<br/>decisions en granja.<br/>El model de decisió semi-Markovià i el Markovià que s'en deriva del primer han<br/>demostrat ser models útils per la representació de les estratègies productives de<br/>maneig reproductiu i de la reposició. La disponibilitat de dades de camp de granges<br/>individuals ha permès la validació del model en situacions reals. La validació ha servit<br/>també per mostrar com el model no pot ser aplicat indiscriminadament a qualsevol<br/>granja, prèviament s'ha d'assegurar l'ajust del model a les condicions concretes de<br/>cada explotació. També s'ha ficat de manifest que quan el model s'utilitza per a<br/>calcular l'estructura de la població a l'equilibri no és necessari que la matriu de<br/>transició representi el pas de temps constant, la qual cosa ha permès treballar amb<br/>transicions associades als estats biològics que són més fàcils d'estimar (embedded<br/>Markov process), ademes, proporcionen estalvis computacionals que permeten una<br/>avaluado més ràpida d'alternatives de maneig reproductiu i la implementació<br/>d'algorismes d'optimització pel problema de la reposició més eficientes.<br/>La implementació del model de decisió semi-Markovià dins d'un sistema d'ajut a la<br/>pressa de decisions (DSS: Decision Support Systems) ha mostrat l'ús potencial del<br/>model en granja. El desenvolupament del DSS ha facilitat la disponibilitat d'un model<br/>complex com el presentat a potencials usuaris menys especialitzats. El DSS permet al<br/>granger avaluar a peu de granja diferentes alternatives productives, analitzar la<br/>sensibilitat dels paràmetres que consideri crítics i optimitzar la política de reposició.<br/>Ademes, la integració del DSS en un sistema de gestió informatitzat (BDporc®2)<br/>facilita la difusió del DSS en empreses de producció porcina i també l'obtenció de<br/>noves variables com el número de serveis por monta, la detecció de zels, la detecció<br/>de la gestació, instalacions, etc, que poden ajudar a incrementar la precisió dels<br/>resultats. El disseny sofisticat del interface del DSS ha millorat la interpretació dels<br/>resultats del model que no sempre és inmediata. La incorporació de l'anàlisi de<br/>sensibilitat permet estudiar i profunditzar en els components crítics del model que<br/>sovint resulta més important que l'obtenció d'un resultat precis. Finalment, el model de<br/>remat formulat de forma flexible, és capaç d'adaptar-se a diferents propòsits amb<br/>canvis mínims, la qual cosa contribueix a una millor comprensió dels efectes de<br/>diferentes alternatives de maneig reproductiu sobre la millora de la eficiència<br/>econòmica de tot el sistema productiu.<br>El sector porcino en España ha sufrido recientemente profundos cambios debido<br/>básicamente al aumento de la competencia y al proceso de globalización económica.<br/>Además, los avances tecnológicos y el creciente grado de especialización en el sector<br/>favorecen el desarrollo y la adopción de herramientas avanzadas para la toma de<br/>decisiones. En este contexto, el objetivo de esta Tesis es presentar la formulación e<br/>¡mplementadón de un modelo dinámico estocástico del comportamiento productivo de<br/>un rebaño de cerdas, basado en procesos de decisión Markovianos y capaz de ser<br/>usado en condiciones reales. La finalidad del modelo es representar alternativas de<br/>manejo reproductivo y de reposición en explotacines porcinas para asistir a granjeros,<br/>técnicos y gerentes en la toma de decisiones en granja.<br/>El modelo de decisión semi-Markovianos y el Markoviano que deriva del primero han<br/>demostrado ser modelos útiles en la representación de las estrategias productivas de<br/>manejo reproductivo y de la reposición. La disponibilidad de datos de campo de<br/>granjas individuales ha permitido la validación del modelo en situaciones reales. La<br/>validación ha servido también para mostrar como el modelo no puede ser aplicado<br/>indiscriminadamente en cualquier granja, previamente se asegurar el ajuste del<br/>modelo a las condiciones concretas de cada explotación. También se ha puesto de<br/>manifiesto que cuando el modelo se utiliza para calcular la estructura de la población<br/>en equilibrio no es necesario que la matriz de transición represente de paso de tiempo<br/>constante, con lo cual ha sido posible trabajar con transiciones asociadas a los<br/>estados biológicas que son más fáciles estimar (embedded Markov process), además,<br/>proporcionan ahorros computacionales que permiten una evaluación más rápida de<br/>alternativas de manejo reproductivo y la implementación de algoritmos de optimización<br/>para el problema de la reposición más eficientes.<br/>La implementación del modelo de decisión semi-Markoviano dentro de un sistema de<br/>ayuda a la toma de decisiones (DSS: Decision Support Systems) ha mostrado el uso<br/>potencial del modelo en granja. El desarrollo del DSS ha facilitado la disponibilidad de<br/>un modelo complejo como el presentado a potenciales usuarios menos especializados.<br/>El DSS permite al granjero evaluar a pie de granja diferntes alternativas productivas,<br/>analizar la sensibilidad de los parámetros que considere críticos y optimiza la política<br/>de reposición. Además, la integración del DSS en un sistema de gestión informatizado<br/>(BDporc®3) facilita la difusión del DSS en empresas de producción porcina y también<br/>la obtención de nuevas variables como el número de servicios por monta, la detección<br/>de celos, la detección de la gestación, instalaciones, etc, que pueden ayudar a<br/>incrementar la precisión de los resultados. El diseño sofisticados del interface del DSS<br/>ha mejorado la interpretación de los resultados que no siempre es inmediata. El<br/>análisis de sensibilidad incorporado permite estudiar y profundizar en los componentes<br/>críticos del modelo que a menudo resulta más importante que el disponer de un<br/>resultado preciso. Finalmente, el modelo de rebaño formulado de forma flexible, es<br/>capaz de adaptarse a distintos propósitos con cambios mínimos, lo que redunda en<br/>una mejor compresión de los efectos de diferentes alternativas de manejo reproductivo<br/>a fin de mejorar la eficiencia económica de todo el sistema productivo.<br>Spanish pig sector has gone through a deep change during recent times, that is due<br/>basically to the increase in competitiveness and the globalisation process of the<br/>economics. Furthermore, technological advances and the increasing degree of<br/>specialisation have maden possible the development and adoption of advanced tools<br/>for decision support. In this context, the objective of this Thesis has been to formulate<br/>and implement a dynamic estochastic model representing the productive behaviour of<br/>a sow herd, based on Markov decision processes. The model was aimed to be used in<br/>field condicions to analyse different management alternatives on reproduction and<br/>replacement, supporting farm managers in the decision-making process.<br/>The semi-Markovià decision model and the derived Markov decision model (embedded<br/>Markov process) have demonstrated to be useful in the representation of management<br/>alternatives on reproduction and replacement. The availability of data from individual<br/>farms has allowed the validation of the model in real situations. The validation also has<br/>served to show how the model can not be applied indiscriminately on any farm.<br/>Previously, it has been required to assess the fit of the model in specific farm<br/>conditions. Also, it is shown that when the model has been used to calculate the<br/>population structure at equilibrium was not necessary a transition matrix being time<br/>step constant. Instead have been possible to consider transitions associated to<br/>biological states that are easier to estimate, more precise and provided computational<br/>time savings. Hence the model, as it was formulated, allowed a faster evaluation of<br/>management alternatives on reproduction and an efficient impleemntation of algorithms<br/>to optimise replacement policies.<br/>The implementation of the semi-Markov model into a DSS (DSS: Decision Support<br/>Systems) has shown the potential on-farm use of the model. The development of the<br/>DSS makes easier the availability of complex models to less specialised users. The<br/>DSS allows the farm manager to evaluate on-farm different management alternatives<br/>on reproduction and optimise replacement decisions. Moreover, the integration of the<br/>DSS in a management information system (BDporc®1) makes easier the spreading of it<br/>over swine enterprises, as well the obtention of new variables like the number of<br/>services by mating, heat detections, pregnancy detection, facilities, etc, can help to<br/>increment model precision. The sophisticated dessign of the DSS interface has<br/>improved the interpretation of the model results, that not always is right direct. The<br/>addition of sensitivity análisis capability provided insight about the impact of changes in<br/>critical components of the model, that quite often result in a more interest than a single<br/>precise result. Finally, the sow herd model formulated in a flexible way, was able to be<br/>adapted to différents goals with minimum changes, thus it contribute to improve the<br/>knowledge about the effect of different management alternatives on overall economic<br/>efficiency of the system.

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.<br>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.

Redes de Anúncios (Ad Networks) são redes que promovem a distribuição de anúncios pela internet, de forma a maximizar o lucro total gerado pela exibição dos anúncios nos websites. Estas redes tipicamente operam através do modelo de negócios chamado CPC (Custo por Clique), em que o anunciante paga um determinado valor somente se algum usuário clicar em seu anúncio. A escolha de como o intermediador planeja a distribuição dos anúncios aos websites é de extrema importância, já que a taxa de cliques nos anúncios é extremamente baixa. Atualmente a alocação dos anúncios tem sido feita através de uma solução aproximada baseada na alocação ótima definida com dados de um período anterior, a qual é calculada através de programação linear aliada à utilização de heurísticas. Entretanto, este sistema claramente é um processo de decisão sequencial em que diversas restrições são aplicáveis, como por exemplo: o orçamento dos anunciantes, limites mínimos do número de exibições de cada anúncio, categorias dos anúncios, entre outras. Neste trabalho argumenta-se que MDPs (Markov Decision Processes) fornecem uma melhor modelagem para o problema, já que conseguem levar em conta a dinâmica do sistema, considerando, por exemplo, que um anúncio que tem poucas chances de ser clicado consiga ser alocado de forma eficiente em relação ao retorno de longo prazo, mesmo quando outros anúncios proveriam um lucro maior a curto prazo. No entanto, devido ao grande número de estados, utilizar uma solução ótima através de MDPs é impraticável. Portanto analisa-se o desempenho relativo entre o estado da arte e a modelagem ótima, obtendo garantias de que a solução aproximada baseada em programação linear não está longe da solução ótima, e que em problemas grandes (similares aos encontrados na prática) essa diferença pode ser ignorada. Por fim, propõe-se uma modelagem baseada em aprendizado por reforço para a solução deste problema, utilizando duas abordagens, uma desconsiderando informações de contexto e outra considerando informações de contexto. Aqui argumenta-se que o uso de aprendizado por reforço é mais apropriado para a solução do problema de alocação de anúncios, já que ele é capaz de adaptar sua política de alocação em função das mudanças que ocorrem como, por exemplo, no perfil do usuário.<br>Ad Networks promote the distribution of ads in the internet, so as to maximize the revenue generated by their display of ads in websites. These networks typically operate using the CPC (Cost per Click) business model, where the advertiser pays a monetary value when a user clicks in its advertisement. The choice of how the Ad Network distributes ads to websites is of utmost importance, since the rate of clicks on ads is extremely low. The allocation of ads has been done by an approximate solution based on data from an early period of time, which is calculated using linear programming combined with heuristics. However, this problem is clearly a sequential decision process in which multiple sequential restrictions apply, such as: the budget of the advertisers, minimum limits on the number of views for each campaign, categories of advertisements. In this dissertation we argue that MDPs (Markov Decision Processes) provide a better model for the problem, since they can automatically take into account the dynamics of the system, considering, for example, an ad with little chance of being clicked can be allocated in an efficient way, even when other ads would provide a higher profit in the short term. However, due to the large number of states, an optimal solution through MDPs is impractical; therefore we analyze here the relative performance between the linear programming and the MDP approaches, deriving guarantees that the approximate solution based on linear programming is not far from the MDP optimal solution, and in large problems (similar to those found in practice) this difference can be disregarded. Finally, we propose a model based on reinforcement learning using two different approaches, one disregarding the contextual information, and the other using contextual information. We argue that the use of reinforcement learning is more suitable for solving the problem of allocation of ads, since it is able to adapt its allocation policy to reflect changes that occur, e.g., in the user profile.

Planejamento em inteligência artificial é a tarefa de determinar ações que satisfaçam um dado objetivo. Nos problemas de planejamento sob incerteza, as ações podem ter efeitos probabilísticos. Esses problemas são modelados como Processos de Decisão Markovianos (Markov Decision Processes - MDPs), modelos que permitem o cálculo de soluções ótimas considerando o valor esperado de cada ação em cada estado. Contudo, resolver problemas grandes de planejamento probabilístico, i.e., com um grande número de estados e ações, é um enorme desafio. MDPs grandes podem ser reduzidos através da computação de bissimulações estocásticas, i.e., relações de equivalência sobre o conjunto de estados do MDP original. A partir das bissimulações estocásticas, que podem ser exatas ou aproximadas, é possível obter um modelo abstrato reduzido que pode ser mais fácil de resolver do que o MDP original. No entanto, para problemas de alguns domínios, a computação da bissimulação estocástica sobre todo o espaço de estados é inviável. Os algoritmos propostos neste trabalho estendem os algoritmos usados para a computação de bissimulações estocásticas para MDPs de forma que elas sejam computadas sobre o conjunto de estados alcançáveis a partir de um dado estado inicial, que pode ser muito menor do que o conjunto de estados completo. Os resultados experimentais mostram que é possível resolver problemas grandes de planejamento probabilístico com desempenho superior às técnicas conhecidas de bissimulação estocástica.<br>Planning in artificial intelligence is the task of finding actions to reach a given goal. In planning under uncertainty, the actions can have probabilistic effects. This problems are modeled using Markov Decision Processes (MDPs), models that enable the computation of optimal solutions considering the expected value of each action when applied in each state. However, to solve big probabilistic planning problems, i.e., those with a large number of states and actions, is still a challenge. Large MDPs can be reduced by computing stochastic bisimulations, i.e., equivalence relations over the original MDP states. From the stochastic bisimulations, that can be exact or approximated, it is possible to get an abstract reduced model that can be easier to solve than the original MDP. But, for some problems, the stochastic bisimulation computation over the whole state space is unfeasible. The algorithms proposed in this work extend the algorithms that are used to compute stochastic bisimulations for MDPs in a way that they can be computed over the reachable set of states with a given initial state, which can be much smaller than the complete set of states. The empirical results show that it is possible to solve large probabilistic planning problems with better performance than the known techniques of stochastic bisimulation.

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.<br>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.

Este trabalho é dedicado ao desenvolvimento teórico e algorítmico de processos de decisão markovianos com probabilidades imprecisas e representações relacionais. Na literatura, essa configuração tem sido importante dentro da área de planejamento em inteligência artificial, onde o uso de representações relacionais permite obter descrições compactas, e o emprego de probabilidades imprecisas resulta em formas mais gerais de incerteza. São três as principais contribuições deste trabalho. Primeiro, efetua-se uma discussão sobre os fundamentos de tomada de decisão sequencial com probabilidades imprecisas, em que evidencia-se alguns problemas ainda em aberto. Esses resultados afetam diretamente o (porém não restrito ao) modelo de interesse deste trabalho, os processos de decisão markovianos com probabilidades imprecisas. Segundo, propõe-se três algoritmos para processos de decisão markovianos com probabilidades imprecisas baseadas em programação (otimização) matemática. E terceiro, desenvolvem-se ideias propostas por Trevizan, Cozman e de Barros (2008) no uso de variantes do algoritmo Real-Time Dynamic Programming para resolução de problemas de planejamento probabilístico descritos através de versões estendidas da linguagem de descrição de domínios de planejamento (PPDDL).<br>This work is devoted to the theoretical and algorithmic development of Markov Decision Processes with Imprecise Probabilities and relational representations. In the literature, this configuration is important within artificial intelligence planning, where the use of relational representations allow compact representations and imprecise probabilities result in a more general form of uncertainty. There are three main contributions. First, we present a brief discussion of the foundations of decision making with imprecise probabilities, pointing towards key questions that remain unanswered. These results have direct influence upon the model discussed within this text, that is, Markov Decision Processes with Imprecise Probabilities. Second, we propose three algorithms for Markov Decision Processes with Imprecise Probabilities based on mathematical programming. And third, we develop ideas proposed by Trevizan, Cozman e de Barros (2008) on the use of variants of Real-Time Dynamic Programming to solve problems of probabilistic planning described by an extension of the Probabilistic Planning Domain Definition Language (PPDDL).