More Web Proxy on the site http://driver.im/

Article

Curvature-bounded traversals of narrow corridors

Authors:

David KirkpatrickAuthors Info & Claims

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

Pages 278 - 287

https://doi.org/10.1145/1064092.1064135

Published: 06 June 2005 Publication History

Abstract

We consider the existence and efficient construction of bounded curvature paths traversing constant-width regions of the plane, called corridors. We make explicit a width threshold τ with the property that (a) all corridors of width at least τ admit a unit-curvature traversal and (b) for any width w < τ there exist corridors of width w with no such traversal. Applications to the design of short, but not necessarily shortest, and high clearance, but not necessarily maximum clearance, curvature-bounded paths in general polygonal domains, are also discussed.

References

[1]

P. Agarwal, T. Biedl, S. Lazard, S. Robbins, S. Suri, and S. Whitesides. Curvature-constrained shortest paths in a convex polygon. SIAM Journal on Computing, 31(6):1814--1851, 2002.

Digital Library

[2]

P. K. Agarwal, P. Raghavan, and H. Tamaki. Motion planning for a steering-constrained robot through moderate obstacles. In Proc. 27th Annu. ACM Sympos. Theory Comput., pages 343--352, 1995.

Digital Library

[3]

P. K. Agarwal and H. Wang. Approximation algorithms for curvature constrained shortest paths. SIAM Journal on Computing, 30(6): 1739--1772, 2002

Digital Library

[4]

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

Digital Library

[5]

