An algorithm for determining the optimal route of the robot for monitoring objects, taking into account obstacles

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.

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. Chentsov A.G. A bottleneck routing problem with a system of priority tasks. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta. 2023;61:156–186. (In Russ.). https://doi.org/10.35634/2226-3594-2023-61-09

3. Chentsov A.G., Chentsov P.A. An extremal two-stage routing problem and procedures based on dynamic programming. Trudy Instituta Matematiki i Mekhaniki UrO RAN. 2022;28(2):215–248. (In Russ.). https://doi.org/10.21538/0134-4889-2022-28-2-215-248

4. Petunin A.A., Chentsov A.G., Chentsov P.A. Optimal routing in problems of sequential traversal of megapolises in the presence of constraints. Chelyabinsk Physical and Mathematical Journal. 2022;7(2):209–233. (In Russ.). 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. Sallam M., Makarovskikh T.A. Designing the Optimal Trajectory for Monitoring Objects. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2024;13(3):32–46. (In Russ.). 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. Mikhailov I.E. Practical comparison of the A* algorithm with the wave tracing algorithm (Lee's algorithm) in terms of performance. Science, Technology and Education. 2016;(1):47–49. (In Russ.).

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.