Open Access Open Access  Restricted Access Subscription Access

Application of RRT Algorithm to Unmanned Ground Vehicle Motion Planning and Obstacle Avoidance

Yiqun Dong, Youmin Zhang

Abstract


This report presents an application of Randomized Rapidly-exploring Tree (RRT) algorithm to unmanned ground vehicle motion planning and obstacle avoidance. Dynamics and kinemics of the vehicle are presented. A pure-pursuit motion controller is discussed. General structure of the RRT algorithm, including node selection, tree expansion, and path generation is introduced. After a feasible path is found, certain optimization efforts are included to shorten the overall length of the path. Experimental tests using real ground vehicle are demonstrated. Based on the test results, the motion planning and obstacle avoidance strategies proposed in this paper proves to be effective.

Full Text:

PDF

References


Lozano-Perez, T., “Automatic Planning of Manipulator Transfer Movements”, IEEE Transaction on Systems, Man, and Cybernetics, Vol. 11, No. 10, 1981, pp. 681-698.

Lozano-Perez, T., and Wesley M., “An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles”, Communications of the ACM, Vol. 22, No. 10, 1979, pp. 560-570.

Edelsbrunner, H., “Algorithms in Combinatorial Geometry”, Springer-Verlag, Berlin, 1987, pp. 275-278.

O’Dunlaing, P., and Yap, C., “A Retraction Method for Planning the Motion of a Disc”, Journal of Algorithms, Vol. 6, No. 1, 1982, pp. 104-111.

Khatib, O., “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots”, International Journal of Robotics Research, Vol. 5, No. 1, 1986, pp. 90-98.

Hwang, Y., and Ahuja, N., “A Potential Field Approach to Path Planning”, IEEE Transactions of Robotics and Automation, Vol. 8, No. 1, 1992, pp. 23-32.

Barraquand, J., Langlois, B., and Latombe, J., “Numerical Potential

Field Technique for Robot Path Planning”, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 22, No. 2, 1992, pp. 224-241.

Rimon, E., and Koditscheck, D., “Exact Robot Navigation Using Artificial Potential Fields”, IEEE Transactions on Robotics and Automation, Vol. 8, No. 5, 1992, pp. 501-518.

LaValle, S., and Kuffner, J., “Randomized Kinodynamic Planning”, Proceedings of the 1999 IEEE International Conference on Robotics and Automation, Detroit, MI, USA, May 10-15, 1999.

Kuffner, J., and LaValle, S., “RRT-Connect: An Efficient Approach to Single-Query Path Planning”, Proceedings of 2000 IEEE International Conference on Robotics and Automation, San Francisco, CA, USA, April 24-28, 2000.

Kalisiak, M., and Panne, M., “RRT-Blossom: RRT with a Local Flood-Fill Behavior”, Proceedings of 2006 International Conference on Robotics and Automation, Orlando, Florida, USA, May 15-19, 2006.

Cheng, P., and LaValle, S., “Reducing Metric Sensitivity in Randomized

Trajectory Design”, Proceedings of 2001 IEEE International Conference on Intelligent Robots and System, Maui, HI, USA, Oct. 29-Nov. 3, 2001.

Kalisiak, M., and Panne, M., “Faster Motion Planning Using Learned Local Viability Models”, Proceedings of 2007 IEEE International Conference on Robots and Automation, Roma, April 10-14, 2007.

Amidi, O., Thorpe, C., Chun, W., and Wolfe, W., Eds., “Integrated Mobile Robot Control”, in Proc. SPIE, Boston, MA, Mar. 1991, Vol. 1388, pp. 504-523.

Kuwata, Y., Teo, J., Fiore., G., Karaman, S., Frazzoli, E., and How, J., “Real-Time Motion Planning with Application to Autonomous Urban Driving”, IEEE Transaction on Control Systems Technology, Vol. 17, No. 5, pp. 1105-1118, September 2009.

Park, S., Deyst, J., and How, J., “Performance and Lyapunov Stability of a Nonlinear Path-Following Guidance Method”, Journal of Guidance, Control, and Dynamics, Vol. 30, No. 6, pp. 1718-1728, November 2007.

Kuwata, Y., Teo, J., Karaman, S., Frazzoli, E., and How, J., “Motion Planning in Complex Environments Using Closed-Loop Prediction”, Proceedings with AIAA Guidance, Navigation, and Control Conference Exhibition, Honolulu, HI, August 2008. AIAA 2008-3257.

Yershova, A., Jaillet, L., Simeon, T., and LaValle, S., “Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain”, Proceeding of 2005 IEEE Conference on Robotics and Automation, Barcelona, Spain, April 2005.

Urmson, C., and Simmons, R., “Approaches for Heuristically Biasing

RRT Growth”, Proceedings of IEEE 2003 International Conference on Intelligent Robots and Systems, Las Vegas, NV USA, Oct. 27-31, 2003.

Gammell, J., Srinivasa, S., and Barfoot, T., “Informed RRT*: Optimal

Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic”, IEEE 2014 International Conference on Intelligent Robots and Systems, Chicago, IL USA, Sept. 14-18, 2014.

LaValle, S., Planning Algorithms, Cambridge University Press, 2006.

Karaman, S., Frazzoli, E., “Sampling-based Algorithms for Optimal

Motion Planning”, the International Journal of Robotics Research, Vol. 30, No. 7, pp. 846-894, June 2011.

Jacobs, P., and Taix, M., “Efficcient Motion Planners for Nonholonomic

Mobile Robots”, Proceedings of International Workshop on Intelligent Robots and Systems, Osaka Japan, Nov. 3-5, 1991.




DOI: http://dx.doi.org/10.21535%2FProICIUS.2015.v11.687

Refbacks

  • There are currently no refbacks.