  Sampling-based motion planning algorithms are very effective at finding
solutions in high-dimensional continuous state spaces as they do not require
prior approximations of the problem domain compared to traditional discrete
graph-based searches. The anytime version of the Rapidly-exploring Random Trees
(RRT) algorithm, denoted as RRT*, often finds high-quality solutions by
incrementally approximating and searching the problem domain through random
sampling. However, due to its low sampling efficiency and slow convergence
rate, research has proposed many variants of RRT*, incorporating different
heuristics and sampling strategies to overcome the constraints in complex
planning problems. Yet, these approaches address specific convergence aspects
of RRT* limitations, leaving a need for a sampling-based algorithm that can
quickly find better solutions in complex high-dimensional state spaces with a
faster convergence rate for practical motion planning applications. This
article unifies and leverages the greedy search and heuristic techniques used
in various RRT* variants to develop a greedy version of the anytime
Rapidly-exploring Random Trees algorithm, denoted as Greedy RRT* (G-RRT*). It
improves the initial solution-finding time of RRT* by maintaining two trees
rooted at both the start and goal ends, advancing toward each other using
greedy connection heuristics. It also accelerates the convergence rate of RRT*
by introducing a greedy version of direct informed sampling procedure, which
guides the sampling towards the promising region of the problem domain based on
heuristics. We validate our approach on simulated planning problems,
manipulation problems on Barrett WAM Arms, and on a self-reconfigurable robot,
Panthera. Results show that G-RRT* produces asymptotically optimal solution
paths and outperforms state-of-the-art RRT* variants, especially in
high-dimensional planning problems.
