Graph-based path planning for intelligent UAVs in area coverage applications

Abstract

In recent times, Unmanned Air Vehicles (UAVs) are being deployed for several tasks of terrain coverage such as surveillance, photogrammetry, smart irrigation, civil security, and disaster management. In these applications, one of the most vital issues to be addressed is, covering the area under observation with minimum traversal for the UAV. So, the problem addressed in this paper is as follows: For a given geographic area and the given parameters describing the UAV’s coverage capacity, the problem is to find an optimal route that covers the given geographic area. In this paper, an optimal path planning algorithm for the area under observation, given as a closed curve, is proposed. The algorithm partitions the given area of interest into multiple non-uniform rectangles while considering other parameters such as the flying altitude of the UAV and obstacles that could be encountered during its flight. The problem is transformed into Traveling Salesman Problem by constructing a graph from the rectangular partitioning. Effective approximate solutions are provided to this problem, using the Minimum Spanning Tree (MST) approximation algorithm and Ant Colony Optimization (ACO). The experimental results show that ACO outperforms the MST based algorithm as it does not get stuck in local minima.

Keywords

Travelling salesman problem minimum spanning tree area coverage path planning ant colony optimization UAV

1 Introduction

Unmanned Aerial Vehicles (UAVs) are becoming very popular and are being widely used by most of the countries across the globe. They are being deployed in numerous applications such as wildlife monitoring, disaster management, target tracking, area patrolling, and more [1]. The UAVs comprise of aerial platforms that are manually and remotely controlled by humans, though they are pre-programmed to perform some automated functions. Autonomous flying could be carried out using smart methods incorporated with onboard receptors.

Area Coverage Problem in UAVs is one of the most vital problems that is being continuously researched. The problem is to cover the area under observation by the UAVs in minimum duration of time considering various other constraints such as the number of obstacles, climatic conditions, battery life of UAVs, and lot more. An optimal solution for any given application must minimize the duration of the traversal covering the entire area of interest [2].

In this paper, an application of covering the given geographic area under surveillance by a single UAV is considered. It could be any application for which the UAV is deployed. The ultimate goal of the proposed work is to cover the entire area with a minimal cost of traversal. The path should be planned in such a way that it originates from a particular point and ends at the same point covering all the regions within the given area of interest. In Fig. 1, a single UAV deployed in an urban environment is illustrated. The area enclosed within the red dotted line indicates the current region that is being surveyed by the UAV. The rest of the regions enclosed within the green dotted lines indicate the other regions of interests yet to be covered.

Fig. 1

Drone deployed Environment.

Some of the preliminaries of Graph Theory are discussed in the following subsection before specifying the problem and the methodology.

1.1 Preliminaries

Given a complete weighted graph G(V, E), where V is a set of n vertices and E is a set of edges between all the pair of vertices in V, a spanning tree is an acyclic subgraph G^| (V, E^|). There might be many spanning trees, but Minimum Spanning Tree (MST) is a spanning tree with minimum total weight [5].

Traveling Salesman Problem (TSP) is one of the widely investigated problems that are majorly used in numerous applications such as Bio-Informatics, Logistics, and also in path planning. Given a complete weighted graph G(V, E), the Travelling Salesperson Problem finds the shortest simple cycle covering all the vertices in graph G and with a minimum cost of traversing [6].

1.2 Problem specification

For a surveillance UAV, an area under study/interest will be given. The UAV has to start at a given point on the boundary of the given geographic area, at a specific altitude. It has to traverse over the given area covering the entire region using the shortest path and come back to the starting point on the boundary. In this paper, this problem is transformed into a Travelling Salesperson problem for which two alternate solutions are proposed. A comparative study of these two algorithms is made in the context of UAV path planning.

1.3 Methodology outline

A bounding polygon for the geographic map of the area under observation is constructed by finding Convex Hull using the Graham Scan Algorithm [3]. A Rectilinear Partitioning Algorithm is designed to partition the coverage area into a set of n Rectangles, R = {R₁, R₂, . . . . . R_n}. The sizes of the rectangles may vary depending on the altitude and the obstacles at that altitude and the like. The rectangular decomposition is done in such a way that they are non-overlapping. This tends to minimize the frequency of visiting the same area more than once.

