moitvivt Моделирование, оптимизация и информационные технологии Modeling, Optimization and Information Technology 2310-6018 Издательство 10.26102/2310-6018/2026.59.8.004 2427 Алгоритм определения оптимального маршрута движения робота для мониторинга объектов с учетом препятствий An algorithm for determining the optimal route of the robot for monitoring objects, taking into account obstacles 0000-0002-3656-9632 Макаровских Татьяна Анатольевна Makarovskikh Tatiana Anatolievna Makarovskikh.T.A@susu.ru aff-1 0000-0002-8703-4523 Саллам Мохамед Эльсайед Хуссейн Мохамед Мохамед Sallam Mohamed Elsayed Hussein Mohamed Mohamed mohamedslam2000@yahoo.com aff-2 Южно-Уральский государственный университет South Ural State University Южно-Уральский государственный университет South Ural State University 01 01 2026 1 1 10.26102/2310-6018/2026.59.8.004 Copyright © Авторы, 2026 2026 This work is licensed under a Creative Commons Attribution 4.0 International License

Одной из актуальных задач является наземный мониторинг состояния различных объектов. Его необходимость может возникать не только на промышленных предприятиях, но и в сельском хозяйстве (осмотр плодовых садов), медицине (мониторинг состояния пациентов инфекционных отделений), при ликвидации чрезвычайных ситуаций. В этих ситуациях невозможно размещение датчиков и умных камер в фиксированных местах. Кроме того, возникают ситуации, когда цели для мониторинга задаются непосредственно перед его проведением. Еще одной актуальной задачей является построение пути робота с учетом наличия препятствий. В данной статье рассматривается алгоритм построения кратчайшего маршрута для проведения мониторинга в конечном множестве точек наземным роботом с учетом препятствий. Задача определения траектории движения робота формулируется как задача о маршрутизации транспортного средства. Данные о координатах робота и местоположении точек мониторинга хранятся в виде взвешенного плоского графа с использованием списка ребер. В статье предложен эвристический алгоритм SearchWithObstacles, использующий функцию SPPA (Shortest Path with Precautionary Avoidance), который основан на методе ближайшего соседа и решает задачу за полиномиальное время. Приведено сравнение алгоритма с известными подходами и обсуждены преимущества и недостатки предложенного алгоритма.

