Obstacle Induced Stochastic Tree for Fast Path Planning

摘要

Rapidly-Exploring Random Tree (RRT) has been extensively applied to robot navigation field as a fast and effective path planning method. Rapidly-Exploring Random Tree Star (RRT*), one of the extensions of RRT, outperforms other methods because it can approach the optimal path with the number of iterations increases. Nonetheless, as the number of sampling points increases, it takes too long to get an optimal path and the convergence speed slows dramatically for RRT and all its variants, since the range of sampling is the entire configuration space. In this paper, we propose a novel method of robot path planning in the global knowledge scenario: obstacle induced stochastic tree algorithm. This algorithm regards the center point in obstacles as the sampling point, which significantly reduces the sampling range then shorts the time for path planning. Simulation results demonstrate that our algorithm can find a feasible path at a rapid rate. Compared with RRT and its variants algorithms, the algorithm has better performance in both time and path cost.