Abstract | ||
---|---|---|
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 $\gamma \left(\frac{\log n}{n}\right)^{1/d}$ to $\gamma' \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 $\gamma$, $\gamma'$, are constants, and $n$, $d$, are the number of samples and the dimension of the problem, respectively. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1109/ICRA40945.2020.9196553 | ICRA |
DocType | Volume | Issue |
Conference | 2020 | 1 |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kiril Solovey | 1 | 71 | 10.30 |
Lucas Janson | 2 | 61 | 6.20 |
Edward Schmerling | 3 | 63 | 7.01 |
Emilio Frazzoli | 4 | 3286 | 229.95 |
Marco Pavone | 5 | 588 | 74.40 |