Эффективный метод генерации кинематически-согласованных примитивов движения на основе параметризации по кривизне
Ключевые слова:
планирование траекторий, решётка состояний, примитивы движения, кинематические ограничения, беспилотный автомобиль, велосипедная модель, метод НьютонаАннотация
Планирование движения для мобильных роботов и беспилотных автомобилей является одной из ключевых задач современной робототехники. Основная её сложность заключается в необходимости учёта кинематических ограничений, таких как гладкость траектории и ограничения на минимальный радиус поворота. Одним из наиболее часто используемых подходов к решению этой задачи является построение траектории из набора заранее сгенерированных, кинематически-согласованных фрагментов, называемых примитивами движения. Робастность и скорость генерации этих примитивов напрямую определяют эффективность всего процесса планирования. В данной работе предлагается новый метод генерации примитивов движения для систем с кинематикой велосипедного типа. Метод основан на представлении траектории в виде кривой с полиномиальной функцией кривизны, а задача генерации примитива, соединяющего два заданных состояния (положение, ориентация, кривизна), сводится к решению системы нелинейных уравнений методом Ньютона. В отличие от существующих подходов, использующих коэффициенты полинома в качестве параметров, применяется новая репараметризация, основанная на значениях кривизны в ключевых точках траектории. Такая параметризация позволяет улучшить сходимость и устойчивость численного метода поиска решения, что демонстрируют проведённые эксперименты.
Литература
1. Pivtoraiko M., Kelly A. Efficient constrained path planning via search in state lattices // International Symposium on Artificial Intelligence, Robotics, and Automation in Space. 2005. pp. 1–7.
2. Pivtoraiko M., Knepper R.A., Kelly A. Differentially constrained mobile robot motion planning in state lattices // Journal of Field Robotics. 2009. vol. 26. no. 3. pp. 308–333. DOI: 10.1002/rob.20285.
3. Pivtoraiko M., Kelly A. Kinodynamic motion planning with state lattice motion primitives // Proceedings of 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. pp. 2172–2179. DOI: 10.1109/IROS.2011.6094900.
4. Hart P.E., Nilsson N.J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE Transactions on Systems Science and Cybernetics. 1968. vol. 4. no. 2. pp. 100–107. DOI: 10.1109/TSSC.1968.300136.
5. Ebendt R., Drechsler R. Weighted A* search – unifying view and application // Artificial Intelligence Journal. 2009. vol. 173. no. 14. pp. 1310–1342. DOI: 10.1016/j.artint.2009.06.004.
6. Nagy B., Kelly A. Trajectory generation for car-like robots using cubic curvature polynomials // Field and Service Robotics. 2001. vol. 11. pp. 479–490.
7. Harabor D., Grastien A. Online graph pruning for pathfinding on grid maps // Proceedings of the 25th AAAI Conference on Artificial Intelligence. 2011. vol. 25. no. 1. pp. 1114–1119. DOI: 10.1609/aaai.v25i1.7994.
8. Carlson M., Moghadam S.K., Harabor D.D., Stuckey P.J., Ebrahimi M. Optimal pathfinding on weighted grid maps // Proceedings of the 37th AAAI Conference on Artificial Intelligence. 2023. vol. 37. no. 10. pp. 12373–12380. DOI: 10.1609/aaai.v37i10.26458.
9. Nobes T.K., Harabor D., Wybrow M., Walsh S.D.C. The JPS pathfinding system in 3D // Proceedings of the 15th International Symposium on Combinatorial Search. 2022. vol. 15. no. 1. pp. 145–152. DOI: 10.1609/socs.v15i1.21762.
10. Daniel K., Nash A., Koenig S., Felner A. Theta*: Any-angle path planning on grids // Journal of Artificial Intelligence Research. 2010. vol. 39. pp. 533–579. DOI: 10.1613/jair.2994.
11. Ahmadi S., Tack G., Harabor D.D., Kilby P. A fast exact algorithm for the resource constrained shortest path problem // Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021. vol. 35. no. 14. pp. 12217–12224. DOI: 10.1609/aaai.v35i14.17450.
12. Ahmadi S., Tack G., Harabor D.D., Kilby P. Weight constrained path finding with bidirectional A* // Proceedings of the 15th International Symposium on Combinatorial Search. 2022. vol. 15. no. 1. pp. 2–10. DOI: 10.1609/socs.v15i1.21746.
13. Cohen B.J., Chitta S., Likhachev M. Search-based planning for manipulation with motion primitives // 2010 IEEE International Conference on Robotics and Automation. 2010. pp. 2902–2908. DOI: 10.1109/ROBOT.2010.5509685.
14. Kang G., Kim Y.B., Lee Y.H., Oh H.S., You W.S., Choi H.R. Sampling-based motion planning of manipulator with goal-oriented sampling // Intelligent Service Robotics. 2019. vol. 12. pp. 265–273. DOI: 10.1007/s11370-019-00281-y.
15. Phillips M., Likhachev M. SIPP: Safe interval path planning for dynamic environments // 2011 IEEE International Conference on Robotics and Automation. 2011. pp. 5628–5635. DOI: 10.1109/ICRA.2011.5980306.
16. Yakovlev K., Andreychuk A., Stern R. Revisiting bounded-suboptimal safe interval path planning // Proceedings of the 30th International Conference on Automated Planning and Scheduling. 2020. vol. 30. no. 1. pp. 300–304. DOI: 10.1609/icaps.v30i1.6674.
17. Rybecky T., Kulich M., Andreychuk A., Yakovlev K. Towards narrowing the search in bounded-suboptimal safe interval path planning // Proceedings of the 12th International Symposium on Combinatorial Search, SoCS 2021. 2021. vol. 12. no. 1. pp. 136–140. DOI: 10.1609/socs.v12i1.18562.
18. Ren Z., Rathinam S., Likhachev M., Choset H. Multi-objective safe-interval path planning with dynamic obstacles // IEEE Robotics and Automation Letters. 2022. vol. 7. no. 3. pp. 8154–8161. DOI: 10.1109/LRA.2022.3187270.
19. Gonzalez D., Perez J., Milanes V., Nashashibi F. A review of motion planning techniques for automated vehicles // IEEE Transactions on Intelligent Transportation Systems. 2016. vol. 17. no. 4. pp. 1135–1145. DOI: 10.1109/TITS.2015.2498841.
20. La Valle S.M., Kuffner Jr J.J. Randomized kinodynamic planning // The International Journal of Robotics Research. 2001. vol. 20. no. 5. pp. 378–400. DOI: 10.1177/02783640122067453.
21. Karaman S., Frazzoli E. Incremental sampling-based algorithms for optimal motion planning // Robotics: Science and Systems. 2010. vol. 104. no. 2. pp. 267–274. DOI: 10.1177/0278364911406761.
22. Otte M., Frazzoli E. RRTX: Real-time motion planning/replanning for environments with unpredictable obstacles // Algorithmic Foundations of Robotics XI. Springer Tracts in Advanced Robotics. 2015. vol. 107. pp. 461–478. DOI: 10.1007/978-3-319-16595-0_27.
23. Paudel A. Motion primitives based path planning with rapidly-exploring random tree. arXiv preprint arXiv: 2210. 15784. 2022.
24. Головин В.А., Яковлев К.С. Примитивы движения робота в задаче планирования траектории с кинематическими ограничениями // Информатика и автоматизация. 2023. Т. 22. №6. C. 1354–1386. DOI: 10.15622/ia.22.6.4.
25. Jingyu Y., Jianjun M. Search-based trajectory planning with motion primitives for quadrotors using pruning A* algorithm // 2022 37th Youth Academic Annual Conference of Chinese Association of Automation (YAC). 2022. pp. 996–1000. DOI: 10.1109/YAC57282.2022.10023615.
26. Scharff J., Gonzalez D., Hernandez J.D., Pairet E., Petillot Y. Online 3-dimensional path planning with kinematic constraints in unknown environments using hybrid A* with tree pruning // Sensors. 2021. vol. 21. no. 4. 1152. p.
27. Agranovskiy M., Yakovlev K. MeshA*: Efficient path planning with motion primitives // Proceedings of the 40th AAAI Conference on Artificial Intelligence. 2026. vol. 40. no. 43. pp. 36785–36792. DOI: 10.1609/aaai.v40i43.41004.
28. Piazzi A., Bianco C.G.L., Bertozzi M., Fascioli A., Broggi A. Quintic G/sup 2/-splines for the iterative steering of vision-based autonomous vehicles // IEEE Transactions on Intelligent Transportation Systems. 2002. vol. 3. no. 1. pp. 27–36. DOI: 10.1109/6979.994793.
29. Walton D.J., Meek D.S. A controlled clothoid spline // Computers & Graphics. 2005. vol. 29. no. 3. pp. 353–363. DOI: 10.1016/j.cag.2005.03.008.
30. Farouki R.T. Pythagorean-hodograph curves: algebra and geometry inseparable // Geometry and Computing. Springer. 2008. vol. 1. pp. 131–196. DOI: 10.1007/978-3-540-73398-0_8.
31. Яковлев К.С., Белинская Ю.С., Макаров Д.А., Андрейчук А.А. Безопасно-интервальное планирование и метод накрытий для управления движением мобильного робота в среде со статическими и динамическими препятствиями // Автоматика и телемеханика. 2022. №6. C. 96–117. DOI: 10.31857/S0005231022060083.
32. De Iaco R., Smith S.L., Czarnecki K. Learning a lattice planner control set for autonomous vehicles // IEEE Intelligent Vehicles Symposium (IV). 2019. pp. 549–556. DOI: 10.1109/IVS.2019.8813797.
33. Weaver C., Capobianco R., Wurman P.R., Stone P., Tomizuka M. Real-time trajectory generation via dynamic movement primitives for autonomous racing // 2024 American Control Conference (ACC). 2024. pp. 352–359. DOI: 10.23919/ACC60939.2024.10644244.
34. Franke J., Moldagalieva A., Hanfeld P., Honig W. Accelerating db-A* for kinodynamic motion planning using diffusion. arXiv preprint arXiv: 2503. 05539. 2025.
35. Kraljusic B., Ajanovic Z., Covic N., Lacevic B. Search-based robot motion planning with distance-based adaptive motion primitives // 2025 XXX International Conference on Information, Communication and Automation Technologies (ICAT). 2025. pp. 1–6. DOI: 10.1109/ICAT66432.2025.11189289.
36. Yao Y., Liu S., Song H., Qu D., Chen Q., Ding Y., Zhao B., Wang Z., Li X., Wang D. Think small, act big: primitive prompt learning for lifelong robot manipulation // Proceedings of the Computer Vision and Pattern Recognition Conference. 2025. pp. 22573–22583.
2. Pivtoraiko M., Knepper R.A., Kelly A. Differentially constrained mobile robot motion planning in state lattices // Journal of Field Robotics. 2009. vol. 26. no. 3. pp. 308–333. DOI: 10.1002/rob.20285.
3. Pivtoraiko M., Kelly A. Kinodynamic motion planning with state lattice motion primitives // Proceedings of 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. pp. 2172–2179. DOI: 10.1109/IROS.2011.6094900.
4. Hart P.E., Nilsson N.J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE Transactions on Systems Science and Cybernetics. 1968. vol. 4. no. 2. pp. 100–107. DOI: 10.1109/TSSC.1968.300136.
5. Ebendt R., Drechsler R. Weighted A* search – unifying view and application // Artificial Intelligence Journal. 2009. vol. 173. no. 14. pp. 1310–1342. DOI: 10.1016/j.artint.2009.06.004.
6. Nagy B., Kelly A. Trajectory generation for car-like robots using cubic curvature polynomials // Field and Service Robotics. 2001. vol. 11. pp. 479–490.
7. Harabor D., Grastien A. Online graph pruning for pathfinding on grid maps // Proceedings of the 25th AAAI Conference on Artificial Intelligence. 2011. vol. 25. no. 1. pp. 1114–1119. DOI: 10.1609/aaai.v25i1.7994.
8. Carlson M., Moghadam S.K., Harabor D.D., Stuckey P.J., Ebrahimi M. Optimal pathfinding on weighted grid maps // Proceedings of the 37th AAAI Conference on Artificial Intelligence. 2023. vol. 37. no. 10. pp. 12373–12380. DOI: 10.1609/aaai.v37i10.26458.
9. Nobes T.K., Harabor D., Wybrow M., Walsh S.D.C. The JPS pathfinding system in 3D // Proceedings of the 15th International Symposium on Combinatorial Search. 2022. vol. 15. no. 1. pp. 145–152. DOI: 10.1609/socs.v15i1.21762.
10. Daniel K., Nash A., Koenig S., Felner A. Theta*: Any-angle path planning on grids // Journal of Artificial Intelligence Research. 2010. vol. 39. pp. 533–579. DOI: 10.1613/jair.2994.
11. Ahmadi S., Tack G., Harabor D.D., Kilby P. A fast exact algorithm for the resource constrained shortest path problem // Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021. vol. 35. no. 14. pp. 12217–12224. DOI: 10.1609/aaai.v35i14.17450.
12. Ahmadi S., Tack G., Harabor D.D., Kilby P. Weight constrained path finding with bidirectional A* // Proceedings of the 15th International Symposium on Combinatorial Search. 2022. vol. 15. no. 1. pp. 2–10. DOI: 10.1609/socs.v15i1.21746.
13. Cohen B.J., Chitta S., Likhachev M. Search-based planning for manipulation with motion primitives // 2010 IEEE International Conference on Robotics and Automation. 2010. pp. 2902–2908. DOI: 10.1109/ROBOT.2010.5509685.
14. Kang G., Kim Y.B., Lee Y.H., Oh H.S., You W.S., Choi H.R. Sampling-based motion planning of manipulator with goal-oriented sampling // Intelligent Service Robotics. 2019. vol. 12. pp. 265–273. DOI: 10.1007/s11370-019-00281-y.
15. Phillips M., Likhachev M. SIPP: Safe interval path planning for dynamic environments // 2011 IEEE International Conference on Robotics and Automation. 2011. pp. 5628–5635. DOI: 10.1109/ICRA.2011.5980306.
16. Yakovlev K., Andreychuk A., Stern R. Revisiting bounded-suboptimal safe interval path planning // Proceedings of the 30th International Conference on Automated Planning and Scheduling. 2020. vol. 30. no. 1. pp. 300–304. DOI: 10.1609/icaps.v30i1.6674.
17. Rybecky T., Kulich M., Andreychuk A., Yakovlev K. Towards narrowing the search in bounded-suboptimal safe interval path planning // Proceedings of the 12th International Symposium on Combinatorial Search, SoCS 2021. 2021. vol. 12. no. 1. pp. 136–140. DOI: 10.1609/socs.v12i1.18562.
18. Ren Z., Rathinam S., Likhachev M., Choset H. Multi-objective safe-interval path planning with dynamic obstacles // IEEE Robotics and Automation Letters. 2022. vol. 7. no. 3. pp. 8154–8161. DOI: 10.1109/LRA.2022.3187270.
19. Gonzalez D., Perez J., Milanes V., Nashashibi F. A review of motion planning techniques for automated vehicles // IEEE Transactions on Intelligent Transportation Systems. 2016. vol. 17. no. 4. pp. 1135–1145. DOI: 10.1109/TITS.2015.2498841.
20. La Valle S.M., Kuffner Jr J.J. Randomized kinodynamic planning // The International Journal of Robotics Research. 2001. vol. 20. no. 5. pp. 378–400. DOI: 10.1177/02783640122067453.
21. Karaman S., Frazzoli E. Incremental sampling-based algorithms for optimal motion planning // Robotics: Science and Systems. 2010. vol. 104. no. 2. pp. 267–274. DOI: 10.1177/0278364911406761.
22. Otte M., Frazzoli E. RRTX: Real-time motion planning/replanning for environments with unpredictable obstacles // Algorithmic Foundations of Robotics XI. Springer Tracts in Advanced Robotics. 2015. vol. 107. pp. 461–478. DOI: 10.1007/978-3-319-16595-0_27.
23. Paudel A. Motion primitives based path planning with rapidly-exploring random tree. arXiv preprint arXiv: 2210. 15784. 2022.
24. Головин В.А., Яковлев К.С. Примитивы движения робота в задаче планирования траектории с кинематическими ограничениями // Информатика и автоматизация. 2023. Т. 22. №6. C. 1354–1386. DOI: 10.15622/ia.22.6.4.
25. Jingyu Y., Jianjun M. Search-based trajectory planning with motion primitives for quadrotors using pruning A* algorithm // 2022 37th Youth Academic Annual Conference of Chinese Association of Automation (YAC). 2022. pp. 996–1000. DOI: 10.1109/YAC57282.2022.10023615.
26. Scharff J., Gonzalez D., Hernandez J.D., Pairet E., Petillot Y. Online 3-dimensional path planning with kinematic constraints in unknown environments using hybrid A* with tree pruning // Sensors. 2021. vol. 21. no. 4. 1152. p.
27. Agranovskiy M., Yakovlev K. MeshA*: Efficient path planning with motion primitives // Proceedings of the 40th AAAI Conference on Artificial Intelligence. 2026. vol. 40. no. 43. pp. 36785–36792. DOI: 10.1609/aaai.v40i43.41004.
28. Piazzi A., Bianco C.G.L., Bertozzi M., Fascioli A., Broggi A. Quintic G/sup 2/-splines for the iterative steering of vision-based autonomous vehicles // IEEE Transactions on Intelligent Transportation Systems. 2002. vol. 3. no. 1. pp. 27–36. DOI: 10.1109/6979.994793.
29. Walton D.J., Meek D.S. A controlled clothoid spline // Computers & Graphics. 2005. vol. 29. no. 3. pp. 353–363. DOI: 10.1016/j.cag.2005.03.008.
30. Farouki R.T. Pythagorean-hodograph curves: algebra and geometry inseparable // Geometry and Computing. Springer. 2008. vol. 1. pp. 131–196. DOI: 10.1007/978-3-540-73398-0_8.
31. Яковлев К.С., Белинская Ю.С., Макаров Д.А., Андрейчук А.А. Безопасно-интервальное планирование и метод накрытий для управления движением мобильного робота в среде со статическими и динамическими препятствиями // Автоматика и телемеханика. 2022. №6. C. 96–117. DOI: 10.31857/S0005231022060083.
32. De Iaco R., Smith S.L., Czarnecki K. Learning a lattice planner control set for autonomous vehicles // IEEE Intelligent Vehicles Symposium (IV). 2019. pp. 549–556. DOI: 10.1109/IVS.2019.8813797.
33. Weaver C., Capobianco R., Wurman P.R., Stone P., Tomizuka M. Real-time trajectory generation via dynamic movement primitives for autonomous racing // 2024 American Control Conference (ACC). 2024. pp. 352–359. DOI: 10.23919/ACC60939.2024.10644244.
34. Franke J., Moldagalieva A., Hanfeld P., Honig W. Accelerating db-A* for kinodynamic motion planning using diffusion. arXiv preprint arXiv: 2503. 05539. 2025.
35. Kraljusic B., Ajanovic Z., Covic N., Lacevic B. Search-based robot motion planning with distance-based adaptive motion primitives // 2025 XXX International Conference on Information, Communication and Automation Technologies (ICAT). 2025. pp. 1–6. DOI: 10.1109/ICAT66432.2025.11189289.
36. Yao Y., Liu S., Song H., Qu D., Chen Q., Ding Y., Zhao B., Wang Z., Li X., Wang D. Think small, act big: primitive prompt learning for lifelong robot manipulation // Proceedings of the Computer Vision and Pattern Recognition Conference. 2025. pp. 22573–22583.
Опубликован
2026-07-03
Как цитировать
Аграновский, М. А., & Яковлев, К. С. (2026). Эффективный метод генерации кинематически-согласованных примитивов движения на основе параметризации по кривизне. Информатика и автоматизация, 25(4), 1090-1113. https://doi.org/10.15622/ia.25.4.4
Раздел
Робототехника, автоматизация и системы управления
Copyright (c) Марат Антонович Аграновский, Константин Сергеевич Яковлев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).