novtexmechМехатроника, автоматизация, управлениеMekhatronika, Avtomatizatsiya, Upravlenie1684-64272619-1253Commercial Publisher «New Technologies»10.17587/mau.23.585-595novtexmech-1269Research ArticleРОБОТЫ, МЕХАТРОНИКА И РОБОТОТЕХНИЧЕСКИЕ СИСТЕМЫROBOT, MECHATRONICS AND ROBOTIC SYSTEMSАлгоритмы планирования сглаженных индивидуальных траекторий движения наземных роботовAlgorithms for Planning Smoothed Individual Trajectories of Ground RobotsКостюковВ. А.KostjukovV. A.

канд. техн. наук, ст. науч. сотр.

г. Таганрог

Cand. of Tech. Sc., Senior Researcher

Rostov-on-Don, 344006

wkost-einheit@yandex.ruМедведевМ. Ю.MedvedevM. Y.

д-р техн. наук, вед. науч. сотр.

г. Таганрог

Rostov-on-Don, 344006

medvmihal@sfedu.ruПшихоповВ. Х.PshikhopovV. Kh.

д-р техн. наук, гл. науч. сотр.

г. Таганрог

Rostov-on-Don, 344006

pshichop@rambler.ruЮжный федеральный университетРоссияSouthern Federal UniversityRussian Federation2022031120222311585595Copyright © Commercial Publisher «New Technologies», 20222022Commercial Publisher «New Technologies»Commercial Publisher «New Technologies»https://mech.novtex.ru/jour/about/submissions#copyrightNoticehttps://mech.novtex.ru/jour/article/view/1269

Обсуждается разработка алгоритма построения траектории робототехнической платформы, движущейся в среде с препятствиями. Алгоритм основан на применении специальной локальной процедуры оптимизации на каждом шаге планирования и позволяет получать более адекватные в физическом смысле программные траектории без увеличения вычислительной сложности алгоритмов по сравнению с имеющимися методами. Алгоритм базируется на применении модернизированного метода потенциальных полей и последующем сглаживании получившейся траектории. Модернизация метода потенциальных полей заключается в обосновании параметров отталкивающего и притягивающего многообразий и новом способе детектирования и избегания локальных минимумов. При обнаружении локального минимума с помощью специального геометрического критерия алгоритм добавляет на карту дополнительное препятствие, что позволяет избежать его при дальнейшем планировании траектории. Для обхода препятствий, которые могут быть аппроксимированы многоугольниками, предложен метод эффективной точки до препятствия, являющейся эквивалентом последнего по отношению к текущему расположению движущейся робототехнической платформы при применении данного метода планирования.

Предложена двухэтапная методика сглаживания кусочно-линейной траектории. Предполагается, что имеется исходная неоптимальная кривая, найденная любым методом планирования. Данная кривая оптимизируется с использованием функционала, включающего длину траектории и отклонение оптимизированной кривой от исходной кривой. На втором этапе осуществляется сопряжение линейных отрезков планируемой прямой кривыми второго порядка. В результате планируемая траектория движения представляет собой квадратично-линейную кривую с гладкой функцией траекторной скорости. При этом предложенный способ сопряжения прямолинейных участков траектории не требует резких изменений скорости при прохождении поворотов.

Рассматриваются и обсуждаются результаты моделирования, подтверждающие эффективность предлагаемой методики планирования траекторий движения роботов.

The article is devoted to the development of an algorithm for constructing the trajectory of a robotic platform moving in an environment with obstacles. This algorithm is based on the application of a special local optimization procedure at each planning step and allows us to obtain feasible program trajectories without increasing the computational complexity of algorithms compared to existing methods. The algorithm is based on the application of the improved method of potential fields and subsequent smoothing of the resulting trajectory. The improving of the potential field method consists in a new way of detecting and avoiding local minima. When a local minimum is detected, it is added to the map as an additional obstacle, which makes it possible to avoid it during further trajectory planning. To circumvent obstacles that can be approximated by polygons, the method of the effective point to the obstacle is proposed, which is the equivalent of the latter in relation to the current location of the moving robotic platform when using this planning method. A two-stage technique for smoothing piecewise linear trajectories is proposed. It is assumed that there is some initial suboptimal curve found by any planning method. This curve is optimized using a functional that includes the length of the trajectory and the deviation of the optimized curve from the original curve. At the second stage, the linear segments of the planned straight line are conjugated with second-order curves. As a result, the planned trajectory of motion is a quadratic-linear curve with a smooth function of the trajectory velocity. At the same time, the proposed method of coupling rectilinear sections of the trajectory does not require sudden changes in speed when passing turns. Simulation results confirming the effectiveness of the proposed method of planning the trajectories of robots are considered and discussed.

