Exportar registro bibliográfico

Planejamento probabilístico com becos sem saída (2017)

  • Authors:
  • Autor USP: SIMÃO, THIAGO DIAS - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Subjects: INTELIGÊNCIA ARTIFICIAL; PROCESSOS ESTOCÁSTICOS; PROCESSOS DE MARKOV
  • Keywords: Becos-sem-saída; Dead-ends; MDP; Planejamento probabilístico; Probabilistic planning; SSP MDP
  • Agências de fomento:
  • Language: Português
  • Abstract: 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 quepodem 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
  • Imprenta:
  • Data da defesa: 06.03.2017
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      SIMÃO, Thiago Dias; BARROS, Leliane Nunes de. Planejamento probabilístico com becos sem saída. 2017.Universidade de São Paulo, São Paulo, 2017. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/ >.
    • APA

      Simão, T. D., & Barros, L. N. de. (2017). Planejamento probabilístico com becos sem saída. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/
    • NLM

      Simão TD, Barros LN de. Planejamento probabilístico com becos sem saída [Internet]. 2017 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/
    • Vancouver

      Simão TD, Barros LN de. Planejamento probabilístico com becos sem saída [Internet]. 2017 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020