Article

Free access

Approximation algorithms for curvature-constrained shortest paths

Authors:

Hongyan Wang,

Pankaj K. AgarwalAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 409 - 418

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

P.K. Agaxwal, P. Raghavan, and H. Tamaki. Motion planning for a steering-constrained robot through moderate obstacles. In Proc. 27th A CM Syrup. Theory of Computing, pages 343-352, 1995.

Digital Library

Google Scholar

[2]

J. Barraquand and J.C. Latombe. Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles. Algorithmica, 10:121-155, 1993.

Google Scholar

[3]

J.D. Boissonnat and X.N. But. Accessibility region for a cax that only moves forwards along optimal paths. Tech. Rept. 2181, INRIA, Sophia Antipolis, France, 1994.

Google Scholar

[4]

J.D. Boissonnat, A. Cerezo, and J. Leblond. Shortest paths of bounded curvature in the plane. In Proc. IEEE Int. Conf. on Robotics and Automation, pages 2315-2320, 1992.

Google Scholar

[5]

J.D. Boissonnat, A. Cerezo, and J. Leblond. A note on shortest paths in the plane subject to a constraint on the derivative of the curvature. Tech. Rept. 2160, INRIA, Sophia Antipolis, France, 1994.

Google Scholar

[6]

X.N. But, J.D. Boissonnat, P. Soueres, and J.P. Laumond. Shortest path synthesis for Dubins nonholonomic robot. In Proc. iEEE Int. Conf. on Robotics and Automation, pages 2-7, 1994.

Google Scholar

[7]

J. Canny. Some algebraic and geometric configurations in PSPACE. In Proc. ~Oth A CM Symp. Theory of Computing., pages 460-467, 1988.

Digital Library

Google Scholar

[8]

J. Canny. Private communication.

Google Scholar

[9]

J. Canny, B. Donald, J. Reif, and P. Xavier. On the complexity of kinodynamic planning. In Proc. 29th Syrup. Foundations of Computer Science, pages 306- 316, 1988.

Google Scholar

[10]

J. Canny, A. Rege, and J. Reif. An exact algorithm for kinodynamic planning in the plane. Discrete Comput. Geom., 6:461-484, 1991.

Crossref

Google Scholar

[11]

J. Canny ~nd J. tLeif. New lower bound techniques for robot motion planning. In Proc. 28th Syrup. Foundations of Computer Science, pages 49-60, 1987.

Google Scholar

[12]

K.L. Glarkson. Approximation algorithms for shortest path motion planning. In Proc. 9th Syrup. Theory of Computing, pages 56-65, 1987.

Digital Library

Google Scholar

[13]

E. Cockayne and G. Hall. Plane motion of a particle subject to curvature constraints. SIAM J. Control, 43:197-220, 1975.

Google Scholar

[14]

R. Cole and M. Sharir. Visibility problems for polyhedral terrains. J. Symbolic Comput., 7:11-30, 1989.

Digital Library

Google Scholar

[15]

T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. The MIT Press, MA, 1991.

Digital Library

Google Scholar

[16]

B. Donald and P. Xavier. Near-optimal kinodynamic planning for robots with coupled dynamics bounds. In IEEE Int. Syrup. Intelligent Controls, pages 354-359, 1989.

Google Scholar

[17]

L.E. Dubins. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. Amer. J. Math., 79:497-516, 1957.

Google Scholar

[18]

S. Fortune and G. Wilfong. Planning constrained motion. Annals of Mathematics and Artificial Intelligence, 3:21-82, 1991.

Google Scholar

[19]

T. Fraichaxd. Smooth trajectory planning for a car in a structured world. In Proc. IEEE Int. Conf. on Robotics and Automation, pages 2-7, 1991.

Google Scholar

[20]

L. Guibas, M. Overmars, and M. Sharir. Ray shooting, implicit point location, and related queries in arrangements of segments. Tech. Rept. 433, Dept. Computer Science, New York University, New York, 1989.

Google Scholar

[21]

J. Hopcroft, J. Schwartz, and M. Sharir, editors. Planning, Geometry, and Complezity of Robot Motion. Ablex Publishing Corp., Norwood, NJ, 1984.

