Title :
Improving the performance of sampling-based planners by using a symmetry-exploiting gap reduction algorithm
Author :
Cheng, Peng ; Frazzoli, Emilio ; LaValle, Steven M.
Author_Institution :
Illinois Univ., Urbana, IL, USA
fDate :
26 April-1 May 2004
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 would 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 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.
Keywords :
path planning; robot dynamics; sampling methods; symmetry; computational cost; motion planning; rapidly exploring random tree; sampling based planner; symmetry exploiting gap reduction algorithm; Computational efficiency; Control systems; History; Instruction sets; Motion planning; Open loop systems; Orbital robotics; Space vehicles; Trajectory; Urban planning;
Conference_Titel :
Robotics and Automation, 2004. Proceedings. ICRA '04. 2004 IEEE International Conference on
Print_ISBN :
0-7803-8232-3
DOI :
10.1109/ROBOT.2004.1302404