Abstract:

This article describes practical collision detection algorithms for robot motion planning. Attention is restricted to algorithms that handle rigid, polyhedral geometries. Both broad phase and narrow phase detection strategies are discussed. For the broad phase, an algorithm using axes-aligned bounding boxes and a hierarchical spatial hash table is described. For the narrow-phase, the Lin-Canny algorithm is presented. Alternatives to these algorithms are also discussed. Finally, the article describes a scheduling paradigm for managing collision checks that can further reduce computation time. Pointers to downloadable software are included.