АЛГОРИТМ ПОСТРОЕНИЯ ТРАЕКТОРИИ ДВИЖЕНИЯ БЕСПИЛОТНЫХ АППАРАТОВ ДЛЯ МОНИТОРИНГА СОСТОЯНИЯ СЕЛЬСКОХОЗЯЙСТВЕННЫХ ПОЛЕЙ
Аннотация
Организация непрерывного мониторинга значительных пространств с динамически
меняющимися условиями и обстановкой является одной ключевых задач в различных направ-
лениях жизнедеятельности человека. Особо остро эта задача стоит в России с учетом ее
территорий (земель), предназначенных для сельскохозяйственной деятельности. Особую
важность организации непрерывного мониторинга подчеркивает и развитие концепции и
технологий точного земледелия. В качестве средств для решения этой системной задачи
могут использоваться различные робототехнические и беспилотные системы, оснащенные
необходимым оборудованием в соответствии с локальными задачами непрерывного монито-
ринга. Непрерывный мониторинг при этом может быть обеспечен только применением
эффективных алгоритмов построения траектории движения используемых подвижных ро-
бототехнических и беспилотных (в первую очередь авиационных) систем. Повышение эф-
фективности таких алгоритмов с математической точки зрения всегда усложняется цик-
личностью траекторий движения, т.е. построением гамильтонова цикла. В рамках данной
работы предлагается метод конструирования оптимальной траектории движения при вы-
полнении задач непрерывного циклического мониторинга сельскохозяйственных полей. Метод
основан на поиске гамильтонова цикла на графе карты местности и позволяет автоматиче-
ски строить оптимальный замкнутый путь для произвольной карты местности. Отличи-
тельной особенностью метода является использование модифицированного алгоритма поис-
ка гамильтонова цикла. Алгоритм может быть масштабирован для карт, соответствую-
щих графам с большим (более 100) количеством вершин, для которых стандартный алго-
ритм поиска гамильтонова цикла методом перебора требует значительно большего времени
выполнения, чем предложенный алгоритм. Показано, что используемый алгоритм обладает в
17 раз меньшей константой роста временной сложности, чем стандартный алгоритм поис-
ка гамильтонова цикла. Это позволяет увеличить количество вершин графа, используемого
для поиска гамильтонова цикла в режиме реального времени (от 0.1 до 100 секунд), на поря-
док (от 30 до 500). Разработанный алгоритм может быть внедрён в современные беспилот-
ные системы мониторинга состояния сельскохозяйственных полей для оптимизации траек-
тории движения беспилотных аппаратов в режиме реального времени (0.1-100 секунд), внося
тем самым вклад в динамично развивающуюся область точного земледелия.
Литература
for Dynamic Site Layout Planning in Large-Scale Construction Projects, Buildings, Dec. 2021,
Vol. 11, No. 12, 602 p. DOI: 10.3390/buildings11120602.
2. Nex F. and Remondino F. UAV for 3D mapping applications: a review, Appl. Geomat., Mar.
2014, Vol. 6, No. 1, pp. 1-15. DOI: 10.1007/s12518-013-0120-x.
3. Eun J., Song B.D., Lee S., and Lim D.-E. Mathematical Investigation on the Sustainability of
UAV Logistics, Sustainability, Oct. 2019, Vol. 11, No. 21, 5932 p. DOI: 10.3390/su11215932.
4. Joshi G.P., Alenezi F., Thirumoorthy G., Dutta A.K., and You J. Ensemble of Deep Learning-
Based Multimodal Remote Sensing Image Classification Model on Unmanned Aerial Vehicle
Networks, Mathematics, Nov. 2021, Vol. 9, No. 22, 2984 p. DOI: 10.3390/math9222984.
5. Lindner G., Schraml K., Mansberger R., and Hübl . ‘UAV monitoring and documentation of a large
landslide’, Appl. Geomat., vol. 8, no. 1, pp. 1–11, Mar. 2016, doi: 10.1007/s12518-015-0165-0.
6. érez-Álvarez R., Sedano-Cibrián ., De Luis-Ruiz .M., Fernández-Maroto G., and 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, Jan. 2022, Vol. 12, No. 2, 140 p. DOI: 10.3390/min12020140.
7. Kloepper L.N. and Kinniry M. Recording animal vocalizations from a UAV: bat echolocation during
roost re-entry, Sci. Rep., May 2018, Vol. 8, No. 1, 7779 p. DOI: 10.1038/s41598-018-26122-z.
8. Chodorek A., Chodorek R.R., and Yastrebov A. Weather Sensing in an Urban Environment
with the Use of a UAV and WebRTC-Based Platform: A Pilot Study, Sensors, Oct. 2021,
Vol. 21, No. 21, 7113 p. DOI: 10.3390/s21217113.
9. Su J., Zhu X., Li S., and Chen W.-H. AI meets UAVs: A survey on AI empowered UAV perception
systems for precision agriculture, Neurocomputing, Jan. 2023, Vol. 518, pp. 242-270.
DOI: 10.1016/j.neucom.2022.11.020.
10. Radoglou-Grammatikis P., Sarigiannidis P., Lagkas T., and Moscholios I. A compilation of
UAV applications for precision agriculture, Comput. Netw., May 2020, Vol. 172, 107148 p.
DOI: 10.1016/j.comnet.2020.107148.
11. Chen W.K. Applied Graph Theory. in North-Holland Series in Applied Mathematics and Mechanics.
Elsevier Science, 2012. [Online]. Available: https://books.google.ru/books?id=
kAcBm96mUvsC.
12. Pasqualetti F., Franchi A., and Bullo F. On Cooperative Patrolling: Optimal Trajectories,
Complexity Analysis, and Approximation Algorithms, IEEE Trans. Robot., Jun. 2012, Vol. 28,
No. 3, pp. 592-606. DOI: 10.1109/TRO.2011.2179580.
13. Portugal D. and Rocha R. MSP algorithm: multi-robot patrolling based on territory allocation using
balanced graph partitioning, in Proceedings of the 2010 ACM Symposium on Applied Computing,
Sierre Switzerland: ACM, Mar. 2010, pp. 1271-1276. DOI: 10.1145/1774088.1774360.
14. Elor Y. and Bruckstein A.M. Multi-a(ge)nt Graph Patrolling and Partitioning, in 2009
IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent
Technology, Milan, Italy: IEEE, 2009, pp. 52-57. DOI: 10.1109/WI-IAT.2009.125.
15. Legovich Yu.S., Diane S.A.K., and Rusakov K.D. Integration of modern technologies for solving
territory patroling problems with the use of heterogeneous autonomous robotic systems, in
2018 leventh International Conference ‘Management of large-scale system development’
(MLSD, Moscow: IEEE, Oct. 2018, pp. 1-5. DOI: 10.1109/MLSD.2018.8551884.
16. Caraballo L. ., Díaz-Báñez .M., Fabila-Monroy R., and Hidalgo-Toscano C. Stochastic
strategies for patrolling a terrain with a synchronized multi-robot system, Eur. J. Oper. Res.,
Sep. 2022, Vol. 301, No. 3, pp. 1099-1116. DOI: 10.1016/j.ejor.2021.11.049.
17. Basak A., Fang F., Nguyen T.H., and Kiekintveld C. Abstraction Methods for Solving Graph-
Based Security Games, in Autonomous Agents and Multiagent Systems, N. Osman and C. Sierra,
Eds., in Lecture Notes in Computer Science. Vol. 10003. Cham: Springer International
Publishing, 2016, pp. 13-33. DOI: 10.1007/978-3-319-46840-2_2.
18. Pan J.-S., Song P.-C., Chu S.-C., and Peng Y.-J. Improved Compact Cuckoo Search Algorithm
Applied to Location of Drone Logistics Hub, Mathematics, Mar. 2020, Vol. 8, No. 3, 333 p.
DOI: 10.3390/math8030333.
19. Li Y., Zhang W., Li P., Ning Y., and Suo C. A Method for Autonomous Navigation and Positioning
of UAV Based on Electric Field Array Detection, Sensors, Feb. 2021, Vol. 21, No. 4,
1146 p. DOI: 10.3390/s21041146.
20. Raymond A.S. Stratigraphic sedimentary inversion using paths in graphs, 2017.
21. Goncharenko V.I., Kochkarov A.A., Yatskin D.V., and Rumiantsev B.V. Modeling the Detection
of Moving Objects by Means of a Spatially Distributed Continuous Monitoring System
with a Dynamic Structure, Adv. Syst. Sci. Appl., 2022, Vol. 2, 110 p. DOI:
10.25728/ASSA.2022.22.2.1147.
22. Luo, Zhang, Wang, Wang, and Meng. Traffic Patrolling Routing Problem with Drones in an
Urban Road System, Sensors, Nov. 2019, Vol. 19, No. 23, 5164 p. DOI: 10.3390/s19235164.
23. Deı˘neko V.G., Klinz B., and Woeginger G.J. Exact algorithms for the Hamiltonian cycle problem
in planar graphs, Oper. Res. Lett., May 2006, Vol. 34, No. 3, pp. 269-274. DOI:
10.1016/j.orl.2005.04.013.
24. Deogun J.S. and Steiner G. Polynomial Algorithms for Hamiltonian Cycle in Cocomparability
Graphs, SIAM J. Comput., Jun. 1994, Vol. 23, No. 3, pp. 520-552. DOI:
10.1137/S0097539791200375.
25. Biswas P. Hamiltonian (Graph, Source, Destination). in MATLAB Central File Exchange.
[Online]. Available: https://www.mathworks.com/matlabcentral/fileexchange/51610-
hamiltonian-graph-source-destination.
26. Sipser M. Introduction to the Theory of Computation, ACM Sigact News, 1996, Vol. 27, No. 1,
pp. 27-29.
