Adaptive rapidly-exploring-random-tree-star (Rrt*) -Smart: algorithm characteristics and behavior analysis in complex environments

Abstract

Rapidly Exploring Random Trees (RRT) are regarded as one of the most efficient tools for planning feasible paths for mobile robots in complex obstacle cluttered environments. The recent development of its variant: RRT* is considered as a major breakthrough as it makes it possible to achieve optimality in paths planning. However, its limitations include the infinite time it takes to reach the optimal solution and a very slow rate of convergence. Just recently the authors have introduced RRT*-Smart which is a rapid convergence implementation of RRT* for improved efficient path planning both in terms of planning time as well as path cost. This paper presents a new scheme for RRT*-Smart that helps it to adapt to various types of environments by tuning its parameters during planning based on the information gathered online. The paper also includes detailed explanation of the algorithm’s characteristics and statistical analysis of its behavior in different environment types including mazes, narrow passages and obstacle cluttered environments in comparison with RRT*. Navigation experiments using the real Pioneer 3-AT Mobile Robot provide a proof of the concept.