A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles (extended abstract)
Jean‐Daniel Boissonnat, Sylvain Lazard · 1996
In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and nal congurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two congurations, avoiding the obstacles, and with the further constraint that, on each C 2 piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al. [1]) and present a polynomial-time exact algorithm to solve this problem. 1 Introduction In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane, SBC path for short. More precisely, given prescribed initial and nal congurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two congurations, avoiding the obstacles,...