The cost of bounded curvature

Abstract

We study the motion-planning problem for a car-like robot whose turning radius is bounded from below by one and which is allowed to move in the forward direction only (Dubins car). For two robot configurations sigma, sigma', let l (sigma, sigma') be the shortest bounded-curvature path from sigma to sigma'. For d >= 0, let l (d) be the supremum of l(sigma, sigma'), over all pairs (sigma, sigma') that are at Euclidean distance d. We study the function dub(d) = l(d) - d, which expresses the difference between the bounded-curvature path length and the Euclidean distance of its endpoints. We show that dub(d) decreases monotonically from dub(0) = 7 pi/3 to dub(d*) = 2 pi, and is constant for d >= d*. Here d* approximate to 1.5874. We describe pairs of configurations that exhibit the worst-case of dub(d) for every distance d. (C) 2012 Elsevier B.V. All rights reserved.