Improving the performance of sampling-based planners by using a symmetry-exploiting gap reduction algorithm

Peng Cheng, Emilio Frazzoli, Steven M Lavalle

Research output: Contribution to journalConference article


Although sampling-based planning algorithms have been extensively used to approximately solve motion planning problems with differential constraints, gaps usually appear in their solution trajectories due to various factors. Higher precision may be requested, but as we show in this paper, this dramatically increases the computational cost. In practice, this could mean that a solution will not be found in a reasonable amount of time. In this paper, we substantially improve the performance of an RRT-based algorithm by planning low precision solutions, and then refining their quality by employing a recent gap reduction technique that exploits group symmetries of the system to avoid costly numerical integrations. This technique also allows PRMs to be extended to problems with differential constraints, even when no high-quality steering method exists.

Original languageEnglish (US)
Pages (from-to)4362-4368
Number of pages7
JournalProceedings - IEEE International Conference on Robotics and Automation
Issue number5
StatePublished - Jul 6 2004


ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Cite this