Tese

Planejamento probabilístico usando programação dinâmica assíncrona e fatorada (2013)

• Authors:
  • Gamarra Holguin, Mijail
  • Barros, Leliane Nunes de (Orientador)
• Autor USP: HOLGUIN, MIJAIL GAMARRA - IME
• Unidade: IME
• Sigla do Departamento: MAC
• Assunto: INTELIGÊNCIA ARTIFICIAL
• Agências de fomento:
  • Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
• Language: Português
• Abstract: Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado.
• Imprenta:
  • Publisher place: São Paulo
  • Date published: 2013
• Data da defesa: 03.04.2013


---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  GAMARRA HOLGUIN, Mijail. Planejamento probabilístico usando programação dinâmica assíncrona e fatorada. 2013. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2013. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-14042013-131306. Acesso em: 06 nov. 2024.

• APA

  Gamarra Holguin, M. (2013). Planejamento probabilístico usando programação dinâmica assíncrona e fatorada (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-14042013-131306

• NLM

  Gamarra Holguin M. Planejamento probabilístico usando programação dinâmica assíncrona e fatorada [Internet]. 2013 ;[citado 2024 nov. 06 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-14042013-131306

• Vancouver

  Gamarra Holguin M. Planejamento probabilístico usando programação dinâmica assíncrona e fatorada [Internet]. 2013 ;[citado 2024 nov. 06 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-14042013-131306

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

• Stochastic bisimulation for MDPs using reachability analysis