Volumetric Tree * : Adaptive Sparse Graph for Effective Exploration of Homotopy Classes We present volumetric tree*, a hybridization of samplingbased and optimizationbased motion planning. Volumetric tree* constructs an adaptive sparse graph with volumetric vertices, hyperspheres encoding free configurations, using a samplingbased motion planner for a homotopy exploration. The coarsegrained paths computed on the sparse graph are refined by optimizationbased planning during the execution, while exploiting the probabilistic completeness of the sampling based planning for the initial path generation. We also suggest a dropout technique probabilistically ensuring that the sampling based planner is capable of identifying all possible homotopies of solution paths. We compare the proposed algorithm against the stateoftheart planners in both synthetic and practical benchmarks with varying dimensions, and experimentally show the benefit of the proposed algorithm.

Samplingbased motion planning of 3D solid objects guided by multiple approximate solutions Samplingbased motion planners are often used to solve motion planning problems for robots with many degrees of freedom. These planners explore the related configuration space by random sampling. The wellknown issue of the samplingbased planners is the narrow passage problem. Narrow passages are small collisionfree regions in the configuration space that are, due to their volume, difficult to cover by the random samples. The volume of the narrow passages can be artificially increased by reducing the size of the robot, e.g., by scalingdown its geometry, which increases the probability of placing the random samples into the narrow passages. This allows us to find an approximate solution (trajectory) and use it as a guide to find the solution for a larger robot. Guiding along an approximate solution may, however, fail if this solution leads through such parts of the configuration space that are not reachable or traversable by a larger robot. To improve this guiding process, we propose to compute several approximate solutions leading through different parts of the configuration space, and use all of them to guide the search for a larger robot. We introduce the concept of disabled regions that are prohibited from the exploration using the sampling process. The disabled regions are defined using trajectories already found in the space being searched. The proposed method can solve planning problems with narrow passages with higher success rate than other stateoftheart planners.