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

Abstract

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
Volume2004
Issue number5
StatePublished - Jul 6 2004

Fingerprint

Sampling
Planning
Motion planning
Refining
Trajectories
Costs

ASJC Scopus subject areas

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

Cite this

Improving the performance of sampling-based planners by using a symmetry-exploiting gap reduction algorithm. / Cheng, Peng; Frazzoli, Emilio; Lavalle, Steven M.

In: Proceedings - IEEE International Conference on Robotics and Automation, Vol. 2004, No. 5, 06.07.2004, p. 4362-4368.

Research output: Contribution to journalConference article

@article{e186d818bdcb4915b3222c480c671e8c,
title = "Improving the performance of sampling-based planners by using a symmetry-exploiting gap reduction algorithm",
abstract = "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.",
author = "Peng Cheng and Emilio Frazzoli and Lavalle, {Steven M}",
year = "2004",
month = "7",
day = "6",
language = "English (US)",
volume = "2004",
pages = "4362--4368",
journal = "Proceedings - IEEE International Conference on Robotics and Automation",
issn = "1050-4729",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "5",

}

TY - JOUR

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

AU - Cheng, Peng

AU - Frazzoli, Emilio

AU - Lavalle, Steven M

PY - 2004/7/6

Y1 - 2004/7/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=3042632353&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3042632353&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:3042632353

VL - 2004

SP - 4362

EP - 4368

JO - Proceedings - IEEE International Conference on Robotics and Automation

JF - Proceedings - IEEE International Conference on Robotics and Automation

SN - 1050-4729

IS - 5

ER -