Vol. 145, No. 2, 1990

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 272: 1
Vol. 271: 1  2
Vol. 270: 1  2
Vol. 269: 1  2
Vol. 268: 1  2
Vol. 267: 1  2
Vol. 266: 1  2
Vol. 265: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Subscriptions
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
Optimal paths for a car that goes both forwards and backwards

James Alexander Reeds, III and Lawrence A. Shepp

Vol. 145 (1990), No. 2, 367–393
DOI: 10.2140/pjm.1990.145.367
Abstract

The path taken by a car with a given minimum turning radius has a lower bound on its radius of curvature at each point, but the path has cusps if the car shifts into or out of reverse gear. What is the shortest such path a car can travel between two points if its starting and ending directions are specified? One need consider only paths with at most 2 cusps or reversals. We give a set of paths which is sufficient in the sense that it always contains a shortest path and small in the sense that there are at most 68, but usually many fewer paths in the set for any pair of endpoints and directions. We give these paths by explicit formula. Calculating the length of each of these paths and selecting the (not necessarily unique) path with smallest length yields a simple algorithm for a shortest path in each case. These optimal paths or geodesics may be described as follows: If C is an arc of a circle of the minimal turning radius and S is a line segment, then it is sufficient to consider only certain paths of the form CCSCC where arcs and segments fit smoothly, one or more of the arcs or segments may vanish, and where reversals, or equivalently cusps, between arcs or segments are allowed. This contrasts with the case when cusps are not allowed, where Dubins (1957) has shown that paths of the form CCC and CSC suffice.

Mathematical Subject Classification 2000
Primary: 49N55
Secondary: 53A04, 70Q05, 93C10
Milestones
Received: 6 September 1988
Published: 1 October 1990
Authors
James Alexander Reeds, III
Lawrence A. Shepp