One of the urgent tasks is ground-based monitoring of the condition of various facilities. It may be necessary not only in industrial enterprises, but also in agriculture (inspection of orchards), medicine (monitoring the condition of patients in infectious diseases departments), and emergency situations. In these situations, it is not possible to place sensors and smart cameras in fixed locations. In addition, there are situations when monitoring goals are set immediately before it is carried out. Another urgent task is to build a robot's path, taking into account the presence of obstacles. This article discusses an algorithm for constructing the shortest route for monitoring at a finite set of points by a ground robot, taking into account obstacles. The task of determining the trajectory of a robot is formulated as a vehicle routing task. Data on the coordinates of the robot and the location of monitoring points is stored as a weighted planar graph using a list of edges. The article proposes the algorithm SearchWithObstacles, using function SPPA (Shortest Path with Precautionary Avoidance), which is based on the nearest neighbor method and solves the problem in polynomial time. The algorithm is compared with known approaches and the advantages and disadvantages of the proposed algorithm are discussed.

 маршрутизация транспортных средств плоский граф эвристический алгоритм оптимизация объезд препятствий задача коммивояжера vehicle routing planar graph heuristic algorithm optimization obstacle avoidance traveling salesman problem Исследование выполнено при поддержке регионального гранта Российского научного фонда № 26-21-20007. The study was performed without external funding. References Sundarrajan M., Jothi A., Prabakar D., et al. The Smart Coverage Path Planner for Autonomous Drones Using TSP and Tree Selection. In: Mining Intelligence and Knowledge Exploration (MIKE 2023), 28–30 June 2023, Kristiansand, Norway. Cham: Springer; 2023. P. 161–172. https://doi.org/10.1007/978-3-031-44084-7_16 Ченцов А.Г. Задача маршрутизации «на узкие места» с системой первоочередных заданий. Известия Института математики и информатики Удмуртского государственного университета. 2023;61:156–186. https://doi.org/10.35634/2226-3594-2023-61-09 Ченцов А.Г., Ченцов П.А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования. Труды Института математики и механики УрО РАН. 2022;28(2):215–248. https://doi.org/10.21538/0134-4889-2022-28-2-215-248 Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений. Челябинский физико-математический журнал. 2022;7(2):209–233. https://doi.org/10.47475/2500-0101-2022-17205 Wu J., Li M., Gao Ch., et al. Research on Deployment Scheme and Routing Optimization Algorithm of Distribution Cable Condition Monitoring Devices. Energies. 2023;16(19):6930. https://doi.org/10.3390/en16196930 Makarovskikh T., Panyukov A., Abotaleb M., et al. Optimal Route for Drone for Monitoring of Crop Yields. In: Advances in Optimization and Applications (OPTIMA 2023), 18–22 September 2023, Petrovac, Montenegro. Cham: Springer; 2024. P. 228–240. https://doi.org/10.1007/978-3-031-48751-4_17 Duan Y.P., Yang Y.Zh., Cao Y., et al. Path planning optimization for swine manure-cleaning robots through enhanced slime mold algorithm with cellular automata. Animal Science Journal. 2024;95(1):e13992. https://doi.org/10.1111/asj.13992 Hassani I., Maalej I., Rekik Ch. Robot Path Planning with Avoiding Obstacles in Known Environment Using Free Segments and Turning Points Algorithm. Mathematical Problems in Engineering. 2018;2018:2163278. http://doi.org/10.1155/2018/2163278 Zhao Y., Seong S.J., Fan Ch., et al. Robot Automatic Path Planning by Avoiding Obstacle using Double Deep Q Networks on the Testbed. In: International Conference on Convergence Content (ICCC 2022), 21–23 December 2022, Jeju, South Korea. 2023. P. 19–20. Muhammad A., Ali M.A.H., Turaev Sh., et al. A Generalized Laser Simulator Algorithm for Mobile Robot Path Planning with Obstacle Avoidance. Sensors. 2022;22(21):8177. https://doi.org/10.3390/s22218177 Daniel K., Nash A., Koenig S., et al. Theta*: Any-Angle Path Planning on Grids. Journal of Artificial Intelligence Research. 2010;39:533–579. https://doi.org/10.1613/jair.2994 Chung S.H., Sah Bh., Lee J. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Computers & Operations Research. 2020;123:105004. https://doi.org/10.1016/j.cor.2020.105004 Cannon J., Rose K., Ruml W. Real-time motion planning with dynamic obstacles. Proceedings of the International Symposium on Combinatorial Search. 2012;3(1):33–40. https://doi.org/10.1609/socs.v3i1.18249 Саллам М., Макаровских Т.А. Проектирование оптимальной траектории проведения мониторинга объектов. Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2024;13(3):32–46. https://doi.org/10.14529/cmse240302 Dai Y., Lv W., Li Sh., et al. Improving the Lifelong Planning A-star algorithm to satisfy path planning for space truss cellular robots with dynamic obstacles. Robotica. 2025;43(4):1243–1257. http://doi.org/10.1017/S0263574725000256 Chatzisavvas A., Dossis M., Dasygenis M. Optimizing Mobile Robot Navigation Based on A-Star Algorithm for Obstacle Avoidance in Smart Agriculture. Electronics. 2024;13(11):2057. https://doi.org/10.3390/electronics13112057 Makarovskikh T., Sallam M. Optimal Trajectory for Monitoring Objects with Obstacles. In: Mathematical Optimization Theory and Operations Research (MOTOR 2025), 07–11 July 2025, Novosibirsk, Russia. Cham: Springer; 2025. P. 255–269. https://doi.org/10.1007/978-3-031-97077-1_18 Михайлов И.Е. Практическое сравнение алгоритма A* с алгоритмом волновой трассировки (алгоритмом Ли) по быстродействию. Наука, техника и образование. 2016;(1):47–49. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation. 1997;1(1):53–66. https://doi.org/10.1109/4235.585892 Dorigo M., Stützle Th. Ant Colony Optimization. Cambridge: MIT Press; 2004. 319 p.

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