IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2019

Volumetric Tree*: Adaptive Sparse Graph for Effective Exploration of Homotopy Classes Volumetric Tree*: Adaptive Sparse Graph for Effective Exploration of Homotopy Classes

by Donghyuk Kim , Mincheul Kang and Sung-Eui Yoon

Korea Advanced Institute of Science and Technology (KAIST)


Abstract

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.


Contents

Paper (author preprint / pdf / 3.76MiB)
Slides (pptx / 90.7MiB)