Very Fast Collision Detection for Practical Motion Planning. Part I: The Spatial Representation.

Abstract

Practical robot motion planning for multiple moving objects in complex scenarios requires very fast collision detection. The efficiency of the algorithms is critically dependent on the representation that is used to model the objects. We present a hierarchical spatial representation based on spheres that is very adequate for speeding up collision detection. The objects can be non-convex and curved and they are not partitioned into convex ones. We present results that show some of its main features: spatial balance, stability and convergence. Comparative results in terms of quality and time are provided.