Autonomous Robots 2019

Simultaneous Planning of Sampling and Optimization

Simultaneous Planning of Sampling and Optimization

Study on Lazy Evaluation and Configuration Free Space Approximation for Optimal Motion Planning Algorithm

by Donghyuk Kim and Sung-Eui Yoon

Korea Advanced Institute of Science and Technology (KAIST)

The left is a visualization of , regions covered by a set of light blue circles in 2D; for simplicity, we show the merged region of circles, instead of visualizing each circle. Each configuration is associated with an approximate collision-free hypersphere in . Their radii are trimmed by witness (red cross symbol) which is a configuration in found during local planning (dotted black segment on the left side) or a sample qsample (the right side in the same figure). The right figure shows an example of local optimization for a trajectory, . 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 on the discretized .

A sequence of witness propagation for a sample configuration and its near neighbors within the light-blue circle with a radius of . Pairs of configuration and its former witness are connected by red segments, and blue dotted lines indicate witness newly updated. inherits its witness first (left) from its near neighbors. It is then propagated to other neighbors in the circle to ensure that near neighbors have a witness as the closest empirical collision.

These figures show the performance comparison over computation time (left) and the given environment (right). The plots show the performance of asymptotic optimal planners tested in our benchmark. The horizontal black dotted line shows the best solution cost achieved by algorithms without our local trajectory optimization. Figures on the right side are the visualization of benchmarks. Results are averaged over 30 attempts, and RRT* is not reported for (c) and (e) due to a high performance gap. The error bars stand for the variance of solution costs.


  A recent trend in optimal motion planning has broadened the research area toward the hybridization of sampling, optimization, and grid-based approaches.
  A synergy from such integrations can be expected to bring the overall performance improvement, but seamless integration and generalization is still an open problem. In this paper, we suggest a hybrid motion planning algorithm utilizing both sampling and optimization techniques, 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 collisions found during the execution, and decentralizes the information over the constructed graph for an efficient reference.With the help of the learned information, we associate the constructed search graph with the approximate configuration-free space so that our optimization-based local planner exploits the local area to identify the connectivity of free space without depending on the precomputed workspace information.
  To show the novelty of the proposed algorithm, we apply the proposed idea to asymptotic optimal planners with lazy collision checking; lazy PRM* and Batch Informed Tree*, and evaluate them against other state-of-the-arts in both synthetic and practical benchmarks with varying degrees of freedom.We also discuss the performance analysis, properties of different algorithm frameworks of lazy collision checking and our approximation method.


Paper: PDF (2.07MB)

Related links

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