Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning With Forward Propagation

Abstract

Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning With Forward Propagation

The Rapidly-exploring Random Tree (RRT) algorithm has been one of the most prevalent and popular motion-planning techniques for two decades now. Surprisingly, in spite of its centrality, there has been an active debate under which conditions RRT is probabilistically complete. We provide two new proofs of probabilistic completeness (PC) of RRT with a reduced set of assumptions. The first one for the purely geometric setting, where we only require that the solution path has a certain clearance from the obstacles. For the kinodynamic case with forward propagation of random controls and duration, we only consider in addition mild Lipschitz-continuity conditions. These proofs fill a gap in the study of RRT itself. They also lay sound foundations for a variety of more recent and alternative sampling-based methods, whose PC property relies on that of RRT.

Links

  • Michal Kleinbort, Kiril Solovey, Zakary Littlefield, Kostas E. Bekris, and Dan Halperin
    Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning With Forward Propagation
    IEEE Robotics and Automation Letters, Volume 4 , Issue 2 , pages pages i–vii, 2019 [link][bibtex]
    arXiv:1809.07051v2 [link][bibtex]
    Corrections to : Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning With Forward Propagation
    IEEE Robotics and Automation Letters, Volume 8 , Issue 2 , pages pages 1149–1150, 2023 [link][bibtex]

Contacts

Dan Halperin
Michal Kleinbort

@article{kslbh-pcrgk-23,
author = {Michal Kleinbort and Kiril Solovey and Zakary Littlefield and Kostas E. Bekris and Dan Halperin},
title = {Corrections to “Probabilistic Completeness of {RRT} for Geometric and Kinodynamic Planning With Forward Propagation”},
journal = {{IEEE} Robotics and Automation Letters},
volume = {8},
number = {2},
pages = {1149–1150},
year = {2023},
doi = {10.1109/LRA.2023.3236496},
}

@article{kslbh-pcrgk-18,
  author       = {Michal Kleinbort and Kiril Solovey and Zakary Littlefield and Kostas E. Bekris and Dan Halperin},
  title        = {Probabilistic completeness of {RRT} for geometric and kinodynamic planning with forward propagation},
  journal      = {CoRR},
  volume       = {abs/1809.07051},
  year         = {2018},
  url          = {http://arxiv.org/abs/1809.07051},
  eprinttype   = {arXiv},
  eprint       = {1809.07051},
  timestamp    = {Fri, 05 Oct 2018 11:34:52 +0200},
  biburl       = {https://dblp.org/rec/journals/corr/abs-1809-07051.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}
@article{kslbh-pcrgk-19,
  author = {Michal Kleinbort and Kiril Solovey and Zakary Littlefield and Kostas E. Bekris and Dan Halperin},
  journal = {IEEE Robotics and Automation Letters}, 
  title = {Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning With Forward Propagation}, 
  year = {2019},
  volume = {4},
  number = {2},
  pages = {i--vii},
  doi = {10.1109/LRA.2018.2888947}
}

Yair Oz - Webcreator

Contact

Skip to content