Approximation algorithms for curvature-constrained shortest paths

Citation
Pk. Agarwal et Hy. Wang, Approximation algorithms for curvature-constrained shortest paths, SIAM J COMP, 30(6), 2000, pp. 1739-1772
Citations number
52
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
30
Issue
6
Year of publication
2000
Pages
1739 - 1772
Database
ISI
SICI code
0097-5397(20000418)30:6<1739:AAFCSP>2.0.ZU;2-H
Abstract
Let B be a point robot in the plane, whose path is constrained to have curv ature of at most 1, and let Omega be a set of polygonal obstacles with n ve rtices. We study the collision-free, optimal path-planning problem for B. G iven a parameter epsilon, we present an O((n(2)/epsilon (4)) log n)-time al gorithm for computing a collision-free, curvature-constrained path between two given positions, whose length is at most ( 1+epsilon) times the length of an optimal path, provided it is robust. ( Roughly speaking, a path is ro bust if it remains collision-free even if certain positions on the path are perturbed). Our algorithm thus runs significantly faster than the previous ly best known algorithm by Jacobs and Canny whose running time is O((n+L/ep silon (2))(2) + n(2)(n+L/epsilon (2)) log n), where L is the total edge len gth of the obstacles. More importantly, the running time of our algorithm d oes not depend on the size of obstacles. The path returned by this algorith m is not necessarily robust. We present an O((n(2.5)/epsilon (4)) log n)-ti me algorithm that returns a robust path whose length is at most ( 1 +) time s the length of an optimal path, provided it is robust. We also give a stro nger characterization of curvature-constrained shortest paths, which, apart from being crucial for our algorithm, is interesting in its own right. Rou ghly speaking, we prove that, except in some special cases, a shortest path touches obstacles at points that have a visible vertex nearby.