Revisiting the Asymptotic Optimality of RRT$^*$
| Autor: | Marco Pavone, Emilio Frazzoli, Edward Schmerling, Lucas Janson, Kiril Solovey |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
0209 industrial biotechnology 02 engineering and technology Binary logarithm Combinatorics Computer Science::Robotics Computer Science - Robotics 020901 industrial engineering & automation Optimization and Control (math.OC) 0202 electrical engineering electronic engineering information engineering FOS: Mathematics 020201 artificial intelligence & image processing Mathematics - Optimization and Control Robotics (cs.RO) Mathematics |
| Zdroj: | ICRA |
| DOI: | 10.48550/arxiv.1909.09688 |
| Popis: | 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. Comment: To appear in ICRA2020. This version includes a detailed counterexample that is not present in the conference version |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|