Digital Library

Google Scholar

[22]

P. Jacobs and J. Canny. Planning smooth paths for mobile robots. In Nonholonomic Motion Planning (Z. Li and J. Canny, editors), Kluwer Academic, Norwell, MA, pages 271-342, 1992.

Google Scholar

[23]

P. Jacobs, J.P. Laumond, and M. Taix. Efficient motion planners for nonholonomic mobile robots. In Proc. IEEE/RSJ Int. Workshop on Intelligent Robots and Systems, pages 1229-1235, 1991.

Google Scholar

[24]

K. Kedem, R. Livne, J. Path, and M. Sharir. On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1:59-71, 1986.

Digital Library

Google Scholar

[25]

V.P. Kostov and E.V. Degtiariova-Kostova. Suboptimal paths in the problem of a planar motion with bounded derivative of the curvature. Tech. Rept., IN- RIA, Cedex, France, 1993.

Google Scholar

[26]

V.P. Kostov and E.V. Degtiariova-Kostova. The planar motion with bounded derivative of the curvature and its suboptimal paths. Tech. Rept., INRIA, Cedex, France, 1994.

Google Scholar

[27]

J.C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA, 1991.

Digital Library

Google Scholar

[28]

J.C. Latombe. A fast path-planner for a car-like indoor mobile robot. In Proc. 9th National Conf. on Artificial Intelligence, pages 659-665, 1991.

Google Scholar

[29]

J.P. Laumond. Finding collision free smooth trajectories for a nonholonomic mobile robot. In Proc. l Oth Int. Joint Conf. on Artificial Intelligence, pages 1120- 1123, 1987.

Google Scholar

[30]

J.P. Laumond, P.E. Jacobs, M. Taix, and R.M. Murray. A motion planner for nonholonomic mobile robots. IEEE Trans. on Robotics and Automation, 10:577-593, 1994.

Google Scholar

[31]

J.P. Laumond and T. Simeon. Motion planning for a two degrees of freedom mobile robot with towing. Tech. Rept., LAAS/CNRS, LAAS, Toulouse France, 1989.

Google Scholar

[32]

J.P. Laumond, M. Taix, and P. Jacobs. A motion planner for car-like robots based on a global/local approach. In Proc. IEEE/RSJ Int. Workshop on Intelligent Robots and Systems, pages 765-773, 1990.

Google Scholar

[33]

Z. Li and J.F. Canny, editors. Nonholonomic Motion Planning. Kluwer Academic Publishers, Norwell, MA, 1992.

Digital Library

Google Scholar

[34]

B. Mirtich and J. Canny. Using skeletons for nonholonomic path planning among obstacles. In Proc. IEEE Int. Conf. on Robotics and A utonomation, pages 2533- 2540, 1992.

Google Scholar

[35]

Y. Nakamura and R. Mukherjee. Nonholonomic path planning and automation, in Proc. IEEE Int. Conf. on Robotics and Automation, pages 1050-1055, 1989.

Google Scholar

[36]

C. 0'Dfinlaing. Motion planning with inertial constraints. Algorithmica, 2:431-475, 1987.

Google Scholar

[37]

J.A. Reeds and L.A. Shepp. Optimal paths for a car that goes both forwards and backwards. Pacific J. of Mathematics, 145:367-393, 1990.

Google Scholar

[38]

J. H. Reif. Complexity of the generalized movers problem. In Planning, Geometry and Complexity of Robot Motion (J. Hopcroft, and J. Schwartz, and M. Sharir, editors), Ablex Publishing Corp., Norwood, NJ, pages 267-281, 1987.

Google Scholar

[39]

J. H. R. eif and M. Shaxir. Motion planning in the presence of moving obstacles, in Proc. 26th IEEE Syrup. Foundations of Computer Science, pages 144- 154, 1985.

Google Scholar

[40]

J.H. Reif and S.R. Tare. Approximate kinodynomic planning using L2-norm dynamic bounds. Computers Math. Applic., 27:29-44, 1994.

Google Scholar

[41]

J.T. Schwartz and M. Sharir. Motion planning and related geometric algorithms in robotics. In Proc. Int. Congress of Mathematicians, pages 1594-1611, 1986.

