УДК 519.853.6, 517.958
MSC: 05B40, 52C17, 35A18
DOI: 10.21538/0134-4889-2025-31-4-115-131
Исследование А.А. Лемперт выполнено за счет гранта Российского научного фонда, проект № 24-21-00264, https://rscf.ru/project/24-21-00264/.
В статье рассматривается задача построения оптимальных по времени маршрутов для одного или нескольких подвижных объектов в динамической среде с препятствиями. Предлагается подход, основанный на оптико-геометрической аналогии и принципах Ферма и Гюйгенса, который сводит задачу к решению уравнения эйконала. Разработана серия алгоритмов (включая модификации метода “быстрого марша), позволяющих строить траектории без столкновений и перепланировать их при изменении обстановки. Эффективность предложенных методов подтверждена вычислительными экспериментами, и показано их превосходство по длине маршрута и времени расчета в сравнении с существующими подходами, такими как CFM, PRIMAL и DHC.
Ключевые слова: задача маршрутизации, динамическая среда, оптико-геометрический подход, уравнение эйконала, алгоритм быстрого марша
СПИСОК ЛИТЕРАТУРЫ
1. Teotia V.S. Impact of delivery speed on customer satisfaction in online shopping: a focus on quick commerce // Inter. J. Sci. Res. Engin. Manag. (IJSREM). 2025. Vol. 9, no. 5. P. 1–9. https://doi.org/10.55041/IJSREM49149
2. Demir E., Syntetos A., Van Woensel T. Last mile logistics: Research trends and needs // IMA J. Manag. Math. 2022. Vol. 33, no. 4. P. 549–561. https://doi.org/10.1093/imaman/dpac006
3. Gutin G., Punnen A.P. The traveling salesman problem and its variations. Ser. Combinatorial Optimization (COOP). Vol. 12. NY: Springer, 2007. 830 p. https://doi.org/10.1007/b101971
4. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: Изд-во УМЦ УПИ, 2016. 220 c.
5. Beresneva E., Avdoshin S. Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution // Proc. Inst. System Programm. RAS. 2018. Vol. 30, no. 3. P. 233–250.
https://doi.org/10.15514/ISPRAS-2018-30(3)-17
6. Youakim D., Ridao P. Motion planning survey for autonomous mobile manipulators underwater manipulator case study // Robot. Auton. Syst. 2018. Vol. 107. P. 20–44. https://doi.org/10.1016/j.robot.2018.05.006
7. Shin Y. W., Abebe M., Noh Y., Lee S., Lee I., Kim D., Bae J., Kim K.C. Near-optimal weather routing by using improved A* algorithm // Appl. Sci. 2020. Vol. 10, no. 17. Art. no. 6010. https://doi.org/10.3390/app10176010
8. Naderi K., Rajamaki J., Hamalainen P. RT-RRT*: a real-time path planning algorithm based on RRT* // Proc. of the 8th ACM SIGGRAPH Conf. Motion in Games (MIG’15). 2015. P. 113–118. https://doi.org/10.1145/2822013.2822036
9. Dijkstra E.W. A note on two problems in connexion with graphs // Numer. Math. 1959. Vol. 1, no. 1.
P. 269–271. https://doi.org/10.1007/BF01386390
10. Floyd R.W. Algorithm 97: Shortest path // Commun. ACM. 1962. Vol. 5, no. 6. P. 345.
11. Matthews J. Basic A* pathfinding made simple // AI Game Programming Wisdom. Boston: Charles River Media, 2002. P. 105–113.
12. Stentz A. Optimal and efficient path planning for partially-known environments // Proc. 1994 IEEE Inter. Conf. Robotics and Automation. San Diego, 1994. P. 3310–3317. https://doi.org/10.1109/ROBOT.1994.351061
13. Injarapu V. A. S. H. H., Gawre S.K. A survey of autonomous mobile robot path planning approaches // Proc. Inter. Conf. Recent innovations in signal processing and embedded systems (RISE 2017). Bhopal, 2017.
P. 624–628. https://doi.org/10.1109/RISE.2017.8378228
14. Pennino S., Gaglione S., Innac A., Piscopo V., Scamardella A. Development of a new ship adaptive weather routing model based on seakeeping analysis and optimization // J. Mar. Sci. Eng. 2020. Vol. 8, no. 4. P. 270. https://doi.org/10.3390/jmse8040270
15. Vemula A., Muelling K., Oh J. Path planning in dynamic environments with adaptive dimensionality // Proc. Ninth Internat. Symp. on Combinatorial Search (SoCS 2016). 2016. Vol. 9, no. 1.
P. 107–116. https://doi.org/10.1609/socs.v7i1.18386
16. Сарапулов А. В. Методы решения задачи построения траектории для беспилотного летательного аппарата в динамической среде // Ракетно-космическая техника. 2017. T. 1, №2. C. 92–99.
17. Ulyanov S., Bychkov I., Maksimkin N. Event-based path-planning and path-following in unknown environments for underactuated autonomous underwater vehicles // Appl. Sci. 2020. Vol. 10, no. 21. Art. no. 7894. https://doi.org/10.3390/app10217894
18. Zheng H., Xu W., Ma D., Qu F. Dynamic rolling horizon scheduling of waterborne AGVs for inter terminal transportation: Mathematical modeling and heuristic solution // IEEE Transactions on Intelligent Transportation Systems. 2022. Vol. 23, no. 4. P. 3853–3865. https://doi.org/10.1109/TITS.2021.3102998
19. Liu C., Chu X., Wu W., Li S., He Z., Zheng M. Human–machine cooperation research for navigation of maritime autonomous surface ships: A review and consideration // Ocean Engineering. 2022. Vol. 246. Art. no. 110555. https://doi.org/10.1016/j.oceaneng.2022.110555
20. He Z., Liu C., Chu X., Negenborn R. R., Wu Q. Dynamic anti-collision A-star algorithm for multi-ship encounter situations // Appl. Ocean Res. 2022. Vol. 118. Art. no. 102995. https://doi.org/10.1016/j.apor.2021.102995
21. Ушаков В.Н., Лавров Н.Г., Ушаков А.В. Конструирование решений в задаче о сближении стационарной управляемой системы // Тр. Ин-та математики и механики УрО РАН. 2014. T. 20, № 4. C. 277–286.
22. Ушаков В.Н., Ершов А.А., Матвийчук А.Р., Ушаков А.В. Некоторые задачи сближения нелинейных управляемых систем в фиксированный момент времени // Изв. Ин-та математики и информатики Удмурт. гос. ун-та. 2023. T. 62. C. 125–155. https://doi.org/10.35634/2226-3594-2023-62-09
23. Ушаков В.Н., Ершов А.А. К конструированию решений игровой задачи с фиксированным моментом окончания // Тр. Ин-та математики и механики УрО РАН. 2024. T. 3. C. 255–273. https://doi.org/10.21538/0134-4889-2024-30-3-255-273
24. Самохина М. А., Галяев А. А. Построение карты локально оптимальных путей управляемого подвижного объекта в конфликтной среде при переходе из точки в точку // Проблемы управления. 2024. T. 1. C. 90–102. https://doi.org/10.25728/pu.2024.1.8
25. Kunz T., Hutchinson S. Real-time path planning for a robot arm in changing environments // Proc. IEEE/RSJ Inter. Conf. Intelligent Robots and Systems (IROS’10). Taipei, 2010. P. 5906–5911.
https://doi.org/10.1109/IROS.2010.5653275
26. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. С. 50–57.
27. Бухаров Д.С., Казаков А.Л. Программная система “ВИГОЛТ” для решения задач оптимизации, возникающих в транспортной логистике // Вычисл. методы и программирование. 2012. Т. 13, № 3.
С. 65–74.
28. Казаков А.Л., Лемперт А.А. О построении маршрутов в динамической среде с использованием решений уравнения эйконала // Изв. Ин-та математики и информатики Удмурт. гос. ун-та. 2021. T. 82, № 6. C. 3–13. https://doi.org/10.35634/2226-3594-2021-58-04
29. Фейнман Р. П., Лейтон Р. Б., Сэндс М. Фейнмановские лекции по физике. Излучение. Волны. Кванты. М.: Эдиториал УРСС, 2004. T. 3. 240 c.
30. Боровских А. В. Двумерное уравнение эйконала // Сиб. мат. журн. 2006. T. 47, №. 5. C. 993–1018.
31. Huptych M., Rock S. Real-time path planning in dynamic environments for unmanned aerial vehicles using the curve-shortening flow method // Inter. J. Adv. Robotic Syst. 2021. Vol. 18, no. 6. P. 1–15.
https://doi.org/10.1177/1729881420968687
32. Sartoretti G., Kerr J., Shi Y., Wagner G., Kumar T. K.S., Koenig S., Choset H. PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning // IEEE Robotics and Autom. Letters. 2018. Vol. 3, no. 4. P. 2378–2385. https://doi.org/10.1109/LRA.2018.2859630
33. Ma Z., Luo Y., Ma H. Distributed heuristic multi-agent path finding with communication // Proc. 2021 IEEE Inter. Conf. Robotics and Automation (ICRA). Xi’an, 2021. P. 8699–8705.
https://doi.org/10.1109/ICRA48506.2021.9560748
Поступила 15.10.2025
После доработки 21.10.2025
Принята к публикации 27.10.2025
Казаков Александр Леонидович
д-р физ.-мат. наук, главный науч. сотрудник
Институт динамики систем и теории управления
имени В.М. Матросова СО РАН
г. Иркутск
e-mail: kazakov@icc.ru
Лемперт Анна Ананьевна
канд. физ.-мат. наук, ведущий науч. сотрудник
Институт динамики систем и теории управления
имени В.М. Матросова СО РАН
г. Иркутск
e-mail: lempert@icc.ru
Чан Туан Вьет
аспирант
Иркутский национальный исследовательский технический университет
г. Иркутск
e-mail:ttviet@ictu.edu.vn
Ссылка на статью: А.Л. Казаков, А.А. Лемперт, Т.В. Чан. Метод построения быстрейших маршрутов без столкновений в среде с динамическими препятствиями // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 4. С. 115–131.
English
A.L. Kazakov, A.A. Lempert, T.V. Tran. On constructing the fastest collision-free routes in dynamic environments with moving obstacles
The article addresses the problem of constructing time-optimal routes for one or several moving objects in a dynamic environment with obstacles. We propose an approach based on the optical-geometrical analogy and the principles of Fermat and Huygens, which reduces the problem to solving the eikonal equation. A series of algorithms (including modifications of the fast marching method) is developed. They allow one to construct collision-free trajectories and correct them when the situation changes. The effectiveness of the proposed methods is confirmed by computational experiments, demonstrating their superiority in route length and computation time compared to existing approaches such as CFM, PRIMAL, and DHC.
Keywords: routing problem, dynamic environment, optical-geometric approach, eikonal equation, fast marching method
Received October 15, 2025
Revised October 21, 2025
Accepted October 27, 2025
Funding Agency: A.A. Lempert’s research is supported by the Russian Science Foundation, project no. 24-21-00264, https://rscf.ru/project/24-21-00264.
Aleksandr Leonidovich Kazakov, Dr. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: kazakov@icc.ru
Anna Ananievna Lempert, Cand. Sci. (Phys.-Math.), Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: lempert@icc.ru
Tuan Viet Tran, Irkutsk National Research Technical University, Irkutsk, 664074 Russia, e-mail: ttviet@ictu.edu.vn
Cite this article as: A.L. Kazakov, A.A. Lempert, T.V. Tran. On constructing the fastest collision-free routes in dynamic environments with moving obstacles. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 4, pp. 115–131.
[References -> on the "English" button bottom right]
