Generalized sampling based motion planners with application to nonholonomic systems

Abstract

In this paper, generalized versions of the probabilistic sampling based planners, Probabilisitic Road Maps (PRM) and Rapidly exploring Random Tree (RRT), are presented. The generalized planners, Generalized Proababilistic Road Map (GPRM) and the Generalized Rapidly Exploring Random Tree (GRRT), are designed to account for uncertainties in the robot motion model as well as uncertainties in the robot map/ workspace. The proposed planners are analyzed and shown to be probabilistically complete. The algorithms are tested by solving the motion planning problem of a nonholonomic unicycle robot in several maps of varying degrees of difficulty and results show that the generalized methods have excellent performance in such situations.