On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents¶
Authors: Lester E. Dubins
Published: 1957 (Journal Paper)
Source: American Journal of Mathematics
Algorithm: Dubins path
DOI: 10.2307/2372560
Summary¶
Dubins provided analytic formulas for the shortest curve that connects two points in the two-dimensional Euclidean plane (i.e. x-y plane) with a constraint on the curvature of the path and with prescribed initial and terminal tangents to the path, and an assumption that the vehicle traveling the path can only travel forward. Dubins proved using tools from analysis that any such path will consist of maximum curvature and/or straight line segments. In other words, the shortest path will be made by joining circular arcs of maximum curvature and straight lines.
Abstract¶
Let a particle pursue a continuously differentiable path from an initial point u to a terminal point v. Suppose that its speed is unity and suppose that its velocity vectors at u and v are U and V respectively. We are interested in a path of minimal length for the particle. It is easy to see that there exist u, U, v and V for which no path of minimal length exists. We need some further reasonable restriction. At first, it seems natural to require that the path possess a curvature everywhere, and to prescribe that its radius of curvature be everywhere greater than or equal to a fixed number R. But again there exist (u, U, v, V, R) for which no path of minimal length exists (Proposition 14). The difficulty is that we have imposed too severe a restriction. In order to arrive at the correct restriction to impose, we observe that if X is a curve in real n-dimensional Euclidean space, parameterized by arc length, for which X''(s) exists everywhere, then the curvature, || X''(s) ||, is less than or equal to R^{-1} everywhere, if and only if,
(1) || X'(s_1) - X'(s_2) || <= R^{-1} |s_1 - s_2|,
for all s_1 and s_2 in the interval of definition of X. By the average curvature of X in the interval [s_1, s_2] we mean the left side of (1) divided by |s_1 - s_2|. We say that a curve X in real Euclidean n-space parameterized by arc length has average curvature always less than or equal to R^{-1} provided that its first derivative X' exists everywhere and satisfies the Lipschitz condition (1). We inquire, for fixed vectors u, U, v, V in real n-dimensional Euclidean space, E_n, and a fixed positive number R, as to the existence and nature of a path of minimal length among the curves in E_n, of average curvature everywhere less than or equal to R^{-1}. Now we find that paths of minimal length necessarily exist. We call such a path an R-geodesic. The purpose of this paper is to prove Theorem 1, which implies that for n = 2, an R-geodesic is necessarily a continuously differentiable curve which consists of not more than three pieces, each of which is either a straight line segment or an arc of a circle of radius R. Furthermore, the corollary to Theorem 1 implies that three is the least integer for which this is true. The nature of R-geodesics for n >= 3 is open.
Links¶
Tags¶
-
Path generation
-
Dubins
-
Curvature