A multi-RRTs framework for robot path planning in high-dimensional configuration space with narrow passages

Abstract

Path planning for robots with many degrees of freedom (dof) receives continuous interest in both robotics and computer graphics communities. A variety of random sampling-based methods have been proposed to solve the path planning problems in high-dimensional configuration space, including Probabilistic Roadmap Method (PRM) and Rapidly-exploring Random Trees (RRTs). However, the efficiency will be dramatically decreased when plenty of narrow passages exist far away from initial and goal configurations. In this paper, a novel Multi-RRTs framework is presented to rapidly capture the connectivity of narrow passages formed by nearby obstacles. The algorithm improves a sampling algorithm called Bridge Test to find global important roadmaps that identify the critical regions, based on which a Multi-RRTs structure is constructed to incrementally explore unknown configuration space. Combined with global heuristics and local connection, the method is shown to be more effective, and experimental results demonstrate the validity of the method.