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.