Collision Checking

Planners check for collisions thousands of times, so collision checking must be fast. The trick is to test simple bounding shapes first, circles or boxes around each object. If even the bounding shapes do not touch, the objects cannot collide, and the slower exact test can be skipped.

Bounding shape for the broad phase Robot rotation Show the bounding shapes

Drag the robot.

Broad phase, then narrow phase

The broad phase tests bounding volumes: two circles overlap when the distance between centers is less than the sum of radii, and two axis-aligned boxes overlap when their ranges overlap on both axes. Only pairs that pass go to the narrow phase, the exact test. For two convex shapes, the separating axis theorem says they are apart exactly when some axis separates their projections:

$$\text{circles: } \lVert \mathbf{c}_1 - \mathbf{c}_2\rVert < r_1 + r_2 \qquad \text{SAT: } \exists\,\mathbf{n}:\ \max_{A}\mathbf{n}^\top\mathbf{p} < \min_{B}\mathbf{n}^\top\mathbf{p}$$

What to notice

Most obstacles are far from the robot, and the broad phase rejects them instantly, so only one or two need an exact test. Bounding circles are the cheapest test, but loose around long shapes, so they pass more pairs on to the narrow phase. Axis-aligned boxes fit better until the robot rotates. Collision libraries such as FCL, used by MoveIt, add trees of bounding volumes so whole groups of objects are skipped at once.