Workspace importance sampling for probabilistic roadmap planning

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but they behave poorly when a robot's configuration space contains narrow passages. This paper presents workspace importance sampling (WIS), a new sampling strategy for PRM planning. Our main idea is to use geometric information from a robot's workspace as "importance" values to guide sampling in the corresponding configuration space. By doing so, WIS increases the sampling density in narrow passages and decreases the sampling density in wide-open regions. We tested the new planner on rigid-body and articulated robots in 2-D and 3-D environments. Experimental results show that WIS improves the planner's performance for path planning problems with narrow passages.

I. Introduction

In recent years, probabilistic roadmap (PRM) planning has emerged as one of the most successful approaches for path planning of robots with many degrees of freedom (dofs) [1], [6], [7], [10], [12], [16], [18], [19] A classic multi-query PRM planner [16] samples points uniformly at random in a robot's configuration space, and connects these points with simple collision-free paths to construct a roadmap graph that approximates the connectivity of a robot's configuration space. The planner then answers path-planning queries by searching the roadmap for a path between query configurations. Due to their efficiency and simplicity, PRM planners have found applications in many areas, such as robotics, computer-aided design, computer graphics, and computational biology (see, e.g., [2], [4], [8], [17]).