The proposed algorithm finds the centroids of every rectangle. These centroids are considered as vertices of a complete graph with straight-line distances between the vertices as edge weights [4]. The Prim’s MST algorithm is used to provide an approximate solution to the TSP by constructing a path using Depth First Search. Ant Colony Optimization (ACO) [7] is also used to provide a solution for the TSP with efficient measures. A comparison is carried out on the minimal routes obtained using MST and ACO. The use of particular algorithms is done as they tend to work well with undirected-weighted graphs. The difference in the optimal route found while changing the various parameters such as the total number of iterations and the number of ants used to perform ACO are evaluated. The entire architecture of the proposed method is given in Fig. 2.

Fig. 2

The architecture of the Proposed Method.

The rest of the paper is organized in the following way: Section 2 discusses various existing systems used for optimal path planning, Section 3 elaborates on the methodology behind the proposed work, Section 4 lists various experiments conducted along with the results obtained and the paper is concluded with some suggestions that could be experimented as future works.

2 Related works

UAVs are used in various applications and each application has its drawbacks while making use of them. It is been widely used in remote sensing [8], coastal engineering [9], agriculture [10], disaster management [11], smart city management [12], and various other fields as stated in [13]. Some of the limitations of using UAVs is mentioned by Mottola, L. in [14].

UAV path planning has emerged as a separate area of research as it is considered as a major component for designing autonomous UAVs. Some of the most common constraints that need to be considered for UAV path planning are energy-related constraints such as its battery life and its constant communication with the base station. An optimal path planning is required by a UAV to traverse with minimum energy consumption and optimally traversing the entire area of interest. An energy-aware path planning algorithm designed by Kouroshnezhad, S. [15], claimed to employ Linear Programming(LP) for planning trajectories for given sensors by making use of localization algorithms. With the help of Heuristic Optimization Methods, a novel framework was claimed to be proposed with optimum coverage [16]. A genetic algorithm developed in [17], stated to minimize the total operational cost of the drones used in parcel delivery. A survey by Zhao, Y. [18] provides a complete review of various computational intelligence algorithms for various path planning techniques. A solution for Multi-UAV path planning problem is suggested in [19], and Geometric Reinforcement Learning(GRL), claimed to discover an optimal path for UAVs, by using a reward matrix [20].

Collision avoidance is another major problem that needs to be considered while planning a path for UAV. A sampling-based path planning method, suggested by Yucong Lin [21], stated to avoid collision with any moving obstacles. With the help of an optimal control method, the path of UAV is designed in such a way that it could solve the dead point problem with great efficiency [22]. The collision avoidance problem becomes very crucial when multiple UAVs are deployed for one particular application. Peng Yao [23], constructed a cooperative path planning model for multiple UAVs, which could be effectively used in target tracking applications.

Covering the entire target area, by a UAV is essential for any given application. Problems on area coverage are solved by various area partitioning algorithms. In [24], the author has effectively decomposed the coastal regions by making use of Constrained Delaunay triangulation. With the help of the coordination variable, an entire area was divided into r x c shape by making use of a distributed algorithm, where r refers to row, and c refers to columns of the respective grids [25]. Another distributed coverage algorithm proposed in [26], covers the entire area using Voronoi partitioning method, with non-overlapping regions. DARP algorithm claimed to divide the areas into several equal partitions by allocating them to a specific autonomous robot, where a complete area coverage is guaranteed [27].

While deploying MST in UAV path planning, it produces a subset of all paths, connecting every node(region) that needs to be visited. In [28], the author has used an image segmentation method for finding the MST using a clustering-based algorithm. Pop, P. C. has discussed the general formulation of MST based problems and various heuristic approaches to solve them [29].

The idea behind solving the TSP problem in area coverage applications is to find a minimum route that traverses all the given regions with the same starting and ending points [30]. TSP belongs to a family of NP-complete problems where the total computational complexity increases exponentially with the increasing number of nodes [31]. Numerous algorithms are in use to solve this problem effectively. Some of the major contributions in solving TSP to obtain an optimal path for UAVs can be found in [32, 33]. The research works highlight various perspectives in deploying a path for a UAV.

