Motion Planning under Uncertainty in Graduated Fidelity Lattices

We present a new approach to motion planning in mobile robotics under sensing and motion uncertainty based on state lattices with graduated fidelity. Uncertainty is predicted at planning time and used to estimate the safety of the paths. Our approach takes into account the real shape of the robot, introducing a deterministic sampling based method to estimate the probability of collision. Anytime Dynamic A*, an informed search algorithm, is used to find safe and optimal paths in the lattice. Moreover, due to the anytime search capabilities of this algorithm our planner is able to retrieve a solution very fast and refine it iteratively until the optimal one is found. We present a novel graduated fidelity approach to build a lattice whose complexity adapts to the obstacles in the environment, along with a multi-resolution heuristic based on the same idea. Thus, the running time of the planner is drastically reduced while maintaining its performance. Experimental results show the potential of the approach in several scenarios, with different robot shapes, motion models and under different uncertainty conditions. The impact of the graduated fidelity approach and the multi-resolution heuristic in the efficiency and performance of the planner is also detailed.

keywords: state lattices, graduated fidelity, multi-resolution, motion planning under uncertainty