Why is RRT efficient?

less than 1 minute read


Trajectory optimization is a local method, it only explores the neighborhood of an initial seed, besides, in the direct transcription, we discretize along the trajectory instead of every dimension of the C-space, thus it scales well in high dimensional space. But RRT is a global method, what makes it efficient in exploring a collision-free path in high dimensional space?

  • Voronoi bias, the nodes in the search tree with the largest Voronoi regions tend to be selected for exploration.
  • It does not explicitly construct the C-space. We leave the planing “in the dark”, the only light is provided by a collision detection algorithm.

But how about the cost of searching for the nearest neighbors?

  • RRT*:

  • Informed RRT*:

  • BIT*:


Lindemann, Stephen R., and Steven M. LaValle. “Incrementally reducing dispersion by increasing Voronoi bias in RRTs.” IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004. Vol. 4. IEEE, 2004.

To be continued…