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

• Processo: 12/10861-0
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Mestrado
• Data de Início da vigência: 13 de agosto de 2012
• Data de Término da vigência: 12 de fevereiro de 2013
• Área de 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: 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
• Instituição Anfitriã: 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
• Palavra(s)-Chave do Pesquisador: Automated Planning | Markov Decision Process | Monte Carlo Planning | Real TIme Dynamic Programming | Symbolic Dynamic Programming | Planejamento em Inteligência Artificial

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)