Approximation algorithms for curvature-constrained shortest paths

摘要

Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let be a set of polygonal obstacles with n vertices. We study the collision-free, optimal path-planning problem for B. Given a parameter ", we present an O((n 2 4) logn)-time algorithm for computing a collision-free, curvature-constrained path between two given positions, whose length is at most (1 + ") times the length of an optimal robust path (a path is robust if it remains collision-free even if certain positions on the path are perturbed). Our algorithm thus runs signicantly faster than the previously best known algorithm by Jacobs and Canny whose running time is O(( n+L 2