TABLE OF CONTENTS John Reif, Duke University, Durham, NC, USA
Hongyan Wang, Duke University, Durham, NC, USA
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 orientation 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 problem 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 O(1) bits. Our reduction is computed by a family of polynomial-size circuits. Previously, there is no known hardness result for the 2D curvature constrained shortest-path problem.
A curvature- constrained path is a path whose curvature at any point along the path is no larger than a prescribed upper bound. Curvature-constrained path planning arises in a variety of robotics problems, e.g. the motions of robot vehicles controlled by steering mechanisms. This paper studies the complexity of planning curvature-constrained paths.
To be more precise, let P : I ? R d be a d-dimensional continuous differential path parameterized by arc length s ? I. The average curvature of P in the interval [ s 1, s 2] ? I is defined by P'( s 1)- P'( s 2)/ s 1- s 2
