International Conference on Ubiquitous Robots (UR) 2018

Adaptive Lazy Collision Checking for Sampling-based Motion Planning Adaptive Lazy Collision Checking for Optimal Sampling-based Motion Planning

by Donghyuk Kim , Youngsun Kwon and Sung-Eui Yoon

Korea Advanced Institute of Science and Technology (KAIST)

The left image shows an example of connecting x_{rand} to its near neighbor set, X_{near}, which correspond to blue points within the red circle. The dotted lines indicate edges to be checked for collision. The right image shows a subset of X_{free} denoted as a set of light blue circles, each of which is centered at a configuration and radius corresponding to the distance to the closest X_{obs}. A sequence of bars along the edge indicates points to be checked for collision. The red bars indicate actual collisons occured in the example.


Abstract

Lazy collision checking has been proposed to reduce the computational burden of collision checking which is considered as a major computational bottleneck in samplingbased motion planning. Unfortunately, in complex environments with many obstacles, lazy collision checking can cause an excessive amount of optimistic thrashing problems and significantly degrade the performance of the planner. In this paper, we present an adaptive lazy collision checking method to alleviate the optimistic thrashing, thus broaden the applicability. Our method delays collision checking on the regions predicted to be in the configuration free space, while checking early on the other regions to reduce the optimistic thrashing. To identify such regions, we adopt a configuration free space approximation represented by a set of hyperspheres which can be constructed without significant proximity computation. To demonstrate benefits of our approach we have compared against prior methods including RRT*, PRM* and lazy PRM* across benchmarks with varying dimensions. Overall, our method shows meaningful performance improvement up to three times higher in terms of convergence speed over the tested methods. We also discuss properties and theoretical analysis of the proposed algorithm.

Contents

Paper (author preprint / pdf / 2.7MiB)
Source code : Zip file(53.8Kib) / GitHub