IEEE International Conference on Robotics and Automation (ICRA) 2018

Dancing PRM* : Simultaneous Planning of Sampling and Optimization with Configuration Free Space Approximation Dancing PRM* : Simultaneous Planning of Sampling and Optimization with Configuration Free Space Approximation

by Donghyuk Kim , Youngsun Kwon and Sung-Eui Yoon

Korea Advanced Institute of Science and Technology (KAIST)


Abstract

A recent trend in optimal motion planning has broadened the research area toward the hybridization of sampling, optimization and grid-based approaches. We can expect that synergy from such integrations leads to overall performance improvement, but seamless integration and generalization is still an open problem. In this paper, we suggest a hybrid motion planning algorithm utilizing a samplingbased and optimization-based planner while simultaneously approximating a configuration free space. Unlike conventional optimization-based approaches, the proposed algorithm does not depend on a priori information or resolution-complete factors, e.g., a distance field. Ours instead learns spatial information on the fly by exploiting empirical information during the execution, and decentralizes the information over the constructed graph for efficient access. With the help of the learned information, our optimization-based local planner exploits the local area to identify the connectivity of configuration free space without depending on the precomputed domain knowledge. To show the novelty of proposed algorithm, we evaluate it against other asymptotic optimal planners in both synthetic and complex benchmarks with varying degrees of freedom. We also discuss the performance improvement, properties and limitations we have observed.

The left is a visualization of our approximate configuration free space covered by a set of merged light blue circles in 2D. Each configuration in the search graph is associated with an approximate collision-free hypersphere. Their radii are trimmed by witness (red cross symbol) which is a configuration in the configuration obstacle space found during a local planning (dotted black segment on the left side) or a sample q_{rand} (right side). The right shows an example of local optimization for the trajectory {xi}. Black arrows show the gradient of obstacle potential computed with our approximate configuration space and the red curved segment shows an optimized trajectory. Each red dot indicates an intermediate configuration {xi}(t) of the discretized trajectory.


Contents

Paper (author preprint / pdf / 1.7MiB)
Source code (zip / 3.4MiB) or GitHub
Spotlight slides (pptx / 36MiB)