| We focus on planning paths for rigid objects moving in a static and known three dimensional workspace, as in applications such as virtual prototyping and maintenance studies of CAD models. Several planners have been proposed for solving this version of the path planning problem, including Probabilistic Roadmaps. PRM planners, despite general success, do not fare well in the presence of narrow passages. We enhance the sampling step of PRM planners to find more configurations in narrow passages by incorporating the robot and workspace geometry into the sampling strategy. From the workspace geometry we compute the medial axis, which succinctly encodes the confined regions of the workspace. By approximately fitting distinct points on the robot to the workspace medial axis we are able to find difficult and valuable configurations. Experimental results demonstrate the ability of our planner to more quickly discover crucial configurations, resulting in faster computation of a solution path. |
