Processos de Decisão Markovianos de Caminho Estocástico mais Curto (SSP-MDPs) são utilizados para modelar problemas de decisões sequenciais probabilísticas em que o objetivo é minimizar o custo acumulado esperado para a meta. No entanto, na presença de estados a partir dos quais não se pode alcançar a meta (dead ends), o critério convencional de SSP-MDPs, que minimiza o custo acumulado esperado, pode deixar de ser bem-definido. Critérios lexicográficos podem resolver isso ao definir uma preferência sobre políticas que alcançam a meta com a máxima probabilidade possível. Outros critérios podem ao invés disso realizar um compromisso entre alguma medida de custo e probabilidade à meta. No entanto, ambas abordagens podem escolher políticas que podem não representar a escolha de um tomador de decisão realístico. O critério GUBS, que combina priorização de metas sobre históricos com Teoria da Utilidade Esperada para realizar compromissos entre custos e probabilidade à meta, foi proposto para resolver esses problemas. O critério eGUBS, que é um caso particular do GUBS quando uma função de utilidade exponencial é utilizada, foi depois também proposto, juntamente com o eGUBS-VI, um algoritmo baseado em iteração de valor que constitui o primeiro método para resolver SSP-MDPs sob o critério GUBS de maneira ótima. Esta dissertação contém uma comparação entre o critério GUBS e outros critérios para resolver SSP-MDPs na presença de dead ends, e introduz definições e resultados teóricos que mostram que o GUBS é o único desses critérios que não apenas possibilita a realização de compromissos entre grandes custos acumulados sobre pequenas perdas em probabilidade à meta, mas que também garante compromissos arbitrários que podem ser configurados a partir dos seus parâmetros sem conhecimento prévio do problema a ser resolvido. Além disso, esta dissertação introduz o eGUBS-AO*, um algoritmo ótimo de busca heurística para resolver o critério eGUBS. Resultados indicam que, quando uma boa função heurística é disponível ou quando o espaço de estados do problema é muito grande, o eGUBS-AO* pode ter um desempenho melhor que o eGUBS-VI ao realizar uma busca eficiente. Em outros casos, a abordagem mais simples do eGUBS-VI pode trazer melhores resultados.

Stochastic Shortest Path Markov Decision Processes (SSP-MDPs) are used to model probabilistic sequential decision problems where the objective is to minimize the expected accumulated cost to goal. However, in the presence of dead ends, the conventional criterion for SSP-MDPs, which minimizes the expected accumulated cost, can become ill-defined. Lexicographic criteria can solve this by preferring policies that reach the goal with the highest possible probability. Other criteria can instead make a trade-off between some cost measure and probability-to-goal. However, both of these approaches can lead to policies that might not represent the choice of a real decision-maker. The GUBS criterion, which combines goal prioritization over histories with Expected Utility Theory to make trade-offs between costs and probability-to-goal, was proposed to address these problems. The eGUBS criterion, which is a particular case of GUBS when an exponential utility function is used, was later proposed, along with eGUBS-VI, a VI-based algorithm that is the first method to optimally solve SSP-MDPs under the GUBS criterion. This dissertation contains a comparison between GUBS and other related criteria for solving SSP-MDPs in the presence of dead-end states, and introduces theoretical definitions and results that show that it is the only criterion between all related criteria that not only allows for a trade-off between a large accumulated cost and a small loss in probability-to-goal, but also guarantees arbitrary trade-offs that can be tuned from its parameters without previous knowledge of the problem being solved. Also, this dissertation introduces eGUBS-AO*, an optimal heuristic search algorithm for solving the eGUBS criterion. Results indicate that, when there is a good heuristic function available or when the state space is too large, eGUBS-AO* can perform better than eGUBS-VI by doing an efficient search. In other cases, eGUBS-VIs simpler approach might have better results.