The Complexity of the Two Dimensional Curvature-Constrained Shortest-Path Problem

The motion planning problems for non-holonomic car-like robots have been extensively studied in the literature. The curvature-constrai-ned shortest-path problem is to plan a path from an initial congu-ration to a nal conguration (where a conguration is dened by a location and an orientation), in the presence of obstacles, such that the path is a shortest among all paths with a prescribed curvature bound. The curvature-constrained shortest-path problem can also be seen as nding a shortest path for a point car-like robot moving forward at constant speed with a radius of curvature bounded from above by some constant. Previously, there is no known hardness result for the 2D cur-vature constrained shortest-path problem. This paper shows that the above problem in two dimensions is NP-hard, when the obstacles are polygons with a total of N vertices and the vertex positions are given withinO(N 2) bits of precision. Our reduction is computed by a family of polynomial-size circuits. This NP-hardness result provides evidence that there are no eÆcient exact algorithms for curvature-constrained shortest-path planning in arbitrary environments, and it justies the approaches based on approximation and discretization used in most of the previous papers on curvature-constrained path planning