SR-RRT: Selective Retraction-based RRT Planner

by Junghwan Lee, OSung Kwon, Liangjun Zhang, Sung-Eui Yoon
IEEE International Conference on Robotics and Automation (ICRA), 2012

Video (mp4, 4MB)

S-tunnel Benchmark: The leftmost figure shows the S-tunnel benchmark. The right two figures show the average performance of two variations of the S-tunnel benchmark. 0.85 and 1.3 indicate the scaling factor of the cubic robot. 0.85 does not create any narrow passages, while 1.3 creates them.


We present a novel retraction-based planner, selective retraction-based RRT, for efficiently handling a wide variety of environments that have different characteristics. We first present a bridge line-test that can identify regions around narrow passages, and then perform an optimizationbased retraction operation selectively only at those regions. We also propose a non-colliding line-test, a dual operator to the bridge line-test, as a culling method to avoid generating samples near wide-open free spaces and thus to generate more samples around narrow passages. These two tests are performed with a small computational overhead and are integrated with a retraction-based RRT. In order to demonstrate benefits of our method, we have tested our method with different benchmarks that have varying amounts of narrow passages. Our method achieves up to 21 times and 3.5 times performance improvements over a basic RRT and an optimization-based retraction RRT, respectively. Furthermore, our method consistently improves the performances of other tested methods across all the tested benchmarks that have or do not have narrow passages.


Paper: PDF (1.4MB)
Presentation: PDF (0.6MB)
  author    = {Junghwan Lee and
               OSung Kwon and
               Liangjun Zhang and
               Sung-eui Yoon},
  title     = {SR-RRT: Selective retraction-based RRT planner},
  booktitle = {ICRA},
  year      = {2012},
  pages     = {2543-2550},
  ee        = {},
  crossref  = {DBLP:conf/icra/2012},
  bibsource = {DBLP,}
Journal version: T-RO 2014
Earlier version (technical report): SR-RRT: Selective Retraction-based RRT Planner
Junghwan Lee, OSung Kwon, Liangjun Zhang, and Sung-Eui Yoon
KAIST Tech. Report, CS-TR-2011-352
July, 2011

Dept. of Computer Science
291 Daehak-ro, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist at gmail dot com