Motion Planning in Uncertain Environments with Rapidly-Exploring Random Markov Decision Processes

We propose rapidly-exploring random Markov decision processes (RRMDPs), a novel sampling-based motion planning approach for situations where the environment parameters are not fully known a priori, but a prior distribution over such parameters is available. Our algorithm combines ideas from established motion planning algorithms to achieve motion policies that are able to robustly drive the robot to its goal in the presence of uncertain action outcomes. We evaluate RRMDP in two domains, showing that it can synthesise motion policies that are more robust than the motion plans obtained by particle rapidly-exploring random trees (pRRT), a widely used algorithm for motion planning under uncertainty which RRMDP builds upon.