Reachable Space Characterization of Markov Decision Processes with Time Variability

We propose a solution to a time-varying variant of Markov Decision Processes which can be used to address the decision-theoretic planning problems for autonomous systems operating in unstructured outdoor environments. We explore the time variability property of the planning stochasticity and investigate the state reachability in order to design an efficient method that can well trade-off the solution optimality and time complexity. The reachability space is constructed by analyzing the means and variances of future states' reaching time. We validate our algorithm through extensive simulations using ocean data and the results show that our method has a great performance in terms of both solution quality and computing time.