Алгоритмы планирования сглаженных индивидуальных траекторий движения наземных роботов

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

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

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

1. 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. P. 100—107.

2. Пискорский Д. С., Абдуллин Ф. Х., Николаева А. Р. Оптимизация алгоритма планирования пути A-star // Вестник ЮУрГУ. Серия "Компьютерные технологии, управление, радиоэлектроника". 2020. Т. 20, № 1. С. 154—160.

3. Stentz A. Optimal and efficient path planning for partially known environments // In Intelligent Unmanned Ground Vehicles. Springer, Boston, MA, USA, 1997. P. 203—220.

4. Казаков К. А., Семенов В. А. Обзор современных методов планирования пути // ТРУДЫ ИСП РАН. 2016. Т. 28(4). С. 241—294.

5. 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.

6. 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.

7. Khatib O. Real-Time Obstacles Avoidance for Manipulators and Mobile Robots // International Journal of Robotics Research. 1986. Vol. 5(1). Р. 90—98.

8. Платонов А. К., Карпов И. И., Кирильченко А. А. Метод потенциалов в задаче прокладки трассы. М.: Препринт Института прикладной математики АН СССР, 1974. 27 с.

9. Филимонов А. Б., Филимонов Н. Б. Вопросы управления движением мобильных роботов методом потенциального наведения // Мехатроника, автоматизация, управление. 2019. Т. 20, № 11. С. 677—685.

10. Пшихопов В. Х., Медведев М. Ю. Децентрализованное управление группой однородных подвижных объектов в двумерной среде с препятствиями// Мехатроника, автоматизация, управление. 2016. Т. 17, № 5. С. 346—353.

11. Пшихопов В. Х., Медведев М. Ю. Групповое управление движением мобильных роботов в неопределенной среде с использованием неустойчивых режимов // Труды СПИИРАН. 2018. Вып. 60. C. 39—63.

12. 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.

13. Гайдук А. Р., Мартьянов О. В., Медведев М. Ю., Пшихопов В. Х., Хамдан Н., Фархуд А. Нейросетевая система управления группой роботов в неопределенной двумерной среде // Мехатроника, автоматизация, управление. 2020. Т. 21, № 8. С. 470—479.

14. 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.

15. 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.

16. 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.

17. Сухарев А. Г. Оптимальные стратегии поиска экстремума // СССР. Вычислительная математика и математическая физика. 1971. Т. 11(4). С. 910—924.

18. 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.

19. 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.

20. 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.

21. Zhou R., Hansen E. A. Memory-Bounded {A*} Graph Search // The Florida AI Research Society Conference — FLAIRS. 2002. P. 203—209.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. Медведев М. Ю., Костюков В. А., Пшихопов В. Х. Оптимизация движения мобильного робота на плоскости в поле конечного числа источников-репеллеров // Труды СПИИРАН. 2020. Т.19, № 1. С. 43—78.

29. 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.

30. Wilkinson J. H. The algebraic Eigenvalue Problem. Oxford, Clarendon Press, 1965.

31. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988.

32. Чекмарев А. А. Инженерная графика. М: Высшая школа, 1988.

33. Sapronov L., Lacaze A. Path planning for robotic vehicles using generalized Field D* // Proc. SPIE, Unmanned Systems Technology X. 2008.

34. Григорьев М. И., Малоземов В. Н., Сергеев А. Н. Полиномы Бернштейна и составные кривые Безье// Журнал вычислительной математики и математической физики. 2006. Т. 46, № 11. С. 1962—1971.

35. 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.