1990/10/01 by James Reeds, James A. Reeds, Lawrence A. Shepp +1 · 1,431 citations
Computer Science · Engineering · Mathematics · Medicine · #Calculus (dental) #Computational Geometry and Mesh Generation #Control and Dynamics of Mobile Robots #Mathematical economics #Mathematics #Medicine #Robotic Path Planning Algorithms
paper · pdf · doi:10.2140/pjm.1990.145.367
published in Pacific Journal of Mathematics 145(2), 367-393 (Mathematical Sciences Publishers)
crossref issued 1990/10/01 · crossref published 1990/10/01 · crossref published-print 1990/10/01 · openalex publication_date 1990/10/01 · crossref created 2012/12/08 · crossref deposited 2017/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29 · crossref indexed 2026/07/31
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 geodesies 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.