An optimal complexity algorithm for minimum-time velocity planning

Velocity planning on a path to be followed by a wheeled autonomous vehicle may be difficult when high curvatures and velocities are allowed. A fast, straightforward algorithm to address this problem is presented. It has linear-time computational complexity and provides an optimal minimum-time velocity profile. The algorithm is based on a curvilinear discretization that makes easy to take into account the constraint on the vehicle's maximal normal acceleration. A generalized problem is also addressed with formal results on feasibility, complexity, and solution characterization. Three examples illustrate the proposed approach.