## 3 The Proposed Coverage Flight Path Planning Algorithm
### Determining the Footprints' Sweeps Visiting Sequence  
After fitting the footprints' sweeps, the next step is to determine the sequence in which the footprints' sweeps will be visited to ensure the complete coverage. To find the low cost footprints' sweeps visiting sequence, we formulate it as a travelling salesman problem (TSP), and the ant colony optimization algorithm is employed to solve the TSP. Given M points set originally calculated from the footprint sweeps, endpoints are used to calculate a close path that visits each point exactly once. We specify the basic parameters of ACO according to problem size. After the parameter setting, the distance and sight matrix are computed between points. Then, \(l\) ants are deployed on random points and the computation is carried out for the pre-defined \(n_{itr}\) iterations. During the computation, each ant calculates the tour by remembering the vertices which have already been explored and choosing the nearby points from their current position based on action choice rule. The probability that point \(j\) will be visited by an ant \(k\) which is currently at point \(i\) can be computed from Equation (3):  
\[p_{ij}^{k}=\left\{\begin{array}{l}\frac{[\tau_{ij}]^{a}[\eta_{ij}]^{\beta}}{ \sum\limits_{s\in allowed_{k}}[\tau_{ij}]^{a}[\eta_{ij}]^{\beta}} \quad,j\in allowed_{k},\\ 0,\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad otherwise,\end{array}\right. \tag{3}\]  
where \(\tau_{ij}\) represents the intensity of the pheromones trial between point \(i\) and \(j\), \(\alpha\) is a parameter used to regulate the influence of \(\tau_{ij}\), the variable \(\eta_{ij}\) represents the visibility between point \(j\) and \(i\), which is computed as \(\
icefrac{{1}}{{d_{ij}}}\) (where \(d_{ij}\) is the Euclidian distance between two points), \(\beta\) is a parameter used to regulate the influence of \(\eta_{ij}\) and \(allowed_{k}\) represents the points that have not been visited by an ant \(k\) yet, respectively.  
At the start, \(l\) ants are deployed to the \(m\) points randomly. Later, each ant makes the decision to choose the next point based on the transition probability \(p_{ij}^{k}\) given by Equation (3). After \(n_{itr}\) of this whole process, every ant computes a complete tour by visiting each point once. It is desirable to reinforce good solutions and the ant with the shortest tour should deposit more pheromones to find the low cost solution compared to other ants. Thus, the trail levels are updated, and each ant leaves a quantity of pheromones given by \(\
icefrac{{K}}{{l_{k}}}\), where \(K\) is a constant and \(L_{k}\) is the length of the tour. Meanwhile, the pheromones' quantity will decrease as time goes by. Therefore, the update rule of the \(\tau_{ij}\) can be written as follows:  
\[\tau_{ij}(t+1)=(1-\rho)\tau_{ij}(t)+\Delta\tau_{ij}, \tag{4}\]  
\[\Delta\tau_{ij}=\sum\limits_{k=1}^{l}\Delta\tau_{ij}^{k}, \tag{5}\]\[\Delta\tau_{ij}^{k}=\left\{\begin{array}{ll}\
icefrac{{k}}{{l_{k}}},&\mbox{ if $int$ $k$ travels on edge $(i,j)$,}\\ 0,&\mbox{,otherwise,}\end{array}\right. \tag{6}\]  
where variable \(t\) represents the iteration counter, \(\rho\) is the parameter to regulate the influence of \(\tau_{ij}\), \(\Delta\tau_{ij}\) represents the total increase of trial level on a particular edge \((i,j)\), and \(\Delta\tau_{ij}^{k}\) represents the increase of trial level on the two respective edges \((i,j)\) caused by an ant \(k\). While determining the visiting sequence, we do not consider the obstacles' effect to find the minimum length global path. We consider the obstacles 'effect in the waypoint graph construction stage. With the help of ACO, we can get the set \(S\), where \(S=\{(F_{1},n_{1}),(F_{2},n_{2}),\ldots,(F_{n},n_{n})\}\) of footprint sweeps' visiting sequence that will be used for graph construction. In set \(S\), the \(n_{i}\) refers to the visiting sequence of a particular sweep.