Revisiting the Asymptotic Optimality of RRT$^*$
This work addresses a theoretical flaw in a widely used algorithm for robotics and motion planning, offering a corrected proof that could impact algorithm design and analysis in the field.
The paper identifies a logical gap in the asymptotic optimality proof of RRT*, a foundational sampling-based motion planning algorithm, and provides an alternative rigorous proof that suggests increasing the connection radius parameter to account for time dimension effects.
RRT* is one of the most widely used sampling-based algorithms for asymptotically-optimal motion planning. This algorithm laid the foundations for optimality in motion planning as a whole, and inspired the development of numerous new algorithms in the field, many of which build upon RRT* itself. In this paper, we first identify a logical gap in the optimality proof of RRT*, which was developed in Karaman and Frazzoli (2011). Then, we present an alternative and mathematically-rigorous proof for asymptotic optimality. Our proof suggests that the connection radius used by RRT* should be increased from $γ\left(\frac{\log n}{n}\right)^{1/d}$ to $γ' \left(\frac{\log n}{n}\right)^{1/(d+1)}$ in order to account for the additional dimension of time that dictates the samples' ordering. Here $γ$, $γ'$, are constants, and $n$, $d$, are the number of samples and the dimension of the problem, respectively.