Random particles boosted RRT for complicated 3D environments with narrow passages
Chengzhi Luan, Zheng Fang · 2016
This paper proposes a fast path planning algorithm for complex 3D environments with many narrow passages, which is named Random Particles Boosted Rapidly-Exploring Random Tree(RP-RRT). This method is an improvement of the basic Rapidly-Exploring Random Tree (RRT) algorithm, which is composed of preprocessing, random tree growth, collision checking and optimization. For preprocessing, random particles are uniformly distributed in the whole 3D collision-free space. Then, there are two phases in random tree growth. In the first phase, the generated particles are used to guide a random tree to grow out of the narrow passages within a few iterations. In the second phase, the basic RRT algorithm is used to extend that random tree to find the mission goal in 3D space. Simplified collision checking and optimization methods are used to reduce the consumption of computation resources. To demonstrate its efficiency and robustness, the proposed method is examined and compared with basic RRT algorithm in various practical complex 3D environments with narrow passages.