Robot path planning using improved rapidly-exploring random tree algorithm

摘要

A rapidly-exploring random tree (RRT) is a data structure and algorithm that is designed for efficiently searching nonconvex high-dimensional spaces. RRT is constructed incrementally in a way that quickly reduces the expected distance of a randomly-chosen point to the tree. RRT is suited for path planning problems that involve obstacles and differential constraints (nonholonomic or kinodynamic). But the robot may collide with the obstacles when the classic RRT algorithm is applied. In this paper, the author proposes an improved RRT algorithm, which is called RRT-Rectangular. RRT-Rectangular is suited for path planning problems on the two-dimensional plane that involve static obstacles. RRT-Rectangular pretreat the map with the rectangular decomposition, and the map is divided into rectangular elements with different sizes. After that, all points that build the planning path are in the center of safe rectangular elements. So the robot moves only in the safe areas. The results of MATLAB simulation show that the length of planning path of RRT-Rectangular is closer to the optimal path than the classic RRT algorithm. Especially, the larger the number of obstacles, the shorter the length of the path planned by the improved RRT algorithm.