T. Berglund, U. Erikson, H. Jonsson, K. Mrozek, and I. Söderkvist. Automatic generation of smooth paths bounded by polygonal chains. In International Conference on Computational Intelligence for Modelling Control and Automation (CIMCA'2001), 2001.

[6]

J.-D. Boissonnat, S. Ghosh, T. Kavitha, and S. Lazard. An algorithm for computing a convex and simple path of bounded curvature in a simple polygon. Algorithmica, 34(2): 109--156, 2002.

Digital Library

[7]

J.-D. Boissonnat and S. Lazard. A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles. Int. J. Comput. Geometry Appl., 13(3): 189--229, 2003.

[8]

X.-N. Bui, P. Souères, J.-D. Boissonnat, and J.-P. Laumond. Shortest path synthesis for Dubins nonholonomic robot. In Proc. IEEE Internat. Conf. Robot. Autom., pages 2--7, 1994.

[9]

J. Canny and B. R. Donald. Simplified Voronoi diagrams. Discrete Comput. Geom., 3:219--236, 1988.

Digital Library

[10]

J. Canny and J. H. Reif. New lower bound techniques for robot motion planning problems. In Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., pages 49--60, 1987.

Digital Library

[11]

L. E. Dubins. On curves of minimal length with a constant on average curvature and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79:497--516, 1957.

[12]

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

[13]

L. J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126--152, 1989.

Digital Library

[14]

J. Hershberger. A new data structure for shortest path queries in a simple polygon. Inform. Process. Lett., 38:231--235, 1991.

Digital Library

[15]

J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Comput. Geom. Theory Appl., 4:63--98, 1994.

Digital Library

[16]

J. Hershberger and S. Suri. An optimal algorithm for euclidean shortest paths in the plane. SIAM Journal on Computing, 28(6):2215--2256, 1999.

Digital Library

[17]

P. Jacobs and J. Canny. Planning smooth paths for mobile robots. In Proc. IEEE Internat. Conf. Robot. Autom., pages 2--7, 1989.

[18]

J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.

Digital Library

[19]

J.-P. Laumond, P. Jacobs, M. Taix, and R. M. Murray. A motion planner for nonholonomic mobile robots. IEEE Trans. Robot. Autom., 10(5):577--593, 1994.

[20]

J.-P. Laumond(ed.). Robot motion planning and control. Springer-Verlag, New York, NY, 1998.

Digital Library

[21]

D. Lutterkort and J. Peters. Smooth paths in a polygonal channel. In Proc. 15th Annual ACM Sympos. on Comput. Geometry, pages 316--321, 1999.

Digital Library

[22]

C. Ó'Dúnlaing and C. K. Yap. A "retraction" method for planning the motion of a disk. J. Algorithms, 6:104--111, 1985.

[23]

J. Reif and H. Wang. The complexity of the two dimensional curvature-constrained shortest-path problem. In Proc. 3rd Workshop on the Algorithmic Foundations of Robotics, 1998.

Digital Library

[24]

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

[25]

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

Digital Library

[26]

J. Sellen. Approximation and decision algorithms for curvature-constrained path planning: A state-space approach. In Proc. 3rd Workshop on the Algorithmic Foundations of Robotics, 1998.

Digital Library

Cited By

Marchidan ABakolas E(2022)A local reactive steering law for 2D collision avoidance with curvature constraints and constant speedRobotics and Autonomous Systems10.1016/j.robot.2022.104156155(104156)Online publication date: Sep-2022
https://doi.org/10.1016/j.robot.2022.104156
Upadhyay SRatnoo A(2018)On Existence and Synthesis of Smooth Four Parameter Logistic Paths Inside Annular PassagesIEEE Robotics and Automation Letters10.1109/LRA.2018.28670693:4(4375-4382)Online publication date: Oct-2018
https://doi.org/10.1109/LRA.2018.2867069
Upadhyay SRatnoo A(2015)Smooth path planning for passages with heading and curvature discontinuities2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS.2015.7353742(2672-2677)Online publication date: Sep-2015
https://doi.org/10.1109/IROS.2015.7353742
Show More Cited By

Index Terms

Curvature-bounded traversals of narrow corridors
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon

Abstract. In this paper we study the collision-free path planning problem for a point robot, whose path is of bounded curvature(i.e., constrained to have curvature at most 1), moving in the plane inside an n -sided simple polygon P . Given two points ...
On rectilinear link distance

In this paper we study two link distance problems for rectilinear paths inside a simple rectilinear polygon P.First, we present a data structure using O(n log n) storage such that a shortest path between two query points can be computed efficiently. If ...
Approximating corridors and tours via restriction and relaxation techniques

Given a rectangular boundary partitioned into rectangles, the Minimum-Length Corridor (MLC-R) problem consists of finding a corridor of least total length. A corridor is a set of connected line segments, each of which must lie along the line segments ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

June 2005

398 pages

ISBN:1581139918

DOI:10.1145/1064092

Program Chairs:
Joe Mitchell
SUNY Stony Brook
,
Günter Rote
Freie Universität Berlin

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG05

Sponsor:

SoCG05: The 21st Annual ACM Symposium on Computational Geometry 2005

June 6 - 8, 2005

Pisa, Italy

Acceptance Rates

SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
374
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Marchidan ABakolas E(2022)A local reactive steering law for 2D collision avoidance with curvature constraints and constant speedRobotics and Autonomous Systems10.1016/j.robot.2022.104156155(104156)Online publication date: Sep-2022
https://doi.org/10.1016/j.robot.2022.104156
Upadhyay SRatnoo A(2018)On Existence and Synthesis of Smooth Four Parameter Logistic Paths Inside Annular PassagesIEEE Robotics and Automation Letters10.1109/LRA.2018.28670693:4(4375-4382)Online publication date: Oct-2018
https://doi.org/10.1109/LRA.2018.2867069
Upadhyay SRatnoo A(2015)Smooth path planning for passages with heading and curvature discontinuities2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS.2015.7353742(2672-2677)Online publication date: Sep-2015
https://doi.org/10.1109/IROS.2015.7353742
Cowlagi RTsiotras P(2014)Curvature-Bounded Traversability Analysis in Motion Planning for Mobile RobotsIEEE Transactions on Robotics10.1109/TRO.2014.231571130:4(1011-1019)Online publication date: Aug-2014
https://doi.org/10.1109/TRO.2014.2315711
Hoy MMatveev ASavkin A(2014)Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a surveyRobotica10.1017/S026357471400028933:3(463-497)Online publication date: 4-Mar-2014
https://doi.org/10.1017/S0263574714000289
Kim HCheong O(2013)The cost of bounded curvatureComputational Geometry: Theory and Applications10.1016/j.comgeo.2012.10.00846:6(648-672)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.comgeo.2012.10.008
Kostitsyna IPolishchuk V(2012)Simple Wriggling is Hard Unless You Are a Fat HippoTheory of Computing Systems10.5555/2556794.255760950:1(93-110)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2556794.2557609
Cowlagi RTsiotras P(2012)Multiresolution Motion Planning for Autonomous Agents via Wavelet-Based Cell DecompositionsIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics10.1109/TSMCB.2012.219226842:5(1455-1469)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1109/TSMCB.2012.2192268
Cowlagi RTsiotras P(2012)Hierarchical Motion Planning With Dynamical Feasibility Guarantees for Mobile Robotic VehiclesIEEE Transactions on Robotics10.1109/TRO.2011.217161328:2(379-395)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1109/TRO.2011.2171613
Cowlagi RTsiotras P(2011)Multi-resolution H-cost motion planning: A new framework for hierarchical motion planning for autonomous mobile vehicles2011 IEEE/RSJ International Conference on Intelligent Robots and Systems10.1109/IROS.2011.6094578(3501-3506)Online publication date: Sep-2011
https://doi.org/10.1109/IROS.2011.6094578
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents