Very fast collision detection for practical motion planning. II. The parallel algorithm

Abstract

Practical robot motion planning for multiple moving objects in large complex scenarios requires very fast collision detection. We present an efficient algorithm for collision detection between multiple moving objects intended to be used for robot motion planning. It is based on our spherical representation for non-convex and curved object that are not partitioned into convex ones. We present results that show the stability of the approach with respect to the number of polygons used to model the scene. Numerical evidence of the efficiency of the algorithm is also shown by several experiments, in which we obtain average intersection detection times of around one millisecond using 8 or 11 processors for two closely moving robots involving 1,900 polygons.