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. 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.