Planejamento probabilístico como busca num espaço de transição de estados (2013)
- Authors:
- Autor USP: DELGADO, DANIEL JAVIER CASANI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2013.tde-04062013-060258
- Assunto: INTELIGÊNCIA ARTIFICIAL
- Language: Português
- Abstract: Um dos modelos mais usados para descrever problemas de planejamento probabilístico, i.e., planejamento de ações com efeitos probabilísticos, é o processo de decisão markoviano (Markov Decision Process - MDP). Soluções tradicionais são baseadas em programação dinâmica, sendo as mais eficientes aquelas baseadas em programação dinâmica em tempo real (Real-Time Dynamic Programming - RTDP), por explorarem somente os estados alcançáveis a partir de um dado estado inicial. Por outro lado, existem soluções eficientes baseadas em métodos de busca heurística em um grafo AND/OR, sendo que os nós AND representam os efeitos probabilísticos das ações e os nós OR representam as escolhas de ações alternativas. Tais soluções também exploram somente estados alcançáveis porém, guardam um subgrafo solução parcial e usam programação dinâmica para a atualização do custo dos nós da desse subgrafo. No entanto, problemas com grandes espaços de estados limitam o uso prático desses métodos. MDPs fatorados permitem explorar a estrutura do problema, representando MDPs muito grandes compactamente e assim, favorecer a escalabilidade das soluções. Neste trabalho, apresentamos uma análise comparativa das diferentes soluções para MDPs, com ênfase naquelas que fazem busca heurística e comparamos com as soluções baseadas em programação dinâmica assíncrona, consideradas o estado da arte das soluções de MPDs. Além isso, propomos um novo algoritmo de busca fatorado baseado no algoritmo ILAO*, e o testamos nos problemas da competição de planejamento probabilístico IPPC-2011.
- Imprenta:
- Data da defesa: 04.02.2013
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
CASANI DELGADO, Daniel Javier. Planejamento probabilístico como busca num espaço de transição de estados. 2013. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2013. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-04062013-060258. Acesso em: 16 abr. 2026. -
APA
Casani Delgado, D. J. (2013). Planejamento probabilístico como busca num espaço de transição de estados (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-04062013-060258 -
NLM
Casani Delgado DJ. Planejamento probabilístico como busca num espaço de transição de estados [Internet]. 2013 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-04062013-060258 -
Vancouver
Casani Delgado DJ. Planejamento probabilístico como busca num espaço de transição de estados [Internet]. 2013 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-04062013-060258
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
