Б.В. Румянцев1, А.А. Кочкаров1,2

1 Федеральный исследовательский центр «Фундаментальные основы биотехнологии» РАН (Москва, Россия)

1,2 Финансовый университет при Правительстве Российской Федерации (Москва, Россия)

Постановка проблемы. В настоящее время в связи с внедрением автоматизированных средств передвижения актуальной становится задача построения оптимальной траектории движения беспилотных летательных аппаратов (БПЛА) в контексте патрулирования местности, для решения которой требуется разработка быстрых и эффективных интеллектуальных алгоритмов, способных обеспечить построение оптимальной траектории движения в режиме реального времени (0,1-100 с).

Цель. Представить метод построения оптимальной траектории движения БПЛА при патрулировании пересеченной местности на основе теории графов, способный работать в режиме реального времени (0,1-100 с).

Результаты. Предложен метод построения оптимального маршрута патрулирования БПЛА произвольной целевой зоны, основанный на применении модифицированного алгоритма поиска гамильтонова цикла. Показано, что данный метод эффективен как с точки зрения покрытия зоны мониторинга (поскольку обеспечивает малое перекрытие соседних областей видимости), так и относительно скорости выполнения алгоритма поиска гамильтонова пути – постоянная роста временной сложности используемого алгоритма в 17 раз меньше, чем у стандартного алгоритма поиска на основе перебора вариантов движения по узлам графа. Установлено, что за счет меньшей постоянной роста удается более чем на порядок (с 30 до 500 узлов) увеличить число узлов графа, на котором происходит поиск гамильтонова цикла в режиме реального времени (0,1-100 с).

Практическая значимость. Рассмотренный подход может быть эффективно использован как в рамках задач по организации патрулирования БПЛА заданной местности, так и в рамках других задач, требующих нахождения гамильтонова пути на графе с большим числом узлов.

Румянцев Б.В., Кочкаров А.А. Построение траектории движения беспилотных летательных аппаратов при патрулировании пересеченной местности // Информационно-измерительные и управляющие системы. 2022. Т. 20. № 5. С. 55−66.
DOI: https://doi.org/10.18127/j20700814-202205-09

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. Куприянов Н.А., Логунов С.В., Хегай Д.К., Сидоров Б.П., Шпак А.В. Модель оценивания информативности высокоширотного траекторного измерительного комплекса // Наукоемкие технологии. 2021. Т. 22. № 3. С. 89−97. DOI: 10.18127/j19998465-202103-10.