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

Abstract

The motion planning problems for non-holonomic car-like robots have been extensively studied in the literature. The curvature-constrained shortest-path problem is to plan a path (from an initial configuration to a final configuration, where a configuration is defined 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 finding a shortest path for a point car-like robot moving forward at constant speed with a radius of curvature upper bounded by some constant. Previously, there is no known hardness result for the 2D curvature 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 within O(N²) bits of precision. Our reduction is computed by a family of polynomial-size ...