Motion Primitives in the Trajectory Planning Problem with Kinematic Constraints

Cover Page

Cite item

Full Text

Abstract

Automatic trajectory planning is an urgent scientific and technical problem, whose solutions are in demand in many fields: unmanned transportation, robotic logistics, social robotics, etc. Often, when planning a trajectory, it is necessary to consider the fact that the agent (robot, unmanned car, etc.) cannot arbitrarily change its orientation while moving, in other words, it is necessary to consider kinematic constraints when planning. One widespread approach to solving this problem is the approach that relies on the construction of a trajectory from prepared parts, motion primitives, each of which satisfies kinematic constraints. Often, the emphasis in the development of methods implementing this approach is on reducing the combinations of choices in planning (heuristic search), with the set of available primitives itself being regarded as externally defined. In this paper, on the contrary, we aim to investigate and analyze the effect of different available motion primitives on the quality of solving the planning problem with a fixed search algorithm. Specifically, we consider 3 different sets of motion primitives for a wheeled robot with differential drive. As a search algorithm, the A* algorithm well known in artificial intelligence and robotics is used. The solution quality is evaluated by 6 metrics, including planning time, length and curvature of the resulting trajectory. Based on the study, conclusions are made about the factors that have the strongest influence on the planning result, and recommendations are given on the construction of motion primitives, the use of which allows to achieve a balance between the speed of the planning algorithm and the quality of the trajectories found.

About the authors

V. A Golovin

Moscow Institute of Physics and Technology (MIPT)

Email: golovin.va@phystech.edu
Institutskiy Lane 9

K. S Yakovlev

Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences (FRC CSC RAS)

Email: yakovlev@isa.ru
60-letiya Oktyabrya Ave. 9

