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 $\sigma ,{\sigma }^{\mathrm{\prime }}$, let $\mathrm{\ell }(\sigma ,{\sigma }^{\mathrm{\prime }})$ be the shortest bounded-curvature path from $\sigma$ to ${\sigma }^{\mathrm{\prime }}$. For $d\ge 0$, let $\mathrm{\ell }(d)$ be the supremum of $\mathrm{\ell }(\sigma ,{\sigma }^{\mathrm{\prime }})$, over all pairs $(\sigma ,{\sigma }^{\mathrm{\prime }})$ that are at Euclidean distance $d$. We study the function $\text{dub}(d)=\mathrm{\ell }(d)-d$, which expresses the difference between the bounded-curvature path length and the Euclidean distance of its endpoints. We show that $\text{dub}(d)$ decreases monotonically from $\text{dub}(0)=7\pi \mathrm{/}3$ to $\text{dub}(\text{ds})=2\pi$, and is constant for $d\ge \text{ds}$. Here $\text{ds}\approx 1.5874$. We describe pairs of configurations that exhibit the worst-case of $\text{dub}(d)$ for every distance $d$.