In this paper, our goal is to plan a coverage path over an area of interest where NFZs exist. The requirements to fulfill for the CPP are:

  • Complete coverage of the area of interest;

  • Ensure minimum completion time, by lowering the turning angle and the length of the planned path.

  • Avoid passing over the interior of NFZs, but the boundary lines of NFZs are passable;

We use one UAV in offline mode to cover an area where NFZs exist. We build the CPP problem model using grid-based technique. We propose the PSAACO to make path planning on this problem model. Furthermore, to avoid the NFZs, we propose a DFA, which can dynamically add points and only need to calculate the changes caused by these points without recalculating the entire algorithm.

Problem Model

We consider planning a path for an area of size approximately 100m (times) 80m, the area is shown in Fig. 1a. In the figure, the grey polygon represents the area that needs to be covered and searched, while the red polygons represent the NFZs.

Fig. 1
figure 1

Grid-based area decomposition and cells labeling

Similarly to [40], this work uses the grid-based technique to model the investigated area. We map the geographical area to grid cells, and the mapped image is shown in Fig. 1b. The longest side of the area is aligned parallel to the X-axis or Y-axis of the mapped image by means of coordinate transformation. Each grid cell has rectangular shape, and its size is determined by the UAV footprint, what it means is the area the UAV can cover at one time [47]. In Fig. 1b, each grid cell is 20 meters long and 20 meters wide. Grid cells filled entirely or partially with grey represent areas that need to be covered, and grid cells filled with red represent NFZs, while the unfilled cells mean areas that do not need to be covered or are not prohibited to fly over.

In Fig. 1c, we label the key points of the mapped image. The key points are divided into two categories, named as A-Type points and N-Type points, respectively. A-Type points are the center points of the grid cells that need to be covered and searched, marked with orange circular labels in the figure. N-Type points are the vertices of NFZ polygons, and marked with red circular labels. The key points in each row are numbered from left to right (x increasing direction), and the rows are numbered incrementally from top to bottom (y increasing direction). The text in each label consists of its type name and sequentially number.

In this work, a key point is represented as a vector V(tesnxy) , where coord(xy) is the coordinate, te is the type of the point, sn is the sequentially number. For example, in Fig. 1c, point (V_{A10}) can be represented by a vector (V(“A”,10,70,50)), while point (V_{N7}) can be represented by a vector (V(“N”,7,20,60)).

NFZs are described by rectangles, eg rectangle (NR(V_{N0},V_{N1},V_{N5},V_{N4})) is an instance of NFZ. If some NFZ rectangles have common edges, try to combine them into a larger rectangle, eg rectangle (NR(V_{N6},V_{N7},V_{N10},V_{N9})) and rectangle (NR(V_{N7},V_{N8},V_{N11},V_{N10})) can be combined into rectangle (NR(V_{N6},V_{N8},V_{N11},V_{N9})). After the NFZs are combined, we can remove those redundant N-Type vertices that are not used to form the NFZ rectangles. Figure 1d shows the area image after removing the redundant vertices.

Figure 1e shows an example of CPP, the back-and-forth is applied on the area. The blue polyline represents the planned path, which starts at point (V_{A4}) and ends at (V_{A14}). In this paper, one path is described by one sequence of points it passes through, and the planned path without considering NFZ avoidance is as follows.

$$begin{aligned} P_{i}=P(V_{A4},V_{A3},V_{A2},V_{A1},V_{A0},V_{A5},V_{A6},V_{A7},V_{A8},V_{A11},V_{A10},V_{A9},V_{A12},V_{A13},V_{A14}) end{aligned}$$

(1)

In this work, we detect whether all line segments in the path intersect the diagonal of the rectangle. If there is a line segment that intersects the diagonal of the NFZ rectangle, it is considered that the line segment has passed the NFZ, and NFZ avoidance processing is required. Use a set named NFZS to record the diagonals of all NFZ rectangles. In Fig. 1e, the diagonals in NFZS are represented by red line segments, and NFZS is as follows.

