Selective retraction-based RRT planner
for various environments

by Junghwan Lee, OSung Kwon, Liangjun Zhang, Sung-Eui Yoon
IEEE Transaction on Robotics, 2014 (to appear)

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 randomized path planner for rigid robots to efficiently handle various environments that have different characteristics. We first present a bridge line-test that can identify narrow passage regions, and then selectively performs an optimization-based retraction 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. These two line-tests are performed with a small computational overhead. We have tested our method with different benchmarks that have varying amounts of narrow passages. Our method achieves up to several times improvements over prior RRT-based planners and consistently shows the best performance across all the tested benchmarks.


Paper: PDF (929KB)

Earlier version (ICRA 2012): SR-RRT: Selective Retraction-based RRT Planner
Junghwan Lee, OSung Kwon, Liangjun Zhang, and Sung-Eui Yoon
IEEE International Conference on Robotics and Automations (ICRA), 2012

Dept. of Computer Science
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com