FF-RRT*: a sampling-improved path planning algorithm for mobile robots against concave cavity obstacle

Abstract

Abstract The slow convergence rate and large cost of the initial solution limit the performance of rapidly exploring random tree star (RRT*). To address this issue, this paper proposes a modified RRT* algorithm (defined as FF-RRT*) that creates an optimal initial solution with a fast convergence rate. An improved hybrid sampling method is proposed to speed up the convergence rate by decreasing the iterations and overcoming the application limitation of the original hybrid sampling method towards concave cavity obstacle. The improved hybrid sampling method combines the goal bias sampling strategy and random sampling strategy, which requires a few searching time, resulting in a faster convergence rate than the existing method. Then, a parent node is created for the sampling node to optimize the path. Finally, the performance of FF-RRT* is validated in four simulation environments and compared with the other algorithms. The FF-RRT* shortens 32% of the convergence time in complex maze environment and 25% of the convergence time in simple maze environment compared to F-RRT*. And in a complex maze with a concave cavity obstacle, the average convergence time of Fast-RRT* in this environment is 134% more than the complex maze environment compared to 12% with F-RRT* and 34% with FF-RRT*. The simulation results show that FF-RRT* possesses superior performance compared to the other algorithms, and also fits with a much more complex environment.

Keywords

• Path planning
• Rapidly exploring random tree star (RRT*)
• Sampling-based algorithm
• Optimal path planning