Planejamento probabilístico lida com a tomada de decisão sequencial em ambientes estocásticos e geralmente é modelado por um Processo de Decisão Markoviano (Markovian Decision Process - MDP). Um MDP modela a interação entre um agente e o seu ambiente: em cada estágio, o agente decide executar uma ação, com efeitos probabilísticos e um certo custo, que irá produzir um estado futuro. O objetivo do agente MDP é minimizar o custo esperado ao longo de uma sequência de escolhas de ação. O número de estágios que o agente atua no ambiente é chamado de horizonte, o qual pode ser finito, infinito ou indefinido. Um exemplo de MDP com horizonte indefinido é o Stochastic Shortest Path MDP (SSP MDP), que estende a definição de MDP adicionando um conjunto de estados meta (o agente para de agir ao alcançar um estado meta). Num SSP MDP é feita a suposição de que é sempre possível alcançar um estado meta a partir de qualquer estado do mundo. No entanto, essa é uma suposição muito forte e que não pode ser garantida em aplicações práticas. Estados a partir dos quais é impossível atingir a meta são chamados de becos-sem-saída. Um beco-sem-saída pode ser evitável ou inevitável (se nenhuma política leva do estado inicial para a meta com probabilidade um). Em trabalhos recentes foram propostas extensões para SSP MDP que permitem a existência de diferentes tipos de beco-sem-saída, bem como algoritmos para resolvê-los. No entanto, a detecção de becos-sem-saída é feita utilizando: (i) heurísticas que podem falhar para becos-sem-saída implícitos ou (ii) métodos mais confiáveis, mas que demandam alto custo computacional. Neste projeto fazemos uma caracterização formal de modelos de planejamento probabilístico com becos-sem-saída. Além disso, propomos uma nova técnica para detecção de becos-sem-saída baseada nessa caracterização e adaptamos algoritmos de planejamento probabilístico para utilizarem esse novo método de detecção. Os resultados empíricos mostram que o método proposto é capaz de detectar todos os becos-sem-saída de um dado conjunto de estados e, quando usado com planejadores probabilísticos, pode tornar esses planejadores mais eficientes em domínios com becos-sem-saída difíceis de serem detectados / Probabilistic planning deals with sequential decision making in stochastic environments and is modeled by a Markovian Decision Process (MDP). An MDP models the interaction between an agent and its environment: at each stage, the agent decides to execute an action, with probabilistic effects and a certain cost which produces a future state. The purpose of the MDP agent is to minimize the expected cost along a sequence of choices. The number of stages that the agent acts in the environment is called horizon, which can be finite, infinite or undefined. An example of MDP with undefined horizon is the Stochastic Shortest Path MDP, which extends the definition of MDP by adding a set of goal states (the agent stops acting after reaching a goal state). In an SSP MDP the assumption is made that it is always possible to achieve a goal state from every state of the world. However, this is a very strong assumption and cannot be guaranteed in practical applications. States from which it is impossible to reach the goal are called dead-ends. A dead-end may be avoidable or unavoidable (when no policy leads from the initial state to the goal with probability one). Recent work has proposed extensions to SSP MDP that allow the existence of different types of dead-ends as well as algorithms to solve them. However, the detection of dead-end is done using: (i) heuristics that may fail to detect implicitly dead-ends or (ii) more reliable methods that require a high computational cost. In this project we make a formal characterization of probabilistic planning models with dead-ends. In addition, we propose a new technique for dead-end detection based on this characterization and we adapt probabilistic planning algorithms to use this new detection method. The empirical results show that the proposed method is able to detect all dead-ends of a given set of states and, when used withprobabilistic planners, can make these planners more efficient in domains with difficult to detect dead-ends.

Planejamento probabilístico lida com a tomada de decisão sequencial em ambientes estocásticos e geralmente é modelado por um Processo de Decisão Markoviano (Markovian Decision Process - MDP). Um MDP modela a interação entre um agente e o seu ambiente: em cada estágio, o agente decide executar uma ação, com efeitos probabilísticos e um certo custo, que irá produzir um estado futuro. O objetivo do agente MDP é minimizar o custo esperado ao longo de uma sequência de escolhas de ação. O número de estágios que o agente atua no ambiente é chamado de horizonte, o qual pode ser finito, infinito ou indefinido. Um exemplo de MDP com horizonte indefinido é o Stochastic Shortest Path MDP (SSP MDP), que estende a definição de MDP adicionando um conjunto de estados meta (o agente para de agir ao alcançar um estado meta). Num SSP MDP é feita a suposição de que é sempre possível alcançar um estado meta a partir de qualquer estado do mundo. No entanto, essa é uma suposição muito forte e que não pode ser garantida em aplicações práticas. Estados a partir dos quais é impossível atingir a meta são chamados de becos-sem-saída. Um beco-sem-saída pode ser evitável ou inevitável (se nenhuma política leva do estado inicial para a meta com probabilidade um). Em trabalhos recentes foram propostas extensões para SSP MDP que permitem a existência de diferentes tipos de beco-sem-saída, bem como algoritmos para resolvê-los. No entanto, a detecção de becos-sem-saída é feita utilizando: (i) heurísticas que podem falhar para becos-sem-saída implícitos ou (ii) métodos mais confiáveis, mas que demandam alto custo computacional. Neste projeto fazemos uma caracterização formal de modelos de planejamento probabilístico com becos-sem-saída. Além disso, propomos uma nova técnica para detecção de becos-sem-saída baseada nessa caracterização e adaptamos algoritmos de planejamento probabilístico para utilizarem esse novo método de detecção. Os resultados empíricos mostram que o método proposto é capaz de detectar todos os becos-sem-saída de um dado conjunto de estados e, quando usado com planejadores probabilísticos, pode tornar esses planejadores mais eficientes em domínios com becos-sem-saída difíceis de serem detectados / Probabilistic planning deals with sequential decision making in stochastic environments and is modeled by a Markovian Decision Process (MDP). An MDP models the interaction between an agent and its environment: at each stage, the agent decides to execute an action, with probabilistic effects and a certain cost which produces a future state. The purpose of the MDP agent is to minimize the expected cost along a sequence of choices. The number of stages that the agent acts in the environment is called horizon, which can be finite, infinite or undefined. An example of MDP with undefined horizon is the Stochastic Shortest Path MDP, which extends the definition of MDP by adding a set of goal states (the agent stops acting after reaching a goal state). In an SSP MDP the assumption is made that it is always possible to achieve a goal state from every state of the world. However, this is a very strong assumption and cannot be guaranteed in practical applications. States from which it is impossible to reach the goal are called dead-ends. A dead-end may be avoidable or unavoidable (when no policy leads from the initial state to the goal with probability one). Recent work has proposed extensions to SSP MDP that allow the existence of different types of dead-ends as well as algorithms to solve them. However, the detection of dead-end is done using: (i) heuristics that may fail to detect implicitly dead-ends or (ii) more reliable methods that require a high computational cost. In this project we make a formal characterization of probabilistic planning models with dead-ends. In addition, we propose a new technique for dead-end detection based on this characterization and we adapt probabilistic planning algorithms to use this new detection method. The empirical results show that the proposed method is able to detect all dead-ends of a given set of states and, when used withprobabilistic planners, can make these planners more efficient in domains with difficult to detect dead-ends.