Graph-Clustering Method for Construction of the Optimal Movement Trajectory under the Terrain Patrolling

Abstract

The method of the optimal movement trajectory construction in the terrain patrolling tasks is proposed. The method is based on the search of the Hamiltonian circuit on the graph of the terrain map and allows automatic construction of the optimal closed path for arbitrary terrain map. The distinguishing feature of the method is the use of the modified algorithm for the Hamiltonian circuit search. The algorithm can be scaled for the maps corresponding to the graphs with a large (more than 100) number of the vertices, for which the standard brute-force algorithm of the Hamiltonian circuit search requires significantly higher execution time than the proposed algorithm. It is demonstrated that the utilized algorithm possesses 17 times less constant of the time complexity growth than the standard brute-force algorithm. It allows more than one order of magnitude (from 30 to 500 vertices, i.e., approximately to the 17 times) increase of the graph vertices that is used for the Hamiltonian circuit search in the real time (0.1–100 s) regime.

1. Introduction

The task of the search for the optimal patrolling path at the present time has special relevance due to implementation of the automated moving devices, which require no presence of the operator and can be used as mobile platforms for a variety of sensor classes: optical, acoustical, chemical, etc. These devices allow solving of the wide range of tasks related to the automation of the spatial monitoring processes [1,2,3,4]. The type of sensors used with these devices is determined by the nature of the tasks that should be solved under the process of terrain patrolling. Therefore, in particular, the patrolling can be carried out with the aim of terrain mapping [5], search for minerals [6], echolocation [7], and also for local registration of the weather conditions [8]. Since effective terrain patrolling requires the construction of the optimal movement trajectory on the given map, the task of the effective patrolling almost inevitably requires the use of the graph theory [9]. The graph-based approaches for the patrolling problem solution are actively used in the modern works. The frequently considered problem is a patrolling with the use of multiple sensors [10]. Therefore, in the work in [11], the problem of efficient patrolling with use of multiple robots in a known environment is solved by assigning individual patrolling regions to each mobile agent. The work in [12] addresses the same problem and demonstrates the method of dynamical graph partitioning by moving ant-like agents using simple local interactions during the patrolling procedure. In another work [13], authors discuss the approach of complex automation of territory patrolling by use of a set of mobile robots and propose the graph-based algorithm for the partitioning of the map between the robots. The article [14] is dedicated to the stochastic graph-based strategy for the terrain patrolling with a set of agents, that can outperform the deterministic approaches.

Another approach for the graph-based solution of the patrolling problem in the frame of Green Security Games is discussed in [15]. In this work, authors propose to construct the patrolling path by the contraction of the complete terrain graph based on the importance of each individual node for the patrolling procedure, which allows reduction of the time complexity in the context of large-graph problem.

In the frame of this work, it is proposed to implement a patrolling procedure on the entire graph with the use of one sensor moving on the map with the given placement of obstacles, which is an alternative to the above-mentioned approaches based on multi-agent partitioning of the graph and its contraction. In this case, as it will be discussed below, the relevant method for the realization of effective terrain patrolling is to construct the graph of the terrain map that allows movement of the sensor over the Hamiltonian circuit [9], i.e., closed path passing through each graph vertex exactly once.

The task of the Hamiltonian circuit search at the present time is a topical mathematical problem, that possess applied nature in a variety of areas. In particular, it is the areas where it is required to realize search of the optimal movement path of an object. These areas include transport and logistics sphere [16,17], geological exploration directions [18], and as it was mentioned above, the area of the terrain patrolling [19,20]. Despite its relevance, the task of the Hamiltonian circuit search remains one of the most difficult for optimization mathematical challenges at the present time.

The problem of the Hamiltonian path search and, in particular, search of the Hamiltonian circuit, is the NP-complete problem and in the case of the brute-force search algorithm possesses exponential time complexity [9]. Under the presence of a priori information about graph that is used for the Hamiltonian path search, it is possible to decrease the time complexity of the problem to the subexponential [21] and even to the polynomial [22] level. Exponential complexity of the Hamiltonian path search on the arbitrary graph restricts the number of the graph vertices that allows solving of the problem in the real-time regime. This factor is of particular importance in applications where it is required to construct an optimal movement trajectory under fast change of the graph configuration.

