ALGORITHM FOR THE CONSTRUCTION OF THE TRAJECTORY OF UNMANNED VEHICLES FOR MONITORING THE CONDITION OF AGRICULTURAL FIELDS
Abstract
Organizing continuous monitoring of large spaces with dynamically changing conditions and
conditions is one of the key tasks in various areas of human life. This task is especially acute in Russia,
taking into account its territories (lands) intended for agricultural activities. The particular importance
of organizing continuous monitoring is also emphasized by the development of the concept and technology
of precision farming. As a means to solve this system problem, various robotic and unmanned systems
can be used, equipped with the necessary equipment in accordance with the local tasks of continuous
monitoring. Continuous monitoring can only be ensured by the use of effective algorithms for constructing
the movement trajectory of the mobile robotic and unmanned (primarily aviation) systems
used. Increasing the efficiency of such algorithms from a mathematical point of view is always complicated
by the cyclical nature of motion trajectories, i.e. construction of a Hamiltonian cycle. This work
proposes a method for constructing an optimal trajectory for continuous cyclic monitoring tasks of agricultural
fields. The method is based on finding a Hamiltonian cycle on the graph of the terrain map and
allows for the automatic construction of an optimal closed path for any terrain map. A distinctive feature
of the method is the use of a modified algorithm for finding Hamiltonian cycles. The algorithm can
be scaled for maps corresponding to graphs with a large (more than 100) number of vertices, for which
the standard brute-force algorithm for finding Hamiltonian cycles requires significantly more execution
time than the proposed algorithm. It is shown that the algorithm used has a 17 times smaller growth
constant in time complexity compared to the standard algorithm for finding Hamiltonian cycles. This
allows for an increase in the number of vertices in the graph used for finding Hamiltonian cycles in
real-time mode (0.1-100 seconds) by an order of magnitude (from 30 to 500). The developed algorithm
can be implemented in modern unmanned monitoring systems for optimizing the trajectory of agricultural
fields monitoring by unmanned vehicles in real-time mode, thus contributing to the dynamically
evolving field of precision agriculture
References
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.