3 Methodology

The problem under consideration is to find an optimal path of a UAV, to cover a given geographic region. The steps in the methodology broadly are as follows:

Find a bounding polygon for the geographic map under observation

Find rectilinear partitioning of the polygon based on the information about obstacles, like trees, at the flying altitude and the coverage area of the surveillance

Mark the centroids of each of the rectangular partitions and construct a complete graph with these centroids as vertices and the distance or energy consumption by UAV as weights

Identify the starting vertex of the UAV and find the shortest cycle covering all the vertices of the graph using MST approximation and Ant Colony Optimization

3.1 Rectilinear partitioning algorithm

Let us consider a UAV flying at an altitude h, over a fixed polygonal area A, comprising of a camera installed onboard. The area that is being captured by this UAV at a particular instance of time is called the Field of View (FoV). Let W be the width and L be the length of the area covered by FoV. The angle enclosed between this area is represented by η and θ as shown in Fig. 3. The rectilinear partitioning is carried out by considering these parameters in different areas of the traversal.

The dimensions W and L of the camera’s FoV can be calculated by Eq. (1) and Eq. (2).

Fig. 3

Field of View(FoV) – UAV.

$W = 2 hXtan (\frac{η}{2})$ (1) $L = 2 hXtan (\frac{θ}{2})$ (2)

where

W: FoV’s total width

L: FoV’s total breadth

h: Altitude of flying

η: enclosed vertical degree

θ: enclosed horizontal degree

3.1.1 Convex hull using graham scan algorithm

Convex Hull for the area of interest is found by grouping points with outermost values, as shown in Fig. 4. The most prominent characteristic of this technique is to use the adjacency information of points to find the outermost points. Graham Scan algorithm is used in applications making use of information visualization algorithms that tend to use images.

The algorithm produces a minimal set of bounding polygonal vertices, for the area of interest. It makes use of the angle between two related lines that originates from the same source point to determine the outermost position of lines. Graham Scan algorithm initializes by determining the starting point from any set of points (in this case, vertex) and in Fig. 4 the starting vertex is V₁.

Fig. 4

Graham Scan Algorithm.

The relation between two adjacent lines is determined based on whether it follows the pattern of “turn right” (clockwise) or of “turn left” (counterclockwise). A vertex falling at the line that follows the pattern “turn left”, is to be removed from the sequence of Convex Hull if there exists no other pattern pertaining to “turn right”. The idea of the algorithm is explained with the help of Fig. 4. In this figure, it can be noted that vertices V₁ and V₂ form a pattern of “turn right”. Vertex V₄ is eliminated from the entire Convex Hull sequence as, when the line from V₃ goes to V₄, it will form a pattern of “turn left” and there is still another “turn right” pattern that leads to V₅ such that the next convex hull line is at vertex V₅, and not V₄.

In Fig. 6, it can be noted that the number of vertices on the boundary of the polygonal area is decreased from Fig. 5 after computing the Convex Hull of the polygon using the Graham Scan algorithm on a sample Geographic area. Table 1 summarizes various parameters that are evaluated while computing the Convex Hull of the polygon for a model geographic map.

Fig. 5

Before Convex Hull – 26 vertices.

Fig. 6

After Convex Hull – 12 vertices.

Table 1

Comparison of parameters for a sample geographic area

	Before using Convex Hull Algorithm	After Using Convex Hull
Number of Vertices	26	12
Perimeter (length units)	0.2675	0.2243
Enclosed Area (length units)	0.0035	0.0030

3.1.2 Rectilinear partitioning algorithm (RPA)

Given a polygonal area, the minimum area of the enclosure is found using the Graham Scan Algorithm. Now it is necessary to partition the area enclosed within the polygon to find an optimal area coverage strategy in such a way that the UAV covers the entire polygon. It is assumed that the UAV flies at an altitude h which varies with many external factors. One such important factor is an obstacle that could be encountered while traveling over the given area.