Google Scholar

[42]

J.T. Schwartz and M. Sharir. Algorithmic motion planning in robotics. In Handbook of Theoretical Computer Science, Vol. A (J. van Leeuwen, editor), Elsevier, Amsterdam, pages 391-430, 1990.

Digital Library

Google Scholar

[43]

G. Wilfong. Motion planning for an autonomous vehicle. In Proc. IEEE Int. Conf. on Robotics and Automation, pages 529-533, 1988.

Google Scholar

[44]

G. Wilfong. Shortest paths for autonomous vehicles. In Proc. IEEE Int. Conf. on Robotics and Automation, pages 15-20, 1989.

Google Scholar

Cited By

View all

Takei RTsai R(2013)Optimal Trajectories of Curvature Constrained Motion in the Hamilton---Jacobi FormulationJournal of Scientific Computing10.1007/s10915-012-9671-y54:2-3(622-644)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1007/s10915-012-9671-y
Ahmadzadeh AMotee NJadbabaie APappas G(2009)Multi-vehicle path planning in dynamically changing environmentsProceedings of the 2009 IEEE international conference on Robotics and Automation10.5555/1703775.1703799(2148-2153)Online publication date: 12-May-2009
https://dl.acm.org/doi/10.5555/1703775.1703799
Backer JKirkpatrick DErickson J(2007)Finding curvature-constrained paths that avoid polygonal obstaclesProceedings of the twenty-third annual symposium on Computational geometry10.1145/1247069.1247080(66-73)Online publication date: 6-Jun-2007
https://dl.acm.org/doi/10.1145/1247069.1247080
Show More Cited By

Index Terms

Approximation algorithms for curvature-constrained shortest paths

Recommendations

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 $\Omega$ be a set of polygonal obstacles with n vertices. We study the collision-free, optimal path-planning problem for B. Given a parameter $\...
Approximation Algorithms for Curvature Constrained Shortest Paths
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths
ISAAC '08: Proceedings of the 19th International Symposium on Algorithms and Computation

We address the problem of finding a polynomial-time approximation scheme for shortest bounded-curvature paths in the presence of obstacles. Given an arbitrary environment $\mathcal{E}$ consisting of polygonal obstacles, two feasible configurations, a length ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
544
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)9

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Takei RTsai R(2013)Optimal Trajectories of Curvature Constrained Motion in the Hamilton---Jacobi FormulationJournal of Scientific Computing10.1007/s10915-012-9671-y54:2-3(622-644)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1007/s10915-012-9671-y
Ahmadzadeh AMotee NJadbabaie APappas G(2009)Multi-vehicle path planning in dynamically changing environmentsProceedings of the 2009 IEEE international conference on Robotics and Automation10.5555/1703775.1703799(2148-2153)Online publication date: 12-May-2009
https://dl.acm.org/doi/10.5555/1703775.1703799
Backer JKirkpatrick DErickson J(2007)Finding curvature-constrained paths that avoid polygonal obstaclesProceedings of the twenty-third annual symposium on Computational geometry10.1145/1247069.1247080(66-73)Online publication date: 6-Jun-2007
https://dl.acm.org/doi/10.1145/1247069.1247080
Ahn HCheong OMatoušek JVigneron ACheng SCheong OAgarwal PFortune S(2000)Reachability by paths of bounded curvature in convex polygonsProceedings of the sixteenth annual symposium on Computational geometry10.1145/336154.336211(251-259)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/336154.336211
Agarwal PBiedl TLazard SRobbins SSuri SWhitesides SJanardan R(1998)Curvature-constrained shortest paths in a convex polygon (extended abstract)Proceedings of the fourteenth annual symposium on Computational geometry10.1145/276884.276928(392-401)Online publication date: 7-Jun-1998
https://dl.acm.org/doi/10.1145/276884.276928
Boissonnat JLazard SWhitesides S(1996)A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles (extended abstract)Proceedings of the twelfth annual symposium on Computational geometry10.1145/237218.237393(242-251)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/237218.237393

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Approximation Algorithms for Curvature-Constrained Shortest Paths

Approximation Algorithms for Curvature Constrained Shortest Paths

A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths