• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2020.tde-30062021-195910
Documento
Autor
Nome completo
Milton Raúl Condori Fernández
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2020
Orientador
Banca examinadora
Barros, Leliane Nunes de (Presidente)
Silva, Valdinei Freire da
Trevizan, Felipe Werndl
Título em inglês
Heuristics based on projection occupation measures for probabilistic planning with dead-ends and risk
Palavras-chave em inglês
Planning as heuristic search
Probabilistic planning
Risk sensitive SSP
SSP as dual linear program
Resumo em inglês
In probabilistic planning an agent interacts with an environment and the objective is to find an optimal policy (state-action mapping) that allows the agent to achieve a goal state from an initial state, while minimizing the expected accumulated cost. Efficient solutions for large instances of probabilistic planning are, in general, based on Stochastic Shortest Path (ssp) problems, and use heuristic search techniques. However, these approaches have two limitations: (1) they can not guarantee to return optimal policies in the presence of dead-ends (states from which it is not possible to reach the goal) and (2) they may present a high variance in terms of cost. In instances where unavoidable dead-ends exist, we can plan in two phases: maximizing the probability to reach the goal (maxprob) and then minimizing the expected cost (mincost); or yet, we can define a penalty for reaching a dead-end state and only minimize the expected cost (mincost-with-penalty). While there exist several heuristics to solve the mincost problem, there are no efficient heuristics to solve maxprobproblem. A recent work proposed the first heuristic that takes into account the probabilities, called hpom, which solves a relaxed version of an ssp as a linear program in the dual space. In this work we propose two new heuristics based on hpom to solve probabilistic planning problems with unavoidable dead-ends, that includes new variables and constraints for dead-end states. The first, h_p_pom(s), estimates the maximum probability to reach the goal from s, and is used to efficiently solve maxprob problems by ignoring action costs and considering only the probabilities. The second, used to solve mincost-with-penalty problems, called h_pe_pom(s), estimates the minimal cost to reach the goal from state s and adds an expected penalty for reaching dead-ends. In order to deal with the second limitation of traditional ssp solutions, we propose a third heuristic, called h_rs_pom, also based on hpom, for a modified version of an ssp, called risk sensitive ssp (rs-ssp), whose optimization criterion is to minimize an exponential utility function including a risk factor to characterize the agent attitude as: (i) risk-averse ( > 0); (ii) risk-prone ( < 0); or (iii) risk-neutral ( 0). Empirical results show that the proposed heuristics can solve larger planning instances when compared to the state-of-the-art solutions for ssps with dead-ends and rs-ssp problems.
Título em português
Heurísticas baseadas na projeção de medidas de ocupação para planejamento probabilístico
Palavras-chave em português
Heurística
Planejamento probabilístico
Resumo em português
não disponível
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Thesis__Milton.pdf (2.54 Mbytes)
Data de Publicação
2021-09-03
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.