In this work, we have taken static obstacles particularly buildings, transmission line towers, and trees over which the UAV needs to fly. In the case of particular applications such as disaster management, the drones must capture images in low altitudes and fly to higher altitudes when it finds a building or any other static obstacles. When the altitude of the UAV changes, it’s FoV also changes as it is completely dependent on the altitude of the flight. In other terms, it could be stated that the area coverage of the UAV is directly proportional to the altitude at which it is flying. The more the UAV altitude is, the more is the area covered by it. It is not mandatory to make the UAVs fly always at higher altitudes, as the images captured by it might have lower resolutions. Some applications make the UAVs to fly at lower altitudes to get better clarity of images.

A rectangular part of the polygonal area is used for experimental purposes to reduce the complexity of the problem. A rectangular region is sub-divided into numerous rectangular partitions using RPA. It is assumed that the UAVs maximum altitude H’ is about 400 feet, and the coordinates of the buildings (x and y) within the area of interest A is known. The minimum altitude of the UAV is considered to be 50 feet such that the images captured by the UAV have a good resolution. The initial altitude of UAV is H and each static obstacle in A is considered as an obstacle o, which when encountered during the flight of the UAV, changes its altitude from H to reach H’. Following is the listing of the algorithm used.

Algorithm of Rectilinear Partitioning for Area Coverage

Inputs: Maximum Altitude H’, Minimum Altitude H Area of Interest – A

X,Y coordinates enclosing the area A

x,y coordinates of static obstacles in A

Output: Set of Rectilinear Partitions R = {R₁, R₂, … R_n}

Compute O, a set of p obstacles in A with known x,y coordinates: O = {o₁, o₂, o₃, …, o_p} where o_i is i^th obstacle

At altitude H, compute the FoV using $\begin{matrix} W = 2 hXtan (\frac{η}{2}) \\ L = 2 hXtan (\frac{θ}{2}) \end{matrix}$

Compute coordinates of the m initial rectangular partitions R_1,R₂ … R_m based on FoV, in row major order

Repeat Steps 5 & 6 for each i = 1 . . . p

For the obstacle o_i find the partition R_k in which the obstacle is present

Compute the FoV for altitude H’ using Step 2. Find the neighbouring partitions that have to be joined with R_k_, considering R_k as at the center_.

RPA algorithm initially starts with an assumption of minimum height H. It then computes a set of points of obstacles O, which consists of all static obstacles within the area A using the coordinates of the obstacles. When there are no obstacles the height of the UAV is H and the FoV is calculated for this altitude by using Equations 1 and 2. The FoV is a rectangular partition as we obtain the width and length of the rectangle. All the partitions are obtained at H and for each of the obstacle from O, the altitude of the UAV is changed from H to H’. An FoV is calculated for this new altitude H’. The computation of FoV iterates until all the obstacles are taken care.

The final output obtained would be a set of rectangular partitions R. Figure 7 shows a rectangular area A partitioned into n number of rectilinear partitions.

Fig. 7

Rectilinear Partitioning.

3.2 Optimal path planning using TSP

The centroid of each rectilinear partition is computed. Each of these is taken as a point to be visited in an optimal path planning algorithm, such that visiting the centroid of every partition will cover the entire area enclosed within the partition. The centroid C, of a partition with (X, Y) as the lower left corner coordinates, is found out using the formula $\bar{X} = X + \frac{b}{2} and \bar{Y} = Y + \frac{h}{2}$ where b is the breadth of the rectangle and h is the altitude of the rectangle as depicted in Fig. 8. Let C = {c₁, c₂, c₃ … , c_n} be the set of centroids. This is used for constructing an optimal path for the UAV using a distance matrix. The centroids for all the rectilinear partitions are depicted in Fig. 9.

Fig. 8

Centroid of a rectangle.

Fig. 9

Centroids of each partition.

The distance matrix is constructed using the Euclidean distances between pairs of centroids in C. The assumption is that a path exists between every pair of centroids as in Fig. 10, and hence the graph is complete. Each centroid in C is considered as a unique vertex, which would be visited once for getting an optimal path for the UAV.

Fig. 10

All possible paths between all centroids.

