Real-Time Symbolic Dynamic Programming for Hybrid MDPs

Autor(es)

Vianna, Luis G. R. ; de Barros, Leliane N. ; Sanner, Scott ; AAAI

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE; v. N/A, p. 7-pg., 2015-01-01.

Resumo

Recent advances in Symbolic Dynamic Programming (SDP) combined with the extended algebraic decision diagram (XADD) have provided exact solutions for expressive subclasses of finite-horizon Hybrid Markov Decision Processes (HMDPs) with mixed continuous and discrete state and action parameters. Unfortunately, SDP suffers from two major drawbacks: (1) it solves for all states and can be intractable for many problems that inherently have large optimal XADD value function representations; and (2) it cannot maintain compact (pruned) XADD representations for domains with nonlinear dynamics and reward due to the need for nonlinear constraint checking. In this work, we simultaneously address both of these problems by introducing real-time SDP (RTSDP). RTSDP addresses (1) by focusing the solution and value representation only on regions reachable from a set of initial states and RTSDP addresses (2) by using visited states as witnesses of reachable regions to assist in pruning irrelevant or unreachable (nonlinear) regions of the value function. To this end, RTSDP enjoys provable convergence over the set of initial states and substantial space and time savings over SDP as we demonstrate in a variety of hybrid domains ranging from inventory to reservoir to traffic control. (AU)

• Processo FAPESP: 11/16962-0 - Programação Dinâmica em Tempo Real e Simulação de Monte Carlo para Planejamento Probabilístico
• Beneficiário: Luis Gustavo Rocha Vianna
• Modalidade de apoio: Bolsas no Brasil - Mestrado