Shortest paths for autonomous vehicles
Gordon Wilfong · 2003
Paths that stay on a given network of line segments except to turn onto one segment from another by following a circular arc are studied. The problem of finding a shortest-length collision-free path of this form for an autonomous vehicle with a bound on its steering angle is considered. A polynomial-time algorithm to modify a given feasible path into a shortest-length path traversing the same sequence of lanes is given. However, if the sequence of lanes to be traversed is not fixed, then the general problem of finding a shortest-length path of the restricted form is shown to be NP-complete.>