Now the problem can be posed as a Travelling Sales Person Problem. This paper computes an optimal solution for TSP using Minimum Spanning Tree and Ant Colony Optimization techniques. Comparisons are done on various parameters to evaluate the efficiency of the algorithms.

3.2.1 Solving TSP using minimum spanning tree

The TSP can be defined as follows: given a complete graph G=(V, E) where V denotes the set of vertices and E denotes the set of edges connecting all pairs of vertices. An edge (i, j) ∈ E, from the graph used, is assigned a cost d_ij, to traverse between vetices i and j. The problem is to find the cycle starting at a given vertex, connecting all the vertices, with minimum total cost.

In our problem, each centroid is taken as a vertex and a distance matrix is calculated using Euclidean distance d_ij. It is calculated as in Eq. (3). $d_{ij} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}}$ (3)

In this work, the distance matrix D_m for the graph constructed with centroids, is computed by making use of the x and y coordinates centroids and the cost between a pair of vertices gives the actual distance between them.

Before going to the details of the solution for the problem, an illustration of finding MST using Prim’s algorithm is shown below: Given a graph G as in Fig. 11, let us consider A to be the starting vertex, and the traversal initiates by taking the smallest edge cost first.

Fig. 11

Graph G.

An MST is found as shown in Fig. 12. Then the Depth First Traversal on the MST is conducted. In DFS, the vertices are traversed from its root node and explore the tree as far as possible along every branch before backtracking and moving to the next branch. Let us consider T as shown in Fig. 13, to be the MST of the given graph G which is used for finding the route of traversing all the vertices. If a route is constructed between the vertices of tree T, it would yield to a path consisting of the traversal T₁. In case, of using DFS for the tree T, the repeated nodes can be removed assuming Triangular Inequality property for Euclidian distances. Hence a new optimal path is obtained which follows the traversal T₂.

Fig. 12

Iterations for finding MST.

Fig. 13

Tree T.

T₁ - A,C,D,C,B,C,A

T₂ - A,C,D,B,A

The traversal T₁ and T₂, clearly shows the minimization of complexity in finding the optimal route, hence providing an optimal solution to the Travelling Salesman Problem. Pictorial representation of the traversals is depicted in Fig. 14.

Fig. 14

Depth First Search in MST.

3.2.2 Solving TSP using ant colony optimization

The Ant Colony Optimization(ACO) is stimulated by the foraging characteristic of ants in the eco-system. The ants are very much capable of finding the shortest path from the source of food to its nest without any visual clues and is called as stigmergic communication between ants. The ants tend to deposit some amount of chemical substance (called a pheromone) on the ground while walking in search for the food source. This pheromone acts as memory preservation, to come up with the shortest path. As the density of the pheromone increase, it is useful in increasing the probability of other ants to follow the same path. As the number of ants walking on a trail increases, the more is the amount of pheromone deposited on the ground which increases the number of ants to follow the trail. With the help of this mechanism, ants will find the shortest path. When it comes to solving a TSP, the algorithm initializes n ants where n is the number of vertices that need to be visited. Each ant initially visits a random vertex (two or more ants cannot have the traversal to the same vertex) and traverses to the next vertex and in the same way, tries to visit all the vertices in the given graph G. The ant updates its local pheromone value as it traverses through the vertices in each iteration. All the ants in the system also communicate with each other to update its Global Pheromone value which is used to find the shortest route for the given graph G. This algorithm gives an effective solution for the TSP and reduces the time complexity of the application to a greater extent. The traversals performed by the ACO algorithm for solving the TSP of a given graph G is shown in Fig. 15.

Fig. 15

Ant Colony Optimization.

4 Experimental analysis

The entire experimental analysis revolves around partitioning a given area of interest into n number of rectilinear partitions and traversing all the partitions with minimum cost. The implementation is performed with QGIS – Desktop version 3.10.0.

