Math @ Duke

Publications [#235428] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Wanq, H, Approximation algorithms for curvatureconstrained shortest paths,
Siam Journal on Computing, vol. 30 no. 6
(2000),
pp. 17391772, ISSN 00975397
(last updated on 2018/10/20)
Abstract: Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let fi be a set of polygonal obstacles with n vertices. We study the collisionfree, optimal pathplanning problem for D. Given a parameter e, we present an O((n2/e4)logn)time algorithm for computing a collisionfree, curvatureconstrained path between two given positions, whose length is at most (l+s) times the length of an optimal path, provided it is robust. (Roughly speaking, a path is robust if it remains collisionfree even if certain positions on the path are perturbed). Our algorithm thus runs significantly faster than the previously best known algorithm by Jacobs and Canny whose running time is O((2;)2 + rc2("L)logn), where L is the total edge length of the obstacles. More importantly, the running time of our algorithm does not depend on the size of obstacles. The path returned by this algorithm is not necessarily robust. We present an O((n25/e4) logn)time algorithm that returns a robust path whose length is at most (1 + s) times the length of an optimal path, provided it is robust. We also give a stronger characterization of curvatureconstrained shortest paths, which, apart from being crucial for our algorithm, is interesting in its own right. Roughly speaking, we prove that, except in some special cases, a shortest path touches obstacles at points that have a visible vertex nearby. © 2001 Society for Industrial and Applied Mathematics.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

