Abstract
In this paper we describe an approach to probabilistic roadmap method. Our algorithm builds initially a roadmap in the configuration space considering that all nodes and edges are collision-free, and searches the roadmap for the shortest path between start and goal nodes. If a collision with the obstacles occurs, the corresponding nodes and edges are removed from the roadmap or the planner updates the roadmap with new nodes and edges, and then searches for a shortest path. The procedure is repeated until a collision-free path is found. The goal of our approach is to minimize the number of collision checks and calls to the local method. Experimental results presented in this paper show that our approach is very efficient in practice.
This is a preview of subscription content, log in via an institution to check access.
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
Overmars, M. H.: A random approach to motion planning. Technical Report RUU-CS-92-32, Utrecht University (1992)
Overmars, M. H., Švestka, P.: A probabilistic learning approach to motion planning. Workshop on the Algorithmic Foundations of Robotics. A. K. Peters (1994) 19–37
Kavraki, L. E., Švestka, P., Latombe, J-C., Overmars, M. H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation. Vol 12, No. 4 (1996) 566–579
Švestka, P., Overmars, M. H.: Motion planning for car-like robots using a probabilistic learning approach. The International Journal of Robotics Research. Vol 16, No. 2 (1997) 119–143
Nissoux, C., Siméon, T., Laumond, J. P.: Visibility based probabilistic roadmaps. IEEE International Conference on Intelligent Robots and Systems (1999)
Kuffner, J. J., LaValle, S. M.: RRT-Connect: An efficient approach to singlequery path planning. IEEE International Conference on Robotics and Automation (2000)
Vallejo, D., Jones, C., Amato, N. M.: An adaptive framework for’ single-shot’ motion planning. Technical Report 99-024. Texas A&M University (1999)
Bohlin, R., Kavraki, L. E.: Path planning using lazy PRM. IEEE International Conference on Robotics and Automation (2000) 521–528
Sánchez, A. G., Latombe, J-C.: A single-query bi-directional probabilistic roadmap planner with lazy collision checking. Int. Symposium on Robotics Research (ISRR’01) (2001)
Laumond, J-P Ed.: Robot motion planning and control. Springer Verlag (1988)
Reeds, J. A., Shepp, R. A.: Optimal paths for a car that goes both forward and backwards. Pacific Journal of Mathematics. 145(2) (1990) 367–393
Sánchez, L. A., Arenas, B. J. A., Zapata, R.: Optimizing trajectories in nonholonomic motion planning. In 3er Encuentro Internacional de Ciencias de la Computación. INEGI (2001) 479–488
Vendittelli, M., Laumond, J. P., Nissoux, C.: Obstacle distance for car-like robots. IEEE Transactions on Robotics and Automation. Vol 15, No. 4 (1999) 678–691
Souères, P., Boissonnat, J-D.: Optimal trajectories for non-holonomic robots. In Robot motion planning and control, J. P. Laumond Ed. Vol 229, Springer Verlag (1998)
Desaulniers, G.: On shortest paths for a car-like robot maneuvering around obstacles. Robotics and Autonomous Systems. Vol 17 (1996) 139–148
Reif, J., Wang, H.: The complexity of the two dimensional curvature-constrained shortest-path problem. Robotics: The algorithmic perspective. P. K. Agarwal et al. Eds, A. K. Peters (1998)
Agarwal, P. K., Raghavan, P., Tamaki, H.: Motion planning for a steering-constrained robot through moderate obstacles. In ACM Symp. on Computational Geometry (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sánchez L., A., Zapata, R., Arenas B., J.A. (2002). Motion Planning for Car-Like Robots Using Lazy Probabilistic Roadmap Method. In: Coello Coello, C.A., de Albornoz, A., Sucar, L.E., Battistutti, O.C. (eds) MICAI 2002: Advances in Artificial Intelligence. MICAI 2002. Lecture Notes in Computer Science(), vol 2313. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46016-0_1
Download citation
DOI: https://doi.org/10.1007/3-540-46016-0_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43475-7
Online ISBN: 978-3-540-46016-9
eBook Packages: Springer Book Archive