The implementation is initialized by taking a set of vertices V’ that encloses a polygonal area. The area enclosed within the vertices V’ is assumed to be a’ The Convex Hull is computed for V’ using the Graham Scan Algorithm that resulted in the minimization of vertices and also minimized the total enclosed area denoted as A’. Table 1 summarized the results obtained while using the Graham Scan Algorithm. To reduce the complexity of the algorithm, a rectangular area A is selected from A’, and the rectilinear partitioning algorithm is used to partition it into various rectangles R_n. Some of the parameters considered for partitioning A’ is UAV’s altitude and the coordinates of the obstacles within A. In the experiment conducted we have taken maximum altitude of the UAV as 400 feet which are minimized gradually to enclose all the unvisited areas in A. The centroids of each rectangular partition are computed that are used for computing an optimal solution for TSP. Each centroid is considered as a vertex of a graph G₁. for which an MST is computed. The distance matrix is computed for G₁, where the distance of traversing from any particular vertex to another in G₁ is obtained. A sample distance matrix obtained from one particular vertex to all other vertices is shown in Fig. 16. MST of the given centroids is depicted in Fig. 17, where the weight of the graph is 7.254 km ≈ 7254 m. It can be noted that all the vertices of the graph are covered with minimal overall distance for traversal.

Fig. 16

Distance Matrix.

Fig. 17

Minimal Spanning Tree.

The MST computed graph is further used for finding an optimal solution for TSP. In MST a particular vertex might be visited more than once whereas, TSP provides a minimal computation cost where a particular vertex is not visited more than once. This solution reduces the computation cost to a greater extent.

In Fig. 18, an optimal solution for the MST computed for the weighted graph is given, where the weight of the graph is about 5.423 km ≈ 5423 m. In this computation, it could be noted that the overall cost of traversal is reduced as the vertices are visited only once. The weight obtained for both MST and TSP is the minimum distance for traversing all the vertices in G₁ and is validated using the distance matrix.

Fig. 18

Solution for TSP using MST.

The value of the solution for TSP by using MST is compared with the solution obtained while solving TSP using Ant Colony Optimization for the graph G₁. constructed from centroids of the rectilinear partitions R_n. Some of the constant parameters initialized while performing ACO where the pheromone exponential weight α=1 and heuristic exponential weight β=1 with an evaporation rate ρ of 0.5. In Fig. 19, the optimal solution obtained while using ACO is depicted.

Fig. 19

Solution for TSP using ACO.

Some of the parameters were not taken as constant values and were gradually changed to obtain an optimal solution. The best cost for the given set of vertices in graph G₁ using ACO is 878.2476. Experiments were carried out by changing the number of ants nAnts and the maximum number of iterations MaxIterations to obtain various results such that the optimal solution could be obtained.

The efficiency graphs while using 40 ants are depicted in Figs. 20, 21 and 22 with MaxIterations ranging from 50 to 200. The efficiency graphs while using 60 ants are depicted in Figs. 23, 24 and 25 with MaxIteration ranging from 50 to 200.

Fig. 20

Efficiency Graph for MaxIterations = 50 nAnts = 40.

Fig. 21

Efficiency Graph for MaxIterations = 100 nAnts = 40.

Fig. 22

Efficiency Graph for MaxIterations = 200 nAnts = 40.

Fig. 23

Efficiency Graph for MaxIterations = 50 nAnts = 60.

Fig. 24

Efficiency Graph for MaxIterations = 100 nAnts = 60.

Fig. 25

Efficiency Graph for MaxIterations = 200 nAnts = 60.

The overall comparison chart is summarized in Fig. 26. The table clearly shows us that the best optimal solution obtained is at iteration 43 with nAnts = 60. The increase in the population of ant can lead to obtaining the best cost with a minimal number of iterations. The overall work helps us in finding an optimal path in a drone deployed environment. The current work provides an optimal solution as it partitions the area into rectilinear partitions, where static obstacles are taken into account with efficient use of MST and ACO algorithms.

Fig. 26

Comparison of parameters.

5 Conclusion and future works

