ABSTRACT
The curvature-constrained shortest-path problem is to plan a path (from an initial position to a final position, where a position is defined by a location and the orien tation angle) in the presence of obstacles, such that the path is the shortest among all paths with a prescribed curvature bound. This paper shows that the above prob lem in two dimensions is NP-hard, when the obstacles are polygons with a total of N vertices and the vertex positions are given with N ° ^ bits. Our reduction is computed by a family of polynomial-size circuits. Pre viously, there is no known hardness result for the 2D curvature constrained shortest-path problem.
