Using workspace information as a guide to non-uniform sampling in probabilistic roadmap planners

The probabilistic roadmap (PRM) planner is a popular method for robot motion planning problems with many degrees of freedom. However, it has been shown that the method performs less well in situations where the robot has to pass through a narrow passage in the scene. This is mainly due to the uniformity of the sampling used in the planner; it places many samples in large open regions and too few in tight passages. A technique based on a robot independent cell decomposition of the free workspace is proposed to guide the probabilistic sampling, such that the distribution of samples tends more toward the interesting regions in the scene. It is shown that this leads to improved performance on difficult planning problems in 2D and 3D workspaces.

I. Introduction

Motion planning is of great importance in various fields, such as robotics, virtual environments, maintenance planning, and computer-aided design. Although a number of exact and complete methods have been proposed for the robot motion planning problem (see [16] for an overview), these are seldomly used because they are only applicable to the simplest instances of the planning problem. For more complicated problems, where the robot has many degrees of freedom, these methods are computationally infeasible. Therefore, the focus has shifted toward probabilistic and heuristic methods, sacrificing completeness for speed and applicability.