Motion Planning in Dynamic Environments with the Rapidly Exploring Random Tree Method

E. Szádeczky-Kardoss; B. Kiss

doi:10.15866/irea.v4i3.10514

Motion Planning in Dynamic Environments with the Rapidly Exploring Random Tree Method

^(*) Corresponding author

DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract

The Rapidly Exploring Random Tree (RRT) algorithm is a probabilistic motion planning method. It builds a graph in the configuration space of a robot such that its motion equation is taken into account. The basic RRT algorithm is able to plan a path which avoids the collision with static obstacles. This paper discusses the required modifications if the environment of the robot contains moving obstacles as well. Two different methods are presented. The first one can only be used if the graph is a single tree. The main modification w.r.t. the original RRT algorithm is that the graph is built in an extended space and a special distance-like pseudo-metric is applied. The second algorithm may work with several trees as well and it is based on the time-scaling of the reference path.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords

Mobile Robots; Moving Obstacles; Probabilistic Motion Planning; RRT; Time-Scaling

Full Text:

PDF

References

L.E. Kavraki, P. Svestka, J.-C. Latombe, and M.H. Overmars, Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces, IEEE Transactions on Robotics and Automation, Vol. 12(Issue 4):566-580, 1996.
http://dx.doi.org/10.1109/70.508439

E. Mazer, J.M. Ahuactzin, and P. Bessiere, The Ariadne’s Clew Algorithm, Journal of Artificial Intelligence Research, Vol. 9:295-316, 1998.
http://dx.doi.org/10.1109/iros.1993.583784

S.M. LaValle, Rapidly-Exploring Random Trees: A New Tool for Path Planning, Tech. Rep., Computer Science Dept, Iowa State University, Ames, IO, 1998.
http://dx.doi.org/10.1109/icit.2010.5472492

S.M. LaValle, Planning Algorithms (Cambridge University Press, 2006).
http://dx.doi.org/10.1017/cbo9780511546877

S.M. LaValle, J.J. Kuffner, Rapidly-Exploring Random Trees: Progress and Prospects, International Workshop on the Algorithmic Foundations of Robotics, pp. 293-308, Hanover, NH, March 2000.
http://dx.doi.org/10.1109/robot.2002.1013372

E. Szádeczky-Kardoss, B. Kiss, Extension of the Rapidly Exploring Random Tree Algorithm with Key Configurations for Nonholonomic Motion Planning, IEEE International Conference on Mechatronics, pp. 363-368, Budapest, Hungary, July 2006.
http://dx.doi.org/10.1109/icmech.2006.252554

K. Pathak, Switched Potential Fields for Navigation and Control of Nonholonomic and Underactuated Autonomous Mobile Robots, Ph.D. dissertation, Dept. Mechanical Eng., Univ. Delaware, Newark, DE, 2005.
http://dx.doi.org/10.2172/6251372

J.J. Kuffner, S.M. LaValle, RRT-Connect: An Efficient Approach to Single-Query Path Planning, IEEE International Conference on Robotics and Automation, Vol. 2, pp. 995–1001, San Francisco, CA, April 2000.
http://dx.doi.org/10.1109/robot.2000.844730

K. Kant and S. Zucker, Toward Efficient Trajectory Planning: The Path-Velocity Decomposition, International Journal of Robotics Research, Vol. 5(Issue 3):72-89, 1986.
http://dx.doi.org/10.1177/027836498600500304

J.M. Hollerbach, Dynamic Scaling of Manipulator Trajectories, Transactions of the ASME, Journal of Dynamic Systems, Measurement, and Control, Vol. 106(Issue 1):102-106, 1984.
http://dx.doi.org/10.1115/1.3149652

E. Szádeczky-Kardoss, B. Kiss, Tracking Error Based On-line Trajectory Time Scaling, IEEE International Conference on Intelligent Engineering Systems, pp. 80-85, London, United Kingdom, June 2006.
http://dx.doi.org/10.1109/ines.2006.1689346

Refbacks

There are currently no refbacks.

Username
Password
Remember me