Motion planning of 3D objects using Rapidly Exploring Random Tree guided by approximate solutions

Abstract

Path planning of 3D objects, where the task is to find a collision-free path for a rigid 3D object among obstacles, is studied in this paper. This task has many applications mainly in robotics, but also in other fields, e.g., in computer-aided design and computational biology. Sampling-based approaches like Rapidly Exploring Random Trees (RRT) solve the problem by randomized search in the corresponding configuration space. A well known bottleneck of sampling-based methods is the narrow passage problem. Narrow passages are small regions in the configuration space that are difficult to cover by the random samples, which prevents to find a path leading through them. In this paper, we propose a novel extension to Rapidly Exploring Random Tree (RRT) to cope with the narrow passage problem. The proposed planner first solves a simplified (relaxed) version of the problem which is achieved, e.g., by reducing the geometry of the robot. This approximate solution is then used to guide the search in the configuration space for a less relaxed version of the problem, i.e., for a larger robot. The proposed approach is compared to several state-of-the-art path planners in a set of 3D planning benchmarks. Besides, the method is verified also in the task of computing exit pathways for small molecules (ligand) from a protein.