$$begin{aligned} NFZS={LS(V_{N0},V_{N5}), LS(V_{N1},V_{N4}), LS(V_{N2},V_{N8}), nonumber \ LS(V_{N3},V_{N7}), LS(V_{N6},V_{N10}), LS(V_{N8},V_{N9}))} end{aligned}$$

(2)

As a special case, the line segment (LS(V_{N7},V_{N8})) is the common edge of two NFZs, which is considered to be the interior of the area. If there is an intersection between the path (P_{i}) and (LS(V_{N7},V_{N8})), NFZ avoidance is also required. The common edge (LS(V_{N7},V_{N8})) is also recorded in NFZS, and the complete NFZS of the Fig. 1e is as follows.

$$begin{aligned} NFZS={LS(V_{N0},V_{N5}), LS(V_{N1},V_{N4}), LS(V_{N2},V_{N8}), nonumber \ LS(V_{N3},V_{N7}), LS(V_{N6},V_{N10}), LS(V_{N8},V_{N9})), LS(V_{N7},V_{N8})} end{aligned}$$

(3)

As can be seen from Fig. 1e, the line segment (LS(V_{A7},V_{A8})) of the path intersects (LS(V_{N0},V_{N5})) in the NFZS , which means that the planned path (P_{i}) passes through the NFZ, but this is not allowed.

In this paper, we use N-Type points to avoid NFZs. Two N-Type points, (V_{N0}) and (V_{N1}), are inserted into the line segment (LS(V_{A7},V_{A8})). The update path (P_{j}) successfully avoids the NFZ, the vector of (P_{j}) is as follows, and it is illustrated in Fig. 1f.

$$begin{aligned} P_{j}=P(V_{A4},V_{A3},V_{A2},V_{A1},V_{A0},V_{A5},V_{A6},V_{A7},V_{N0},V_{N1},V_{A8},V_{A11},V_{A10},V_{A9},V_{A12},V_{A13},V_{A14}) end{aligned}$$

(4)

In short, the CPP problem in this paper can be regarded as an optimization problem. The problem is described as follows: plan a path passing through all A-Type points, require each A-Type point to be traversed only once, use N-Type points to avoid the NFZs, and require the shortest time for a UAV to cover the path. The mathematical model of the CPP problem can be described by Eq. 5.

$$begin{aligned} tau = underset{forall P_i in G}{minimize} f(P_i,nu ,psi ) end{aligned}$$

(5)

Where f is a function to calculate the completion time for a planned path. (tau) is the minimum completion time of all paths. (P_i) is a planning path, as in Eq. 4. (nu) is UAV speed, and (psi) is UAV rotation rate. G means area after decomposition, which is composed of several sets. VAS is the set of A-Type points, containing all A-Type points in the area, while VNS is the set of N-Type points. NFZS defines a set of line segments to determine whether NFZ avoidance is required, which consists of the diagonals of the NFZ rectangles and the common edge of two NFZ rectangles.

$$begin{aligned} G=G(VAS,VNS,NFZS) end{aligned}$$

(6)

The mathematical model of the CPP problem subject to:

$$begin{aligned} forall V_k in P_i rightarrow V_k in (VAS cup VNS) end{aligned}$$

(7)

$$begin{aligned} forall V_k in VAS rightarrow V_k in P_i end{aligned}$$

(8)

$$begin{aligned} i ne j, V_i in P_k,V_j in P_k rightarrow V_i ne V_j end{aligned}$$

(9)

$$begin{aligned} forall LS_x in P_i, forall LS_y in NFZS rightarrow LS_x cap LS_y=varnothing end{aligned}$$

(10)

Constraint formula 7 represents any point in the planned path (P_i), which must also exist in the set of A-Type points or N-Type points. Constraint formula 8 indicates that (P_i) contains all A-Type points. Constraint formula 9 shows that each point in (P_i) can only appear once, and no two identical points exist in the same path. Constraint formula 10 states that the line segment (LS_x) in (P_i) does not intersect with the line segment (LS_y) in NFZS, that is, the path (P_i) does not pass through the NFZs.

