Asymptotic Optimality of Rapidly Exploring Random Tree
Titas Bera1 and Debasish Ghose2 and Suresh Sundaram3
Abstract— In this paper we investigate the asymptotic op-
timality property of a randomized sampling based motion
planner, namely RRT. We prove that a RRT planner is not
an asymptotically optimal motion planner. Our result, while
being consistent with similar results which exist in the literature,
however, brings out an important characteristics of a RRT plan-
ner. We show that the degree distribution of the tree vertices
follows a power law in an asymptotic sense. A simulation result
is presented to support the theoretical claim. Based on these
results we also try to establish a simple necessary condition for
sampling based motion planners to be asymptotically optimal.
I. INTRODUCTION
Several early studies have shown that the basic problem
of robot motion planning is PSPACE-complete [1] and exact
deterministic algorithms show exponential complexity with
the dimension of the configuration space [2]. To avoid such
curse of dimensionality, several sampling based probabilistic
motion planners have been proposed and widely used for
motion planning for robots in high dimensional configu-
ration spaces. Although, such randomized sampling based
algorithms show polynomial complexity, it is well known
that these algorithms can only guarantee completeness in a
probabilistic sense.
Two most extensively used and studied sampling based
approaches are Probabilistic Roadmap Method or PRM, [3],
and Rapidly Exploring Random Tree or RRT, [4]. A very
general characteristics of both these methods are that these
algorithms work in two consecutive phases.
In the first phase, called a processing phase, a graph/tree
structure is created which consist of nodes, representing the
free configurations and edges, representing a planning phase
which should be executed by a local planner. The main
purpose of this local planner is to connect a pair of selected
nodes by means of solving a small scale local planning
problem. At the end of the processing phase, a network of
achievable configurations within the configuration space is
created.
The second phase or a query phase, uses a graph search
algorithm to identify a path between any two nodes corre-
sponding to two given user input configuration. Because of
various types of sampling scheme and local planners, there
*This work was supported byt ST-Engineering under project CRP3-P2P
1Titas Bera is a research fellow in the School of Electrical and
Electronic Engineering, Nanyang Technological University, Singapore
btitas@ntu.edu.sg
2Debasish
Ghose
is
with
the
Faculty
in
the
Department
of
Aerospace
Engineering,
Indian
Institute
of
Science,
India
dghose@aero.iisc.ernet.in
3Suresh Sundaram is with the Faculty in the School of Computer
Science and Engineering, Nanyang Technological University, Singapore
Ssundaram@ntu.edu.sg
exist many variants of these sampling based planners. For
example, EST [6], Lazy-PRM [7], sampling based roadmap
of trees [8], and RRT*[9], to name a few. For necessary
details about these planners, see [11] and for a somewhat
old but excellent survey see [12].
Since its inception, several attempts have been made to
formalize the performance of these algorithms in terms of
various parameters such as properties of the free configura-
tions space, type of sampling sequence, etc. The objective
was to understand the completeness and optimality of the
algorithmic solution to the problem. For example, In [13],
[14] using various combinatorial and measure theoretic ap-
proach, failure probability of s-PRM is analyzed. In [15] it
is shown that the performance of PRM is dependent on the
expansiveness property of the free configuration space. It is
shown that, with an expansive free space, failure probability
to find a path decreases exponentially as number of samples
increases. In [16], a smoothed analysis of PRM is given
which shows how such planners utilizes discrepancies in
input specifications. In [9], the asymptotic optimality of
many such sampling based algorithms analysed and char-
acterized in terms of algorithmic completeness, asymptotic
convergence to optimal solution, and time complexities. This
paper also points out the lack of asymptotic optimality of the
solution returned and consequently proposes new algorithms
which are asymptotically optimal. In [17] the completeness
and optimality properties of various PRM planners are inves-
tigated in the light of different random sampling sequence.
In this paper, we present an analysis of the asymptotic
optimality property of RRT. Note that, in [9], using a series
of complex argument, it is already established that RRT is not
an asymptotically optimal planner. In this work we present
a much simpler proof of the asymptotic sub-optimality
property of RRT. Although our work re-establishes a known
result, it also brings out an important property of such
planners related to the behaviour of asymptotically optimal
sampling based planner, in general. In particular, we focus
on the degree distribution of the RRT node vertices and the
relationship to this with asymptotic optimality property. We
also substantiate the findings with a numerical simulation
presented at the end of the paper. Our work is primarily based
on the analyse of scale free properties of a random network,
more specifically on the power law of the asymptotic degree
distribution of the network. For details of this problem and
definitions, see [18],[19].
This paper is organized as follows. In section II we
define the problem of motion planning and define the notion
of asymptotically optimal motion planning. Following in
section III, we present and discuss the RRT planner in detail.
arXiv:1707.03976v1  [cs.RO]  13 Jul 2017
Section IV contains the main result regarding the asymptotic
optimality of RRT. Section V contains a simulation results
and discussion on the validity of our theoretical claim.
Finally, in VI we conclude and enlists the future work.
II. MOTION PLANNING PROBLEM FORMULATION
The configuration of an autonomous agent, with d degrees
of freedom, can be represented as a point in a d-dimensional
space, called the configuration space C, which is locally
like a d−dimensional Euclidean space Rd. A configuration
q in C is free if the robot placed at q does not collide
with the obstacles in C. Let us augment this definition of
configuration space with its tangent bundle. A tangent bundle
of C is defined as T(C) = ∪q∈CTq(C), where Tq(C) is the
collection of all tangent vectors at q.
The configuration space together with its tangent bundle
is called a state space X, in which a state x ∈X is simply
defined as x = (q, ˙q). Holonomic constraints can be defined
as hi(q,t) = 0. Non-holonomic constraints require the use
of rate variables and or inequalities, that is li(q, ˙q,t) = 0
or li(q, ˙q,t) < 0. Differential constraints can be written in
Lagrangian dynamics as a set of equations of the form
gi(q, ˙q, ¨q,t) = 0, additionally involving acceleration. The use
of state space formulation allows representations of the
dynamic constraints as a set of m equations Gi(x, ˙x) = 0,
m < 2d, where, d is the dimension of the configuration space.
These equations can be rewritten in the form ˙x = f(x,u),
where u ∈U, where U is the set of allowable control inputs to
the system. The equations thus describe the state transitions
resulting from a control input.
To define state space obstacles apart from defining x ∈
Xobs ⇔q ∈Cobs for x = (q,( ˙q)), we need to define the
reachable set from an initial configuration. For the system
defined by the expression ˙x = f(x,u), a state x′ can be
obtained by applying a control input u over time t from
an initial state of x0. The set of all possible x′ is called the
reachable state of x0 for a time t. For each state x, among the
set of reachable states, one can define future collision states
Xfc and free state space Xfree = X \Xfc. Note that, Xfc grows
as the speed of the system increases and may look rather
different from Xobs. This makes finding a valid kinodynamic
trajectory more difficult.
The goal of a motion planner is to find a trajectory x(t) ∈
Xfree from an initial state xinit ∈Xfree to a final state xfinal ∈
Xfree and to find a time parametrized function of control input
u(t) that results in such a trajectory. For convergence issues,
a general goal subset xgoal is assumed, rather than a specific
xfinal. Clearly, xfinal ∈xgoal.
III. RAPIDLY EXPLORING RANDOM TREE
Rapidly Exploring Random Tree (RRT) has been shown
to be very effective in solving robot motion planning prob-
lems in a complex state space with kinodynamic motion
constraints. RRT is introduced in [4],[5] as an efficient
data structure and sampling scheme to quickly search high
dimensional spaces that have algebraic constraints (arising
from the obstacle) and differential constraints (arising from
nonholonomy and system dynamics). The algorithm incre-
mentally builds a tree whose nodes are different states of
the robot/vehicle. These nodes are added randomly to the
tree until one of the node comes close enough to any of
the states in xgoal. Next, that goal state is added to the tree
and a solution trajectory connecting xfinal ∈xgoal and xinit can
be found by backtracking the nodes. The edges of the tree
forms a feasible path or solution trajectory connecting a pair
of initial and final states.
The key idea behind RRT is to bias the tree growth
towards unexplored regions of the state space by random
sampling and extending tree nodes to those regions. The
selection of tree nodes for expansion is heavily dependent
on current spatial distribution of tree nodes within the state
space. Implicitly, the nodes with larger Voronoi cells are
more probable for expansion. This is because the probability
that a node is selected for expansion is directly proportional
to the volume measure of its Voronoi cell. The tree node
extension logic is based on forward simulation of system
dynamics upon random control input. In the following, we
present the basic RRT algorithm. The RRT algorithm consists
of two subroutines, Build-RRT (Algorithm 1) and Extend-
RRT (Algorithm 2).
Algorithm 1: Build-RRT
T ·init(xinit) ▷Initialize tree T;
for i=1,...,K do
xrand ←Random Configuration;
Extend (T,xrand)
end
return T
Algorithm 2: Extend RRT
xnear ←Nearest Neighbor (x,T);
xnew ←New State(xnear,u);
if xnew is Not in Obstacle then
T ·add vertex(xnew);
T ·add edge(xnear,xnew,unew);
if xnew ∈Xgoal then
return Reached;
else
return Continue
end
end
end
The Build-RRT algorithm initially samples a random state
or xrand. In the Extend-RRT function, a nearest node xnear
from the tree to the generated random state xrand is selected
for future expansion. The function New State(xnear,u), does
a forward simulation of system dynamics for ∆t time period
by applying a control input u ∈U, where U is a finite input
set, to the state at xnear. This input can be chosen at random
or can be selected from all possible inputs by choosing one
which yields a new state xnew which is as close as possible
to xrand. The selection of input u can also be based on
minimization of some performance criterion. Further, xnew
is checked for collision and system constraint violation. If
xnew does not collide with any of the state space obstacles
and satisfies all the constraints, then xnew is added to the
tree as a child node of xnear; otherwise it is discarded. If
xnew ∈xgoal, the algorithm stops. This way the vertices or
nodes of the RRT tree eventually forms a large connected
component within Xfree and can come arbitrarily close to
any specified xgoal. Note that, since the algorithm is only
probabilistically complete, the algorithm continues to search
for a solution until it finds a close enough node to xgoal.
Heuristic termination condition can be added to stop the
algorithm after a certain number of iterations.
Before we move on to the asymptotically optimality
analyse of the RRT planner it is worthwhile to look into
a few aspects of the algorithm. For example, although RRT
vertices can come arbitrarily close to any state in xgoal, the
convergence to the solution trajectory may be slow. One
solution may be to sample certain xgoal ∈Xgoal repeatedly
in random sampling stage so that this introduces a biased
sample generation towards Xgoal. In such a way, a quick
convergence towards the solution trajectory can be found,
although it may lead RRT vertices to fall into a trap formed
by certain spatial distribution of state space obstacle.
The choice of step size and ∆t used in forward simulation
of the Extend function is also important. If the obstacles
are located far away and system dynamics is considerably
simple, then a larger step size can be used. In such cases,
instead of attempting to extend xnear by incremental step
size, one can use the Extend function repeatedly until the
extension is no longer possible. That is, a forward simulation
produces states that violate system constraints or collide with
the obstacle. Obviously, the success of this heuristics method
is heavily dependent on the chosen problem. As reported in
[10], this modification works best for holonomic planning.
RRT can be used as a single directional or bidirectional
planner. A single directional RRT planner builds a tree
starting from xinit towards Xgoal. A bidirectional planner
however builds two separate trees. One from xinit to Xgoal,
and the other is from any state x ∈Xgoal to xinit. Once the
distance between a pair of vertices from either tree is within
a certain tolerance bound, the two trees gets connected and
forms a large single connected component. For holonomic
planning, a bidirectional planner is faster than the single
directional planner. This heuristics, however, does not work
for non-holonomic or for differential systems, because of
reachability problem.
Finally, an important subroutine in the RRT algorithm is
the nearest neighbour search. Currently, the basic RRT’s
nearest neighbour search algorithm works based on the
principle of exhaustive search. For a fixed dimension d, if
at any instant the RRT tree contains n vertices, the task
of searching for a true nearest neighbour node from a
given query point has O(n) time complexity. This approach,
although linear with the number of vertices, eventually slows
down (in the sense of computational time) the growth of RRT
as the number of vertices increases. It should be noted that
any approximate nearest neighbour searching degrades the
RRT’s exploration capability. For example, suppose at every
iteration, a random vertex is selected as the nearest neighbour
and RRT is expanded from this vertex. The probability of
selecting any node from the n number of nodes is 1/n.
While for a basic RRT, probability of selecting any node q as
nearest neighbour for some query point, is O(Vor(q)), where
Vor(q) is the associated Voronoi cell of the node q. Since
the node with largest Voronoi area has a higher probability
of selection, the RRT vertices tend to grow to the region of
largest Voronoi regions or, in other words, to the unexplored
regions of state space. Clearly, selecting a random vertex
as nearest neighbour is a compromise with the search of
unexplored areas. However, after a large number of iterations
if O(Vor(q)) ≈1/n then selection of any vertex, as nearest
neighbour, may be effective, specially for holonomic cases.
IV. ASYMPTOTIC OPTIMALITY OF RRT
Sometimes it is necessary to find an optimal solution for
certain motion planning problems. For example, a motion
planning task may contain additional objectives such as
minimization of control effort or determination of a shortest
path to minimize fuel cost. Except for a very simplistic
situation, in general, the search for an optimal solution
is difficult. For example, consider the general problem of
shortest path calculation in 3-dimension among polyhedral
obstacles. There are a number of solutions that exist only for
a restricted class of problems, as can be found in [20]. These
solutions are algorithms with polynomial time complexity,
applicable in an environment which consists of a few convex
polyhedra. In [21] a polynomial time approximate algorithm
is given which finds a sub-optimal path in 3-dimension. In
[22] a 22O(n) complexity algorithm is proposed to construct
the shortest path by reducing the problem to an algebraic
decision problem. The best bound is obtained in [23], which
is 2nO(1).
These results indicate that finding an optimal path in a
very general condition is computationally expensive. Since
sampling based algorithms are used to avoid computational
complexity issues that are present in obstacle avoidance and
motion planning problems, it is natural to investigate the
quality of the path returned by a sampling based motion
planner. In this context, only [9] discusses and show the
asymptotic optimality properties of various sampling based
motion planning algorithms including RRT.
For sampling based motion planning algorithms, optimal-
ity of the solution can only be analysed in an asymptotic
sense. Naturally, a definition of the asymptotic optimality of
the solution is required. We outline the definition according
to [9].
Definition 1: An algorithm is asymptotically optimal if,
for any path planning problem and cost function c that
admits a robustly optimal solution with finite cost c∗,
P({limsup
n→∞
Yn = c∗}) = 1, where Yn is the algorithmic solution
after n iterations.
In the argument presented in [9], first it is defined that the
set of vertices that contains the kth child of the root along
with all its descendants in the tree is called the kth branch of
the tree. Then, it is shown that a necessary condition for
the asymptotic optimality of RRT is that infinitely many
branches of the tree contain vertices outside a small ball
centred at the initial condition. This is captured in the
following lemma.
Lemma 1: Let 0 < R < infy∈Xgoal ||y −xinit||. The event
{limN→∞Yn = c∗} occurs only if the kth branch of the RRT
has vertices outside the R-ball centred at xinit, for infinitely
many k.
We observe that a necessary condition for optimality
should be applicable to all the nodes in the tree and not
just only xinit. Consequently, we hypothesize that for a tree
like planner to return an asymptotically optimal solution it
is a necessary condition to have a mechanism which creates
infinite degree of the tree vertices.
Next, it is shown that the RRT algorithm does not sat-
isfy the condition for asymptotic optimality. In the detailed
analysis, as can be found in [9], the authors note that if
U = {X1,X2,...,Xn} be a set of independently sampled and
uniformly distributed points in the d-dimensional unit cube
[0,1]d, and if Xn+1 is a newly sampled i.i.d. point, then
the probability, that among all points in U the point in Xi
is the one that is closest to Xn+1, is 1/n. An immediate
consequence of this result is that each vertex of the RRT has
unbounded degree almost surely as the number of samples
approaches infinity.
We note that, although in the sample configuration phase
of RRT algorithm, a new sample is chosen according to
a uniform distribution, the selection of a node as nearest
neighbour to this sample also depends on the existing geo-
metric Voronoi partition of all nodes. The node with higher
Voronoi volume will have a higher chance of being selected
as the nearest neighbour. Only when the Voronoi partition
is approximately equal for every node, the selection of the
nearest neighbour will be independent of spatial distribution
of nodes. Secondly, even if the nearest neighbour selection is
according to a uniform distribution, this does not guarantee
that each vertex will have an unbounded degree. We present
a theoretical argument as well as a simulation to support our
claim. Additionally, an extension of this observation leads to
an alternate proof of non-optimality of RRT algorithm in an
asymptotic sense.
Theorem 1: The solution trajectory returned by the RRT
algorithm is not asymptotically optimal.
Proof: Before giving the proof, in the following, some
definitions are presented which was used in the deduction.
Definition 2: Let the state space X be a metric space.
We assume X is path connected. That is, any pair of states
A,B ∈X can be connected by a continuous path ζ ∈X
which is appropriately parametrized. Denote d(x,y) as a
distance metric in X. For simplicity, we consider a holonomic
planning problem.
Definition 3: Let
the
tree
nodes,
defined
as
{x0,x1,...,xi,...}, form an incremental construction of
the RRT tree where indexes are identified with time
instances.
Definition 4: Given a region R and a set of points in
PX ∈R, there exists a unique arrangement of partition of
the region, denoted as Voronoi partitions VPX for each x ∈PX
as the set of points closer to x than any other point y ∈PX.
Note that, for an nth incremental construction, the obtained
RRT vertices are defined as {x0,x1,...,xn}. The Voronoi
volume of xi, Vxi,n is a non increasing function in n. That
is, Vxi,n ≥Vxi,n+1. We emphasize this fact continuing in the
similar way as in [19].
Let xn be a point, uniformly at random, in a convex region
R. Let xc be a point in R considered as the origin. Now, we
can divide R into f(d) number of disjoint cones, defined as
c1,...,cf(d) [26]. Suppose xn falls into some such cone ci.
If y is any other point in ci then let R′ be the set of points
in R which is closer to xn than xc.
Now we can write that R \ R′ contains a segment of ci
which is shrunk by a factor of two in every dimension. So,
in this case,
µ(R\R′) ≥µ(ci)/2d
(1)
where, d is the dimension and µ is the d dimensional
Lebesgue measure. Note that, the probability that xn will
be within any of such cis is equal to the volume ratio of ci
to R. Taking the expectation over all ci,
E(µ(R\R′) =
f(d)
∑
i=1
piµ(ci)/2d
(2)
where, pi is the probability that xn will fall within of the ci.
Since, pi = µ(ci)/µ(R), therefore,
E(µ(R\R′))
≥
f(d)
∑
i=1
µ(ci)2/(2dµ(R))
(3)
=
µ(R)/(2d f(d))
(4)
Naturally,
this
implies
E(µ(R′))
≤
(2d f(d) −
1)(µ(R))/(2d f(d)).
Let, at any instant t0, the Voronoi volume of the ith node
is µ(Vxi,n)0 and γ = (2d f(d)−1)/(2d f(d)). From recursion,
E(µ(Vt0+k
xi,n )) ≤γkµ(V 0
xi,n)
(5)
Now, we try to show an upper bound on the probability
of the event that a RRT vertex increases its degree from k
to k +1 at some instant.
Let the degree of xi be k. Then, in order to have a degree
of k+1 in the next instant of the tree generation, either of the
following event should happen. For any volume vx, either the
Voronoi volume of Vxi,n is more than vx, or the dispersions
created by the other vertices of the tree should have a volume
less than vx. Taking an union bound,
p(deg(xi) ≥k +1) ≤p(µ(Vxi,n)k ≥vx)+ p(µ(Vxj,n) ≤vx)
(6)
∀j ∈{x0,x1,...,xn}, j ̸= i Now, using Markov’s inequality,
we have p(µ(Vxi,n)k ≥vx) ≤E(µ(Vxi,n)k)/vx.
For the other probability we can use again the union bound
over all x0,...,xn and, p(µ(Vx j,n) ≤vx) ≤αnvx, for some
constant α. Therefore,
p(deg(xi) ≥k +1) ≤E(µ(Vxi,n)k)/vx +αnvx
(7)
If, µ(Vxi,n)0 = O(1/n), using (5), vx can be chosen optimally
as vx = γk/2O(1/n). The choice of µ(Vxi,n)0 = O(1/n) is
justified as it is shown in [28]. Then summing over all the
n nodes, the expected number of nodes with degree at least
k + 1 is at most αγk/2O(1). Hence, it is evident that the
degree distribution of the vertices of the RRT tree follows
a power law. This implies that the RRT tree will contain
fewer and fewer vertices with higher and higher degree. In
other words, the chance that nodes will create an infinite
number of branches becomes lesser and lesser as the number
of iterations increases.
However, since for a sampling based planner, the measure
of the event that the planner finds the optimal path within any
finite iteration is zero; hence, there must be a sequence of
paths which converges to the optimum path. For existence of
such a sequence, it is necessary that the vertex degrees should
be infinite, which is in opposition to the present findings.
Hence, an RRT planner with such node degree distribution
cannot be an asymptotically optimal planner.
As a corollary to the above theorem, it can be said that
a sampling based planner for which its degree distribution
follows a power law cannot be a candidate for optimal motion
planning.
In the following section, to further establish Theorem 1,
a numerical simulation is provided which clearly shows that
the cumulative degree distribution follows a power law, if
not exponential.
V. RESULTS AND DISCUSSION
To validate the theoretical claim the following simulation
of an RRT is performed. The system is a simple non-
holonomic car, shown in Figure 1, and defined by the
following equations:
˙x
=
v cosθ
(8)
˙y
=
v sinθ
(9)
˙θ
=
(v/L) tanφ
(10)
where, L is the length between the wheels, v is the velocity
and φ is the steering angle. The position of the car and
its orientation is denoted by a 3-tuple (x,y,θ). The control
variables are velocity v and steering angle. The configuration
space is R2 ×S1. Figure 2 shows the histogram of vertex out
degree of the RRT planner after 5000, 10000, 15000, and
20000 iterations. The vertex out degree is an indication of
how many branches are emitted from a single vertex. Clearly,
the histogram shows that a vertex with very high value of out
degree is less frequent compared to the vertices with lesser
out degree.
The simulation strongly supports the theoretical claim.
Note that this characteristics of RRT vertices are actually
L
θ
φ
x
y
Fig. 1.
A Non-holonomic car
(a)
(b)
(c)
(d)
Fig. 2.
(a) Histogram of RRT vertices out degree after 5000 iterations (b)
after 10000 iterations (c) after 150000 iterations (d) after 20000 iterations.
The abscissa represents node out degree and the ordinate represents the
number of RRT nodes having the same out degree.
independent of system dynamics. This is because the addi-
tional node generation is only dependent on random samples
and nearest neighbour subroutines.
VI. CONCLUSION
In this paper we investigated the asymptotic optimality of
an existing randomized sampling based algorithms, namely
RRT. We showed that the degree distribution in RRT plan-
ner follows a power law. This also implies that the RRT
planner is not an asymptotically optimal planner which is
consistent with existing results. We also present a simulation
which strongly supports the theoretical claim. It would be
interesting to analyse other sampling based algorithms in the
perspective of asymptotic degree distribution.
REFERENCES
[1] Schwartz, J. T. and Sharir, M., “On the piano mover’s problem: II.
General techniques for computing topological properties of algebraic
manifolds,” Communications on pure and Applied mathematics, vol.
36, pp. 345-398, 1983.
[2] Reif, J. H., “Complexity of the mover’s problem and generalization,”
In: Proc. of 20th Annual Symposium on Foundations of Computer
Science, San Juan, Puerto Rico, pp. 421-427, 1979.
[3] Kavraki, L. E., Svestka, P., Latombe, J. C. and Overmars, M. H.,
“Probabilistic roadmap for path planning in high dimensional config-
uration spaces,” IEEE Transaction on Robotics and Automation, vol.
12, no. 4, pp. 566-580, 1996.
[4] Lavalle, S. M., “Rapidly exploring random tree,” Technical Report TR
98 -11, Computer Science Department, Iowa State University, 1998.
[5] S. M. LaValle and J. J. Kuffner. “Randomized kinodynamic planning”.
The International Journal of Robotics Research, 20(5):378?400, 2001
[6] D. Hsu, J.-C. Latombe, and R. Motwani. “Path planning in expansive
configuration spaces,” International Journal of Computational Geom-
etry and Applications, 9(4):495?512, 1999.
[7] Bohlin, Robert, and Lydia E. Kavraki. “Path planning using lazy
PRM.” International Conference on Robotics and Automation, Vol.
1. IEEE, 2000.
[8] Plaku, E., Bekris, K. E., Chen, B. Y., Ladd, A. M., and Kavraki, L. E.
“Sampling-based roadmap of trees for parallel motion planning,IEEE
Transactions on Robotics, 21(4), 597-608.
[9] Karaman, S. and Frazzoli, E., “Sampling-based algorithms for optimal
motion planning,” International Journal of Robotic Research, vol. 30,
no. 7, pp. 846-894, 2011.
[10] S. R. Lindemann and S. M. LaValle. “Current issues in sampling-
based motion planning,” In The Eleventh International Symposium on
Robotics Research, pp. 36?54, Siena, Italy, 2003.
[11] Choset, H. et al., “Principles of robot motion: theory algorithms and
implementations,” MIT Press, Cambridge, Massachusetts, 2005.
[12] Carpin, S., “Randomized motion planning - a tutorial,” International
Journal of Robotics and Automation, vol. 21, no. 3, pp. 184-196, 2006.
[13] Kavraki, L. E., Kolountzakis, M. N. and Latombe, J. C., “Analysis
of probabilistic roadmaps for path planning,” IEEE Transactions on
Robotics and Automation, vol. 14, no. 1, pp. 166-171, 1998
[14] Ladd, A. M. and Kavraki, L. E., “Measure theoretic analysis of
probabilistic path planning,” IEEE Transactions on Robotics, vol. 20,
no. 2, pp. 229-242, 2004.
[15] Hsu, D., Latombe, J. C. and Kurniawati, H., “On the probabilistic
foundations of probabilistic roadmap planning,” In Proc. International
Symposium on Robotics Research, vol. 25, no. 7, pp. 627-643, 2005.
[16] Chaudhuri, S. and Koltun, V., “Smoothed analysis of probabilis-
tic roadmaps,” Computational Geometry: Theory and Applications
archive, vol. 42, no. 8, pp. 731-747, 2009.
[17] Bera, T., Bhat. M. S and Ghose D., “Probabilistic analysis of sampling
based path planning algorithms,” IEEE Multi-Conference on Systems
and Control, Hyderabad, India, 2013
[18] Fabrikant, Alex, Elias Koutsoupias, and Christos H. Papadimitriou.
“Heuristically optimized trade-offs: A new paradigm for power laws
in the Internet.” International Colloquium on Automata, Languages,
and Programming. Springer Berlin Heidelberg, 2002.
[19] Berger, N., Bollobs, B., Borgs, C., Chayes, J., and Riordan, O. “Degree
distribution of the FKP network model”.
International Colloquium
on Automata, Languages, and Programming, (pp. 725-738). Springer
Berlin Heidelberg, 2003
[20] D. M. Mount. “On finding shortest paths on convex polyhedra,”
Technical report, DTIC Document, CS-TR-1495, 1985.
[21] C. H. Papadimitriou.“ An algorithm for shortest-path motion in three
dimensions,” Information Processing Letters, 20(5):259?263, 1985.
[22] A. Sharir and A. Baltsan. “On shortest paths amidst convex polyhedra,”
In Proceedings of the Second Annual Symposium on Computational
Geometry, pages 193-206, Yorktown Heights, NY, USA, 1986.
[23] J. H. Reif and J. A. Storer. “Shortest paths in euclidean space with
polyhedral obstacles,” Technical report, DTIC Document, 1985
[24] Steven M LaValle and James J Kuffner Jr. “Rapidly-exploring random
trees: Progress and prospects. In New Directions in Algorithmic and
Computational Robotics”, pages 293-308, Hannovar, Germany, 2000
[25] Bollobas, B. and Riordan, O., “Percolation,” Cambridge University
Press, 2006.
[26] Yukich, J., “Probability theory of classical euclidean optimization
problem,” Springer, 1998.
[27] Niederreiter, H., “Random Number Generation and Quasi-Monte-
Carlo Methods,” Society for Industrial and Applied Mathematics,
Philadelphia, USA, 1992.
[28] Janson,
Lucas,
Brian
Ichter,
and
Marco
Pavone.“Deterministic
Sampling-Based Motion Planning: Optimality, Complexity, and Per-
formance,” arXiv preprint arXiv:1505.00023 (2015).
Asymptotic Optimality of Rapidly Exploring Random Tree
Titas Bera1 and Debasish Ghose2 and Suresh Sundaram3
Abstract— In this paper we investigate the asymptotic op-
timality property of a randomized sampling based motion
planner, namely RRT. We prove that a RRT planner is not
an asymptotically optimal motion planner. Our result, while
being consistent with similar results which exist in the literature,
however, brings out an important characteristics of a RRT plan-
ner. We show that the degree distribution of the tree vertices
follows a power law in an asymptotic sense. A simulation result
is presented to support the theoretical claim. Based on these
results we also try to establish a simple necessary condition for
sampling based motion planners to be asymptotically optimal.
I. INTRODUCTION
Several early studies have shown that the basic problem
of robot motion planning is PSPACE-complete [1] and exact
deterministic algorithms show exponential complexity with
the dimension of the configuration space [2]. To avoid such
curse of dimensionality, several sampling based probabilistic
motion planners have been proposed and widely used for
motion planning for robots in high dimensional configu-
ration spaces. Although, such randomized sampling based
algorithms show polynomial complexity, it is well known
that these algorithms can only guarantee completeness in a
probabilistic sense.
Two most extensively used and studied sampling based
approaches are Probabilistic Roadmap Method or PRM, [3],
and Rapidly Exploring Random Tree or RRT, [4]. A very
general characteristics of both these methods are that these
algorithms work in two consecutive phases.
In the first phase, called a processing phase, a graph/tree
structure is created which consist of nodes, representing the
free configurations and edges, representing a planning phase
which should be executed by a local planner. The main
purpose of this local planner is to connect a pair of selected
nodes by means of solving a small scale local planning
problem. At the end of the processing phase, a network of
achievable configurations within the configuration space is
created.
The second phase or a query phase, uses a graph search
algorithm to identify a path between any two nodes corre-
sponding to two given user input configuration. Because of
various types of sampling scheme and local planners, there
*This work was supported byt ST-Engineering under project CRP3-P2P
1Titas Bera is a research fellow in the School of Electrical and
Electronic Engineering, Nanyang Technological University, Singapore
btitas@ntu.edu.sg
2Debasish
Ghose
is
with
the
Faculty
in
the
Department
of
Aerospace
Engineering,
Indian
Institute
of
Science,
India
dghose@aero.iisc.ernet.in
3Suresh Sundaram is with the Faculty in the School of Computer
Science and Engineering, Nanyang Technological University, Singapore
Ssundaram@ntu.edu.sg
exist many variants of these sampling based planners. For
example, EST [6], Lazy-PRM [7], sampling based roadmap
of trees [8], and RRT*[9], to name a few. For necessary
details about these planners, see [11] and for a somewhat
old but excellent survey see [12].
Since its inception, several attempts have been made to
formalize the performance of these algorithms in terms of
various parameters such as properties of the free configura-
tions space, type of sampling sequence, etc. The objective
was to understand the completeness and optimality of the
algorithmic solution to the problem. For example, In [13],
[14] using various combinatorial and measure theoretic ap-
proach, failure probability of s-PRM is analyzed. In [15] it
is shown that the performance of PRM is dependent on the
expansiveness property of the free configuration space. It is
shown that, with an expansive free space, failure probability
to find a path decreases exponentially as number of samples
increases. In [16], a smoothed analysis of PRM is given
which shows how such planners utilizes discrepancies in
input specifications. In [9], the asymptotic optimality of
many such sampling based algorithms analysed and char-
acterized in terms of algorithmic completeness, asymptotic
convergence to optimal solution, and time complexities. This
paper also points out the lack of asymptotic optimality of the
solution returned and consequently proposes new algorithms
which are asymptotically optimal. In [17] the completeness
and optimality properties of various PRM planners are inves-
tigated in the light of different random sampling sequence.
In this paper, we present an analysis of the asymptotic
optimality property of RRT. Note that, in [9], using a series
of complex argument, it is already established that RRT is not
an asymptotically optimal planner. In this work we present
a much simpler proof of the asymptotic sub-optimality
property of RRT. Although our work re-establishes a known
result, it also brings out an important property of such
planners related to the behaviour of asymptotically optimal
sampling based planner, in general. In particular, we focus
on the degree distribution of the RRT node vertices and the
relationship to this with asymptotic optimality property. We
also substantiate the findings with a numerical simulation
presented at the end of the paper. Our work is primarily based
on the analyse of scale free properties of a random network,
more specifically on the power law of the asymptotic degree
distribution of the network. For details of this problem and
definitions, see [18],[19].
This paper is organized as follows. In section II we
define the problem of motion planning and define the notion
of asymptotically optimal motion planning. Following in
section III, we present and discuss the RRT planner in detail.
arXiv:1707.03976v1  [cs.RO]  13 Jul 2017
Section IV contains the main result regarding the asymptotic
optimality of RRT. Section V contains a simulation results
and discussion on the validity of our theoretical claim.
Finally, in VI we conclude and enlists the future work.
II. MOTION PLANNING PROBLEM FORMULATION
The configuration of an autonomous agent, with d degrees
of freedom, can be represented as a point in a d-dimensional
space, called the configuration space C, which is locally
like a d−dimensional Euclidean space Rd. A configuration
q in C is free if the robot placed at q does not collide
with the obstacles in C. Let us augment this definition of
configuration space with its tangent bundle. A tangent bundle
of C is defined as T(C) = ∪q∈CTq(C), where Tq(C) is the
collection of all tangent vectors at q.
The configuration space together with its tangent bundle
is called a state space X, in which a state x ∈X is simply
defined as x = (q, ˙q). Holonomic constraints can be defined
as hi(q,t) = 0. Non-holonomic constraints require the use
of rate variables and or inequalities, that is li(q, ˙q,t) = 0
or li(q, ˙q,t) < 0. Differential constraints can be written in
Lagrangian dynamics as a set of equations of the form
gi(q, ˙q, ¨q,t) = 0, additionally involving acceleration. The use
of state space formulation allows representations of the
dynamic constraints as a set of m equations Gi(x, ˙x) = 0,
m < 2d, where, d is the dimension of the configuration space.
These equations can be rewritten in the form ˙x = f(x,u),
where u ∈U, where U is the set of allowable control inputs to
the system. The equations thus describe the state transitions
resulting from a control input.
To define state space obstacles apart from defining x ∈
Xobs ⇔q ∈Cobs for x = (q,( ˙q)), we need to define the
reachable set from an initial configuration. For the system
defined by the expression ˙x = f(x,u), a state x′ can be
obtained by applying a control input u over time t from
an initial state of x0. The set of all possible x′ is called the
reachable state of x0 for a time t. For each state x, among the
set of reachable states, one can define future collision states
Xfc and free state space Xfree = X \Xfc. Note that, Xfc grows
as the speed of the system increases and may look rather
different from Xobs. This makes finding a valid kinodynamic
trajectory more difficult.
The goal of a motion planner is to find a trajectory x(t) ∈
Xfree from an initial state xinit ∈Xfree to a final state xfinal ∈
Xfree and to find a time parametrized function of control input
u(t) that results in such a trajectory. For convergence issues,
a general goal subset xgoal is assumed, rather than a specific
xfinal. Clearly, xfinal ∈xgoal.
III. RAPIDLY EXPLORING RANDOM TREE
Rapidly Exploring Random Tree (RRT) has been shown
to be very effective in solving robot motion planning prob-
lems in a complex state space with kinodynamic motion
constraints. RRT is introduced in [4],[5] as an efficient
data structure and sampling scheme to quickly search high
dimensional spaces that have algebraic constraints (arising
from the obstacle) and differential constraints (arising from
nonholonomy and system dynamics). The algorithm incre-
mentally builds a tree whose nodes are different states of
the robot/vehicle. These nodes are added randomly to the
tree until one of the node comes close enough to any of
the states in xgoal. Next, that goal state is added to the tree
and a solution trajectory connecting xfinal ∈xgoal and xinit can
be found by backtracking the nodes. The edges of the tree
forms a feasible path or solution trajectory connecting a pair
of initial and final states.
The key idea behind RRT is to bias the tree growth
towards unexplored regions of the state space by random
sampling and extending tree nodes to those regions. The
selection of tree nodes for expansion is heavily dependent
on current spatial distribution of tree nodes within the state
space. Implicitly, the nodes with larger Voronoi cells are
more probable for expansion. This is because the probability
that a node is selected for expansion is directly proportional
to the volume measure of its Voronoi cell. The tree node
extension logic is based on forward simulation of system
dynamics upon random control input. In the following, we
present the basic RRT algorithm. The RRT algorithm consists
of two subroutines, Build-RRT (Algorithm 1) and Extend-
RRT (Algorithm 2).
Algorithm 1: Build-RRT
T ·init(xinit) ▷Initialize tree T;
for i=1,...,K do
xrand ←Random Configuration;
Extend (T,xrand)
end
return T
Algorithm 2: Extend RRT
xnear ←Nearest Neighbor (x,T);
xnew ←New State(xnear,u);
if xnew is Not in Obstacle then
T ·add vertex(xnew);
T ·add edge(xnear,xnew,unew);
if xnew ∈Xgoal then
return Reached;
else
return Continue
end
end
end
The Build-RRT algorithm initially samples a random state
or xrand. In the Extend-RRT function, a nearest node xnear
from the tree to the generated random state xrand is selected
for future expansion. The function New State(xnear,u), does
a forward simulation of system dynamics for ∆t time period
by applying a control input u ∈U, where U is a finite input
set, to the state at xnear. This input can be chosen at random
or can be selected from all possible inputs by choosing one
which yields a new state xnew which is as close as possible
to xrand. The selection of input u can also be based on
minimization of some performance criterion. Further, xnew
is checked for collision and system constraint violation. If
xnew does not collide with any of the state space obstacles
and satisfies all the constraints, then xnew is added to the
tree as a child node of xnear; otherwise it is discarded. If
xnew ∈xgoal, the algorithm stops. This way the vertices or
nodes of the RRT tree eventually forms a large connected
component within Xfree and can come arbitrarily close to
any specified xgoal. Note that, since the algorithm is only
probabilistically complete, the algorithm continues to search
for a solution until it finds a close enough node to xgoal.
Heuristic termination condition can be added to stop the
algorithm after a certain number of iterations.
Before we move on to the asymptotically optimality
analyse of the RRT planner it is worthwhile to look into
a few aspects of the algorithm. For example, although RRT
vertices can come arbitrarily close to any state in xgoal, the
convergence to the solution trajectory may be slow. One
solution may be to sample certain xgoal ∈Xgoal repeatedly
in random sampling stage so that this introduces a biased
sample generation towards Xgoal. In such a way, a quick
convergence towards the solution trajectory can be found,
although it may lead RRT vertices to fall into a trap formed
by certain spatial distribution of state space obstacle.
The choice of step size and ∆t used in forward simulation
of the Extend function is also important. If the obstacles
are located far away and system dynamics is considerably
simple, then a larger step size can be used. In such cases,
instead of attempting to extend xnear by incremental step
size, one can use the Extend function repeatedly until the
extension is no longer possible. That is, a forward simulation
produces states that violate system constraints or collide with
the obstacle. Obviously, the success of this heuristics method
is heavily dependent on the chosen problem. As reported in
[10], this modification works best for holonomic planning.
RRT can be used as a single directional or bidirectional
planner. A single directional RRT planner builds a tree
starting from xinit towards Xgoal. A bidirectional planner
however builds two separate trees. One from xinit to Xgoal,
and the other is from any state x ∈Xgoal to xinit. Once the
distance between a pair of vertices from either tree is within
a certain tolerance bound, the two trees gets connected and
forms a large single connected component. For holonomic
planning, a bidirectional planner is faster than the single
directional planner. This heuristics, however, does not work
for non-holonomic or for differential systems, because of
reachability problem.
Finally, an important subroutine in the RRT algorithm is
the nearest neighbour search. Currently, the basic RRT’s
nearest neighbour search algorithm works based on the
principle of exhaustive search. For a fixed dimension d, if
at any instant the RRT tree contains n vertices, the task
of searching for a true nearest neighbour node from a
given query point has O(n) time complexity. This approach,
although linear with the number of vertices, eventually slows
down (in the sense of computational time) the growth of RRT
as the number of vertices increases. It should be noted that
any approximate nearest neighbour searching degrades the
RRT’s exploration capability. For example, suppose at every
iteration, a random vertex is selected as the nearest neighbour
and RRT is expanded from this vertex. The probability of
selecting any node from the n number of nodes is 1/n.
While for a basic RRT, probability of selecting any node q as
nearest neighbour for some query point, is O(Vor(q)), where
Vor(q) is the associated Voronoi cell of the node q. Since
the node with largest Voronoi area has a higher probability
of selection, the RRT vertices tend to grow to the region of
largest Voronoi regions or, in other words, to the unexplored
regions of state space. Clearly, selecting a random vertex
as nearest neighbour is a compromise with the search of
unexplored areas. However, after a large number of iterations
if O(Vor(q)) ≈1/n then selection of any vertex, as nearest
neighbour, may be effective, specially for holonomic cases.
IV. ASYMPTOTIC OPTIMALITY OF RRT
Sometimes it is necessary to find an optimal solution for
certain motion planning problems. For example, a motion
planning task may contain additional objectives such as
minimization of control effort or determination of a shortest
path to minimize fuel cost. Except for a very simplistic
situation, in general, the search for an optimal solution
is difficult. For example, consider the general problem of
shortest path calculation in 3-dimension among polyhedral
obstacles. There are a number of solutions that exist only for
a restricted class of problems, as can be found in [20]. These
solutions are algorithms with polynomial time complexity,
applicable in an environment which consists of a few convex
polyhedra. In [21] a polynomial time approximate algorithm
is given which finds a sub-optimal path in 3-dimension. In
[22] a 22O(n) complexity algorithm is proposed to construct
the shortest path by reducing the problem to an algebraic
decision problem. The best bound is obtained in [23], which
is 2nO(1).
These results indicate that finding an optimal path in a
very general condition is computationally expensive. Since
sampling based algorithms are used to avoid computational
complexity issues that are present in obstacle avoidance and
motion planning problems, it is natural to investigate the
quality of the path returned by a sampling based motion
planner. In this context, only [9] discusses and show the
asymptotic optimality properties of various sampling based
motion planning algorithms including RRT.
For sampling based motion planning algorithms, optimal-
ity of the solution can only be analysed in an asymptotic
sense. Naturally, a definition of the asymptotic optimality of
the solution is required. We outline the definition according
to [9].
Definition 1: An algorithm is asymptotically optimal if,
for any path planning problem and cost function c that
admits a robustly optimal solution with finite cost c∗,
P({limsup
n→∞
Yn = c∗}) = 1, where Yn is the algorithmic solution
after n iterations.
In the argument presented in [9], first it is defined that the
set of vertices that contains the kth child of the root along
with all its descendants in the tree is called the kth branch of
the tree. Then, it is shown that a necessary condition for
the asymptotic optimality of RRT is that infinitely many
branches of the tree contain vertices outside a small ball
centred at the initial condition. This is captured in the
following lemma.
Lemma 1: Let 0 < R < infy∈Xgoal ||y −xinit||. The event
{limN→∞Yn = c∗} occurs only if the kth branch of the RRT
has vertices outside the R-ball centred at xinit, for infinitely
many k.
We observe that a necessary condition for optimality
should be applicable to all the nodes in the tree and not
just only xinit. Consequently, we hypothesize that for a tree
like planner to return an asymptotically optimal solution it
is a necessary condition to have a mechanism which creates
infinite degree of the tree vertices.
Next, it is shown that the RRT algorithm does not sat-
isfy the condition for asymptotic optimality. In the detailed
analysis, as can be found in [9], the authors note that if
U = {X1,X2,...,Xn} be a set of independently sampled and
uniformly distributed points in the d-dimensional unit cube
[0,1]d, and if Xn+1 is a newly sampled i.i.d. point, then
the probability, that among all points in U the point in Xi
is the one that is closest to Xn+1, is 1/n. An immediate
consequence of this result is that each vertex of the RRT has
unbounded degree almost surely as the number of samples
approaches infinity.
We note that, although in the sample configuration phase
of RRT algorithm, a new sample is chosen according to
a uniform distribution, the selection of a node as nearest
neighbour to this sample also depends on the existing geo-
metric Voronoi partition of all nodes. The node with higher
Voronoi volume will have a higher chance of being selected
as the nearest neighbour. Only when the Voronoi partition
is approximately equal for every node, the selection of the
nearest neighbour will be independent of spatial distribution
of nodes. Secondly, even if the nearest neighbour selection is
according to a uniform distribution, this does not guarantee
that each vertex will have an unbounded degree. We present
a theoretical argument as well as a simulation to support our
claim. Additionally, an extension of this observation leads to
an alternate proof of non-optimality of RRT algorithm in an
asymptotic sense.
Theorem 1: The solution trajectory returned by the RRT
algorithm is not asymptotically optimal.
Proof: Before giving the proof, in the following, some
definitions are presented which was used in the deduction.
Definition 2: Let the state space X be a metric space.
We assume X is path connected. That is, any pair of states
A,B ∈X can be connected by a continuous path ζ ∈X
which is appropriately parametrized. Denote d(x,y) as a
distance metric in X. For simplicity, we consider a holonomic
planning problem.
Definition 3: Let
the
tree
nodes,
defined
as
{x0,x1,...,xi,...}, form an incremental construction of
the RRT tree where indexes are identified with time
instances.
Definition 4: Given a region R and a set of points in
PX ∈R, there exists a unique arrangement of partition of
the region, denoted as Voronoi partitions VPX for each x ∈PX
as the set of points closer to x than any other point y ∈PX.
Note that, for an nth incremental construction, the obtained
RRT vertices are defined as {x0,x1,...,xn}. The Voronoi
volume of xi, Vxi,n is a non increasing function in n. That
is, Vxi,n ≥Vxi,n+1. We emphasize this fact continuing in the
similar way as in [19].
Let xn be a point, uniformly at random, in a convex region
R. Let xc be a point in R considered as the origin. Now, we
can divide R into f(d) number of disjoint cones, defined as
c1,...,cf(d) [26]. Suppose xn falls into some such cone ci.
If y is any other point in ci then let R′ be the set of points
in R which is closer to xn than xc.
Now we can write that R \ R′ contains a segment of ci
which is shrunk by a factor of two in every dimension. So,
in this case,
µ(R\R′) ≥µ(ci)/2d
(1)
where, d is the dimension and µ is the d dimensional
Lebesgue measure. Note that, the probability that xn will
be within any of such cis is equal to the volume ratio of ci
to R. Taking the expectation over all ci,
E(µ(R\R′) =
f(d)
∑
i=1
piµ(ci)/2d
(2)
where, pi is the probability that xn will fall within of the ci.
Since, pi = µ(ci)/µ(R), therefore,
E(µ(R\R′))
≥
f(d)
∑
i=1
µ(ci)2/(2dµ(R))
(3)
=
µ(R)/(2d f(d))
(4)
Naturally,
this
implies
E(µ(R′))
≤
(2d f(d) −
1)(µ(R))/(2d f(d)).
Let, at any instant t0, the Voronoi volume of the ith node
is µ(Vxi,n)0 and γ = (2d f(d)−1)/(2d f(d)). From recursion,
E(µ(Vt0+k
xi,n )) ≤γkµ(V 0
xi,n)
(5)
Now, we try to show an upper bound on the probability
of the event that a RRT vertex increases its degree from k
to k +1 at some instant.
Let the degree of xi be k. Then, in order to have a degree
of k+1 in the next instant of the tree generation, either of the
following event should happen. For any volume vx, either the
Voronoi volume of Vxi,n is more than vx, or the dispersions
created by the other vertices of the tree should have a volume
less than vx. Taking an union bound,
p(deg(xi) ≥k +1) ≤p(µ(Vxi,n)k ≥vx)+ p(µ(Vxj,n) ≤vx)
(6)
∀j ∈{x0,x1,...,xn}, j ̸= i Now, using Markov’s inequality,
we have p(µ(Vxi,n)k ≥vx) ≤E(µ(Vxi,n)k)/vx.
For the other probability we can use again the union bound
over all x0,...,xn and, p(µ(Vx j,n) ≤vx) ≤αnvx, for some
constant α. Therefore,
p(deg(xi) ≥k +1) ≤E(µ(Vxi,n)k)/vx +αnvx
(7)
If, µ(Vxi,n)0 = O(1/n), using (5), vx can be chosen optimally
as vx = γk/2O(1/n). The choice of µ(Vxi,n)0 = O(1/n) is
justified as it is shown in [28]. Then summing over all the
n nodes, the expected number of nodes with degree at least
k + 1 is at most αγk/2O(1). Hence, it is evident that the
degree distribution of the vertices of the RRT tree follows
a power law. This implies that the RRT tree will contain
fewer and fewer vertices with higher and higher degree. In
other words, the chance that nodes will create an infinite
number of branches becomes lesser and lesser as the number
of iterations increases.
However, since for a sampling based planner, the measure
of the event that the planner finds the optimal path within any
finite iteration is zero; hence, there must be a sequence of
paths which converges to the optimum path. For existence of
such a sequence, it is necessary that the vertex degrees should
be infinite, which is in opposition to the present findings.
Hence, an RRT planner with such node degree distribution
cannot be an asymptotically optimal planner.
As a corollary to the above theorem, it can be said that
a sampling based planner for which its degree distribution
follows a power law cannot be a candidate for optimal motion
planning.
In the following section, to further establish Theorem 1,
a numerical simulation is provided which clearly shows that
the cumulative degree distribution follows a power law, if
not exponential.
V. RESULTS AND DISCUSSION
To validate the theoretical claim the following simulation
of an RRT is performed. The system is a simple non-
holonomic car, shown in Figure 1, and defined by the
following equations:
˙x
=
v cosθ
(8)
˙y
=
v sinθ
(9)
˙θ
=
(v/L) tanφ
(10)
where, L is the length between the wheels, v is the velocity
and φ is the steering angle. The position of the car and
its orientation is denoted by a 3-tuple (x,y,θ). The control
variables are velocity v and steering angle. The configuration
space is R2 ×S1. Figure 2 shows the histogram of vertex out
degree of the RRT planner after 5000, 10000, 15000, and
20000 iterations. The vertex out degree is an indication of
how many branches are emitted from a single vertex. Clearly,
the histogram shows that a vertex with very high value of out
degree is less frequent compared to the vertices with lesser
out degree.
The simulation strongly supports the theoretical claim.
Note that this characteristics of RRT vertices are actually
L
θ
φ
x
y
Fig. 1.
A Non-holonomic car
(a)
(b)
(c)
(d)
Fig. 2.
(a) Histogram of RRT vertices out degree after 5000 iterations (b)
after 10000 iterations (c) after 150000 iterations (d) after 20000 iterations.
The abscissa represents node out degree and the ordinate represents the
number of RRT nodes having the same out degree.
independent of system dynamics. This is because the addi-
tional node generation is only dependent on random samples
and nearest neighbour subroutines.
VI. CONCLUSION
In this paper we investigated the asymptotic optimality of
an existing randomized sampling based algorithms, namely
RRT. We showed that the degree distribution in RRT plan-
ner follows a power law. This also implies that the RRT
planner is not an asymptotically optimal planner which is
consistent with existing results. We also present a simulation
which strongly supports the theoretical claim. It would be
interesting to analyse other sampling based algorithms in the
perspective of asymptotic degree distribution.
REFERENCES
[1] Schwartz, J. T. and Sharir, M., “On the piano mover’s problem: II.
General techniques for computing topological properties of algebraic
manifolds,” Communications on pure and Applied mathematics, vol.
36, pp. 345-398, 1983.
[2] Reif, J. H., “Complexity of the mover’s problem and generalization,”
In: Proc. of 20th Annual Symposium on Foundations of Computer
Science, San Juan, Puerto Rico, pp. 421-427, 1979.
[3] Kavraki, L. E., Svestka, P., Latombe, J. C. and Overmars, M. H.,
“Probabilistic roadmap for path planning in high dimensional config-
uration spaces,” IEEE Transaction on Robotics and Automation, vol.
12, no. 4, pp. 566-580, 1996.
[4] Lavalle, S. M., “Rapidly exploring random tree,” Technical Report TR
98 -11, Computer Science Department, Iowa State University, 1998.
[5] S. M. LaValle and J. J. Kuffner. “Randomized kinodynamic planning”.
The International Journal of Robotics Research, 20(5):378?400, 2001
[6] D. Hsu, J.-C. Latombe, and R. Motwani. “Path planning in expansive
configuration spaces,” International Journal of Computational Geom-
etry and Applications, 9(4):495?512, 1999.
[7] Bohlin, Robert, and Lydia E. Kavraki. “Path planning using lazy
PRM.” International Conference on Robotics and Automation, Vol.
1. IEEE, 2000.
[8] Plaku, E., Bekris, K. E., Chen, B. Y., Ladd, A. M., and Kavraki, L. E.
“Sampling-based roadmap of trees for parallel motion planning,IEEE
Transactions on Robotics, 21(4), 597-608.
[9] Karaman, S. and Frazzoli, E., “Sampling-based algorithms for optimal
motion planning,” International Journal of Robotic Research, vol. 30,
no. 7, pp. 846-894, 2011.
[10] S. R. Lindemann and S. M. LaValle. “Current issues in sampling-
based motion planning,” In The Eleventh International Symposium on
Robotics Research, pp. 36?54, Siena, Italy, 2003.
[11] Choset, H. et al., “Principles of robot motion: theory algorithms and
implementations,” MIT Press, Cambridge, Massachusetts, 2005.
[12] Carpin, S., “Randomized motion planning - a tutorial,” International
Journal of Robotics and Automation, vol. 21, no. 3, pp. 184-196, 2006.
[13] Kavraki, L. E., Kolountzakis, M. N. and Latombe, J. C., “Analysis
of probabilistic roadmaps for path planning,” IEEE Transactions on
Robotics and Automation, vol. 14, no. 1, pp. 166-171, 1998
[14] Ladd, A. M. and Kavraki, L. E., “Measure theoretic analysis of
probabilistic path planning,” IEEE Transactions on Robotics, vol. 20,
no. 2, pp. 229-242, 2004.
[15] Hsu, D., Latombe, J. C. and Kurniawati, H., “On the probabilistic
foundations of probabilistic roadmap planning,” In Proc. International
Symposium on Robotics Research, vol. 25, no. 7, pp. 627-643, 2005.
[16] Chaudhuri, S. and Koltun, V., “Smoothed analysis of probabilis-
tic roadmaps,” Computational Geometry: Theory and Applications
archive, vol. 42, no. 8, pp. 731-747, 2009.
[17] Bera, T., Bhat. M. S and Ghose D., “Probabilistic analysis of sampling
based path planning algorithms,” IEEE Multi-Conference on Systems
and Control, Hyderabad, India, 2013
[18] Fabrikant, Alex, Elias Koutsoupias, and Christos H. Papadimitriou.
“Heuristically optimized trade-offs: A new paradigm for power laws
in the Internet.” International Colloquium on Automata, Languages,
and Programming. Springer Berlin Heidelberg, 2002.
[19] Berger, N., Bollobs, B., Borgs, C., Chayes, J., and Riordan, O. “Degree
distribution of the FKP network model”.
International Colloquium
on Automata, Languages, and Programming, (pp. 725-738). Springer
Berlin Heidelberg, 2003
[20] D. M. Mount. “On finding shortest paths on convex polyhedra,”
Technical report, DTIC Document, CS-TR-1495, 1985.
[21] C. H. Papadimitriou.“ An algorithm for shortest-path motion in three
dimensions,” Information Processing Letters, 20(5):259?263, 1985.
[22] A. Sharir and A. Baltsan. “On shortest paths amidst convex polyhedra,”
In Proceedings of the Second Annual Symposium on Computational
Geometry, pages 193-206, Yorktown Heights, NY, USA, 1986.
[23] J. H. Reif and J. A. Storer. “Shortest paths in euclidean space with
polyhedral obstacles,” Technical report, DTIC Document, 1985
[24] Steven M LaValle and James J Kuffner Jr. “Rapidly-exploring random
trees: Progress and prospects. In New Directions in Algorithmic and
Computational Robotics”, pages 293-308, Hannovar, Germany, 2000
[25] Bollobas, B. and Riordan, O., “Percolation,” Cambridge University
Press, 2006.
[26] Yukich, J., “Probability theory of classical euclidean optimization
problem,” Springer, 1998.
[27] Niederreiter, H., “Random Number Generation and Quasi-Monte-
Carlo Methods,” Society for Industrial and Applied Mathematics,
Philadelphia, USA, 1992.
[28] Janson,
Lucas,
Brian
Ichter,
and
Marco
Pavone.“Deterministic
Sampling-Based Motion Planning: Optimality, Complexity, and Per-
formance,” arXiv preprint arXiv:1505.00023 (2015).