Busca avançada
Ano de início
Entree

Programação dinâmica assíncrona para processos de decisão markovianos com variáveis discretas e contínuas

Processo: 12/10861-0
Linha de fomento:Bolsas no Exterior - Estágio de Pesquisa - Mestrado
Vigência (Início): 13 de agosto de 2012
Vigência (Término): 12 de fevereiro de 2013
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Leliane Nunes de Barros
Beneficiário:Luis Gustavo Rocha Vianna
Supervisor no Exterior: Scott P. Sanner
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Local de pesquisa : National ICT Australia (NICTA), Austrália  
Vinculado à bolsa:11/16962-0 - Programação dinâmica em tempo real e Simulação de Monte Carlo para planejamento probabilístico, BP.MS
Assunto(s):Inteligência artificial   Processos de Markov   Método de Monte Carlo   Programação dinâmica

Resumo

Muitos problemas de planejamento podem ser modelados como um processo de decisão markoviano com variáveis discretas e contínuas (Discrete and Continuous Markov Decision Process - DC-MDP), uma generalização de processos de decisão markovianos (Markov Decision Processes - MDPs). Uma vez que são poucas as soluções encontradas na literatura para DC-MDPs, estamos interessados em propor uma nova solução baseada nas soluções eficientes para MDPs baseadas em simulação, dentre elas: (i) o algoritmo Real Time Dynamic Programming (RTDP), que atualiza o valor dos estados visitados segundo a equação de Bellman garantindo convergência para valores ótimos e (ii) técnicas baseadas em simulação de Monte-Carlo, especialmente o algoritmo Upper Confidence Bounds Applied to Trees (UCT), recentemente proposto para planejamento probabilístico e que obteve um grande sucesso na última competição internacional de planejamento probabilístico. Considerando a eficiência desses algoritmos para MDPs pretendemos propor uma adaptação do RTDP para espaços contínuos. Além disso, pretendemos acelerar as operações de atualização da função valor de estado do RTDP com técnicas de amostragem como as utilizadas pelo UCT. Os algoritmos propostos serão testados em domínios de planejamento benchmark e comparados com soluções existentes. Esse projeto será realizado no NICTA (National ICT Australia) e os algoritmos desenvolvidos serão aplicados a um problema de interesse prático. (AU)