Compromissos arbitrários entre custo e probabilidade à meta e algoritmo de busca heurística em planejamento probabilístico sob o critério GUBS (2023)
- Authors:
- Autor USP: CRISPINO, GABRIEL NUNES - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2023.tde-25042023-220822
- Subjects: ALGORITMOS; PROCESSOS DE MARKOV; PROCESSOS ESTOCÁSTICOS
- Keywords: Caminho Estocástico mais Curto; Markov Decision Processes; Planejamento probabilístico; Probabilistic planning; Processos de Decisão Markovianos; Sequential decision making; Stochastic Shortest Path; Tomada de decisão sequencial
- Agências de fomento:
- Language: Português
- Abstract: 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óricosque 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
- Imprenta:
- Data da defesa: 13.02.2023
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
CRISPINO, Gabriel Nunes. Compromissos arbitrários entre custo e probabilidade à meta e algoritmo de busca heurística em planejamento probabilístico sob o critério GUBS. 2023. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2023. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25042023-220822/. Acesso em: 19 abr. 2024. -
APA
Crispino, G. N. (2023). Compromissos arbitrários entre custo e probabilidade à meta e algoritmo de busca heurística em planejamento probabilístico sob o critério GUBS (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25042023-220822/ -
NLM
Crispino GN. Compromissos arbitrários entre custo e probabilidade à meta e algoritmo de busca heurística em planejamento probabilístico sob o critério GUBS [Internet]. 2023 ;[citado 2024 abr. 19 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25042023-220822/ -
Vancouver
Crispino GN. Compromissos arbitrários entre custo e probabilidade à meta e algoritmo de busca heurística em planejamento probabilístico sob o critério GUBS [Internet]. 2023 ;[citado 2024 abr. 19 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25042023-220822/
Informações sobre o DOI: 10.11606/D.45.2023.tde-25042023-220822 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
