PATH PLANNING OF TRACTOR-TRAILER ROBOT BY FAST MARCHING METHODE (FMM)

Authors

modarres

Abstract

This paper deals with motion planning of Tractor-trailer robots, which are car-like robot dragging several trailers with no driving force. Each trailer has a nonholonomic kinematic constraint which increases the complexity of the path planning problem. We solved this problem by implementing the Equivalent Size concept, which depending on the size, number, and link-point positions of trailers, transforms a tractor-trailer path planning problem into a single car-like robot path planning problem. In this paper a new path planning algorithm is proposed for car-like robots which utilizes the Fast Marching Method (FMM), which is a numerical method for solving the Eikonal differential equation, and the concept of Virtual Obstacles. The algorithm is fast, works independent of the shape of obstacles, and is easy to implement. To evaluate the quality of the solutions the algorithm is compared with the grid search and nonholonomic RRT algorithms. The results showed that the new method has by far lower runtime compared to the other algorithms, while producing short and smooth paths.

Keywords

References

1-      
[1]     Gonzalez-Banos, H.H. Hsu, D., and Latombe, J.C., “Motion planning: Recent developments,” In S.S. Ge and F.L. Lewis, editors, Autonomous Mobile Robots: Sensing, Control, Decision-Making and Applications, CRC Press, 2006.
[2]     Lozano-Pérez, T., and Wesley, M.A., “An algorithm for planning collision-free paths among polyhedral obstacles,” Communications of ACM, Vol. 22, No. 10, pp. 560–570, (1979).
[3]     Vasseur, H.A., Pin, F.G., and Taylort, J.R., “Navigation of car-like mobile robot using a decomposition of the environment in convex cell,” in Proc. IEEE ICRA, Sacramento, California, (1991).
[4]     Latombe, J.C., “Robot motion planning”, Kluwer Academic Publishers, (1991).
[5]     Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L., and Thrun, S., “Principle of Robot Motion: Theory, Algorithms, and Application”. MIT Press, Cambridge, (2005).
[6]     Dubins, L.E., “On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents,” American Journal of Math. Vol. 79, pp. 497–516, (1957).
[7]     Reeds, J.A., and Shepp, L.A., “Optimal paths for a car that goes both forwards and backwards,” Pacific Journal of Mathe­matics, vol. 145, no 2. pp 367–393, (1990).
[8]     Barraquand, J., and Latombe, J.C., “Non­holonomic Multibody Mobile Robots: Con­trollability and Motion Planning in the Presence of Obstacles,” Algorith­mica, Vol. 10, No. 2, p. 121–155, (1993).
[9]     Kuffner, J.J., and LaValle, S.M., “RRT-connect: An efficient approach to single-query path planning,” in Proc. of IEEE International Conf. on Robotics and Automation, Vol. 2, pp. 995–1001, (2002).
[10] Laumond, J.P., Jacobs, P.E., Taix, M., and Murray, R.M., “A motion planner for nonholonomic mobile robots,” IEEE Transactions on Robotics and Automation, Vol. 10, No. 5, (1994).
[11] Sánchez, A.L., Zapata, R., and Are­nas, A.B., “Motion planning for car-like ro­bots using lazy probabilistic roadmap method,” in Proc. MICAI 2002, pp. 1–10, (2002).
[12] Guang, S., and Nancy, A.M., “Randomized motion planning for car-like robots with C-PRM,” in Proc. IEEE Int. Conf. on Robotics and Automation, Vol. 1. pp. 37–42, (2002).
[13] LaValle, S.M., “Planning algorithms”, Cambridge University Press, (2006).
[14] Svestka, P., and Vleugels, J., “Exact motion planning for tractor-trailer robots,” in Proc. of IEEE International Conference on Robotics and Automation, vol. 3, pp. 2445–2450, (1995).
[15] Sekhavat, S., Svestka, P., Laumond, J. P., and Overmars, M.H., “Multilevel path planning for non­holonomic robots using semiholonomic subsystems,” The International Journal of Robotics Research, Vol. 17, No. 8, p. 840–857, (1998).
[16] Yuan, J., Huang, Y., Sun, F., and Kang, Y., “Computation of equivalent size for tractor-trailer wheeled mobile robot,” 5th World Congress on Intelligent Control and Automation, pp. 4788–4792, Hangzhou, China, (2004).
[17] Liu, Z.J., Huang, P., Huang, J.L., and Que, J.L., “Path planning for tractor-trailer mobile robot based on heuristic genetic algorithm,” in Proceedings of International Conference on Machine Learning and Cybernetics, Vol. 2, pp. 1119–1124, (2004).
[18] Sun, F., Huang, Y., Yuan, J., Kang, Y., and Ma, F., “A Compound PRM Method for Path Planning of the Tractor-Trailer Mobile Robot,” in Proceedings of IEEE International Conference on Automation and Logistics, pp. 1880–1885, (2007).
[19] http://math.berkeley.edu/~sethian/2006/Applications/Robotics/robotics.html.
[20] Farag, A.A., and Hassouna, M.S. “Theoretical foundations of tracking monotonically advancing fronts using fast marching level set method,” Technical Report, Computer Vision and Image Processing Lab., ECE Dept., University of Louisville, (2005).
[21] Sethian, J.A., “A fast marching level set method for monotonically advancing fronts,” in Proc. National Academy of Science, USA, Vol. 93, No. 4, pp. 1591–1595, (1996).
[22] Li, Y., “Real-time motion planning of multiple agents and formations in virtual environments,” PhD Thesis, Simon Fraser University, (2008).
[23] Chiang, C.H., Chiang, P.J., Fei, J.C.C., and Liu, J.S., “A comparative study of implementing fast marching method and A* search for mobile robot path planning in grid environment: effect of map resolution,” National Science Council under contract NSC 96-2221-E-001-018-MY2, (2007).
[24] Garrido, S., Moreno, L., Blanco, D., and Martin, F., “Exploratory navigation based on Voronoi transform and fast marching,” in IEEE International Symposium on Intelligent Signal Processing, pp. 1–6, (2007).
[25] Chiang, C.H., and Liu, J.S., “Boundary following in unknown polygonal environment based on fast marching method,” National Science Council, (2008).
[26] Cohen, L.D., and Kimmel, R., “Global minimum for active contour models: a minimal path approach,” Int. Journal of Computer Vision, Vol. 24, No. 1, pp. 57–78, (1997).
[27] Petres, C., Pailhas, Y., Patron, P., Petillot, Y., Evans, J., and Lane, D., “Path planning for autonomous underwater vehicles,” IEEE Transaction on Robotics, Vol. 23, No. 2, pp. 331–341, (2007).
[28] Gonzalez, R.C. and Woods, R.E., “Digital Image Processing”, Addison-Wesley, ISBN 0-201-60078-1, pp. 231–235 (1993).
[29] جنّت، داود، برنامه­ریزی حرکت بهنگام روبات­های ماشین­واره منفرد و چندتایی با استفاده از روش پیشروی سریع (FMM)، پایان نامه کارشناسی ارشد، دانشگاه تربیت مدرس، اردیبهشت 89.
[30] P. Cheng, Z. Shen, and S.M. LaValle, “RRT-based trajectory design for autonomous automobiles and spacecraft,” Archives of Control Science, vol. 11, 2001, pp. 167–194.
 
 
Journal of Modeling in Engineering
Volume 11, Issue 34
October 2013
Pages 31-47

Files

History

  • Receive Date: 28 January 2017
  • Revise Date: 25 September 2017
  • Accept Date: 28 January 2017

Share

How to cite

Statistics