Título: "Discrete and Continuous Markov Decision Process"
Palestrante: Karina Valdivia Delgado (EACH-USP)

Local: Auditorio Giglioli, Bloco A do IME-USP
Data: quinta-feira, 25/08/2011 às 14h


Resumo:  Many real-world decision-theoretic planning problems can be naturally
modeled with discrete and continuous state Markov decision processes
(DC-MDPs). While previous work has addressed automated decision-theoretic
planning for DC-MDPs, optimal solutions have only been defined so far for
limited settings, e.g., DC-MDPs having hyper-rectangular piecewise linear
value functions. In this work, we extend symbolic dynamic programming (SDP)
techniques to provide optimal solutions for a vastly expanded class of
DC-MDPs. To address the inherent combinatorial aspects of SDP, we introduce
the XADD ? a continuous variable extension of the algebraic decision diagram
(ADD) ? that maintains compact representations of the exact value
function. Empirically, we demonstrate an implementation of SDP with XADDs on
various DC-MDPs, showing the first optimal automated solutions to DC-MDPs with
linear and nonlinear piecewise partitioned value functions and showing the
advantages of constraint-based pruning for XADDs.

Todos são benvindos