Revisiting the Asymptotic Optimality of RRT*
METADATA ONLY
Loading...
Author / Producer
Date
2020
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
RRT* is one of the most widely used sampling-based algorithms for asymptotically-optimal motion planning. RRT* 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 by 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 γ (log n/n)1/d to γ' (log n/n)1/(d+1) in order to account n n 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.
Permanent link
Publication status
published
Editor
Book title
2020 IEEE International Conference on Robotics and Automation (ICRA)
Journal / series
Volume
Pages / Article No.
2189 - 2195
Publisher
IEEE
Event
International Conference on Robotics and Automation (ICRA 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
09574 - Frazzoli, Emilio / Frazzoli, Emilio
Notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.