| dc.description.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. | |
