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

Michal Kleinbort, Kiril Solovey, Zakary Littlefield, Kostas E. Bekris, Dan Halperin

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number8584061
Pages (from-to)277-283
Number of pages7
JournalIEEE Robotics and Automation Letters
Volume4
Issue number2
DOIs
StatePublished - Apr 2019

All Science Journal Classification (ASJC) codes

  • Mechanical Engineering
  • Control and Optimization
  • Artificial Intelligence
  • Human-Computer Interaction
  • Control and Systems Engineering
  • Computer Vision and Pattern Recognition
  • Biomedical Engineering
  • Computer Science Applications

Keywords

  • Motion and path planning
  • nonholonomic motion planning

Fingerprint Dive into the research topics of 'Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward Propagation'. Together they form a unique fingerprint.

Cite this