The motivation of the present work is the development of the real-time (0.1–100 s) algorithm for construction of the optimal patrolling route in the form of the Hamiltonian circuit that ensures the full covering of the given terrain map. The novelty of the method is provided by the modified algorithm of the Hamiltonian circuit search that lies at the core of the proposed method and provides significant acceleration of the search procedure in comparison with the standard brute-force search algorithm while preserving the exponential time complexity. Further in the paper, the complete statement of the problem, the description of the developed theoretic-graph method for the construction of the optimal patrolling trajectory, and the results of the method effectiveness investigation are considered.

2. Problem Statement

In the frame of this work, the task of the terrain patrolling on the given two-dimensional map of the obstacles is considered (Figure 1).

The “patrolling” (or “monitoring”) term in this work means the movement of one sensor over map that is accompanied by the registration of generalized targets. At the initial moment of patrolling targets are placed in the random points ($x,y$) of map with equal probability. During the patrolling procedure, targets randomly move across the map. The ”obstacles” term means the areas of the map where targets cannot be placed and sensors cannot be located. In a real situation, this kind of obstacle could be the mountain chains, reservoirs, and elements of the urban terrain infrastructure, that can be insurmountable obstacles for both the ground- and air-based sensors.

In the context of the approach under consideration, the sensor is assigned by a field of view in which the sensor can register an event. The field of view is a circle of radius $R$ with the center at the sensor location point (Figure 2).

In the discussed model, it is considered that under the process of monitoring, the sensor moves on the map in the discrete manner with the step $\Delta \overrightarrow{r}$ that is less or equal to the diameter $2R$ of its field of view ($1 pix\le \left|\Delta \overrightarrow{r}\right|\le 2R$). This approximation corresponds to the real situation under the condition that time step $\Delta t$ is much less than the complete monitoring time $T$ ($\Delta t\ll T$). The use of this approximation allows treating of the sensor movement as a movement between centers of the fields of view placed in the monitoring area with some intersection (density) between each other. By covering of the monitoring area with fields of view, it is possible to formalize the sensor movement on the map as a movement between vertices of the graph that is constructed in correspondence with the fields of view placement.

It can be demonstrated that in order to minimize the targets detection time, the movement trajectory should represent a Hamiltonian circuit, which is discussed in previous paper concerning the considered problem [19]. The main idea is as follows.

In case of one sensor moving with the constant speed and nonmoving targets, the time of the targets registration $\Delta t_{reg}$ is equal to the time $\Delta t_{sweep}$ of complete sweeping (or coverage) of the monitoring area by the sensor that is inversely proportional to the sweeping rate of the sensor:

$$\Delta t_{sweep}=\frac{S_{total}}{d{S}_{swept}/dt}$$

(1)

where $S_{\mathrm{total}}$ is the total area of monitoring zone, $d{S}_{swept}/dt$ is the sweeping rate that is area of map swept by the sensor in a unit of time. Under the given map area $S_{total}$, in order to minimize the sweeping time $\Delta t_{sweep}$ and, consequently, the registration time $\Delta t_{reg}$, it is required to maximize the sweeping rate $d{S}_{swept}/dt$. In turn, under the given sensor movement speed, this maximization can be realized if every point of the map is covered exactly once during the period $\Delta t_{sweep}$. This is ensured by the movement of the sensor along the Hamiltonian path on the terrain graph.

In the case of moving targets, the single sweeping of the patrolling area can be insufficient for the registration of all targets and more sweeping cycles can be required. The cyclic sweeping of the patrolling zone, which ensures the coverage of every point of the map during one patrolling cycle exactly once and with equal coverage period, requires the return of the sensor to the initial point at every patrolling cycle. This can be ensured using the Hamiltonian cycle instead of the Hamiltonian path as a movement trajectory of the sensor. Thus, the optimal movement trajectory, which minimizes the detection time of moving targets in the discussed problem, is a Hamiltonian cycle.

Thus, the task of the effective terrain patrolling can be divided into two consecutive tasks. The first task is the realization of the effective covering of the target monitoring zone with the sensor fields of view and construction of the terrain graph in accordance with the obtained placement of the fields of view. The second task is the search for the Hamiltonian cycle on the constructed terrain graph that represents the optimal movement trajectory for the sensor. Further in the Section 3 “Method description”, the algorithms for the solution of these two tasks are discussed.

3. Method Description

3.1. The Algorithm of Target Zone Covering

In order to cover the monitoring area with the sensor fields of view, the following algorithm is used (Figure 3).

In order to ensure the effective monitoring of the terrain map that is characterized by the minimal crossing area between sensor fields of view and obstacles, the size of the field of view $R$ should be less or equal to the minimal distance between the obstacles on the given map.

