The Cost of Bounded Curvature

摘要

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 $σ, σ'$, let $\ell(σ, σ')$ be the shortest bounded-curvature path from $σ$ to $σ'$. For $d \geq 0$, let $\ell(d)$ be the supremum of $\ell(σ, σ')$, over all pairs $(σ, σ')$ that are at Euclidean distance $d$. We study the function $\dub(d) = \ell(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π/3$ to $\dub(\ds) = 2π$, and is constant for $d \geq \ds$. Here $\ds \approx 1.5874$. We describe pairs of configurations that exhibit the worst-case of $\dub(d)$ for every distance $d$.