планирование траекторийгладкие траекториилокальные минимумыробототехническая платформадвумерная средаtrajectory planningsmooth trajectorieslocal minimarobotic platformtwo-dimensional environment*Исследование выполнено при финансовой поддержке РНФ в рамках научного проекта № 22-29-00370.The study was carried out with the financial support of the Russian Science Foundation, project No. 22-29-00370 performed at Joint-Stock Company "Robotics and Control Systems".ReferencesHart 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. 2. P. 100—107.References1. 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. 2, pp. 100—107.Пискорский Д. С., Абдуллин Ф. Х., Николаева А. Р. Оптимизация алгоритма планирования пути A-star // Вестник ЮУрГУ. Серия "Компьютерные технологии, управление, радиоэлектроника". 2020. Т. 20, № 1. С. 154—160.Piskorskii D. S., Abdullin F. K., Nikolaeva A. R. Optimization of A-Star Search Algorithm, Bulletin of the South Ural State University. Ser. Computer Technologies, Automatic Control, Radio Electronics, 2020, vol. 20, no. 1, pp. 154—160.Stentz A. Optimal and efficient path planning for partially known environments // In Intelligent Unmanned Ground Vehicles. Springer, Boston, MA, USA, 1997. P. 203—220.Stentz A. Optimal and efficient path planning for partially known environments, In Intelligent Unmanned Ground Vehicles, Springer, Boston, MA, USA, 1997, pp. 203—220.Казаков К. А., Семенов В. А. Обзор современных методов планирования пути // ТРУДЫ ИСП РАН. 2016. Т. 28(4). С. 241—294.Kazakov K. A., Semenov V. A. Reviwes of moderm path planing methods, Proceedings of ISP RAS, 2016, vol. 28(4), pp. 241—294 (in Russian)LaValle S. M., Kuffner J. J. Rapidly-exploring random trees: Progress and prospects // 2000 Workshop on the Algorithmic Foundations of Robotics. 2000. P. 293—308.LaValle S. M., Kuffner J. J. Rapidly-exploring random trees: Progress and prospects, 2000 Workshop on the Algorithmic Foundations of Robotics, 2000, pp. 293—308.Ravankar A., Ravankar Ab., Emaru T., Kobayashi Y. HPPRM: Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots // IEEE Acsess. 2020. Vol. 8. P. 221743—221766.Ravankar A., Ravankar Ab., Emaru T., Kobayashi Y. HPPRM: Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots, IEEE Acsess, 2020, vol. 8, pp. 221743—221766.Khatib O. Real-Time Obstacles Avoidance for Manipulators and Mobile Robots // International Journal of Robotics Research. 1986. Vol. 5(1). Р. 90—98.Khatib O. Real-Time Obstacles Avoidance for Manipulators and Mobile Robots, International Journal of Robotics Research, 1986, vol. 5(1), pp. 90—98.Платонов А. К., Карпов И. И., Кирильченко А. А. Метод потенциалов в задаче прокладки трассы. М.: Препринт Института прикладной математики АН СССР, 1974. 27 с.Platonov A. K., Karpov I. I., Kiril’chenko A. A. Potential field attitude in the problem of path finding, Moscow. Institute of Applied Mathematics. Academy of Science USSR, 1974, 27 p. (in Russian).Филимонов А. Б., Филимонов Н. Б. Вопросы управления движением мобильных роботов методом потенциального наведения // Мехатроника, автоматизация, управление. 2019. Т. 20, № 11. С. 677—685.Filimonov A. B., Filimonov N. B. Issues of Motion Control of Mobile Robots Based on the Potential Guidance Method, Mekhatronika, Avtomatizatsiya, Upravlenie. 2019, vol. 20, no. 11, pp. 677—685 (in Russian).Пшихопов В. Х., Медведев М. Ю. Децентрализованное управление группой однородных подвижных объектов в двумерной среде с препятствиями// Мехатроника, автоматизация, управление. 2016. Т. 17, № 5. С. 346—353.Pshikhopov V. Kh., Medvedev M. Yu. Decentralized Control of a Group of Similar Objects Moving in a Two-Dimensional Environment with Obstacles, Mekhatronika, Avtomatizatsiya, Upravlenie, 2016, vol. 17, no.5, pp. 346—353 (in Russian).Пшихопов В. Х., Медведев М. Ю. Групповое управление движением мобильных роботов в неопределенной среде с использованием неустойчивых режимов // Труды СПИИРАН. 2018. Вып. 60. C. 39—63.Pshikhopov V., Medvedev M. Group control of autonomous robots motion in uncertain environment via unstable modes, SPIIRAS Proceedings, 2018, vol. 60, no. 5, pp. 39—63 (in Russian).Medvedev M., Pshikhopov V., Gurenko B., Hamdan N. Path planning method for mobile robot with maneuver restrictions // Proc. of the International Conference on Electrical, Computer, Communications and Mechatronics Engineering. 7—8 October 2021, Mauritius.Medvedev M., Pshikhopov V., Gurenko B., Hamdan N. Path planning method for mobile robot with maneuver restrictions, Proc. of the International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME), 7—8 October 2021, Mauritius.Гайдук А. Р., Мартьянов О. В., Медведев М. Ю., Пшихопов В. Х., Хамдан Н., Фархуд А. Нейросетевая система управления группой роботов в неопределенной двумерной среде // Мехатроника, автоматизация, управление. 2020. Т. 21, № 8. С. 470—479.Gaiduk A. R., Martjanov O. V., Medvedev M. Yu., Pshikhopov V. Kh., Hamdan N., Farhood A. Neural network based control system for robots group operating in 2nd uncertain environment, Mekhatronika, Avtomatizatsiya, Upravlenie, 2020, vol. 21, no. 8, pp. 470—479.Nazarahari M., Khanmirza E., Doostie S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm // Expert Systems with Applications. 2019. Vol. 115. P. 106—120.Nazarahari M., Khanmirza E., Doostie S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm, Expert Systems with Applications, 2019, vol. 115, pp. 106—120.Hoy M., Matveev A. S., Savkin A. V. Algorithms for collision-free navigation of mobile robots in complex cluttered environments. A survey // Robotica. 2015. Vol. 33, N. 3. P. 463—497.Hoy M., Matveev A. S., Savkin A. V. Algorithms for collision-free navigation of mobile robots in complex cluttered environments. A survey, Robotica, 2015,vol. 33, no. 3, pp. 463—497.Shlyakhov N. E., Vatamaniuk I. V., Ronzhin A. L. Review of the Methods and Algorithms of a Robot Swarm Aggregation // Mekhatronika, Avtomatizatsiya, Upravlenie. 2017. Vol. 18, N. 1. P. 22—29.Shlyakhov N. E., Vatamaniuk I. V., Ronzhin A. L. Review of the Methods and Algorithms of a Robot Swarm Aggregation, Mekhatronika, Avtomatizatsiya, Upravlenie, 2017, vol. 18, no. 1, pp. 22—29.Сухарев А. Г. Оптимальные стратегии поиска экстремума // СССР. Вычислительная математика и математическая физика. 1971. Т. 11(4). С. 910—924.Sukharev A. G. Optimal strategies of the search for an extremum, U. S.S. R. Computational Mathematics and Mathematical Physics, 1971, vol. 11, no. 4, pp. 910—924.Hornung A., Wurm K. M., Bennewitz M., Stachniss C., Burgard W. OctoMap: An efficient probabilistic 3D mapping framework based on octrees // Autonomous Robots. 2013. Vol. 34(3). P. 189—206.Hornung A., Wurm K. M., Bennewitz M., Stachniss C., Burgard W. OctoMap: An efficient probabilistic 3D mapping framework based on octrees, Autonomous Robots, 2013, vol. 34, no. 3, pp. 189—206.Janson L., Ichter B., Pavone M. Deterministic samplingbased motion planning: Optimality, complexity, and performance // International Journal of Robotics Research. 2018. Vol. 37, N. 1. P. 46—61.Janson L., Ichter B., Pavone M. Deterministic samplingbased motion planning: Optimality, complexity, and performance, International Journal of Robotics Research, 2018, vol. 37, no. 1, pp. 46—61.Wang Q., Hao Y., Chen F. Deepening the IDA* algorithm for knowledge graph reasoning through neural network architecture // Neurocomputing. 2021. Vol. 429. P. 101—109.Wang Q., Hao Y., Chen F. Deepening the IDA* algorithm for knowledge graph reasoning through neural network architecture, Neurocomputing, 2021, vol. 429, pp. 101—109.Zhou R., Hansen E. A. Memory-Bounded {A*} Graph Search // The Florida AI Research Society Conference — FLAIRS. 2002. P. 203—209.Zhou R., Hansen E. A. Memory-Bounded {A*} Graph Search, The Florida AI Research Society Conference — FLAIRS, 2002, pp. 203—209.Holte R., Perez M., Zimmer R., MacDonald A. Hierarchical A*: Searching abstraction hierarchies efficiently // Proceedings of the 13th national conference on Artificial intelligence. 1996. Vol. 1. P. 530—535.Holte R., Perez M., Zimmer R., MacDonald A. Hierarchical A*: Searching abstraction hierarchies efficiently, Proceedings of the thirteenth national conference on Artificial intelligence, 1996, vol. 1, pp. 530—535.Liu B., Xiao X., Stone P. A Lifelong Learning Approach to Mobile Robot Navigation // IEEE Robotics and Automation Letters. 2021. Vol. 6, N. 2. P. 1090—1096.Liu B., Xiao X., Stone P. A Lifelong Learning Approach to Mobile Robot Navigation, IEEE Robotics and Automation Letters, 2021, vol. 6(2), pp. 1090—1096.Chen B. Y., Chen X.-W., Chen H.-P., Lam W. H. K. Efficient algorithm for finding k shortest paths based on reoptimization technique // Transportation Research Part E: Logistics and Transportation Review. 2020. Vol. 133, Article number 101819.Chen B. Y., Chen X.-W., Chen H.-P., Lam W. H. K. Efficient algorithm for finding k shortest paths based on re-optimization technique, Transportation Research Part E: Logistics and Transportation Review, 2020, vol. 133, Article number 101819.Pshikhopov V. Kh. (Ed.), Beloglazov D., Finaev V., Guzik V., Kosenko E., Krukhmalev V., Medvedev M., Pereverzev V., Pyavchenko A., Saprykin R., Shapovalov I., Soloviev V. Path Planning for Vehicles Operating in Uncertain 2D Environments. Elsevier, Butterworth-Heinemann, 2017. 312 p.Pshikhopov V. Kh. (Ed.), Beloglazov D., Finaev V., Guzik V., Kosenko E., Krukhmalev V., Medvedev M., Pereverzev V., Pyavchenko A., Saprykin R., Shapovalov I., Soloviev V. Path Planning for Vehicles Operating in Uncertain 2D Environments, Elsevier, Butterworth-Heinemann, 2017, 312 p.Ge S. S., Cui Y. J. New potential functions for mobile robot path planning // IEEE Transactions on Robotics and Automation. 2000. Vol. 16, N. 5. P. 615—620.Ge S. S., Cui Y. J. New potential functions for mobile robot path planning, IEEE Transactions on Robotics and Automation, 2000, vol. 16, no. 5, pp. 615—620.Woods A. C., La H. M. A Novel Potential Field Controller for Use on Aerial Robots // IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2019. Vol. 49, N. 4. P. 665—676.Woods A. C., La H. M. A Novel Potential Field Controller for Use on Aerial Robots, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, vol. 49, no. 4, pp. 665—676.Медведев М. Ю., Костюков В. А., Пшихопов В. Х. Оптимизация движения мобильного робота на плоскости в поле конечного числа источников-репеллеров // Труды СПИИРАН. 2020. Т.19, № 1. С. 43—78.Medvedev M., Kostjukov V., Pshikhopov V. Optimization of mobile robot movement on a plane with finite number of repeller sources, SPIIRAS Proceedings, 2020, vol. 19, no. 1, pp. 43—78.Kostjukov V., Medvedev M., Pshikhopov V. Method for Optimizing of Mobile Robot Trajectory in Repeller Sources Field // Informatics and Automation. 2021. Vol. 20, N. 3. P. 690—726.Kostjukov V., Medvedev M., Pshikhopov V. Method for Optimizing of Mobile Robot Trajectory in Repeller Sources Field, Informatics and Automation, 2021, vol. 20, no. 3, pp. 690—726.Wilkinson J. H. The algebraic Eigenvalue Problem. Oxford, Clarendon Press, 1965.Wilkinson J. H. The algebraic Eigenvalue Problem, Oxford, Clarendon Press, 1965.Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988.Gantmakher F. R. Theory of Matrices, Moscow, Nauka, 1988 (in Russian).Чекмарев А. А. Инженерная графика. М: Высшая школа, 1988.Checkmarev A. A. Engineering Graphics, Moscow, High School, 1988 (in Russian).Sapronov L., Lacaze A. Path planning for robotic vehicles using generalized Field D* // Proc. SPIE, Unmanned Systems Technology X. 2008.Sapronov L., Lacaze A. Path planning for robotic vehicles using generalized Field D*, Proc. SPIE 6962, Unmanned Systems Technology X, 2008.Григорьев М. И., Малоземов В. Н., Сергеев А. Н. Полиномы Бернштейна и составные кривые Безье// Журнал вычислительной математики и математической физики. 2006. Т. 46, № 11. С. 1962—1971.Grigor’ev M. I., Malozemov V. N., Sergeev A. N. Bernstein polynomials and composite Bezier curves, Zh. Vychisl. Mat. Mat. Fiz., 2006, vol. 46, no. 11, pp. 1962—1971.Li F. Tan Y., Wang Y., Ge G. Mobile Robots Path Planning Based on Evolutionary Artificial Potential Fields Approach // Proc. Of the 2nd Intern. Conf. on Computer Science and Electronics Engineering. 2013. P. 1314—1317.Li F. Tan Y., Wang Y., Ge G. Mobile Robots Path Planning Based on Evolutionary Artificial Potential Fields Approach, Proc. Of the 2nd Intern. Conf. on Computer Science and Electronics Engineering, 2013, pp. 1314—1317.

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