Detalhes bibliográficos
Ano de defesa: |
2017 |
Autor(a) principal: |
Simão, Thiago Dias |
Orientador(a): |
Não Informado pela instituição |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Dissertação
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/
|
Resumo: |
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 |