References

  1. Дудакова Д.С., Анохин В.М., Дудаков М.О., Ронжин А.Л. О теоретических основах аэролимнологии: изучение пресных водоемов и прибрежных территорий с применением воздушных робототехнических средств // Информатика и автоматизация. 2022. Т. 21. № 6. С. 1359–1393.
  2. Балабанов А.Н., Безуглая А.Е., Шушляпин Е.А. Управление манипулятором подводного робота // Информатика и автоматизация. 2021. Т. 20. № 6. С. 1307–1332. doi: 10.15622/ia.20.6.5.
  3. Макаров Д.А., Панов А.И., Яковлев К.С. Архитектура многоуровневой интеллектуальной системы управления беспилотными летательными аппаратами // Искусственный интеллект и принятие решений. 2015. № 3. С. 18–33.
  4. Otsu K., Matheron G., Ghosh S., Toupet O., Ono M. Fast approximate clearance evaluation for rovers with articulated suspension systems // Journal of Field Robotics. 2020. vol. 37. no. 5. pp. 768–785.
  5. Al Mashhadany Y.I. Design and analysis of 7-DOF human-link manipulator based on hybrid intelligent controller // Informatics and Automation. 2020. vol. 19. no. 4. pp. 774–802.
  6. Пшихопов В.Х., Медведев М.Ю. Планирование движения группы подвижных объектов в двумерной среде с препятствиями // Известия Южного федерального университета. Технические науки. 2016. Т. 2(175). С. 6–22.
  7. LaValle S.M. Rapidly-exploring random trees: A new tool for path planning. Research Report 9811. 1998.
  8. Kuffner J.J., LaValle S.M. RRT-connect: An efficient approach to single-query path planning // Proceedings ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings. 2000. vol. 2. pp. 995–1001.
  9. Sharma P., Gupta A., Ghosh D., Honkote V., Nandakumar G., Ghose, D. PG-RRT: A Gaussian Mixture Model Driven, Kinematically Constrained Bi-directional RRT for Robot Path Planning // Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 2021. pp. 3666–3673.
  10. Webb D.J., Van Den Berg J. Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics // IEEE international conference on robotics and automation. IEEE. 2013. pp. 5054–5061.
  11. Gammell J.D., Srinivasa S.S., Barfoot T.D. Informed RRT: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic // IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE. 2014. pp. 2997–3004.
  12. Zhang Y., Sun H., Zhou J., Pan J., Hu J., Miao J. Optimal vehicle path planning using quadratic optimization for baidu apollo open platform // IEEE Intelligent Vehicles Symposium (IV). IEEE. 2020. pp. 978–984.
  13. Li B., Wang K., Shao Z. Time-optimal maneuver planning in automatic parallel parking using a simultaneous dynamic optimization approach // IEEE Transactions on Intelligent Transportation Systems. 2016. vol. 17. no. 11. pp. 3263–3274.
  14. Karlsson J., Murgovski N., Sjoberg J. Computationally efficient autonomous overtaking on highways // IEEE Transactions on Intelligent Transportation Systems. 2019. vol. 21. no. 8. pp. 3169–3183.
  15. Heiden E., Palmieri L., Koenig S., Arras K.O., Sukhatme G.S. Gradient-informed path smoothing for wheeled mobile robots // Proceedings of the IEEE International Conference on Robotics and Automation. 2018. pp. 1710–1717.
  16. Yongzhe Z., Ma B., Wai C.K. A practical study of time-elastic-band planning method for driverless vehicle for auto-parking // International Conference on Intelligent Autonomous Systems (ICoIAS). IEEE. 2018. pp. 196–200.
  17. Kicki P., Gawron T., Cwian K., Ozay M., Skrzypczynski P. Learning from experience for rapid generation of local car maneuvers // Engineering Applications of Artificial Intelligence. 2021. vol. 105. pp. 104399. doi: 10.1016/j.engappai.2021.104399.
  18. Vitelli M., Chang Y., Ye Y., Ferreira A., Wolczyk M., Osinski B., Niendorf M., Grimmett H., Huang Q., Jain A., Ondruska P. Safetynet: Safe planning for real-world self-driving vehicles using machine-learned policies // International Conference on Robotics and Automation (ICRA). IEEE. 2022. pp. 897–904.
  19. Nasiriany S., Pong V., Lin S., Levine S. Planning with goal-conditioned policies // Advances in Neural Information Processing Systems. 2019. vol. 32.
  20. Chen L., Hu X., Tang B., Cheng Y. Conditional DQN-Based Motion Planning With Fuzzy Logic for Autonomous Driving // IEEE Transactions on Intelligent Transportation Systems. 2020. vol. 23. no. 4. pp. 2966–2977.
  21. Wu K., Wang H., Esfahani M.A., Yuan S. Achieving Real-Time Path Planning in Unknown Environments Through Deep Neural Networks. IEEE Transactions on Intelligent Transportation Systems. 2022. vol. 23. no. 3. pp. 2093–2102.
  22. Cohen B.J., Chitta S., Likhachev M. Search-based planning for manipulation with motion primitives // IEEE International Conference on Robotics and Automation. 2010. pp. 2902–2908. doi: 10.1109/ROBOT.2010.5509685.
  23. Low T., Bandyopadhyay T., Borges P.V. Identification of effective motion primitives for ground vehicles // IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE. 2020. pp. 2027–2034.
  24. Wang B., Gong J., Chen H. Motion primitives representation, extraction and connection for automated vehicle motion planning applications // IEEE Transactions on Intelligent Transportation Systems. 2019. vol. 21. no. 9. pp. 3931–3945.
  25. Jarin-Lipschitz L., Paulos J., Bjorkman R., Kumar V. Dispersion-minimizing motion primitives for search-based motion planning // IEEE International Conference on Robotics and Automation (ICRA). IEEE. 2021. pp. 12625–12631.
  26. Bergman K., Ljungqvist O., Axehill D. Improved optimization of motion primitives for motion planning in state lattices // IEEE Intelligent Vehicles Symposium (IV). IEEE. 2019. pp. 2307–2314.
  27. Koutras L., Doulgeri Z. Dynamic movement primitives for moving goals with temporal scaling adaptation // IEEE International Conference on Robotics and Automation (ICRA). IEEE. 2020. pp. 144–150.
  28. Abu-Dakka F.J., Kyrki V. Geometry-aware dynamic movement primitives // IEEE International Conference on Robotics and Automation (ICRA). IEEE. 2020. pp. 4421–4426.
  29. Sood R., Vats S., Likhachev M. Learning to use adaptive motion primitives in search-based planning for navigation // IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE. 2020. pp. 6923–6929.
  30. Chernik C., Tajvar P., Tumova J. Robust Feedback Motion Primitives for Exploration of Unknown Terrains // IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE. 2021. pp. 8173–8179.
  31. Palmieri L., Arras K.O. A novel RRT extend function for efficient and smooth mobile robot motion planning // Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2014. pp. 205–211.
  32. Яковлев К.С., Белинская Ю.С., Макаров Д.А., Андрейчук А.А. Безопасно-интервальное планирование и метод накрытий для управления движением мобильного робота в среде со статическими и динамическими препятствиями // Автоматика и телемеханика. 2022. № 6. С. 96–117.
  33. Wang X., Krasowski H., Althoff M. CommonRoad-RL: A configurable reinforcement learning environment for motion planning of autonomous vehicles // IEEE International Intelligent Transportation Systems Conference (ITSC). IEEE. 2021. pp. 466–472.
  34. Ilievski M. Wisebench: A motion planning benchmarking framework for autonomous vehicles: MS thesis. Ontario: University of Waterloo, 2020. 129 p.
  35. Xu C., Ding W., Lyu W., Liu Z., Wang S., He Y., Hu H., Zhao D., Li B. SafeBench: A Benchmarking Platform for Safety Evaluation of Autonomous Vehicles // Advances in Neural Information Processing Systems. 2022. vol. 35. pp. 25667–25682.
  36. Heiden E., Palmieri L., Bruns L., Arras K.O., Sukhatme G.S., Koenig S. Bench-MR: A motion planning benchmark for wheeled mobile robots // IEEE Robotics and Automation Letters. 2021. vol. 6. no. 3. pp. 4536–4543.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».