B.V. Rumiantsev1, A.A. Kochkarov2

1,2 Federal Research Centre «Fundamentals of Biotechnology» of the RAS (Moscow, Russia)

2 Financial University under the Government of the Russian Federation (Moscow, Russia)

Problem statement. The task of construction of an optimal movement trajectory in the context of the terrain patrolling task is currently becoming particularly relevant due to the development of automated vehicles. Despite its relevance, this task still requires the development of fast and efficient intelligent algorithms that can ensure the construction of an optimal trajectory in real time regime (0.1-100 s).

Goal. The goal of the work is the development of method for construction of an optimal movement trajectory under terrain patrolling. The developed method is based on the use of graph theory and capable of working in real time regime (0.1-100 s).

Results. The method of search for the optimal movement trajectory in the terrain patrolling tasks, that is based on the search for the Hamiltonian cycle on the graph of the terrain map, is proposed. The method allows automatic building of an optimal closed trajectory from that ensures effective monitoring for any given terrain map. A distinctive feature of the method is the use of a modified algorithm for a Hamiltonian cycle search. This algorithm can be used for maps corresponding to the graphs with a large (>100) number of nodes, for which standard brute-force algorithm of Hamiltonian cycle search requires significantly longer execution time than the proposed algorithm.

Practical significance. It is shown that the developed algorithm has a 17 times smaller time complexity growth constant than the standard brute-force search algorithm, which allows for more than an order of magnitude (from 30 to 500 nodes, approximately 17 times) increase of the number of graph nodes on which the search for the Hamiltonian cycle is realized in real time regime (0.1-100 s).

Rumiantsev B.V., Kochkarov A.A. The method of optimal movement trajectory construction in the context of terrain patrolling task. Information-measuring and Control Systems. 2022. V. 20. № 5. P. 55−66. DOI: https://doi.org/10. 18127/j20700814-202205-09 (in Russian)

1. Hammad W.A., da Costa B.B.F., Soares C.A.P., Haddad A.N. The use of unmanned aerial vehicles for dynamic site layout planning in large-scale construction projects. Buildings. 2021. V. 11. Р. 602.
2. Nex F., Remondino F. UAV for 3D mapping applications: a review. Applied geomatics. 2014. V. 6. Р. 1–15.
3. Eun J., Song B.D., Lee S., Lim D.-E. Mathematical investigation on the sustainability of UAV logistics. Sustainability. 2019. V. 11. Р. 5932.
4. Joshi G.P., Alenezi F., Thirumoorthy G., Dutta A.K., You J. Ensemble of deep learning-based multimodal remote sensing image classification model on unmanned aerial vehicle networks. Mathematics. 2021. V. 9. Р. 2984.
5. Lindner G., Schraml K., Mansberger R., Hübl J. UAV monitoring and documentation of a large landslide. Applied Geomatics. 2016. V. 8. Р. 1–11.
6. Pérez-Álvarez R., Sedano-Cibrián J., de Luis-Ruiz J.M., Fernández-Maroto G., Pereda-Garcı́a R. Mining Exploration with UAV, Low-Cost Thermal Cameras and GIS Tools - Application to the Specific Case of the Complex Sulfides Hosted in Carbonates of Udı́as (Cantabria, Spain). Minerals. 2022. V. 12. Р. 140.
7. Kloepper L.N., Kinniry M. Recording animal vocalizations from a UAV: bat echolocation during roost re-entry. Scientific reports. 2018. V. 8. Р. 1–6.
8. Chodorek R.R., Yastrebov A. Weather Sensing in an Urban Environment with the Use of a UAV and WebRTC-Based Platform: A Pilot Study. Sensors. 2021. V. 21. Р. 7113.
9. Chen W.-K. Applied graph theory. Elsevier. 2012. V. 13.
10. Goncharenko V.I., Kochkarov A.A., Yatskin D.V., Rumiantsev B.V. Modeling the Detection of Moving Objects by Means of a Spatially Distributed Continuous Monitoring System with a Dynamic Structure. Advances in Systems Science and Applications. 2022. V. 22. Р. 1–10.
11. Pan J.-S., Song P.-C., Chu S.-C., Peng Y.-J. Improved compact cuckoo search algorithm applied to location of drone logistics hub. Mathematics. 2020. V. 8. Р. 333.
12. Li Y., Zhang W., Li P., Ning Y., Suo C. A method for autonomous navigation and positioning of UAV based on electric field array detection. Sensors. 2021. V. 21. Р. 1146.
13. Raymond S. Stratigraphic sedimentary inversion using paths in graphs. 2017.
14. Luo H., Zhang P., Wang J., Wang G., Meng F. Traffic patrolling routing problem with drones in an urban road system. Sensors. 2019. V. 19. Р. 5164.
15. Deı V.G., Klinz B., Woeginger G.J., et al. Exact algorithms for the Hamiltonian cycle problem in planar graphs. Operations Research Letters. 2006. V. 34. Р. 269–274.
16. Deogun J.S., Steiner G. Polynomial algorithms for hamiltonian cycle in cocomparability graphs. SIAM Journal on Computing. 1994. V. 23. Р. 520–552.
17. Sahalot А., Shrimali S. A comparative study of brute force method, nearest neighbour and greedy algorithms to solve the travelling salesman problem. International Journal of Research in Engineering & Technology. 2014. V. 2. Р. 59–72.
18. Kochkarov R., Kochkarov A. Introduction to the Class of Prefractal Graphs. Mathematics. 2022. V. 10. Р. 2500.
19. Garcı́a-Dı́az J., Rodrı́guez-Henrı́quez L.M.X., Pérez-Sansalvador J.C., Pomares-Hernández S.E. Graph Burning: Mathematical Formulations and Optimal Solutions. Mathematics. 2022. V. 10. Р. 2777.
20. Sipser M. Introduction to the Theory of Computation. ACM Sigact News. 1996. V. 27. Р. 27–29.
21. Kuprijanov N.A., Logunov S.V., Hegaj D.K., Sidorov B.P., Shpak A.V. Model' ocenivanija informativnosti vysokoshirotnogo traektornogo izmeritel'nogo kompleksa. Naukoemkie tehnologii. 2021. T. 22. № 3. S. 89−97. DOI: 10.18127/j19998465-202103-10 (in Russian).