5.5 Rapidly Exploring Dense Trees

This section introduces an incremental sampling and searching approach
that yields good performance in practice without any parameter
tuning.^{5.14}The idea is to incrementally construct a search tree that gradually
improves the resolution but does not need to explicitly set any
resolution parameters. In the limit, the tree densely covers the
space. Thus, it has properties similar to space filling curves
[842], but instead of one long path, there are shorter paths
that are organized into a tree. A dense sequence of samples is used
as a guide in the incremental construction of the tree. If this
sequence is random, the resulting tree is called a *rapidly
exploring random tree (RRT)*. In
general, this family of trees, whether the sequence is random or
deterministic, will be referred to as *rapidly exploring dense
trees (RDTs)* to indicate that a
dense covering of the space is obtained. This method was originally
developed for motion planning under differential constraints
[608,611]; that case is covered in Section
14.4.3.