skip to main content
Idioma:

Planejamento probabilístico com becos sem saída

Simão, Thiago Dias

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2017-03-06

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Planejamento probabilístico com becos sem saída
  • Autor: Simão, Thiago Dias
  • Orientador: Barros, Leliane Nunes de
  • Assuntos: Becos-Sem-Saída; Mdp; Planejamento Probabilístico; Ssp Mdp; Dead-Ends; Probabilistic Planning
  • Notas: Dissertação (Mestrado)
  • Descrição: 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
  • DOI: 10.11606/D.45.2017.tde-04072017-095306
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2017-03-06
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Resultado  1

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.