At the first step the grid with the uniform step $\Delta r$ consisting of the fields of view is constructed on the map, where step $\Delta r$ is set as $\Delta r=\rho \cdot 2R$, $\rho \in \left(0,1\right]$ is the factor that determines the density of the fields of view placement. The term density is used because $\rho$ determines the distance between the neighboring fields of view. Therefore, the smaller $\rho$, the more fields of view is placed on a given area, that indicates the increase of density of the fields of view placement.

At the second step, the grid is distorted: the grid step is changed in such a way that the size of the noncovered map region along $x$ axis is less or equal to $0.5\cdot \rho R$ (Figure 3). The fields of view are placed in the nodes of the distorted grid lying outside the obstacles.

As a result of the conducted procedure, the grid consisting of the sensor fields of view is formed on the map. After passing through each of the grid nodes, the sensor will provide an almost complete scan of the target monitoring zone area. As will be discussed in Section 3.1, the fundamental limit of the fraction of covered area is 0.75 for the square map filled with the circular sensor fields of view without overlap. This means that the area of map patrolled by the sensor with the circular field of view will be covered almost completely, i.e., 75% of the map area will be scanned. This is the consequence for the application that cannot be overcome in the task of the patrolling with use of the sensor with circular shape of the field of view. The possible solution here is to overlap fields of view on the terrain map, which inevitably leads to the loss of the patrolling optimality, since in this case there will be “selected” points, which sensor monitors for more time, than the other ones, under one cycle of the terrain scan.

As mentioned above, the optimal movement trajectory, which minimizes the detection time of moving targets in the discussed problem, is a Hamiltonian cycle. In order to find the Hamiltonian circuit, the grid of the sensor fields of view is treated as a simple undirected graph $G_1\left(V_1,E_1\right)$ with the vertices located at the corresponding nodes of the grid, i.e., at the centers of the sensor fields of view (Figure 4).

The edges $E_1$ of the graph $G_1\left(V_1,E_1\right)$ connect those vertices $V_1$ that are located at the distance of the sensor step $\left|\Delta \overrightarrow{r}\right|$ from each other, $\left|\Delta \overrightarrow{r}\right|\le 2R$. The terrain graph $G_1\left(V_1,E_1\right)$ does not contain self-loops $\left(i,i\right)$ and parallel ${\left(i,j\right)}_k$ edges [9].

3.2. Algorithm of the Hamiltonian Circuit Search

The idea of the algorithm is as follows. In the frame of the stated patrolling problem, the number of the terrain graph vertices $V_1$ can be too high to implement the standard brute-force algorithm [23] for the Hamiltonian circuit search in real-time regime specified in this work as 0.1–100 seconds (3 orders of magnitude). In order to overcome the problem of the graph size, the following method is proposed. The terrain graph is decomposed into the so-called clusters, i.e., separate connected graphs $g_k\left(v_k,e_k\right)$, $k\in \left[1,n\right], n=\left|V_1\right|/N, v_k\in V_1$ which contains low number of the vertices $N$ ($N=20-30$ in the frame of the conducted computational experiments), that allows application of the standard brute-force algorithm for the Hamiltonian path search in real-time regime in the frame of each cluster. The decomposition of the terrain graph $G_1\left(V_1,E_1\right)$ into clusters $g_k\left(v_k,e_k\right)$ allows consideration of the clusters set $\left\{g_k\left(v_k,e_k\right)\right\}$ as a single high-level graph $G_0\left(V_0,E_0\right)$, which can be treated as a terrain graph in the zero approximation, where clusters $g_k\left(v_k,e_k\right)$ acts as vertices $V_0$, and edges $E_0$ connect vertices $V_0$, which correspond to the neighboring clusters. In the zero approximation, it can be considered that the movement of the sensor under the patrolling procedure is realized over the graph $G_0\left(V_0,E_0\right)$, which ensures the Hamiltonian circuit search on its vertices in real-time regime due to low number $N$ of the vertices $V_0$. At the next step, in order to clarify the route, the sensor movement in the frame of each cluster $g_k\left(v_k,e_k\right)$ is considered. The movement trajectory of the sensor in each cluster is set as Hamiltonian path $p_k\left(g_k\right)$ that allows movement of the sensor from initial vertex in k^th cluster $g_k\left(v_k,e_k\right)$ to connected with the k^th cluster vertex of the (k+1)^th cluster $g_{k+1}\left(v_{k+1},e_{k+1}\right)$. The latter vertex becomes the initial vertex in (k+1)^th cluster. The search of every Hamiltonian path $p_k\left(g_k\right)$ is realized with use of the standard brute-force algorithm, which due to the low ($N=20-30$) number of the cluster vertices, can be implemented in real-time regime. By the connection of the Hamiltonian paths $p_k\left(g_k\right)$ in accordance with the Hamiltonian circuit over the graph $G_0\left(V_0,E_0\right)$, the total Hamiltonian circuit $C_1\left(G_1\right)$ over the graph $G_1\left(V_1,E_1\right)$ is constructed.

