An improved RRT algorithm incorporating obstacle boundary information
Jiankun Wang, Xintong Li, Max Q.‐H. Meng · 2016
Rapidly-Exploring Random Trees (RRT) is a sampling-based path planning method, which aims at finding the feasible path using a randomized data structure. But RRT usually can not find the optimal path. Although RRT* is an asymptotically optimal algorithm, its planning time scales poorly. In this paper, we propose an improved RRT algorithm incorporating obstacle boundary information to deal with these two problems. We classify obstacles in the environment into valuable and valueless obstacles. For the obstacle placed between the start and goal positions, it is regarded as valuable and we use its boundary information to make the path planner sample points around it to avoid other bad sampling points. Then the random tree will grow more intentionally to the goal position. By applying Partially Observed Markov Decision Process (POMDP) in our algorithm, we also can prove in theory that obstacle boundary information really improves RRT algorithm. In our experiments, we show that our algorithm can find a better feasible path faster than RRT.