Skip to content

The Role of Vertex Consistency in Sampling-based Algorithms for Optimal Motion Planning

Authors: Oktay Arslan, Panagiotis Tsiotras

Published: 2013 (Conference Paper)

Source: IEEE International Conference on Robotics and Automation (ICRA)

Algorithm: RRT#

arXiv: 1204.6453

DOI: 10.1109/ICRA.2013.6630906

Summary

RRT# is based on RRG, just like RRT*, but is aimed at obtaining faster convergence to the optimal cost compared to RRT* by maintaining better estimates of nodal costs. There is also some interesting commentary in Section 5 of the arXiv preprint where the authors discuss the "relevant region" as an elliptic region which could be "used to implement more intelligent sampling strategies"; it would seem this idea was picked up on and formalized by Gammell et al. in the "Informed RRT*" (https://arxiv.org/pdf/1404.2334) paper.

Abstract

Several variants of incremental sampling-based algorithms have been recently proposed in order to optimally solve motion planning problems. Popular examples include the RRT* and the PRM* algorithms. These algorithms are asymptotically optimal and thus provide high quality solutions. However, the convergence rate to the optimal solution may still be slow. Borrowing from ideas used in the well-known LPA* algorithm, in this paper we present a new incremental sampling-based motion planning algorithm based on Rapidly-exploring Random Graphs (RRG), denoted by RRT# (RRT "sharp"), which also guarantees asymptotic optimality, but, in addition, it also ensures that the constructed spanning tree rooted at the initial state contains lowest-cost path information for vertices which have the potential to be part of the optimal solution. This implies that the best possible solution is readily computed if there are some vertices in the current graph that are already in the goal region.

Primary

Paper arxiv.org

Standard

arXiv Abstract 1204.6453 arXiv PDF 1204.6453 arXiv HTML 1204.6453 DOI 10.1109/ICRA.2013.6630906

Alternate

ieeexplore.ieee.org ieeexplore.ieee.org dcsl.gatech.edu PDF dcsl.gatech.edu

Tags

  • Motion planning

  • Optimal motion planning

  • Sampling-based planning

  • Asymptotic optimality

  • RRT#

  • RRT*

  • RRT

  • RRG

  • Graph search

  • Dynamic programming

  • Vertex consistency

  • Consistent tree