Abstract
Motion planning is becoming an important topic in many application areas, ranging from robotics to virtual environments and games. In this paper I review some recent results in motion planning, concentrating on the probabilistic roadmap approach that has proven to be very successful for many motion planning problems. After a brief description of the approach I indicate how the technique can be applied to various motion planning problems. Next I give a number of global techniques for improving the approach, and finally I describe some recent results on improving the quality of the resulting motions.
This research has been supported by the ESPRIT LTR project MOLOG.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
N. Amato, O. Bayazit, L. Dale, C. Jones, D. Vallejo, OBPRM: An obstacle-based PRM for 3D workspaces, in: P.K. Agarwal, L.E. Kavraki, M.T. Mason (eds.), Robotics: The algorithmic perspective, A.K. Peters, Natick, 1998, pp. 155–168.
N. Amato, Y. Wu, A randomized roadmap method for path and manipulation planning, Proc. IEEE Int. Conf. on Robotics and Automation, 1996, pp. 113–120.
P. Bessière. J.M. Ahuactzin, E.-G. Talbi, E. Mazer, The Ariadne’s clew algorithm: Global planning with local methods, in: K. Goldberg et al. (eds.), Algorithmic foundations of robotics, A.K. Peters, 1995, pp. 39–47.
R. Bohlin, L.E. Kavraki, Path planning using lazy PRM, Proc. IEEE Int. Conf. on Robotics and Automation, 2000, pp. 521–528.
V. Boor, M.H. Overmars, A.F. van der Stappen, The Gaussian sampling strategy for probabilistic roadmap planners, Proc. IEEE Int. Conf. on Robotics and Automation, 1999, pp. 1018–1023.
J. Cortes, T. Simeon, J.P. Laumond, A random loop generator for planning the motions of closed kinematic chains using PRM methods, Rapport LAAS N01432, 2001.
L. Han, N. Amato, A kinematics-based probabilistic roadmap method for closed chain systems, Proc. Workshop on Algorithmic Foundations of Robotics (WAFR’00), 2000, pp. 233–246.
O. Hofstra, D. Nieuwenhuisen, M.H. Overmars, Improving path quality for probabilistic roadmap planners, 2002, in preparation.
C. Holleman, L. Kavraki, J. Warren, Planning paths for a flexible surface patch, Proc. IEEE Int. Conf. on Robotics and Automation, 1998, pp. 21–26.
D. Hsu, L. Kavraki, J.C. Latombe, R. Motwani, S. Sorkin, On finding narrow passages with probabilistic roadmap planners, in: P.K. Agarwal, L.E. Kavraki, M.T. Mason (eds.), Robotics: The algorithmic perspective, A.K. Peters, Natick, 1998, pp. 141–154.
L. Kavraki, Random networks in configuration space for fast path planning, PhD thesis, Stanford University, 1995.
L. Kavraki, M. Kolountzakis, J.C. Latombe, Analysis of probabilistic roadmaps for path planning, Proc. IEEE Int. Conf. on Robotics and Automation, 1996, pp. 3020–3025.
L. Kavraki, J.C. Latombe, Randomized preprocessing of configuration space for fast path planning, Proc. IEEE Int. Conf. on Robotics and Automation, 1994, pp. 2138–2145.
L. Kavraki, P. Svestka, J-C. Latombe, M.H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. on Robotics and Automation 12 (1996), pp. 566–580.
F. Lamiraux, L.E. Kavraki, Planning paths for elastic objects under manipulation constraints, Int. Journal of Robotics Research 20 (2001), pp. 188–208.
J-C. Latombe, Robot motion planning, Kluwer Academic Publishers, Boston, 1991.
C. Nissoux, T. Siméon, J.-P. Laumond, Visibility based probabilistic roadmaps, Proc. IEEE Int. Conf. on Intelligent Robots and Systems, 1999, pp. 1316–1321.
M.H. Overmars, A random approach to motion planning, Technical Report RUU-CS-92-32, Dept. Comput. Sci., Utrecht Univ., Utrecht, the Netherlands, October 1992.
G. Sánchez, J.-C. Latombe, A single-query bi-directional probabilistic roadmap planner with lazy collision checking, Int. Journal of Robotics Research, 2002, to appear.
D. Sent, M.H. Overmars, Motion planning in an environment with dangerzones, Proc. IEEE Int. Conf. on Robotics and Automation, 2001, pp. 1488–1493.
T. Simeon, J. Cortes, A. Sahbani, J.P. Laumond, A manipulation planner for pick and place operations under continuous grasps and placements, Rapport LAAS N01433, 2001.
P. Svestka, Robot motion planning using probabilistic roadmaps, PhD thesis, Utrecht Univ. 1997.
P. Švestka, M.H. Overmars, Motion planning for car-like robots, a probabilistic learning approach, Int. Journal of Robotics Research 16 (1997), pp. 119–143.
P. Švestka, M.H. Overmars, Coordinated path planning for multiple robots, Robotics and Autonomous Systems 23 (1998), pp. 125–152.
S. Sekhavat, P. Švestka, J.-P. Laumond, M.H. Overmars, Multilevel path planning for nonholonomic robots using semiholonomic subsystems, Int. Journal of Robotics Research 17 (1998), pp. 840–857.
J. Vleugels, J. Kok, M.H. Overmars, Motion planning with complete knowledge using a colored SOM, Int. Journal of Neural Systems 8 (1997), pp. 613–628.
S.A. Wilmarth, N.M. Amato, P.F. Stiller, MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space, Proc. IEEE Int. Conf. on Robotics and Automation, 1999, pp. 1024–1031.
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
Overmars, M.H. (2002). Recent Developments in Motion Planning. In: Sloot, P.M.A., Hoekstra, A.G., Tan, C.J.K., Dongarra, J.J. (eds) Computational Science — ICCS 2002. ICCS 2002. Lecture Notes in Computer Science, vol 2331. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47789-6_1
Download citation
DOI: https://doi.org/10.1007/3-540-47789-6_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43594-5
Online ISBN: 978-3-540-47789-1
eBook Packages: Springer Book Archive