In the common case of arbitrary high number of the terrain graph vertices $V_1$, it is possible to accelerate the procedure of the Hamiltonian circuit search by the recursive multi-level repetition of the clustering process, which can be done with use of the fast METIS algorithm [24], and search for the Hamiltonian paths in each cluster. In the frame of the present work, the case of a single-level clustering was realized, which provided the opportunity to increase the number of graph vertices in 17 times in comparison with the brute-force method while maintaining the real-time nature of the calculations.

The algorithm of the method is as follows (Figure 5). First, the clustering of the terrain graph vertices $V_1$ is performed. In the frame of clustering procedure at the first step, the ascending sorting of the graph vertices $V_1$ in accordance with vertices degree $d$ is conducted. The formation of the first cluster $g_1\left(v_1,e_1\right)$ is performed starting from the vertex with the lowest degree $d$. The neighboring vertices with the degree $d\ge 2$ in relation to the cluster $g_1\left(v_1,e_1\right)$ are added to this cluster until either number of vertices in this cluster is equal to limiting number of vertices $N$ or vertices with the degree $d\ge 2$ in relation to this cluster are absent. The formation of the next cluster $g_2\left(v_2,e_2\right)$ is conducted by starting with the non-clustered vertex with the lowest degree $d$ among remaining ones. The repeating of this procedure provides the clustering of almost all vertices of the terrain graph $G_1\left(V_1,E_1\right)$. The clustering process is, in fact, the operation that is reversed in relation to the operation of the replacing a graph vertex with a seed [25]. The algorithm of clustering itself can be treated as a solution of the graph burning problem [26]. The number of the remaining non-clustered vertices is relatively low and in the frame of the conducted experiments was no more than 5% of the total number of the terrain graph vertices (Figure 5).

After the clustering procedure, the search of the Hamiltonian circuit $C_0\left(G_0\right)$ on the graph of clusters $G_0\left(V_0,E_0\right)$ is started (Figure 6).

If the Hamiltonian circuit $C_0\left(G_0\right)$ on the graph of clusters is absent, the density of the fields of view placement is increased by the decrease of the factor $\rho$. Then, the clustering starts again and the search of the Hamiltonian cycle $C_0\left(G_0\right)$ is performed on the updated graph $G_0\left(V_0,E_0\right)$. This procedure is repeated until the Hamiltonian cycle $C_0\left(G_0\right)$ is found. Discussing this in more detail, if the algorithm does not find Hamiltonian cycle at the fixed density coefficient $\rho$, the $\rho$ is decreased by small step (0.05 in our realization), the terrain graph is updated in correspondence with the updated vertices placement, and the algorithm tries to find Hamiltonian cycle on the updated terrain graph. Since the increase of the density of the vertex placement under decrease of $\rho$ adds new vertices to the terrain graph and, therefore, opens new possible routes for the sensor movement, then under certain small $\rho$, the possibility of Hamiltonian cycle construction on the terrain graph will be guaranteed. Hamiltonian cycle found under sufficiently small $\rho$, which results in significant overlap of sensor fields of view, will not be optimal, since in this case, there will be “selected” points in the overlapped regions, which sensor monitors more time under one cycle of the terrain scan than the other ones.

After the Hamiltonian cycle $C_0\left(G_0\right)$ is found, the search of the Hamiltonian paths $p_k\left(g_k\right)$ in each cluster $g_k\left(v_k,e_k\right)$ is performed. As it was mentioned above, the search is conducted in such a way that every Hamiltonian path $p_k\left(g_k\right)$ is connected with the Hamiltonian path $p_{k+1}\left(g_{k+1}\right)$, where order $k$ of the clusters $g_k$ is fixed by the Hamiltonian cycle $C_0\left(G_0\right)$. The subsequent connection of the Hamiltonian paths $p_k\left(g_k\right)$ gives the total Hamiltonian cycle $C_1\left(G_1\right)$ over the full terrain graph $G_1\left(V_1,E_1\right)$ (Figure 7).

