Trajectory planning for narrow environments that require changes of driving directions

• Autorzy: Roth Jörg

Identyfikatory

DOI

10.14313/JAMRIS/4-2021/23

• Języki publikacji: EN

Abstrakty

EN

In the area of mobile robotics, trajectory planning is the task to find a sequence of primitive trajectories that connect two configurations, whereas non-holonomic constraints, obstacles and driving costs have to be considered. In this paper, we present an approach that is able to handle situations that require changes of driving directions. In such situations, optimal trajectory sequences contain costly turning maneuvers – sometimes not even on the direct path between start and target. These situations are difficult for most optimization approaches as the robot partly has to drive paths with higher cost values that seem to be disadvantageous. We discuss the problem in depth and provide a solution that is based on maneuvers, partial backdriving and free-place discovery. We applied the approach on top of our Viterbi-based trajectory planner.

Słowa kluczowe

EN

mobile robot; navigation; trajectory planning; complex turning situations

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2021
• Tom: Vol. 15, No. 4
• Strony: 18--29
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Roth Jörg

• Faculty of Computer Science, Nuremberg Institute of Technology, Nuremberg, Germany

Bibliografia

• [1] L. Barraquand, B. Langlois and J. -C. Latombe, “Numerical potential field techniques for robot path planning”, IEEE Trans. on Syst., Man., and Cybern., vol. 22, no. 2, 1992, 224–241, 10.1109/21.148426.
• [2] J. D. Boissonnat, A. Cerezo and J. Leblond, “A note on shortest paths in the plane subject to a constraint on the derivative of the curvature”, Research Report 2160, Inst. Nat. de Recherche en Informatique et an Automatique, 1994.
• [3] X. N. Bui, J. D. Boissonnat, P. Soueres and J. P. Laumond, “Shortest Path Synthesis for Dubins Non--Holonomic Robot”. In: IEEE Conf. on Robotics and Automation, San Diego, CA, USA, 1994, 2–7,10.1109/ROBOT.1994.351019.
• [4] M. Čikeš, M. Đakulović and I. Petrović, “The path planning algorithms for a mobile robot based on the occupancy grid map of the environment – A comparative study”. In: XXIII Intern. Symposium on Information, Communication and Automation Technologies, Sarajevo, 2011, 1–8, 10.1109/ICAT.2011.6102088.
• [5] L. E. Dubins, “On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents”, American Journal of Mathematics, vol. 79, no. 3, 1957, 497–516, 10.2307/2372560.
• [6] S. Garrido and L. Moreno, “Mobile Robot Path Planning using Voronoi Diagram and Fast Marching”, Robotics, Automation, and Control in Industrial and Service, 2015, 10.4018/978-1-4666-8693-9.
• [7] T. Gu and J. M. Dolan, “On-Road Motion Planning for Autonomous Vehicles”. In: Su, CY., Rakheja, S., Liu, H. (eds) Intelligent Robotics and Applications. ICIRA, 2012, 588–597, 10.1007/978-3-642-33503-7_57.
• [8] P. E. Hart, N. J. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, no. 2, 1968, 100–107, 10.1109/TSSC.1968.300136.
• [9] S. Karaman and E. Frazzoli, “Incremental sampling-based algorithms for optimal motion planning”, Robotics Science and Systems, no. VI 104.2, 2010, 10.48550/arXiv.1005.0416.
• [10] S. Karaman, M. R. Walter, A. Perez, E. Frazzoli and S. Teller, “Anytime Motion Planning using theRRT*”. In: 2011 IEEE International Conference on Robotics and Automation, 2011, 4307–4313, 10.1109/ICRA.2011.5980479.
• [11] J.-P. Laumond, P. E. Jacobs, M. Taïx and R. M. Murray, “A Motion Planner for Nonholonomic Mobile Robots”, IEEE Transactions on Robotics and Automation, vol. 10, no. 5, 1994, 577–593, 10.1109/70.326564.
• [12] S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning”, Technical Report 98-11, Computer Science Dept., Iowa State University, 1998.
• [13] S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic planning”, International Journal of Robotics Research, vol. 20, no. 5, 2001, 378–400, 10.1177/02783640122067453.
• [14] M. Mukadam, X. Yan and B. Boots, “Gaussian Process Motion Planning”. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), 2016, 9–15, 10.1109/ICRA.2016.7487091.
• [15] V. F. Muñoz and A. Ollero, “Smooth Trajectory Planning Method for Mobile Robots”. In: Proc. of the Congress on Comp. Engineering in System Applications, Lille, France, 1995, 700–705.
• [16] M. Pitvoraiko and A. Kelly, “Efficient constrained path planning via search in state lattices”. In: Proceedings of 8th International Symposium on Artificial Intelligence, Robotics and Automation in Space (iSAIRAS ‘05), 2005.
• [17] J. A. Reeds and L. A. Shepp, “Optimal paths for a car that goes both forwards and backwards”,Pacific Journal of Mathematics, no. 145, 1990, 367–393.
• [18] J. Roth, “Efficient Computation of Bypass Areas”. In: Progress in Location-Based Services 2016, Proc. of the 13th Intern. Symposium on Location--Based Services, Vienna, Austria, 2016, 193–210, 10.1007/978-3-319-47289-8_10.
• [19] J. Roth, “A Viterbi-like Approach for Trajectory Planning with Different Maneuvers”. In: Intern. Conf. on Intelligent Autonomous Systems 15, 2018, Baden-Baden (Germany), 2018, 10.1007/978-3-030-01370-7_1.
• [20] J. Roth, “Robots in the Classroom – Mobile Robot Projects in Academic Teaching”. In: Innovations for Community Services. I4CS 2019., vol. CCIS 14041, 2019, 10.1007/978-3-030-22482-0_4.
• [21] J. Roth, “Continuous-Curvature Trajectory Planning”, Journal of Automation, Mobile Robotics and Intelligent Systems, vol. 15, no. 1, 2021, 9–23, 10.14313/JAMRIS/1-2021/2.
• [22] A. Scheuer and T. Fraichard, “Continuous--Curvature Path Planning for Car-Like Vehicles”. In: Proceedings of the 1997 IEEE/RSJ International Conference on Intelligent Robot and Systems. Innovative Robotics for Real--World Applications. IROS ‘97, 1997, 10.1109/IROS.1997.655130.
• [23] A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm”, IEEE Transactions on Information Theory, vol. 13, no. 2, 1967, 260–269, 10.1109/TIT.1967.1054010.
• [24] Y. You, C. Cai and Y. Wu, “3D Visibility Graph based Motion Planning and Control”. In: ICRAI ‘19: Proceedings of the 2019 5th International Conference on Robotics and Artificial Intelligence, 2019, 10.1145/3373724.3373735.
• [25] J. Zhang, Z. Shi, X. Yang and J. Zhao, “Trajectory planning and tracking control for autonomous parallel parking of a non-holonomic vehicle”, Measurement and Control, vol. 53, no. 9-10, 2020, 1800–1816, 10.1177/0020294020944961.
• [26] Z. Zhang, S. Lu, L. Xie, H. Su, D. Li, Q. Wang and W. Xu, “A guaranteed collision-free trajectory planning method for autonomous parking”, IET Intelligent Transport Systems, vol. 15, no. 2, 2021, 331–343, 10.1049/itr2.12028.
• [27] M. Zucker, N. Ratliff, A. Dragan, M. Pivtoraiko, M. Klingensmith, C. Dellin, J. A. Bagnell and S. Srinivasa, “CHOMP: Covariant Hamiltonian Optimization for Motion Planning”, International Journal of Robotics Research, 2013, 10.1177/0278364913488805.