Analysis of Sampling-Based Planners: RRTs
Continuing from my last blog post, I now want to look at the proof that the famous RRT algorithm (which stands for Rapidly-Exploring Random Tree ) is probabilistically complete (and the resulting bound on sample complexity that proof yields). On a somewhat-related note, I recently put out a preprint of my submission to IROS 2025. It examines sampling-based planning when the configuration space has discrete symmetries (such as those that arise when manipulating a symmetric object), and a key part of the paper is a theoretical analysis that suggests that various sampling-based planning algorithms should improve in performance when leveraging the underlying symmetries. Those analyses were built upon existing bounds (like the ones in this blog post and the previous one), so perhaps that gives a bit of a hint as to why I've been thinking about this stuff! The Rapidly-Exploring Random Tree (RRT) Algorithm Since Steven LaValle introduced the RRT algorithm in 1998, it has become one of t...