Learning high-dimensional Mixture Models for fast collision detection in Rapidly-Exploring Random Trees

Abstract

This paper presents a new approach for fast collision detection in high dimensional configuration spaces for Rapidly-exploring Random Trees (RRT) motion planning. The proposed method is based upon Gaussian Mixture Models (GMM) that are learned using an incremental Expectation Maximization clustering algorithm trained online using exemplars provided by a slow, conventional kinematic-based collision detection routine. The number of collision checks needed can be drastically reduced using a biased random sampling from the learned GMM distribution, and the learned models are continually refined and improved as the RRT planning algorithm proceeds. Our proposed method is demonstrated on several example applications and experimental results show marked improvement in computational efficiency over previous approaches.