Continuous Real Time Dynamic Programming for Discrete and Continuous State MDPs

Applications of automated planning under uncertainty are often modelled as a discrete and continuous state Markov Decision Process (DC-MDP). Symbolic Dynamic Programming is the existent exact solution for DC-MDPs that uses the eXtended Algebraic Decision Diagrams (XADDs) to symbolically represent the state value function and that computes a complete state-space policy (which is very costly and limits solutions to problems with small size and depth). Real-Time Dynamic Programming (RTDP) is an efficient solution method for discrete state MDPs that provides a partial solution for a known initial state. In this paper we combine the RTDP solution with XADD symbolic representation and computation of the value function to propose the Continuous Real Time Dynamic Programming (CRTDP) algorithm. This novel planner uses heuristic search and symbolic generalisation to efficiently update the value function by regions. We show that using the initial state information greatly reduces the number of regions in the value function, therefore allowing CRTDP to solve DC-MDPs more efficiently than standard symbolic dynamic programming both in time and space required for the solution.