Optimal Sequential Decision-making in Continuous State Processes
Scott Sanner (NICTA)
NICTA SML SEMINARDATE: 2011-10-13
TIME: 11:00:00 - 12:00:00
LOCATION: NICTA - 7 London Circuit
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Many real-world decision-theoretic planning problems can be naturally modelled 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" a continuous variable extension of the algebraic decision diagram (ADD) a" 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.