Area coverage is one of the most vital problems that need to be solved while making use of autonomous UAVs in an application. The problem is to cover an entire given area of interest for a particular application, with minimal cost of traveling. To obtain this minimal traversal cost, we have proposed a method of using a Rectilinear Partitioning Algorithm. The algorithm partitions the given area of interest into multiple non-uniform rectangles while considering several other parameters such as the altitude of flight of UAV and obstacles that could be encountered during its flight. The problem is transformed as a Traveling Salesman Problem and effective solutions are provided by computing an approximate solution via Minimum Spanning Tree (MST) and Depth First Search. The minimum cost obtained for a given graph G₁ by solving TSP using MST is 5.423 km ≈ 5423 m. The optimal solution of TSP was also obtained using Ant Colony Optimization (ACO. The optimal solution was obtained by changing various parameters such as several ants and the number of maximum iterations. The comparison proved that ACO outperforms MST without being stuck at local minima as a change in the parameters in ACO could avoid them being stuck at the local minima. Other factors such as the evaporation rate and several ants used for performing the iterations, also have a huge impact on obtaining the best cost. Comparative analysis proves that both the number of iterations and the number of ants used to find the optimal solution is indirectly proportional to the best cost achieved. Future work can include the construction of Steiner points on the region of interest and hence could be used for developing Steiner Trees, to achieve an optimal solution. Steiner Tree problem would help return the minimum cost of the entire traversal in an undirected weighted graph. This will deploy some unused nodes called Steiner points that would minimize the entire traversal of the UAV.

References

Aydin

, Public acceptance of drones: Knowledge, attitudes, and practice, Technology in Society 59 (2019), 101180.

Ropero

, Muñoz

and R-Moreno

M.D.

, TERRA: A path planning algorithm for cooperative UGV–UAV exploration, Engineering Applications of Artificial Intelligence 78 (2019), 260–272.

Zhu

, He

, Ling

and Zhang

, Cooperative search strategies of multiple UAVs based on clustering using minimum spanning tree. In International Conference on Sensing and Imaging (pp. 112–121), (2018, June). Springer, Cham.

Tinós

, Helsgaun

and Whitley

, Efficient recombination in the Lin-Kernighan-Helsgaun traveling salesman heuristic. In International Conference on Parallel Problem Solving from Nature (pp. 95–107), (2018, September). Springer, Cham.

Dey

, Mondal

and Pal

, Robust and minimum spanning tree in fuzzy environment, International Journal of Computing Science and Mathematics 10(5) (2019), 513–524.

Kitjacharoenchai

, Ventresca

, Moshref-Javadi

, Lee

, Tanchoco

J.M.

and Brunese

P.A.

, Multiple traveling salesman problem with drones: Mathematical model and heuristic approach, Computers & Industrial Engineering 129 (2019), 14–30.

Blum

, Ant colony optimization: Introduction and recent trends, Physics of Life reviews 2(4) (2005), 353–373.

George

and Vishnukumar

, A hybrid approach to generate visually seamless aerial mosaicks from unmanned aerial vehicles, Journal of Intelligent & Fuzzy Systems 36(3) (2019), 2075–2083.

Lee

J.K.

, Kim

J.O.

and Park

S.J.

, A study on the UAV image-based efficiency improvement of bridge maintenance and inspection, Journal of Intelligent & Fuzzy Systems 36(2) (2019), 967–983.

10.

Candiago

, Remondino

, De Giglio

, Dubbini

and Gattelli

, Evaluating multispectral images and vegetation indices for precision farming applications from UAV images, Remote Sensing 7(4) (2015), 4026–4047.

11.

Akshya

and Priyadarsini

P.L.K.

, A Hybrid Machine Learning Approach for Classifying Aerial Images of Flood-Hit Areas. In 2019 International Conference on Computational Intelligence in Data Science (ICCIDS) (pp. 1–5) (2019, February). IEEE.

12.

Menouar

, Guvenc

, Akkaya

, Uluagac

A.S.

, Kadri

and Tuncer

, UAV-enabled intelligent transportation systems for the smart city: Applications and challenges, IEEE Communications Magazine 55(3) (2017), 22–28.

13.

Akshya

and Priyadarsini

P.L.K.

, A Comparison of Machine Learning Approaches for Classifying Flood-Hit Areas in Aerial Images. In International Conference on Innovative Computing and Communications (pp. 407–415), (2020). Springer, Singapore.

14.

Mottola

, Real-world Drone Sensor Networks: A Multi-disciplinary Challenge. In Proceedings of the 6th ACM Workshop on Real World Wireless Sensor Networks (pp. 1–1) (2015, November).

15.

Kouroshnezhad

, Peiravi

, Haghighi

M.S.

and Jolfaei

, An energy-aware drone trajectory planning scheme for terrestrial sensors localization, Computer Communications (2020).

16.

Kilic

K.I.

, Gemikonakli

and Mostarda

, Multi-objective Priority Based Heuristic Optimization for Region Coverage withUAVs. In International Conference on Advanced Information Networking and Applications (pp. 768–779), (2020, April). Springer, Cham.

17.

Q.M.

, Deville

, Pham

Q.D.

and Hà

M.H.

, A hybrid genetic algorithm for the traveling salesman problem with drone, Journal of Heuristics 26(2) (2020), 219–247.

18.

Zhao

, Zheng

and Liu

, Survey on computational-intelligence-based UAV path planning, Knowledge-Based Systems 158 (2018), 54–64.

19.

Chen

, Yu

, Su

and Luo

, Path planning for multi-UAV for-mation, Journal of Intelligent &Robotic Systems 77(1) (2015), 229–246.

20.

Zhang

, Mao

, Liu

and Liu

, Geometric reinforcement learning for path planning of UAVs, Journal of Intelligent & Robotic Systems 77(2) (2015), 391–409.

21.

Lin

and Saripalli

, Sampling-based path planning for UAV collision avoidance, IEEE Transactions on Intelligent Transportation Systems 18(11) (2017), 3179–3192.

22.

Chen

Y.B.

, Luo

G.C.

, Mei

Y.S.

, Yu

J.Q.

and Su

X.L.

, UAV path planning using artificial potential field method updated by optimal control theory, International Journal of Systems Science 47(6) (2016), 1407–1420.

23.

Yao

, Wang

and Su

, Cooperative path planning with applications to tar-get tracking and obstacle avoidance for multi-UAVs, Aerospace Science and Technology 54 (2016), 10–22.

24.

Balampanis

, Maza

and Ollero

, Area partition for coastal regions with multiple UAS, Journal of Intelligent & Robotic Systems 88(2-4) (2017), 751–766.

25.

Acevedo

J.J.

, Arrue

B.C.

, Maza

and Ollero

, A distributed algorithm for area partitioning in grid-shape and vector-shape configurations with multiple aerial robots, Journal of Intelligent & Robotic Systems 84(1-4) (2016), 543–557.

26.

, Wang

, Zhao

, Pan

and Du

, Formation control and collision avoidance for multi-UAV systems based on Voronoi partition, Science China Technological Sciences 63(1) (2020), 65–72.

27.

Kapoutsis

A.C.

, Chatzichristofis

S.A.

and Kosmatopoulos

E.B.

, DARP: divide areas algorithm for optimal multi-robot coverage path planning, Journal of Intelligent & Robotic Systems 86(3-4) (2017), 663–680.

28.

Wang

, Zheng

, Cui

and Lin

, A minimum spanning tree based method for UAV image segmentation, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences 3 (2016), 111.

29.

Pop

P.C.

, The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances, European Journal of Operational Research 283(1) (2020), 1–15.

30.

Gutin

and Punnen

A.P.

, The traveling salesman problem and its variations (pp. 1–28), (2002). New York: Springer.

31.

Papadimitriou

C.H.

, Euclidean traveling salesman problem is NP complete, Theoretical Computer Science 4 (1978), 237–244.

32.

Alemayehu

T.S.

and Kim

J.H.

, Efficient nearest neighbor heuristic TSP algorithms for reducing data acquisition latency of UAV relay WSN, Wireless Personal Communications 95(3) (2017), 3271–3285.

33.

Khanra

, Pal

, Maiti

M.K.

and Maiti

, Multi-objective four dimensional imprecise TSP solved with a hybrid multi-objective ant colony optimization-genetic algorithm with diversity, Journal of Intelligent & Fuzzy Systems 36(1) (2019), 47–65.