Table 1 defines the notation of relevant sets, vectors, parameters and variables of our work.

Table 1 Table of notations

PSAACO Algorithm for CPP

Ant colony algorithm(ACO) is a bionic optimization algorithm, which simulates the behavior of ant colony foraging in nature, and uses probabilistic search technology to find the optimal path. This technique is first introduced by Dorigo and his colleagues [48], and then many scholars have continuously enriched and improved it, forming an algorithm family. The well-known algorithms in the algorithm family include: Elitist Ant System (EAS) [49], Rank Based Ant System(ASRank) [50], MAX-MIN Ant System (MMAS) [51], Ant Colony System(ACS) [52], etc. ACO is used for many applications especially complex combinatorial optimization problems such as vehicle routing problem (VRP) [53], job-shop scheduling problem (JSP) [54], traveling salesman problem (TSP) [55], quadratic assignment problem (QAP) [56], and so on.

In this paper, we extend the ACO algorithm presented in our previous work [57], and propose a new PSAACO to deal with CPP problem. This new PSAACO algorithm is mainly expanded as follows: make some modifications to solve CPP problems, modify the self-adaptive strategy to construct and apply a new parameter vector at each iteration, apply the inversion and insertion operators to construct new solutions, use a multi-threaded parallel computing approach to improve the solution quality and search speed.

The pseudocode of the PSAACO is presented in Algorithm 1. As seen in the algorithm, procedure InitializeGlobalParameters() is used to initialize the global parameters G, (psi), (nu), TdNum, Itmax,Itmax2, Cmax, Cmin, a, n and q, whose meanings are provided in the algorithm. The G is an instance of CPP model, as represented by Eq. 6. The CPP model instance contains three sets: A-Type points set VAS, N-Type points set VNS and line segments set NFZS. The following subsections elaborate on the other procedures in the algorithm.

figure a

Calculate the Sub-path Matrix after Avoiding NFZs

The pseudocode used for calculate the sub-path matrix is in Algorithm 2. As seen in the Algorithm 2, in steps 6 to 16, it is checked whether the line segment composed of any two points in VAS has an intersection with the line segment defined by NFZS. If there is no intersection, the corresponding element value in the sub-path matrix is assigned to the sub-path composed of these two points. If there is an intersection, it means that the line segment passes through the NFZs, then start the NFZ avoidance algorithm to obtain the sub-path and assign the obtained sub-path to the element in the sub-path matrix. The procedure GetSubpathByFloyd in step 18 will be described in later subsection.

For example, in the CPP model instance shown in Fig. 1, the line segment consisting of (V_{A6}) and (V_{A7}) has no intersection with any line segment in NFZS, so the value of PM[6][7] is (SP(V_{A6},V_{A7})). And the line segment (LS(V_{A7}, V_{A8})) has an intersection with the line segment (LS(V_{N0},V_{N5})) in NFZS, so the value of PM[7][8] is (SP(V_{A7},V_{N0},V_{N1},V_{A8})) after NFZ avoidance processing.

figure b

The Procedures for Solution

As seen in the Algorithm 1, the main processing flow for the solution archive in the PSAACO algorithm is indicated below:

  • The first process applies the “InitializeSolutionArchive” procedure in step 10 to initialize the solution archive, and uses “UpdateSolutionArchive” procedure in step 11 to update the archive.

  • The second process corresponds to steps 21 to 23 in the algorithm. Each ant selects a base solution from the solution archive, constructs one new solution from the base solution by “ConstructSolution” procedure, and then adds the new solution into the solution archive.

  • The third process uses the “UpdateSolutionArchive” procedure to sort the solutions in the solution archive by their quality, then keep the best n solutions in the solution archive and remove redundant solutions.

  • Repeat the second and third process before a termination condition is satisfied.

The structure of solution archive

The structure of solution archive S of PSAACO algorithm is shown in Fig. 2. The solution archive stores n solutions. Each solution (s_j) is represented by an m-dimensional vector, as shown in the following formulas:

$$begin{aligned} s_{j}=(s_j^1, s_j^2, cdots , s_j^i, cdots , s_j^m) end{aligned}$$

(11)

(f(s_j)) and (omega _j) means the fitness value and selection weight of solution (s_j) ,respectively.

Fig. 2
figure 2

The structure of solution archive

For the CPP problem, each solution of PSAACO corresponds to a planned path without NFZ avoidance, and each variable in the solution corresponds to the sn of one point in the path. For example, the solution (s_{i}) corresponding to the path (P_i) described in Eq. 1 is as follows:

$$begin{aligned} s_{i}=s(4,3,2,1,0,5,6,7,8,11,10,9,12,13,14) end{aligned}$$

(12)

Initializing solution archive

The pseudocode used for generating the initial solutions for the solution archive is presented in Algorithm 3. As seen in the algorithm, each solution was randomly generated as a permutation of the set of the points in VSA. Then, each solution is converted to a path using the “getPathFromSolution” procedure in step 4. The fitness value of the path is calculated in step 5, and the new solution is added into the solution archive in step 6.

figure c

The pseudocode of the “getPathFromSolution” procedure is shown in Algorithm 4. Take out two adjacent points of the solution solu in turn, query their corresponding sub-paths from PM, and combine these sub-paths into a complete path P. Since the sub-paths in PM are NFZs-avoiding, the new path is also NFZs-avoiding.

figure d

Constructing new solutions probabilistically

First, each ant applies the roulette wheel selection algorithm, probabilistically selecting a solution from the solution archive S. As shown in the following equation, the selection probability (PS_j) of the solution (s_j) is calculated according to its selection weight (omega _j).

$$begin{aligned} PS_j = dfrac{omega _j}{sum _{i=1}^{n}{omega _i} } end{aligned}$$

(13)

Where (omega _j) can be calculated by Eq. 14. In the equation, (eta) represents the search size constant, and n is the number of solutions in S.

$$begin{aligned} omega _j = dfrac{1}{eta n sqrt{2pi }}{e^{dfrac{-(j-1)^2}{2eta ^2n^2}} } end{aligned}$$

(14)

Then, a new solution is built based on the selected solution. Similarly to [58], this work uses the local search operators to construct a solution. The pseudocode to construct a new solution is shown in Algorithm 5. We use the inversion and insertion operators, which are among the most popular local search operators. The algorithm chooses to use the inversion operator with a probability of 50%, as shown in steps 6 and 7. And the insertion operator is selected with a probability of 25% in steps 8 and 9. In steps 10 to 22, we apply the inversion operator multiple times in a continuous loop, and take the best constructed solution as the new solution. The local search operators can be described as follows:

  • The inversion operator: The inversion operator simply inverses the variables of the solution between positions x and y. In other words, it randomly selects two positions on the solution and then reverses the sub-path between these two positions. For example, inversion((s_i, x, y)) generates a new solution (s_j), which is (s_j=(s_i^1,cdots ,s_i^{x-1},s_i^y,s_i^{y-1},cdots ,s_i^x,s_i^{y+1},cdots ,s_i^n)), where (1le x < y le n).

  • The insertion operator: The insertion operator randomly selects the positions x and y in the solution. Then it moves the variable from Position y to Position x. Insertion((s_i, x, y)) generates a new solution (s_j), which is (s_j=(s_i^1,cdots ,s_i^{x-1},s_i^y,s_i^x,s_i^{x+1},cdots ,s_i^{y-1},s_i^{y+1},cdots ,s_i^n)) , where (1le x < y le n).

figure e

Updating the solution archive

The “InitializeSolutionArchive” and “ConstructSolution” procedures add some new solutions into the solution archive S. The “UpdateSolutionArchive” procedure performs the update S operation. First, the solutions in S containing new solutions are sorted according to their fitness function value, and the solutions with good quality are ranked above the solutions with poor quality. Then, the top n solutions with the best quality in S are retained, and other redundant solutions are removed.

The Procedures for Self-Adptive Parameters

