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
- Este artigo possui versão em acesso aberto
- URL de acesso aberto
- PDF de acesso aberto
- Versão do Documento: Versão publicada (Published version)
-
Status: Artigo publicado em periódico de acesso aberto (Gold Open Access) -
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: 17 mar. 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 mar. 17 ] 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 mar. 17 ] 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).
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
