Parallel collision detection between moving robots for practical motion planning

Abstract

Abstract Motion planning has made few inroads into practical applications in the real world. Practical motion planning involving multiple moving objects with complex geometries requires very fast collision detection. We present an approach to collision detection between moving robots for motion planning. It is based on a spherical hierarchy of detail for nonconvex and curved objects that need not be partitioned into convex ones. We present results that show the stability of the approach regarding the number of polygons used to model the scene. Numerical evidence of the algorithm's efficiency is also shown by several experiments, in which we obtain average intersection detection times of around 1 ms using eight processors for two closely moving robots involving 1900 polygons. © 2001 John Wiley & Sons, Inc.