Sampling-based motion planning of 3D solid objects guided by multiple approximate solutions

Abstract

Sampling-based motion planners are often used to solve motion planning problems for robots with many degrees of freedom. These planners explore the related configuration space by random sampling. The well-known issue of the sampling-based planners is the narrow passage problem. Narrow passages are small collision-free regions in the configuration space that are, due to their volume, difficult to cover by the random samples. The volume of the narrow passages can be artificially increased by reducing the size of the robot, e.g., by scaling-down its geometry, which increases the probability of placing the random samples into the narrow passages. This allows us to find an approximate solution (trajectory) and use it as a guide to find the solution for a larger robot. Guiding along an approximate solution may, however, fail if this solution leads through such parts of the configuration space that are not reachable or traversable by a larger robot. To improve this guiding process, we propose to compute several approximate solutions leading through different parts of the configuration space, and use all of them to guide the search for a larger robot. We introduce the concept of disabled regions that are prohibited from the exploration using the sampling process. The disabled regions are defined using trajectories already found in the space being searched. The proposed method can solve planning problems with narrow passages with higher success rate than other state-of-the-art planners.