Abstract
A mobile robot with a wheeled based is subject to non-holonomic constraints on its motion. We present a planner for finding obstacle-avoiding paths subject to the constraints. We define a set of canonical trajectories which satisfy the constraints. A configuration space can be constructed for these trajectories in which there is a simple characterization of the boundaries of the obstacles generated by the workspace obstacles.
We describe a graph search algorithm which divides the configuration space into sample trajectories. The characterization of the boundaries enables us to calculate an approximate path in time \( O\left( {\frac{{{{n}^{3}}}}{\delta }\log n + A\log \left( {\frac{n}{\delta }} \right)} \right) \), where n is the number of obstacle vertices, A is the number of free trajectories, and δ is a robustness measure. Using a plane sweep technique and quadtrees we can generate robust paths in time \( O\left( {{{n}^{4}}\log n + \frac{{{{n}^{2}}}}{{{{\delta }^{2}}}}} \right) \).
Research supported by the Defense Advanced Research Projects Agency (DoD), monitored by Space and Naval Warfare Systems Command under Contract N00039-88-C-0292.
Supported by a David and Lucile Packard Foundation Fellowship and by NSF Presidential Young Investigator Grant IRI-8958577
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alfred Aho, John Hopcroft, and Jeffrey Ullman. Data Structures and Algorithms. Addison-Wesley, Reading MA, 1983.
L. E. Dubins. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79:497–516, 1957.
Steven Fortune and Gordon Wilfong. Planning constrained motion. In STOCS, pages 445–459, Chicago IL, May 1988. Association for Computing Machinery.
Victor Guillemin and Alan Pollack. Differential Topology. Prentice-Hall, 1974.
Kurt Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag, Berlin, 1984.
Hanan Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys, 16(2):187–260, June 1984.
Patrick Henry Winston. Artificial Intelligence. Addison Wesley, second edition edition, 1984.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer Science+Business Media New York
About this chapter
Cite this chapter
Jacobs, P., Canny, J. (1993). Planning Smooth Paths for Mobile Robots. In: Li, Z., Canny, J.F. (eds) Nonholonomic Motion Planning. The Springer International Series in Engineering and Computer Science, vol 192. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-3176-0_8
Download citation
DOI: https://doi.org/10.1007/978-1-4615-3176-0_8
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-6392-7
Online ISBN: 978-1-4615-3176-0
eBook Packages: Springer Book Archive