Formulation of the total algorithm for terrain graph construction and search of the Hamiltonian circuit is presented in Algorithm 1 as MATLAB-like pseudo-code.

Algorithm 1 MATLAB-like pseudo-code of the total algorithm

hamCycle = empty; % initialization of total Hamiltonian cycle as empty constant. N = 21; % Initialization of maximal number of nodes in cluster. rhoCounter = 0; while hamCycle == empty  rho = 1 – rhoCounter*0.01; % density factor $\rho$  %------------------------------------------------  % Construction of the terrain graph $G_1\left(V_1,E_1\right)$     undistortedPlacement = fieldsUndistortedPlacement(Map, R rho);     distortedPlacement = fieldsDistortedPlacement(Map, R, rho, undistortedPlacement);     terrainGraph = createTerrainGraph(distortedPlacement, R, rho);     numGk = round(numNodes(terrainGraph)/N); % Calculation of number of clusters     % ----------------------------------------------     % Execution of clustering procedure:     for i = 1:1: numGk     Gk(i) = “node with maximal degree $d$ among non-clustered nodes”;     n = 0;       while n < N or “no new nodes with $d\ge 2$ for current cluster Gk(i)”        Gk(i) = [Gk(i) “node with $d\ge 2$ for Gk(i)”];       end     end     %-----------------------------------------------------------------     % Construction of the graph of clusters $G_0\left(V_0,E_0\right)$     clustersGraph = createClustersGraph(Gk, R, rho);     %-----------------------------------------------------------------     % % Search of Hamiltonian cycle $C_0\left(G_0\right)$ over graph of clusters $G_0\left(V_0,E_0\right)$     hamCycleClusters = hamiltonianCycle(clustersGraph);     %-----------------------------------------------------------------     % Search of Hamiltonian paths $p_k\left(g_k\right)$ inside every cluster-subgraph $g_k\left(v_k,e_k\right)$     if hamCycleClusters != empty      for i = 1:1:length(Gk)      hamPath(i) = hamiltonianPath(Gk(hamCycleClusters(i)), Gk(hamCycleClusters(i + 1)));       if hamPath(i) == empty         break;       end      end      %-------------------------------------------------------------- % Connecting of Hamiltonian paths $p_k\left(g_k\right)$ to the total Hamiltonian cycle $C_1\left(G_1\right)$ over the terrain % graph $G_1\left(V_1,E_1\right)$      hamCycle = connect(hamPath);     end end

4. Results and Discussion

In order to characterize the efficiency of the discussed approach for the search of optimal patrolling route, it is proposed, first of all, to characterize the efficiency of the terrain map covering algorithm and, secondly, to compare the time complexity of the proposed algorithm for the Hamiltonian circuit search with the time complexity of the standard brute-force algorithm.

The realization of the brute-force method, used in the frame of the discussed work, is presented in [27]. This recursive algorithm checks at every iteration if the neighboring vertex can be added to the Hamiltonian circuit or it has already been added. Thus, the algorithm iterates through the path options and finally finds the Hamiltonian cycle in case it exists for the given graph.

The execution of discussed algorithms was performed in MATLAB R2021b (Mathworks, Natick, MA, USA) with the use of CPU 11th Gen Intel Core i7-11800H, 2.30 GHz.

4.1. Efficiency of the Terrain Map Covering Algorithm

For the assessment of the efficiency of the terrain map covering algorithm the ratio $S_{\Sigma }/S_{\Omega }$ can be used, where $S_{\Sigma }$ is a total area of the monitoring zone covered by the sensor fields of view, $S_{\Omega }$ is a total area of the monitoring zone. As a reference value of this ratio there can be used the value that characterizes the covering of the square monitoring zone by the non-overlapping sensor fields of view (Figure 8). The value of ratio $S_{\Sigma }/S_{\Omega }$ in this case is equal to $\pi /4 \approx 0.75$ for every radius of the sensor fields of view inscribed in the monitoring area.