Some parameters greatly affect the performance of PSAACO. The scheme of manually setting parameters depends too much on the experience of setting personnel. This paper adopts a self-adaptive parameters setting scheme for PSAACO.

Fig. 3
figure 3

The structure of parameter archive

The self-adaptive parameter archive C is added to store these self-adaptive parameters. Assume that there are a parameter setting schemes, and each scheme is a vector composed of b self-adaptive parameters, the corresponding parameter archive is shown in Fig. 3. (c_j^i) is the i-th parameter value in the j-th parameter vector. (f(c_j)) is the fitness value of the (c_j). (omega _j) means the weight of (c_j).

In the algorithm 1, the main processing flow for the self-adaptive parameters in the PSAACO algorithm is indicated below:

  • The first process applies the “InitializelParameterArchive” procedure in step 7 to initialize the parameter archive. Randomly create a parameter vectors and store them into the parameter archive.

  • The second process corresponds to steps 15 to 29 in the algorithm. Each iteration selects a base parameter vector from the archive, constructs a new parameter vector from the base parameter vector by “ConstructParameter” procedure. Take this new parameter vector as the current parameter vector for this iterative calculation. Record the fitness value of the best solution constructed by ants in this iteration, and take this value as the fitness value of the new parameter vector. Add the new parameter vector and its fitness value into the parameter archive.

  • The third process uses the “UpdateParameterArchive” procedure to sort the parameter vectors in C by their quality, then keep the best a parameter vectors in C and remove redundant parameter vectors.

  • Repeat the second and third process before a termination condition is satisfied.

The procedures for parameter archive are very similar to that for solution archive, and they have almost the same operations in initializing archive, selecting base vector from archive, updating archive, etc.

There is a big different procedure for parameter archive, and that is constructing a new parameter. Each variable in the base parameter vector probabilistically selects new value in its neighborhood, and these new values form a new parameter vector. The probability density function Pd(x) for each variable is as follows:

$$begin{aligned} Pd(x) = f(x,mu ,sigma ) = dfrac{1}{sigma sqrt{2pi }}{e^{dfrac{-(x-mu )^2}{2sigma ^2}} } end{aligned}$$

(15)

and

$$begin{aligned} mu = c_j^i, sigma = xi sum _{r=1}^{a} dfrac{|c_r^i-c_j^i|}{a-1} end{aligned}$$

(16)

(f(x,mu ,sigma )) is the Gaussian function, x is a variable in one parameter vector. (sigma) denotes the mean square error , (mu) is the mean value , and (xi) means the algorithm parameter.

Parallel Computing with Multiple Threads

Parallel computing can enhance the algorithm speed, and it introduces parallel computing elements to expand the search mode, which can often improve the quality of algorithm results [59]. In this work, we use a multi-threaded parallel computing approach to improve the solution quality and search speed of PSAACO.

Step 6 of Algorithm 1 starts TdNum parallel threads, and steps 7 to 45 in Algorithm 1 are the running steps of each thread. Each thread runs an independent ACO algorithm, and it has its own solution archives, parameter archives and global parameters, etc. These threads have independent ant colonies to explore new solutions. And they independently update their own solution archives and parameter archives. After all threads run, take the best solution obtained by all threads as the result of the whole algorithm.

The application of parallel computing speeds up the run of the algorithm, reduces the probability of PSAACO falling into a local optimum, and improves the overall performance of PSAACO. The relevant proof experiments are described in the later experimental part.

The Fitness Value

The most common performance metrics are: path length, number of turning maneuvers, completion time, energy consumption, and quality of area coverage. Path length and turning angle are the two main basic factors, and most common performance metrics usually rely on one of these factors or a combination of two factors. The completion time and energy consumption metrics include the evaluation of these two factors, so these two metrics are more comprehensive and reasonable. In this paper, the completion time is used as the fitness function value.

NFZ Avoidance Using DFA

