Алгоритм определения оптимального маршрута движения робота для мониторинга объектов с учетом препятствий

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

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

2. Ченцов А.Г. Задача маршрутизации «на узкие места» с системой первоочередных заданий. Известия Института математики и информатики Удмуртского государственного университета. 2023;61:156–186. https://doi.org/10.35634/2226-3594-2023-61-09

3. Ченцов А.Г., Ченцов П.А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования. Труды Института математики и механики УрО РАН. 2022;28(2):215–248. https://doi.org/10.21538/0134-4889-2022-28-2-215-248

4. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений. Челябинский физико-математический журнал. 2022;7(2):209–233. https://doi.org/10.47475/2500-0101-2022-17205

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

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

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

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

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

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

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

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

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

14. Саллам М., Макаровских Т.А. Проектирование оптимальной траектории проведения мониторинга объектов. Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2024;13(3):32–46. https://doi.org/10.14529/cmse240302

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

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

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

18. Михайлов И.Е. Практическое сравнение алгоритма A* с алгоритмом волновой трассировки (алгоритмом Ли) по быстродействию. Наука, техника и образование. 2016;(1):47–49.

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

20. Dorigo M., Stützle Th. Ant Colony Optimization. Cambridge: MIT Press; 2004. 319 p.