Compromissos arbitrários entre custo e probabilidade à meta e algoritmo de busca heurística em planejamento probabilístico sob o critério GUBS
Resumo
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), esse critério pode deixar de ser bem-definido. GUBS, um critério baseado em Teoria da Utilidade Esperada que realiza compromissos entre custos e probabilidade à meta, foi proposto para resolver esses problemas. A dissertação de mestrado tem como contribuições uma comparação entre o 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, ao contrário desses outros critérios, possibilita a realização de compromissos entre custos acumulados sobre perdas em probabilidade à meta, e 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, o presente trabalho introduz o eGUBS-AO*, um algoritmo ótimo de busca heurística para resolver o critério eGUBS. Como subprodutos da dissertação de mestrado, também foram propostos o α-MCMP, um novo critério, e o UCT-GUBS, um algoritmo de Monte Carlo Tree Search para resolver SSPs sob o critério GUBS.
Referências
Bertsekas, D. (1995). Dynamic Programming and Optimal Control. Athena Scientific, Belmont, Mass.
Crispino, G., Freire, V., and Delgado, K. V. (2020). Algoritmo de Monte Carlo Tree Search para SSPs sob o critério GUBS. In Anais do XVII Encontro Nacional de Inteligência Artificial e Computacional, pages 402–413, Porto Alegre, RS, Brasil. SBC.
Crispino, G. N., Freire, V., and Delgado, K. V. (2023). α-MCMP: Trade-offs between probability and cost in SSPs with the MCMP criterion. In Brazilian Conference on Intelligent Systems, pages 112–127. Springer.
Freire, V. and Delgado, K. V. (2017). GUBS: a utility-based semantic for goal-directed Markov decision processes. In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, pages 741–749.
Freire, V., Delgado, K. V., and Reis, W. A. S. (2019). An exact algorithm to make a trade-off between cost and probability in SSPs. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, pages 146–154.
Kolobov, A., Weld, D., et al. (2012). A theory of goal-oriented MDPs with dead ends. In Uncertainty in artificial intelligence : proceedings of the Twenty-eighth Conference [on uncertainty in artificial intelligence] (2012), pages 438–447.
Kolobov, A., Weld, D. S., and Geffner, H. (2011). Heuristic search for generalized stochastic shortest path MDPs. In Proceedings of the Twenty-First International Conference on International Conference on Automated Planning and Scheduling, pages 130–137.
Little, I., Thiebaux, S., et al. (2007). Probabilistic planning vs. replanning. In ICAPS Workshop on IPC: Past, Present and Future, pages 1–10.
Patek, S. D. (2001). On terminating Markov decision processes with a risk-averse objective function. Automatica, 37(9):1379–1386.
Sanner, S. and Yoon, S. (2011). IPPC results presentation. In International Conference on Automated Planning and Scheduling. Acessado em março de 2024.
Teichteil-Königsbuch, F. (2012). Stochastic safest and shortest path problems. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pages 1825–1831.
Teichteil-Königsbuch, F., Vidal, V., and Infantes, G. (2011). Extending classical planning heuristics to probabilistic planning with dead-ends. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, pages 1017–1022.
Trevizan, F. W., Teichteil-Königsbuch, F., and Thiébaux, S. (2017). Efficient solutions for stochastic shortest path problems with dead ends. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence (UAI) (2017), pages 1–10.
