Примитивы движения робота в задаче планирования траектории с кинематическими ограничениями
Ключевые слова:
планирование траектории, кинематическое планирование, примитивы движения, эвристический поискАннотация
Автоматическое планирование траектории – актуальная научно-техническая задача, решения которой востребованы во многих областях: беспилотный транспорт, роботизированная логистика, социальная робототехника и т.д. Зачастую при планировании траектории необходимо учитывать тот факт, что агент (робот, беспилотный автомобиль и др.) не может произвольно менять ориентацию при движении, другими словами – необходимо учитывать кинематические ограничения при планировании. Одним из широко-распространенных подходов к решению этой задачи является подход, опирающийся на конструирование траектории из заранее подготовленных фрагментов, примитивов движения, каждый из которых в свою очередь удовлетворяет кинематическим ограничениям. Зачастую, акцент при разработке методов, реализующих этот подход, делается на сокращении перебора вариантов при планировании (эвристический поиск), при этом сам набор доступных примитивов считается заданным извне. В этой же работе, мы наоборот ставим своей целью провести исследование и анализ влияния различных доступных примитивов движения на качество решения задачи планирования при фиксированном алгоритме поиска. В частности, рассматриваются 3 различных набора примитивов движения для колесного робота с дифференциальным приводом. В качестве алгоритма поиска используется известный в искусственном интеллекте и робототехнике алгоритм A*. Качество решения оценивается по 6 метрикам, включая время планирования, длину и кривизну результирующей траектории. На основании проведенного исследования делаются выводы о факторах, оказывающих наибольшее влияние на результат планирования, и даются рекомендации по построению примитивов движения, использование которых позволяет достичь баланса между скоростью работы алгоритма планирования и качеством отыскиваемых траекторий.
Литература
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.
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.
Опубликован
2023-11-10
Как цитировать
Головин, В. А., & Яковлев, К. С. (2023). Примитивы движения робота в задаче планирования траектории с кинематическими ограничениями. Информатика и автоматизация, 22(6), 1354-1386. https://doi.org/10.15622/ia.22.6.4
Раздел
Робототехника, автоматизация и системы управления
Copyright (c) Владислав Андреевич Головин, Константин Сергеевич Яковлев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).