The Floyd Warshall algorithm is used to search for the shortest path between any two points, and can handle the shortest path problem of undirected graphs or weighted directed graphs [60, 61]. The idea of the algorithm is to insert different intermediate vertices between two points and find out the insertion scheme of the shortest path. Let (d_{ij}^x) be the shortest path from vertex i to vertex j , and its intermediate vertex is in the set 1, 2… y, where x is the iteration number and y is the total number of all vertices. Then for (y > 1),

$$begin{aligned} d_{ij}^x = min( d_{ij}^{x-1} ,d_{ik}^{x-1} + d_{kj}^{x-1}) end{aligned}$$

(17)

Thus, (d_{ij}^y) is the shortest paths matrix calculated by the Floyd Warshall algorithm from the input graph. The Floyd Warshall algorithm cannot dynamically add points. When a new vertex is added into the graph, all shortest path needs to be recalculated, and the time complexity is (O(n^3)).

This paper improves the algorithm so that when vertices are added, only the changes caused by these vertices are calculated, and the algorithm are named DFA.

The DFA is presented in Algorithm 6. The algorithm has three input parameters. DistanceM1 represents the distance matrix that has been calculated so far, and DistanceM1[i][j] records the shortest distance from vertex i to vertex j. PathM1 indicates the path matrix that has been calculated, and PathM1[i][j] records the intermediate vertex for the shortest path from vertex i to vertex j. DistanceA is an array of distances between new point and calculated points, where DistanceA[i] records the distance between new point and vertex i. In steps 3 to 17 in Algorithm 6, initialize the DistanceM2 and PathM2 by copying the calculated data in DistanceM1 and PathM1 , and adding the data of the new point from DistanceA. The steps 18 to 23 of the algorithm calculate and update all paths ending at the new point, and the steps 24 to 29 calculate and update all paths starting at the new point, while the steps 30 to 35 calculate and update all paths with the new point as intermediate point. The calculation and update operations are implemented by the “updateMatrix” procedure. The detailed steps of the “updateMatrix” procedure are described in algorithm 7, and its principle is shown in Formula 17.

It is easy to see that the time complexity of DFA is (O(3n^2)). When the number of points is large, DFA has great advantages in running speed.

figure f
figure g

We apply the DFA to deal with NFZ avoidance. Assume we get a CPP model G and a sub-path (P_k=(V_{Ai},V_{Aj})), then the main process for (P_k) to avoid NFZs is as follows:

  • The first process is to calculate all N-Type points in G using DFA, and store the result in the distance matrix DistanceM1 and the path matrix PathM1. We take the CPP model shown in Fig. 1 as an example, The DistanceM1 is shown in Table 2. The data in the table represents the shortest distance between two N-Types points. In particular, (infty) indicates that there is no feasible path between two points. Table 3 describes the data of PathM1. From the table we can see that the shortest path from (V_{N1}) to (V_{N10}) is: ((V_{N1},V_{N5},V_{N10})), since 5 is the intermediate vertex between (V_{N1}) to (V_{N10}).

  • The second process is to calculate the distance between the starting vertex (V_{Ai}) and all N-Type points to obtain the distance array of DistanceA1. For example, the DistanceA1 for vertex (V_{A7}) in Fig. 1 is ((14.1, infty , cdots , infty , 51.0)).

  • The third process is to take DistanceA1, DistanceM1 and PathM1 as input parameters, apply the DFA to calculate and update the distance matrix DistanceM1 and the path matrix PathM1.

  • Repeat process 2 and process 3 to calculate the end vertex (V_{Aj}). And we can get the NFZ avoidance path from final path matrix PathM1. In the example, the final DistanceM1 is shown in Table 4 and the final PathM1 is shown in Table 5. It can be seen from the tables that the NFZ avoidance path of (P_k=(V_{A7},V_{A8})) is ((V_{A7},V_{N0},V_{N1},V_{A8})).

Table 2 Distance matrix for N-Type points
Table 3 Path matrix for N-Type points
Table 4 Distance matrix after NFZ avoidance
Table 5 Path matrix after NFZ avoidance

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Disclaimer:

This article is autogenerated using RSS feeds and has not been created or edited by OA JF.

Click here for Source link (https://www.springeropen.com/)