RJ-RRT: Improved RRT for Path Planning in Narrow Passages

摘要

As a representative of sampling-based planning algorithms, rapidly exploring random tree (RRT), is extensively welcomed in solving robot path planning problems due to its wide application range and easy addition of nonholonomic constraints. However, it is still challenging for RRT to plan the path for configuration space with narrow passages. As a variant algorithm of RRT, rapid random discovery vine (RRV) gives a better solution, but when configuration space contains more obstacles instead of narrow passages, RRV performs slightly worse than RRT. In order to solve these problems, this paper re-examines the role of sampling points in RRT. Firstly, according to the state of the random tree expanding towards the current sampling point, a greedy sampling space reduction strategy is proposed, which decreases the redundant expansion of the random tree in space by dynamically changing the sampling space. Secondly, a new narrow passage judgment method is proposed according to the environment around of sampling point. After the narrow passage is identified, the narrow passage is explored by generating multiple subtrees inside the passage. The subtrees can be merged into the main tree that expands in a larger area by subsequent sampling. These improvements further enhance the value of sampling points. Compared with the existing RRT algorithms, the adaptability for different environments is improved, and the planning time and memory usage are saved.