izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2020-24-4-107-125izvestswsu-823Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentСглаживание кривизны траектории движения наземного робота в трехмерном пространствеSmoothing the Curvature of Trajectory of Ground Robot in 3D SpaceЗахаровК. С.ZakharovK. S.

Захаров Константин Станиславович, младший научный сотрудник лаборатории автономных робототехнических систем  

14-я линия В.О. 39, г. Санкт-Петербург 199178

Konstantin S. Zakharov, Junior Researcher of Autonomous Robotic Systems Laboratory

39, 14-th Line V.O., St. Petersburg 199178

kon7666007@yandex.ruСавельевА. И.SavelievA. I.

Савельев Антон Игоревич, кандидат технических наук, старший научный сотрудник, заведующий лабораторией автономных робототехнических систем

14-я линия В.О. 39, г. Санкт-Петербург 199178

Anton I. Saveliev, Cand. of Sci. (Engineering, Senior Researcher, Head of the Autonomous Robotic Systems Laboratory

39, 14-th Line V.O., St. Petersburg 199178

saveliev.ais@yandex.ruСанкт-Петербургский институт информатики и автоматизации Российской академии наук (СПИИРАН)St.Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences (SPIIRAS)202003022021244107125Copyright © Захаров К.С., Савельев А.И., 20212021Захаров К.С., Савельев А.И.Zakharov K.S., Saveliev A.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://izvestswsu.elpub.ru/jour/article/view/823

Цель исследования. Разработка алгоритма сглаживания траектории движения наземного робота по пересеченной местности, представленной в виде графа в трехмерном пространстве. Методы. В данной статье представлен алгоритм CSA (Curve Smoothing and Averaging) для сглаживания на плоскости Оху локальных кривых, составляющих глобальную кривую, представленную в виде пути на связном графе в трехмерном пространстве. Представленный алгоритм основан на разработанном ранее подходе LRLHD-A*, в котором используется информация о вершинах графа, их соседях и соединяющих их ребрах для выбора области, через которую будет пролегать сглаженная кривая. Во избежание на выходе алгоритма ломаной кривой был разработан метод усреднения кривой, идея которого заключается в смещении серединных точек локальных кривых, вдоль ребер, на которых они находятся. Результаты. Было произведено экспериментальное сравнение кривизны траекторий, получаемых с помощью алгоритма сглаживания кривой с усреднением кривой (CSA) и без него (CS). Тестирование метода проводилось на трехмерной карте местности, представленной в виде графа с 100082 вершинами. Для проведения экспериментов использовалась выборка из 10 пар случайных вершин, между которыми строился путь с помощью алгоритма LRLHD-A*. Результаты экспериментов показали, что усреднение кривой после сглаживания снижает ее кривизну от 24 до 42%. Заключение. Траектории, сглаженные с помощью разработанного алгоритма CSA, имеют более плавные изгибы кривой на поворотах, по сравнению с алгоритмом, взятым за основу. Это позволяет добиться более плавного движения роботов и как следствие снижения расхода заряда аккумулятора робота.

Purpose or research. Development of an algorithm for smoothing the trajectory of a ground robot over rough terrain, represented as a graph in three-dimensional space. Methods. This article presents the CSA (Curve Smoothing and Averaging) algorithm for smoothing local curves in the Oxy plane that make up a global curve, represented as a path on a connected graph in 3D space. The presented algorithm is based on the previously developed LRLHD-A * approach, which uses information about the vertices of the graph, their neighbors and the edges connecting them to select the area through which the smoothed curve will run. In order to avoid a broken curve at the output of the algorithm, a curve averaging method was developed, the idea of which is to shift the midpoints of local curves along the edges on which they are located. Results. An experimental comparison was made of the curvature of the trajectories obtained using the curve smoothing algorithm with curve averaging (CSA) and without it (CS). The method was carried out on a threedimensional map of the area, presented in the form of a graph with 100082 vertices. For the experiments, a sample of 10 pairs of random vertices was used, between which a path was built using the LRLHD-A * algorithm. The results of the experiments have shown that averaging the curve after smoothing reduces its curvature from 24 to 42%. Conclusion. Trajectories smoothed using the developed CSA algorithm have smoother curve bends at turns, compared to the algorithm taken as a basis. This allows the robots to move more smoothly and, as a consequence, reduce the consumption of the robot's battery.

планирование путиавтономная навигациясглаживание траекториитрехмерное пространствонавигационный графpath planningself-navigationsmoothing the trajectorythree-dimensional spacenavigation graphИсследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-33-90053.The research was carried out with the financial support of the Russian Foundation for Basic Research within the framework of scientific project No. 19-33-90053.ReferencesDubins 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 mathematics. 1957. № 79(3). Р. 497-516. https://doi.org/10.2307/2372560Dubins 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 mathematics, 1957, no. 79(3), pp. 497-516. https://doi.org/10.2307/2372560Pérez J., Godoy J., Villagrá J., Onieva E. Trajectory generator for autonomous vehicles in urban environments // 2013 IEEE International Conference on Robotics and Automation. IEEE, 2013. Р. 409-414. https://doi.org/10.1109/ICRA.2013.6630608Pérez J., Godoy J., Villagrá J., Onieva E. Trajectory generator for autonomous vehicles in urban environments. 2013 IEEE International Conference on Robotics and Automation, IEEE. 2013, pp. 409-414. https://doi.org/10.1109/ICRA.2013.6630608Gerlach A.R., Kingston D., Walker B.K. UAV navigation using predictive vector field control // 2014 American Control Conference. IEEE, 2014. Р. 4907-4912. https://doi.org/10.1109/ACC.2014.6859082Gerlach A.R., Kingston D., Walker B.K. UAV navigation using predictive vector field control. 2014 American Control Conference, IEEE. 2014, pp. 4907-4912. https://doi.org/10.1109/ACC.2014.6859082Lin Y., Saripalli S. Path planning using 3D dubins curve for unmanned aerial vehicles // 2014 international conference on unmanned aircraft systems (ICUAS). IEEE, 2014. Р. 296-304. https://doi.org/10.1109/ICUAS.2014.6842268Lin Y., Saripalli S. Path planning using 3D dubins curve for unmanned aerial vehicles. 2014 international conference on unmanned aircraft systems (ICUAS). IEEE, 2014, pp. 296-304. https://doi.org/10.1109/ICUAS.2014.6842268Choi J., Curry R., Elkaim G. Path planning based on bézier curve for autonomous ground vehicles // Advances in Electrical and Electronics Engineering-IAENG Special Edition of the World Congress on Engineering and Computer Science 2008. IEEE, 2008. Р. 158- 166. https://doi.org/10.1109/WCECS.2008.27Choi J., Curry R., Elkaim G. Path planning based on bézier curve for autonomous ground vehicles. Advances in Electrical and Electronics Engineering-IAENG Special Edition of the World Congress on Engineering and Computer Science 2008. IEEE, 2008, pp. 158- 166. https://doi.org/10.1109/WCECS.2008.27Rastelli J.P., Lattarulo R., Nashashibi F. Dynamic trajectory generation using continuouscurvature algorithms for door to door assistance vehicles // 2014 IEEE Intelligent Vehicles Symposium Proceedings. IEEE, 2014. Р. 510-515. https://doi.org/10.1109/IVS.2014.6856526Rastelli J.P., Lattarulo R., Nashashibi F. Dynamic trajectory generation using continuous-curvature algorithms for door to door assistance vehicles. 2014 IEEE Intelligent Vehicles Symposium Proceedings. IEEE, 2014, pp. 510-515. https://doi.org/10.1109/ IVS.2014.6856526Walton D.J., Meek D.S., Ali J.M. Planar G2 transition curves composed of cubic Bé- zier spiral segments // Journal of Computational and Applied Mathematics. 2003. № 157(2). Р. 453-476. https://doi.org/10.1016/S0377-0427(03)00435-7Walton D.J., Meek D.S., Ali J.M. Planar G2 transition curves composed of cubic Bé- zier spiral segments. Journal of Computational and Applied Mathematics, 2003, no. 157(2), pp. 453-476. https://doi.org/10.1016/S0377-0427(03)00435-7Montes N., Mora M.C., Tornero J. Trajectory generation based on rational bezier curves as clothoids // 2007 IEEE Intelligent Vehicles Symposium. IEEE, 2007. Р. 505-510. https://doi.org/10.1109/IVS.2007.4290165Montes N., Mora M.C., Tornero J. Trajectory generation based on rational bezier curves as clothoids. 2007 IEEE Intelligent Vehicles Symposium. IEEE, 2007, pp. 505-510. https://doi.org/10.1109/IVS.2007.4290165Real-time clothoid approximation by Rational Bezier curves / N. Montés, A. Herraez, L. Armesto, J. Tornero // 2008 IEEE International Conference on Robotics and Automation. IEEE, 2008. Р. 2246-2251. https://doi.org/10.1109/ROBOT.2008.4543548Montés N., Herraez A., Armesto L., Tornero J. Real-time clothoid approximation by Rational Bezier curves. 2008 IEEE International Conference on Robotics and Automation. IEEE, 2008, pp. 2246-2251. https://doi.org/10.1109/ROBOT.2008.4543548Bezier curve based path planning for autonomous vehicle in urban environment / L. Han, H. Yashiro, H.T.N. Nejad, Q.H. Do, S. Mita // 2010 IEEE Intelligent Vehicles Symposium. IEEE. 2010. Р. 1036-1042. https://doi.org/10.1109/IVS.2010.5548085Han L., Yashiro H., Nejad, H.T.N., Do Q.H., Mita S. Bezier curve based path planning for autonomous vehicle in urban environment. 2010 IEEE Intelligent Vehicles Symposium. IEEE, 2010, pp. 1036-1042. https://doi.org/10.1109/IVS.2010.5548085Continuous curvature planning with obstacle avoidance capabilities in urban scenarios / D. González, J. Perez, R. Lattarulo, V. Milanés, F. Nashashibi // 17th International IEEE Conference on Intelligent Transportation Systems (ITSC). IEEE, 2014. Р. 1430-1435. https://doi.org/10.1109/ITSC.2014.6957887González D., Perez J., Lattarulo R., Milanés V., Nashashibi F. Continuous curvature planning with obstacle avoidance capabilities in urban scenarios. 17th International IEEE Conference on Intelligent Transportation Systems (ITSC). IEEE, 2014, pp. 1430-1435. https://doi.org/10.1109/ITSC.2014.6957887Elbanhawi M., Simic M., Jazar R.N. Continuous path smoothing for carlike robots using B-spline curves // Journal of Intelligent & Robotic Systems. 2015. № 80(1). Р. 23-56. https://doi.org/10.1007/s10846-014-0172-0Elbanhawi M., Simic M., Jazar R.N. Continuous path smoothing for car-like robots using B-spline curves. Journal of Intelligent & Robotic Systems, 2015, no. 80(1), pp. 23-56. https://doi.org/10.1007/s10846-014-0172-0Elbanhawi M., Simic M., Jazar R. Randomized bidirectional B-Spline parameterization motion planning // IEEE Transactions on intelligent transportation systems. 2015. № 17(2). Р. 406-419. https://doi.org/10.1109/TITS.2015.2477355Elbanhawi M., Simic M., Jazar R. Randomized bidirectional B-Spline parameterization motion planning. IEEE Transactions on intelligent transportation systems, 2015, no. 17(2), pp. 406-419. https://doi.org/10.1109/TITS.2015.2477355Komoriya K., Tanie K. Trajectory design and control of a wheel-type mobile robot using B-spline curve // Proceedings. IEEE/RSJ International Workshop on Intelligent Robots and Systems'. (IROS'89)'The Autonomous Mobile Robots and Its Applications. IEEE, 1989. Р. 398-405. https://doi.org/10.1109/IROS.1989.637937Komoriya K., Tanie K. Trajectory design and control of a wheel-type mobile robot using B-spline curve. Proceedings. IEEE/RSJ International Workshop on Intelligent Robots and Systems'. (IROS'89)'The Autonomous Mobile Robots and Its Applications IEEE, 1989, pp. 398-405. https://doi.org/10.1109/IROS.1989.637937Berglund T., Brodnik A., Jonsson H., Staffanson M., Soderkvist I. Planning smooth and obstacle-avoiding B-spline paths for autonomous mining vehicles // IEEE Transactions on Automation Science and Engineering. 2009. № 7(1). Р. 167-172. https://doi.org/10.1109/TASE.2009.2015886Berglund T., Brodnik A., Jonsson H., Staffanson M., Soderkvist I. Planning smooth and obstacle-avoiding B-spline paths for autonomous mining vehicles. IEEE Transactions on Automation Science and Engineering, 2009, no. 7(1), pp. 167-172. https://doi.org/10.1109/TASE.2009.2015886Yang K., Sukkarieh S. An analytical continuous-curvature path-smoothing algorithm // IEEE Transactions on Robotics. 2010. № 26(3). Р. 561-568. https://doi.org/10.1109/TRO.2010.2042990Yang K., Sukkarieh S. An analytical continuous-curvature path-smoothing algorithm. IEEE Transactions on Robotics, 2010, no. 26(3), pp. 561-568. https://doi.org/10.1109/TRO.2010.2042990Herrmann P., Gerngroß M., Endisch C. NURBS based trajectory generation for an industrial five axis needle winding robot // 2018 4th International Conference on Control, Automation and Robotics (ICCAR). IEEE, 2018. Р. 31-36. https://doi.org/10.1109/ICCAR.2018.8384640Herrmann P., Gerngroß M., Endisch C. NURBS based trajectory generation for an industrial five axis needle winding robot. 2018 4th International Conference on Control, Automation and Robotics (ICCAR). IEEE, 2018, pp. 31-36. https://doi.org/10.1109/ICCAR.2018.8384640Ravari A.N., Taghirad H.D. NURBS-based representation of urban environments for mobile robots // 2016 4th International Conference on Robotics and Mechatronics (ICROM). IEEE, 2016. Р. 20-25. https://doi.org/10.1109/ICRoM.2016.7886782Ravari A.N., Taghirad H.D. NURBS-based representation of urban environments for mobile robots. 2016 4th International Conference on Robotics and Mechatronics (ICROM). IEEE, 2016, pp. 20-25. https://doi.org/10.1109/ICRoM.2016.7886782Shi X., Fang H., Guo L. Multi-objective optimal trajectory planning of manipulators based on quintic NURBS // 2016 IEEE International Conference on Mechatronics and Automation. IEEE, 2016. Р. 759-765. https://doi.org/10.1109/ICMA.2016.7558658Shi X., Fang H., Guo L. Multi-objective optimal trajectory planning of manipulators based on quintic NURBS. 2016 IEEE International Conference on Mechatronics and Automation. IEEE, 2016, pp. 759-765. https://doi.org/10.1109/ICMA.2016.7558658NURBs trajectory generation and following by an autonomous mobile robot navigating in 3D environment / H. Belaidi, A. Hentout, B. Bouzouia, H. Bentarzi, A. Belaidi // The 4th Annual IEEE International Conference on Cyber Technology in Automation, Control and Intelligent. IEEE, 2014. Р. 168-173. https://doi.org/10.1109/CYBER.2014.6917455Belaidi H., Hentout A., Bouzouia B., Bentarzi H., Belaidi A. NURBs trajectory generation and following by an autonomous mobile robot navigating in 3D environment. The 4th Annual IEEE International Conference on Cyber Technology in Automation, Control and Intelligent. IEEE, 2014, pp. 168-173. https://doi.org/10.1109/CYBER.2014.6917455Guo H., Meng Y., Jin Y. Swarm robot pattern formation using a morphogenetic multicellular based self-organizing algorithm // 2011 IEEE International Conference on Robotics and Automation. IEEE, 2011. Р. 3205-3210. https://doi.org/10.1109/ICRA.2011.5979821Guo H., Meng Y., Jin Y. Swarm robot pattern formation using a morphogenetic multi-cellular based self-organizing algorithm. 2011 IEEE International Conference on Robotics and Automation. IEEE, 2011, pp. 3205-3210. https://doi.org/10.1109/ICRA.2011.5979821Huh U.Y., Chang S.R. AG 2 continuous path-smoothing algorithm using modified quadratic polynomial interpolation // International Journal of Advanced Robotic Systems. – 2014. № 11(2). Р. 25. https://doi.org/10.5772/57340Huh U.Y., Chang S.R. AG 2 continuous path-smoothing algorithm using modified quadratic polynomial interpolation. International Journal of Advanced Robotic Systems, 2014, no. 11(2), 25 p. https://doi.org/10.5772/57340Chang S.R., Huh U.Y. A collision-free G 2 continuous path-smoothing algorithm using quadratic polynomial interpolation // International Journal of Advanced Robotic Systems. 2014. № 11(12). Р. 194. https://doi.org/10.5772/59463Chang S.R., Huh U.Y. A collision-free G 2 continuous path-smoothing algorithm using quadratic polynomial interpolation. International Journal of Advanced Robotic Systems, 2014, no. 11(12), 194 p. https://doi.org/10.5772/59463Lawonn K., Gasteiger R., Rössl C., Preim B. Adaptive and robust curve smoothing on surface meshes // Computers & graphics. 2014. № 40(22-35). https://doi.org/10.1016/j.cag.2014.01.004Lawonn K., Gasteiger R., Rössl C., Preim B. Adaptive and robust curve smoothing on surface meshes. Computers & graphics, 2014, no. 40(22-35). https://doi.org/10.1016/j.cag.2014.01.004Zhang H., Yang S. Smooth path and velocity planning under 3D path constraints for car-like vehicles // Robotics and Autonomous Systems. 2018. №107. Р. 87-99. https://doi.org/10.1016/j.robot.2018.05.013Zhang H., Yang S. Smooth path and velocity planning under 3D path constraints for car-like vehicles. Robotics and Autonomous Systems, 2018, no. 107, pp. 87-99. https://doi.org/10.1016/j.robot.2018.05.013Hameiri E., Shimshoni I. Estimating the principal curvatures and the Darboux frame from real 3-D range data // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 2003. № 33(4). Р. 626-637. https://doi.org/10.1109/TSMCB.2003.814304Hameiri E., Shimshoni I. Estimating the principal curvatures and the Darboux frame from real 3-D range data. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2003, no.33(4), pp. 626-637. https://doi.org/10.1109/TSMCB.2003.814304Zakharov K., Saveliev A., Sivchenko O. Energy-Efficient Path Planning Algorithm on Three-Dimensional Large-Scale Terrain Maps for Mobile Robots // International Conference on Interactive Collaborative Robotics. Springer, Cham, 2020. Р. 319-330. https://doi.org/10.1007/978-3-030-60337-3Zakharov K., Saveliev A., Sivchenko O. Energy-Efficient Path Planning Algorithm on Three-Dimensional Large-Scale Terrain Maps for Mobile Robots. International Conference on Interactive Collaborative Robotics. Springer, Cham, 2020, pp. 319-330. https://doi.org/10.1007/978-3-030-60337-3_31Аksamentov E., Astapova M., Usina E. Approach to Obstacle Localization for Robot Navigation in Agricultural Territories // International Conference on Interactive Collaborative Robotics. Springer, Cham, 2020. Р. 13-20. https://doi.org/10.1007/978-3-030-60337-3_2Аksamentov E., Astapova M., Usina E. Approach to Obstacle Localization for Robot Navigation in Agricultural Territories. International Conference on Interactive Collaborative Robotics. Springer, Cham, 2020, pp. 13-20. https://doi.org/10.1007/978-3-030-60337-3_2Robot Navigation System in Stochastic Environment Based on Reinforcement Learning on Lidar Data / D. Dudarenko, A. Kovalev, I. Tolstoy, I. Vatamaniuk // Proceedings of 14th International Conference on Electromechanics and Robotics “Zavalishin's Readings”. Springer, Singapore, 2020. Р. 537-547. https://doi.org/10.1007/978-981-13-9267-2_44Dudarenko D., Kovalev A., Tolstoy I., Vatamaniuk I. Robot Navigation System in Stochastic Environment Based on Reinforcement Learning on Lidar Data. Proceedings of 14th International Conference on Electromechanics and Robotics “Zavalishin's Readings”. Springer, Singapore, 2020, pp. 537-547. https://doi.org/10.1007/978-981-13-9267-2_Денисов А.В. Алгоритмы организации беспроводного информационного взаимодействия сенсорных систем и роботизированных устройств // Известия Волгоградского государственного технического университета. 2020. № 9(244). С. 30-34. https://doi.org/10.35211/1990-5297-2020-9-244-30-34Denisov A.V. Algoritmy organizatsii besprovodnogo informatsionnogo vzaimodeistviya sensornykh sistem i robotizirovannykh ustroistv [Development of a recommender system for parameter calculation in wireless network of sensor devices]. Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta = Bulletin of the Volgograd State Technical University, 2019, no. 7(4), pp. 30-34 (In Russ.). https://doi.org/10.26102/2310-6018/2019.27.4.025Ронжин А.Л., Тьен Н.К., Винь Н.В. Задачи управления обменом физических ресурсов между сельскохозяйственной техникой разной степени роботизации // Известия ЮФУ. Технические науки. 2020. № 1. С. 40-51. https://doi.org/10.18522/2311-3103-2020-1-39-51.Ronzhin A.L., Ngo K.T., Nguyen V.V. Zadachi upravleniya obmenom fizicheskikh resursov mezhdu sel'skokhozyaistvennoi tekhnikoi raznoi stepeni robotizatsii [Tasks of controlling the exchange of physical resources between agricultural means with varying degrees of robotization]. Izvestiya YuFU. Tekhnicheskie nauki = Izvestiya SFedU. Engineering Sciences, 2020, no. 1, pp. 40-51 (In Russ.). https://doi.org/10.18522/2311-3103-2020-1-39-51Ковалев А.Д. Подход к реконфигурации модульной робототехнической системы с использованием полиномиального алгоритма субоптимального поиска // Известия Волгоградского государственного технического университета. 2020. № 9(244). С. 48-51. https://doi.org/10.35211/1990-5297-2020-9-244-48-51Kovalev A.D. Podkhod k rekonfiguratsii modul'noi robototekhnicheskoi siste-my s ispol'zovaniem polinomial'nogo algoritma suboptimal'nogo poiska [Approach to reconfiguration of a modular robot system with a suboptimal search polynomial algorithm]. Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta = Bulletin of the Volgograd State Technical University. 2020, no. 9(244), pp. 48-51 (In Russ.). https://doi.org/10.35211/1990-5297-2020-9-244-48-51Pavliuk N., Saveliev A., Cherskikh E., Pykhov D. Formation of Modular Structures with Mobile Autonomous Reconfigurable System // Proceedings of 14th International Conference on Electromechanics and Robotics “Zavalishin's Readings”. Springer, Singapore, 2019. Р. 383-395. https://doi.org/10.1007/978-981-13-9267-2_31Pavliuk N., Saveliev A., Cherskikh E., Pykhov D. Formation of Modular Structures with Mobile Autonomous Reconfigurable System. Proceedings of 14th International Conference on Electromechanics and Robotics “Zavalishin's Readings”. Springer, Singapore. 2019, pp. 383-395. https://doi.org/10.1007/978-981-13-9267-2_31

The authors declare that there are no conflicts of interest present.