Path Smoothing and Shortcutting

Paths from grid and sampling planners zigzag. A robot following them would turn constantly. Two cheap steps fix most of it: shortcutting, which replaces any stretch of the path with a straight line when that line is collision-free, and smoothing, which rounds the remaining corners.

Shortcut attempts Smoothing passes Show the original path

Two steps

Shortcutting: repeatedly pick two random points on the path. If the straight line between them is collision-free, delete everything in between. Smoothing: Chaikin's corner cutting replaces each corner with two points at one quarter and three quarters along its edges, and repeating it converges to a smooth curve:

$$\mathbf{q}_i = \tfrac{3}{4}\mathbf{p}_i + \tfrac{1}{4}\mathbf{p}_{i+1} \qquad \mathbf{r}_i = \tfrac{1}{4}\mathbf{p}_i + \tfrac{3}{4}\mathbf{p}_{i+1}$$

What to notice

Shortcutting removes most of the length and turning in the first few dozen attempts. Smoothing then trades a tiny bit of clearance for gentle curves, so each smoothed path is checked again for collisions. The readout's total turning, the sum of all heading changes, is a good proxy for how hard the path is to follow.