Um dos modelos mais usados para descrever problemas de planejamento probabilístico, i.e., planejamento de ações com efeitos probabilísticos, é o processo de decisão markoviano (Markov Decision Process - MDP). Soluções tradicionais são baseadas em programação dinâmica, sendo as mais ecientes aquelas baseadas em programação dinâmica em tempo real (Real-Time Dynamic Programming - RTDP), por explorarem somente os estados alcançáveis a partir de um dado estado inicial. Por outro lado, existem soluções ecientes baseadas em métodos de busca heurística em um grafo AND/OR, sendo que os nós AND representam os efeitos probabilísticos das ações e os nós OR representam as escolhas de ações alternativas. Tais soluções também exploram somente estados alcançáveis a partir de um estado inicial porém, guardam um subgrafo solução parcial e usam programação dinâmica para a atualização do custo dos nós desse subgrafo. No entanto, problemas com grandes espaços de estados limitam o uso prático desses métodos. MDPs fatorados permitem explorar a estrutura do problema, representando MDPs muito grandes de maneira compacta e assim, favorecer a escalabilidade das soluções. Neste trabalho, apresentamos uma análise comparativa das diferentes soluções para MDPs, com ênfase naquelas que fazem busca heurística e as comparamos com soluções baseadas em programação dinâmica assíncrona, consideradas o estado da arte das soluções de MPDs. Além disso, propomos um novo algoritmo de busca heurística para MDPs fatorados baseado no algoritmo ILAO* e o testamos nos problemas da competição de planejamento probabilístico IPPC-2011. / One of the most widely used models to describe probabilistic planning problems, i.e., planning of actions with probabilistic eects, is the Markov Decision Process - MDP. The traditional solutions are based on dynamic programming, whereas the most ecient solutions are based on Real-Time Dynamic Programming - RTDP, which explore only the reachable states from a given initial state. Moreover, there are ecient solutions based on search methods in a AND/OR graph, where AND nodes represent the probabilistic eects of an action and OR nodes represent the choices of alternative actions. These solutions also explore only reachable states but maintain the parcial subgraph solution, using dynamic programming for updating the cost of nodes of these subgraph. However, problems with large state spaces limit the practical use of these methods. Factored representation of MDPs allow to explore the structure of the problem, and can represent very large MDPs compactly and thus improve the scalability of the solutions. In this dissertation, we present a comparative analysis of dierent solutions for MDPs, with emphasis on heuristic search methods. We compare the solutions which are based on asynchronous dynamic programming which are also considered the state of the art. We also propose a new factored algorithm based on the search algorithm ILAO*. It is also tested by using the problems of the International Probabilistic Planning Competition IPPC-2011.

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado. / Markov Decision Process (MDP) model problems of sequential decision making, where the possible actions have probabilistic effects on the successor states (defined by state transition matrices). Real-time dynamic programming (RTDP), is a technique for solving MDPs when there exists information about the initial state. Traditional approaches show better performance in problems with sparse state transition matrices, because they can achieve the convergence to optimal policy efficiently, without visiting all states. But, this advantage can be lose in problems with dense state transition matrices, in which several states can be achieved in a step (for example, control problems with exogenous events). An approach to overcome this limitation is to explore regularities existing in the domain dynamics through a factored representation, i.e., a representation based on state variables. In this master thesis, we propose a new algorithm called FactRTDP (Factored RTDP), and its approximate version aFactRTDP (Approximate and Factored RTDP), that are the first factored efficient versions of the classical RTDP algorithm. We also propose two other extensions, FactLRTDP and aFactLRTDP, that label states for which the value function has converged to the optimal. The experimental results show that when these new algorithms are executed in domains with dense transition matrices, they converge faster. And they have a good online performance in domains with dense transition matrices and few dependencies among state variables.

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado. / Markov Decision Process (MDP) model problems of sequential decision making, where the possible actions have probabilistic effects on the successor states (defined by state transition matrices). Real-time dynamic programming (RTDP), is a technique for solving MDPs when there exists information about the initial state. Traditional approaches show better performance in problems with sparse state transition matrices, because they can achieve the convergence to optimal policy efficiently, without visiting all states. But, this advantage can be lose in problems with dense state transition matrices, in which several states can be achieved in a step (for example, control problems with exogenous events). An approach to overcome this limitation is to explore regularities existing in the domain dynamics through a factored representation, i.e., a representation based on state variables. In this master thesis, we propose a new algorithm called FactRTDP (Factored RTDP), and its approximate version aFactRTDP (Approximate and Factored RTDP), that are the first factored efficient versions of the classical RTDP algorithm. We also propose two other extensions, FactLRTDP and aFactLRTDP, that label states for which the value function has converged to the optimal. The experimental results show that when these new algorithms are executed in domains with dense transition matrices, they converge faster. And they have a good online performance in domains with dense transition matrices and few dependencies among state variables.

Um dos modelos mais usados para descrever problemas de planejamento probabilístico, i.e., planejamento de ações com efeitos probabilísticos, é o processo de decisão markoviano (Markov Decision Process - MDP). Soluções tradicionais são baseadas em programação dinâmica, sendo as mais ecientes aquelas baseadas em programação dinâmica em tempo real (Real-Time Dynamic Programming - RTDP), por explorarem somente os estados alcançáveis a partir de um dado estado inicial. Por outro lado, existem soluções ecientes baseadas em métodos de busca heurística em um grafo AND/OR, sendo que os nós AND representam os efeitos probabilísticos das ações e os nós OR representam as escolhas de ações alternativas. Tais soluções também exploram somente estados alcançáveis a partir de um estado inicial porém, guardam um subgrafo solução parcial e usam programação dinâmica para a atualização do custo dos nós desse subgrafo. No entanto, problemas com grandes espaços de estados limitam o uso prático desses métodos. MDPs fatorados permitem explorar a estrutura do problema, representando MDPs muito grandes de maneira compacta e assim, favorecer a escalabilidade das soluções. Neste trabalho, apresentamos uma análise comparativa das diferentes soluções para MDPs, com ênfase naquelas que fazem busca heurística e as comparamos com soluções baseadas em programação dinâmica assíncrona, consideradas o estado da arte das soluções de MPDs. Além disso, propomos um novo algoritmo de busca heurística para MDPs fatorados baseado no algoritmo ILAO* e o testamos nos problemas da competição de planejamento probabilístico IPPC-2011. / One of the most widely used models to describe probabilistic planning problems, i.e., planning of actions with probabilistic eects, is the Markov Decision Process - MDP. The traditional solutions are based on dynamic programming, whereas the most ecient solutions are based on Real-Time Dynamic Programming - RTDP, which explore only the reachable states from a given initial state. Moreover, there are ecient solutions based on search methods in a AND/OR graph, where AND nodes represent the probabilistic eects of an action and OR nodes represent the choices of alternative actions. These solutions also explore only reachable states but maintain the parcial subgraph solution, using dynamic programming for updating the cost of nodes of these subgraph. However, problems with large state spaces limit the practical use of these methods. Factored representation of MDPs allow to explore the structure of the problem, and can represent very large MDPs compactly and thus improve the scalability of the solutions. In this dissertation, we present a comparative analysis of dierent solutions for MDPs, with emphasis on heuristic search methods. We compare the solutions which are based on asynchronous dynamic programming which are also considered the state of the art. We also propose a new factored algorithm based on the search algorithm ILAO*. It is also tested by using the problems of the International Probabilistic Planning Competition IPPC-2011.