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