An Overview of the Class of Rapidly-Exploring Random Trees.

Abstract

In motion planning the objective is to move a robot from one place to another in a possibly constrained environment. There exist exact methods to solve this problem but exact solutions in constrained higher dimensional spaces are in general unfeasible. It has been shown that sampling-based algorithms, such as the Rapidly-Exploring Random Trees (RRT), perform well when solving motion planning problems under certain constraints. A tree is constructed incrementally to search for the goal by taking samples from the state space. The class of RRTs has been shown to be probabilistically complete; it will eventually find a solution as the tree grows. The basic RRT algorithm has been shown to be asymptotically suboptimal, it will almost surely converge to a path of suboptimal cost. RRT* was proposed to overcome this problem and was in turn shown to be asymptotically optimal. Informed RRT* exploited this property by introducing a heuristic that focused the algorithm between the start and the goal. In this paper the theory behind these baseline algorithms, as well as some of their variants, is explained along with their behaviour and properties. Extensive research has been done in the field of RRTs but no updated account exists on the class of RRTs. This paper organises an overarching review of the class of RRTs. Additionally, the three baseline algorithms are compared to each other. From the analysis of this comparison it follows that Informed RRT* converges significantly faster to optimal paths, as opposed to RRT* and RRT. Finally, current issues and assumptions for future research are discussed.