Based on this value, it is possible to characterize the coverage efficiency as follows: $S_{\Sigma }/S_{\Omega }<0.75$ corresponds to the insufficient coverage of the target monitoring zone, $S_{\Sigma }/S_{\Omega }=0.75$ corresponds to the maximum coverage of the target zone provided there is no overlap of the fields of view areas, $S_{\Sigma }/S_{\Omega }>0.75$ corresponds to the increase of the coverage area of the target zone due to the overlapping of the fields of view. Thus, one has to choose between maximization of the covered area of target zone and minimization of the overlap area of the fields of view. The discussed algorithm allows reaching of values $S_{\Sigma }/S_{\Omega }$ at the level of 0.75–0.85, which indicates the relatively low (the ratio of overlap area to the area of target zone is $S_{\cap }/S_{\Sigma }\approx 0.01-0.03$ on the map in Figure 2) overlap of the fields of view, which provides increase of the covered area in comparison with the case of $S_{\Sigma }/S_{\Omega }=0.75$. A possible improvement of this coverage algorithm for the increase of the coverage area while maintaining the overlap area of the fields of view is to realize distortion procedure of the covering grid relatively to both $x$ and $y$ axes.

4.2. Efficiency of the Algorithm for the Hamiltonian Circuit Search

In order to characterize the efficiency of the proposed algorithm for the Hamiltonian circuit search, the concept of time complexity is used [28]. The strict mathematical derivation of the computational complexity of the proposed algorithm seems to be hardly retrieved, since the performance depends on the map configuration. However, the statistical approach, which is realized by measurement of the algorithm execution time on the different maps, allows experimental determination of the complexity asymptotic law. It is the approach that has been used in the frame of the present work for the establishment of the time complexity growth law. The comparison of the experimentally determined time complexity for modified algorithm and standard brute-force search method is presented in Figure 9.

To obtain these dependencies, the algorithms were run for various maps with random location of obstacles and different sizes of visibility areas, that allowed achievement of a different number of terrain graph vertices.

As it is indicated in Figure 9, the standard brute-force algorithm is performed in a real-time regime (0.1–100 seconds) in the case of graphs with the number of vertices up to 30, while the proposed modified method allows enhancement of this range up to 500 vertices. It should be mentioned that values of 30 and 500 vertices determine the number of vertices corresponding to the increase of the execution time by three orders of magnitude for standard brute-force and modified algorithms respectively.

Both discussed algorithms possess the exponential law of the time complexity growth under the increase of the input data volume, that is represented by the number of terrain graph vertices $V_1$. However, the growth constant $t_1$ (Figure 9) of the time complexity curve for the modified algorithm is significantly lower (in $36.52/2.16\approx 17$ times) than the one for the brute-force algorithm. Due to this fact, it is possible to increase by more than an order of magnitude (from 30 to 500 vertices, approximately in $500/30\approx 17$ times) the number of the terrain graph vertices while keeping unchanged the real-time nature of the search procedure. Thus, in comparison with the standard brute-force algorithm, the use of the proposed modified algorithm makes it possible to significantly increase the number of graph vertices which are used for search of the Hamiltonian circuit in real-time (0.1–100 s) regime.

5. Conclusions

In the frame of the present work the method for the construction of the optimal path for arbitrary terrain map patrolling is developed. The method is based on the use of the modified algorithm for the search of Hamiltonian circuit on the terrain graph. It is demonstrated that the proposed method is effective both in the coverage of the monitoring zone, since it provides almost total coverage of the terrain area, and in the search of the Hamiltonian circuit over the terrain graph, since it ensures the increase of the search rate in comparison with the standard brute-force method. Moreover, in comparison with the brute-force method the proposed algorithm for the Hamiltonian circuit search allows more than an order of magnitude increase of the number of graph vertices (from 30 to 500 vertices, in $500/30\approx 17$ times), which are used for the real-time (0.1–100 seconds) search of Hamiltonian circuit. The proposed approach of the vertices clustering that is used in the frame of the developed Hamiltonian circuit search procedure can be scaled to the graphs with the higher number of vertices by the recursive multi-level clustering of the terrain graph vertices.

The implementation of the proposed method in practical cases could be as follows. A user uploads the 2D terrain map to the computer program, which uses described algorithm for the patrolling path construction. The constructed path (i.e., the sequential set of 2D coordinates) is uploaded to the automated moving device which carries a sensor. Finally, moving device starts to patrol the terrain according to the uploaded path while the current position of device is monitored via, for example, GPS.

Thus, the discussed method can be applied both in the frame of the terrain patrolling problems and in the common area of tasks which require the use of the fast algorithm for the Hamiltonian circuit search on the large graphs.