Korea Advanced Institute of Science and Technology (KAIST)
We present volumetric tree*, a hybridization of
sampling-based and optimization-based motion planning. Volumetric
tree* constructs an adaptive sparse graph with volumetric
vertices, hyper-spheres encoding free configurations, using
a sampling-based motion planner for a homotopy exploration.
The coarse-grained paths computed on the sparse graph are
refined by optimization-based planning during the execution,
while exploiting the probabilistic completeness of the samplingbased
planning for the initial path generation. We also suggest a
dropout technique probabilistically ensuring that the samplingbased
planner is capable of identifying all possible homotopies
of solution paths. We compare the proposed algorithm against
the state-of-the-art planners in both synthetic and practical
benchmarks with varying dimensions, and experimentally show
the benefit of the proposed algorithm.
A heatmap-style visualization of the vertex set V,
constructed by a conventional planner (top, |V| = 14384)
and that of volumetric tree* (bottom, |V| = 540) in the same
time budget. We can observe the volumetric tree* constructs
a sparse graph, while capturing the samples around narrow
passages or boundaries. The vertices close to the obstacles
are encoded red; otherwise blue.