VPP: Visibility-Based Path Planning Heuristic for Monitoring Large Regions of Complex Terrain Using a UAV Onboard Camera

944 IEEE JOURNAL OF SELECTED TOPICS IN APPLIED EARTH OBSERVATIONS AND REMOTE SENSING, VOL. 15, 2022 VPP: Visibility-Based Path Planning Heuristic for Monitoring Large Regions of Complex Terrain Using a UAV Onboard Camera Andres J. Sanchez-Fernandez , Luis F. Romero , Gerardo Bandera , and Siham Tabik Abstract—The use of unmanned aerial vehicles with multiple onboard sensors has grown significantly in tasks involving terrain coverage such as environmental and civil monitoring, disaster management, and forest fire fighting. Many of these tasks require a quick and early response, which makes maximizing the land covered from the flight path a challenging objective, especially when the area to be monitored is irregular, large and includes many blind spots. Accordingly, state-of-the-art total viewshed algorithms can be of great help to analyze large areas and find new paths providing maximum visibility. This article shows how the total viewshed computation is a valuable tool for generating paths that provide maximum visibility during a flight. We introduce a new heuristic called visibility-based path planning (VPP) that offers a different solution to the path planning problem. VPP identifies the hidden areas of the target territory to generate a path that provides the highest visual coverage. Simulation results show that VPP can cover up to 98.7% of the Montes de Malaga Natural Park and 94.5% of the Sierra de las Nieves National Park, both located within the province of Malaga (Spain) and chosen as regions of interest. In addition, a real flight test confirmed the high visibility achieved using VPP. Our methodology and analysis can be easily applied to enhance monitoring in other large outdoor areas. Index Terms—Area coverage, fire prevention, monitoring path, path planning, total viewshed, unmanned aerial vehicle (UAV), visibility analysis. I. INTRODUCTION THE analysis of visibility is of paramount importance in Geographic Information System (GIS) software. Visibility estimation consists in finding the amount of terrain seen by an observer from a given location, which can contribute considerably to nature conservation in regions of complex terrain [1]. Monitoring areas of difficult access is still a challenging task, even though novel advanced technologies have emerged, e.g., Manuscript received August 7, 2021; revised October 17, 2021; accepted December 4, 2021. Date of publication December 13, 2021; date of current version January 17, 2022. This work was partially supported by the Spanish Ministry of Science and Technology through the projects TIN2016-80920-R and PID2019-105396RB-I00, the Regional Government of Andalusia through the projectA-TIC-458-UGR18(DeepL-ISCO)withintheAndalucíaERDF2014-20 Operational Programme, and the University of Malaga through the I Plan Propio de Investigación. (Corresponding author: Andres J. Sanchez-Fernandez.) Andres J. Sanchez-Fernandez, Luis F. Romero, and Gerardo Bandera are with theDepartment ofComputerArchitecture,Universityof Malaga,29071 Malaga, Spain (e-mail: [email protected]; [email protected]; [email protected]). Siham Tabik is with the Department of Computer Science and Artificial Intelligence and DaSCI (Andalusian Research Institute in Data Science and Computational Intelligence), University of Granada, 18071 Granada, Spain (e-mail: [email protected]). Digital Object Identifier 10.1109/JSTARS.2021.3134948 systems using infrared rays and cameras installed in fixed and mobile terrain locations [2]. Nowadays, the monitoring activity in these areas is still carried out in situ by one or several forest rangers located at fixed points within the territory and moving around when necessary [3], [4]. Since human personnel is required, these monitoring systems suffer from significant shortcomings as they 1) are unsuitable for situations that require real-time response since it is people who detect and report the hazard, 2) compromise personnel safety by being close to the risk, and 3) could provide inaccurate information, leading to a misunderstanding of the magnitude of a hazard. On the bright side, these disadvantages have led to the use of other systems such as unmanned aerial vehicles (UAVs) to effectively monitor forest regions of complex terrain [5]–[7]. UAVs, commonly known as drones, have become more useful for civil applications since many companies started to research and use them with new objectives. Their uses have evolved towards much more specific tasks that include remote-sensing [8], disaster prevention [9], operational support during emergencies [10], damage monitoring of critical infrastructures [11], traffic control [12], and environmental monitoring [13]. All these applications have in common the need to collect vast amounts of data, making UAVs suitable for this task. They carry multiple sensors and processing units that enable the acquisition of datasets on demand during the flight over a target area. Many other advantages of using UAVs include: 1) low cost of deployment; 2) high visibility of the terrain due to low flight height; 3) high capacity to reach remote locations and capture high-resolution images; 4) accurate measurements of environmental variables such as temperature, humidity, atmospheric pressure, and vegetation health; 5) adequate ability to compute lightweight algorithms on onboard processing units; and 6) high safety conditions for all personnel. When monitoring a target area, the first decision to make is whether to use one or several UAVs, which depends on several considerations [14]: the aim of the activity, the number of points to monitor, the extension of the region, etc. In general, a single UAV monitors small areas, whereas coordinated groups of UAVs usually cover larger ones. However, the latter case could be improved if a path providing all-round visibility is found. Following this path could reduce the number of UAVs required to cover the region and the time needed to complete the task. This problem is similar to the observer siting problem that involves finding the minimal number of observers providing maximum coverage of a target area, improving response times to unexpected events [15], [16]. Exploiting this similarity is key This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ SANCHEZ-FERNANDEZ et al.: VPP: VISIBILITY-BASED PATH PLANNING HEURISTIC FOR MONITORING LARGE REGIONS 945 to optimizing those approaches using UAVs to monitor large regions of complex terrain. This article proposes a new heuristic called visibility-based path planning (VPP) that offers a different solution to the path planning problem based on visibility data, where we have chosen forest fire prevention as a case study. VPP shows the benefits of the total viewshed computation: we find several safe and flyable paths providing all-round visibility from the results obtained from a thorough visibility analysis that exposes the most hidden areas. These results open the possibility of monitoring challenging regions of complex terrain using the onboard camera of a single UAV. As the generated path is composed of several waypoints, we also provide a method to determine the direction of the onboard camera for each one, aiming to avoid overlapping visual areas of already monitored locations to increase the amount of terrain covered. These images—taken throughout the flight—can be analyzed in real time to alert local authorities in case of fire. Finally, we assessed the performance of VPP by simulating the UAV flight over two complex terrain regions of 48 and 202 km2, where we achieved 98.7% and 94.5% terrain coverage, respectively. In addition, a real flight test over a reduced area is presented. The contributions of this article are as follows. 1) A new heuristic called VPP is presented. VPP finds the waypoints that will form a safe and flyable path providing high visibility for a single UAV based on a thorough visibility analysis. This analysis allows us to identify the most hidden areas in regions of complex terrain, achieving the monitoring of entire regions to prevent fires at a relatively low cost. 2) We describe the steps taken to estimate the direction of the UAV onboard camera for each waypoint included in the generated route. These directions are chosen to maximize the area covered by avoiding overlapping visual areas during the flight. 3) We provide the coverage results obtained by simulating the flight of the UAV over two different real environments following the path generated by VPP. The rest of this article is organized as follows. Section II describes the state-of-the-art research on path planning for UAVs. Section III describes the proposed VPP heuristic, which generates safe and flyable paths providing high visibility. Section IV explains the steps taken to set the direction of the camera for each waypoint of the path to maximize coverage. Section V evaluates the performance of the VPP heuristic based on the results from two different flight simulations and a real flight test. Finally, Section VI concludes this article. II. RELATED WORK There is a large body of research on UAV path planning, so we have considered those most relevant to this article. The literature distinguishes three relevant research areas according to the primary purpose of the flight: obstacles avoidance, energy constraints, and area coverage. A. Obstacles Avoidance MostresearchonUAVpathplanningaimstooptimizethepath between several points by avoiding obstacles. For example, the methodproposedin[17]iscapable ofgeneratingsafe andflyable paths between two points on the sea in the presence of different threat environments (obstacles) using hybrid differential evolution and quantum-behaved particle swarm optimization. Lin and Saripalli[18] developed a sampling-based pathplanningmethod to generate collision-free paths in real time considering moving obstacles. The algorithm presented in [19] considers both static and dynamic threads to generate a smooth path with low cost for UAVs based on ant colony optimization (ACO). Cekmez et al. [20] implemented a UAV path planning strategy based on the multicolony ACO algorithm for checking several control points considering obstacle avoidance in a large area. The dynamic path planning method introduced in [21] generates an optimal path in a known environment based on the A* algorithm for the UAV so that it can avoid both static and moving obstacles. Chen et al. [22] presented a robust and effective path planning strategy for UAVs based on the searching ability of the ACO algorithm. These algorithms are useful for dynamic environments, e.g., surveillance flights over military areas and reconnaissance flights at low height in the presence of buildings and other obstacles. However, such solutions are not generally suited for the particular requirements of forest fire monitoring. This particular scenario can be considered as a static environment—no significant changes occur over time—and the only restriction on flight height is imposed by the competent authority. B. Energy Constraints Research is also conducted considering energy consumption constraints for the UAV to achieve an efficient flight, either with the path determined beforehand or by generating it in real time. The proposal given in [23] focuses on developing an energy-aware path planning algorithm that minimizes energy consumption for the UAV and other conditions such as coverage and resolution. The method proposed in [24] aims to assign energy-efficient trajectories for UAVs. It estimates the energy consumption resulting from basic UAV movements and also considers discrete spaces to avoid collisions. Lee and Yu [25] assessed the endurance flight of a solar-powered UAV, which was improved by optimizing the path based on gravitational potential and controlling the flight height in real time. The novel approach proposed in [26] performs an energy-efficient inspection to minimize the overall energy consumption of the UAV flight. Finally, Yang et al. [27] an adaptive crop scouting mechanism for a single UAV that includes a real-time path planning methodology based on limited energy and power consumption. Alltheseapproachesaddressedthecoverageproblembyusing discrete spaces (subregions) that must be visited by the UAV. This solution is inefficient because it neglects the fact that the UAV could have covered some locations from others nearby if the horizontal coordinate of the onboard camera is considered. C. Area Coverage Coverage path planning algorithms aim to find optimal paths from which every point in the target area is visually covered. Very few path planning algorithms aim to guarantee significant or total visual coverage of the target area. 946 IEEE JOURNAL OF SELECTED TOPICS IN APPLIED EARTH OBSERVATIONS AND REMOTE SENSING, VOL. 15, 2022 Gramajo and Shankar [28] introduced a real-time path planning methodology for a single UAV based on limited energy and power consumption, which depends on the vehicle motion. It aims to maximize the spatial coverage of a given area by optimizingtheturning ratesaccordingtothemaximum loadfactorof the UAV. The main advantage of this proposal is that it does not require adjusting the space discretization beforehand. However, the weaknesses include the following: 1) the drone coverage is limited to the vertical component below it and 2) some areas are not finally covered, one of which is of considerable size. The algorithm proposed in [29] generates paths specially designed for UAV photogrammetry based on E-Spiral and E-BF algorithms. The method considers the camera characteristics, overlapping rates and energy consumption. The main downsides are as follows: 1) the discretization of the target area is required making the UAV fly following a path that sweeps the whole territory and 2) only vertical photography is considered. Nam et al. [30] proposed addressing the coverage path planning problem for a UAV using approximate cellular decomposition and a wavefront expansion algorithm. It succeeds to cover the study area but, similarly to the previously presented approaches, it performs a prior grid-based area decomposition so that the UAV must fly over each target center inefficiently. The proposal in [31] addressed the path planning problem using a new method based on siting multiple observers and an evolutionary algorithm. First, an iterative process removes redundant points according to how each particular viewshed value affects the area coverage. As a result, they obtained a set of locations that includes the fewest number of places providing maximum coverage. This method generates a near-optimal path covering the terrain but it suffers from the following drawbacks: 1) it considers the restricted viewshed from each location in the territory resulting in a loss of information in processing and 2) a grid-based decomposition method is required for the target area. On the other hand, few coverage path planning approaches focus on monitoring using UAVs for fire prevention purposes. For example, Leng et al. [32] introduced a model to monitor regions with zone occlusions due to vegetation through a two-steps approach to determine near-optimal flight paths. First, they arranged the waypoints using the Centroidal Voronoi Tessellation method. Second, they generated Dubins paths using a clustered spiral-alternating algorithm. This article achieved to cover dense areas by considering more points for the path than typical grid-based methods. Nevertheless, it suffers from several limitations: 1) the decomposition of the target area following a CVT-based approach which, although it seems to perform better than other grid-based works, is still inefficient as the drone must fly over every independent region; 2) the consideration of restricted viewshed; 3) the high cost of development that implies a multi-UAV approach; and 4) the unavailability of the digital surface model of forest regions for most territories. Zhou et al. [33] presented a path planning approach for forest fire prevention based on two stages: local and global. At the local stage, they find the optimal path between every two target points by applying a Dubins path—based on the A* algorithm. At the global stage, the authors determine the visiting order of each target point using an improved ant colony optimization (ACO) algorithm. This approach successfully calculates a near-optimal path that passes through every point in the terrain. However, this proposalhas several weak points asfollows:1) the waypointsare directly placed and only the path between them is generated and 2)each waypointinthe areais placedin atwo-dimensional(2-D) space without considering its elevation, neither the visibility, which are very important variables in real-world applications for forest fire prevention. The abovementioned approaches, which are specific to the coverage path planning problem, suffer from several shortcomings. 1) None of the proposed solutions so far considers the visibility from the initial set of locations for further calculations, e.g., the viewshed results from the starting and ending points. This data should be the input of the heuristic methods used to solve the path planning problem. 2) Those alternatives using grid-based discretization for computing the waypoints in a given area have the drawback of forcing the UAV to fly over each independent subregion. This solution neglects whether a particular subregionhasalreadybeen visually coveredfrom adjacent locations. 3) Many algorithms consider restricted viewshed. It means that the terrain captured by the camera sensor is related to the area that falls within a preset circle of fixed radius just directlyunderneaththeUAV.Therefore,theUAVmayvisit many redundant locations within the territory, despite the high resolution of the cameras currently available. These approaches are typically motivated by some performance constraints. 4) All these approaches may be valid for small territories but hardly applicable in large and complex scenarios since they do not perform a thorough visibility analysis of the area. In this article, we use the total viewshed analysis to solve the path planning problem for large regions of complex terrain. This typeofanalysis impliescomputing theviewshedfromeachpoint in the digital elevation mode (DEM) with no visibility restrictions. Therefore, our approach does not require the application of a discretization technique of the space beyond that provided by DEM spatial resolution. III. VISIBILITY-BASED PATH PLANNING Unfortunately, forest fires have become more common nowadays, putting our ecosystems at risk. Millions of hectares of forest burn every year, bringing substantial costs to the countries affected and damaging the environment [34]. Experts consider early detection the most important way to minimize the consequences of fires; therefore, governments have invested substantial resources to develop better systems for the early detection of forest fires. This section introduces a new heuristic called VPP designed to address the problem of monitoring large regions of complex terrain based on a thorough visibility analysis. To this aim, VPP generates a safe and flyable path from which the UAV onboard camera visually covers most of the target terrain. As a starting point, we assume that the UAV must fly over some initial locations of the given region for monitoring purposes (e.g., high environmental value locations and battery recharging points). From this initial assumption, the goal is to SANCHEZ-FERNANDEZ et al.: VPP: VISIBILITY-BASED PATH PLANNING HEURISTIC FOR MONITORING LARGE REGIONS 947 Fig. 1. Area of the Montes de Malaga Natural Park (Spain). The boundaries of the park are represented by a white line. maximize the visual coverage of the entire area by optimizing the number of points that will form the path. We achieve this by identifying the hidden locations of reduced visibility, usually called hidden areas, to monitor them during the flight and warn the local authorities in case of detecting fire hotspots. Another consideration is that the UAV will fly following a straight line between every two target points and maintaining a steady height along the path. We do not consider obstacles avoidance as the flight height of the UAV is typically much higher than the height of trees found in any forest region. In case the environment changes with respect to the initial model (e.g., installation of new power lines), the path can be adjusted to avoid these new static obstacles with the help of GIS tools. For the sake of clarity, throughout the following sections, we will use some figures showing partial results to explain the steps to be followed in the VPP heuristic. The selected study area comprises a forest region particularly affected by fires within the last 10 years: the Montes de Malaga Natural Park (see Fig. 1) [35]–[37]. This area is located in the south of Spain and has significant environmental interest with extremely varied relief—which causes remarkable monitoring difficulties. A. Types of Waypoints A path is defined as a route between one place and another formed by connecting several points located in a territory. The selection of these points, called waypoints, is essential for the resulting path to provide maximum visibility during flight. Note that there are many possibilities for defining the waypoints and the shortest way to connect them, but each possibility should consider the viewshed from the initial locations of mandatory monitoring in the target region. We distinguish between two types of waypoints according to their arrangement along the path. 1) Primary waypoints (Wp): This group includes the initial locations of mandatory monitoring, as well as those found by the VPP heuristic. These points are connected using straight lines to form the path. 2) Secondary waypoints (Ws): To this type belong those intermediate points placed on the straight line of travel between two consecutive primary waypoints from which the UAV can also capture the terrain (more detail in Section IV). The distance between two consecutive waypoints in Wsis adjusted so that the processing of an image taken at the first point is completed before reaching the second. Obtaining a suitable solution to the path planning problem based on maximizing visibility is highly challenging due to the many variables influencing the result. Some examples are the UAV flight height and camera characteristics such as field of view and resolution. These variables significantly change the area covered from each of the waypoints in Wpand Ws.For example, it is possible that after getting a first approximation of the path, some waypoints set at the beginning of the process becomeredundant. It happens when someofthe areas monitored from these points have already been covered from other nearby locations, which can lead to a challenging vicious circle. This issue states the importance of visibility analysis to reduce the effect of overlapping viewsheds on the path generation process. B. Main Data Structures The VPP heuristic requires different types of data at each of its stages, so these are defined as follows. 1) Digital elevation model (DEM): The 3-D representation of the terrain with a size of dimy xdimx where each cell represents the elevation above sea level of the corresponding point of the ground. Cells are represented with i,jsubscripts corresponding to xand ycoordinates, respectively. 2) Singular viewshed (SVS): Map storing the viewshed, i.e., the area visible from a particular point of view (POV), which represents any point/location of the DEM where we “place” an observer. SVS is a unique matrix with the same size and grid as the DEM. Each cell, related to a point in the DEM, contains a Boolean value representing whether the corresponding location is visible from the POV. No visibility restrictions are considered for this computation and, therefore, each line of sight is considered without distance constraints. 3) Point set cumulative viewshed (PS-CVS): Map that accumulatestheSVS results. Only the viewshedsfrom primary waypoints contribute to this structure. 4) Masked total viewshed (M-TVS): Map obtained from solving the total viewshed problem where specific points/areas are left out of the analysis. Instead of considering all the points in the DEM, we only find those providing maximum viewshed over no redundant areas. Therefore, we exclude uninteresting and already monitored areas from the viewshed computation [16]. C. Workflow of the VPP Heuristic Fig.2showstheflowchartoftheVPPheuristicwitheachstage represented. First, the VPP heuristic requires setting two initial design thresholds αand γ. Each of these thresholds is related to a target percentage of visual coverage (Cv) sought for the region of interest: αrepresents the minimum target percentage of area to be covered as a result of the process; γindicates the minimum percentage increase in area coverage that must occur between two measurements. In general, low thresholds involve few waypoints and shorter but imprecise flight paths, whereas 948 IEEE JOURNAL OF SELECTED TOPICS IN APPLIED EARTH OBSERVATIONS AND REMOTE SENSING, VOL. 15, 2022 Fig. 2. Flowchart of the VPP heuristic showing the main workflow on the left and the workflows within the first three stages on the right (the fourth stage is not broken down as it is only one step). high thresholds increase the number of waypoints, which can turn the path into a tremendously expensive zigzag sweep. In our case study, we set α= 90% and γ=5%. It means, respectively, that we would accept a result of 90% of the area visually covered and a 5% increase in area coverage between two consecutive measurements, based on the requirements and difficulty of the terrain at hand. These thresholds may need to be adjusted for other environments depending on the goal and relief of the target region. Each of the four stages that make up the VPP heuristic is detailed below. D. Description of the Four Stages 1) Stage-1: Evaluating the Contribution to the Coverage of the Initial Locations: For any path planner, the first step is to define a target point or set of target points on the ground that the UAV must monitor. These locations are called logistic points (L), and among them are such obvious ones as the starting and ending points of the flight. We can also include some locations for recharging batteries, ensuring communications coverage or effectively monitoring some areas of high environmental value. Note that these requirements may vary depending on the objective of the study and the complexity of the terrain, but the logistic points are always the first to be included in Wp. Based on the initial conditions of our case study, the UAV has to fly over five logistics points including three locations for monitoring important natural areas. The viewshed maps for each of these must be computed and merged to obtain a first approximation of the terrain coverage (Cv).1The SVS map is obtained for each Pi∈Wp,i=1...|Wp|so that, afterwards, theyarealladdeduptoformthePS-CVSmap.ThegeneratedPS- CVS map represents the amount of terrain covered and, at this early stage, provides a global overview of the coverage results obtained from considering the logistic points at the beginning of the process. Once the viewshed from each logistic point has been computed, the focus is on the uncovered terrain. To show these areas, we will use the cumulative hidden areas (CHAR) map—the complementary structure of the PS-CVS map. The CHAR map highlights the uncovered areas, allowing us to find and define the most remote ones (see Fig. 3). This map shows that, although we have analyzed five initial logistical locations, many hidden areas of difficult access are still widely scattered and diverse in shape, not forming simply connected topological spaces. At this early stage, connecting the points to generate the path, which is a problem similar to the travelling salesman problem (TSP), is impractical because we will not obtain good results in terms of coverage. But in the following stages, adding new locations to Wpwill increase the visual coverage over the target region, ensuring successful monitoring. 2) Stage-2: Finding New Points of Maximum Visibility: Finding the following locations to be included in Wpis vital to increase coverage. For instance, Cervilla et al. [16] addressed 1Hereafter, the observer’s height (flight height) is set to h=30m. SANCHEZ-FERNANDEZ et al.: VPP: VISIBILITY-BASED PATH PLANNING HEURISTIC FOR MONITORING LARGE REGIONS 949 Fig. 3. CHAR map generated at the end of Stage-1. It shows the remaining uncovered area (purple layer) after having analyzed the viewsheds from the initial five logistic points (L) in Wp. The white line represents the boundaries of the Montes de Malaga Natural Park. a similar problem and concluded that it is already possible to guarantee a visual coverage above 90% with only two or three points considering a similar territory of about 50 km2with complex orography. In this case, we must ensure an appropriate balance between the number of points to be included and their locations to minimize the path length. This consideration will allow implementation in a real environment at a relatively low cost. Following this line, we naturally infer that the points providing maximum viewshed are good choices at this stage. These points are called POVs of maximum viewshed (V), and we find them by solving the total viewshed problem using the M-TVS map. In the first iteration, we compute the viewshed from each point in the DEM and accumulate their results in the M-TVS map (same number of cells as in the DEM). Each cell in this map relates to a specific location on the terrain and contains its viewshed value (measured in, e.g., km2). The point with the highest viewshed value is included in Wp. In the next iteration, the area visually covered from that point is excluded from the analysis; the new POVs of maximum viewshed will be the ones covering the largest uncovered area. Including these points progressively in Wpgradually increases the area covered so that it mayatsomepointexceedtheαthreshold.Wewillstop including POVs of maximum viewshed when this does not significantly increase the coverage result, i.e., ΔCv < γ calculated from the difference between two consecutive PS-CVS maps. In our case study, the inclusion of the two best POVs of maximum viewshed to Wphas proved to be the best strategy, guaranteeing a visual coverage above 80% for our region of interest (see Fig. 4), but there are still many hidden areas. The advantage is that the hidden areas at this stage begin to form small regions in objectively isolated valleys, and are, therefore, called isolated areas. Due to their visual isolation, only the flight ofthedroneoverthemguaranteesadequatemonitoring.Thenext step, covered in the third stage, is to identify these isolated areas to include them or points close to them in Wp. Solving the TSP at this stage is discouraged for the same reason as in the first stage, although better results would be obtained. 3) Stage-3: Identifying the Isolated Areas: Some path planning strategies, such as in [31] and [32], ensure that the UAV Fig. 4. CHAR map generated at the end of Stage-2. It shows the remaining uncovered area (purple layer) after having analyzed the viewshed from the initial five logistic points (L) and two points of maximum viewshed (V) in Wp.The white line represents the boundaries of the Montes de Malaga Natural Park. Fig. 5. Isolated areas identified using contour lines with a viewshed area less than λ=1km2at the end of Stage-3. Their centroids are marked with green pins only within the Montes de Malaga Natural Park. The white line represents the park boundaries. reaches all isolated areas of the target region, but following a greedy approach: they force the UAV to fly over almost any point on the ground. Conversely, VPP provides a better solution: identify visually isolated areas for the UAV to fly over their centroids, avoiding the need to sweep the whole region. We proposetwomethodstocharacterizetheisolatedareasaccording to the perspective from which it is analyzed. 1) From the observer’s viewshed, we define an area as isolated if it is not visible from a set of POVs of maximum viewshed. 2) From the viewshed of the target area, we consider an area isolated if the area of terrain seen from its center—similar toplacinganobserverthere—isless thana fixedparameter λ. This result is achieved by using contour lines based on this parameter. In this article, isolated areas are identified using the latter method, as it is the most objective. The parameter λ=1km2 is chosen after having carried out several optimization tests so that the resulting areas are more delimited in most cases, constituting simply connected spaces that are easily identifiable by their centroids (see Fig. 5). These centroids are included in Wpand, finally, the PS-CVS map is generated to check whether 950 IEEE JOURNAL OF SELECTED TOPICS IN APPLIED EARTH OBSERVATIONS AND REMOTE SENSING, VOL. 15, 2022 Fig. 6. Resulting flight path (red line) generated by VPP in the area of the Montes de Malaga Natural Park. The area covered is represented using a white layer over the terrain model. The white line represents the park boundaries. the percentage of terrain coverage is above the αthreshold. If this condition is met, we can proceed to the final stage. 4) Stage-4: Generating the Flight Path: The last stage of the VPP heuristic consists in generating the path by connecting the primary waypoints included in the final set Wp. After having completed the previous three stages, the set of waypoints Wp contains the following. 1) In total, five logistic locations including the starting and ending points and three easily accessible locations of high environmental value that can be used as recharging points for the UAV. 2) In total, two POVs of maximum viewshed obtained after computing the M-TVS map. 3) In total, 12 centroids of the isolated areas. Fig. 6 shows the path generated after connecting all the primary waypoints (similarly to solving the TSP) in the area of the Montes de Malaga Natural Park (Malaga, Spain). This 34 km-long path offers all-round visibility during the flight and, therefore, the UAV can successfully monitor the target area using its onboard camera. Note that the PS-CVS map calculated here may differ from that of a real flight because a 360◦onboard camera has been considered. However, it is more common to use an onboard camera with a narrower field of view, which affects the resulting coverage. In this case, we must set the best direction of the camera for each of the waypoints of the flight pathto maximizetheground coveredduringthe flight. Thisissue is the focus of the following section. IV. VIEWSHED-REJECTION METHOD FOR SETTING EACH DIRECTION OF THE ONBOARD CAMERA In the previous section, we presented the VPP heuristic for generating flight paths based on a thorough visibility analysis. That analysis considered the full range of visibility from any point in any of the four stages, as if a 360◦camera were placed at each of these points. But in real life, the use of this type of camera in UAVs is not a common practice and therefore the camera’s angle of view (AOV) comes into play. In photography, the camera’s AOV describes the angular extent of a given scene captured by a camera, measured horizontally, vertically, or diagonally. This variable can be seen as the maximum number of consecutive sectors (i.e., angles) that the camera is capable of capturing. This is why the camera’s AOV highly affects the choice of the direction of the camera— the middle sector of the set of consecutive sectors—for each waypoint of the flight, which is called Center of Interest (COI). Here, we propose a new methodology to find the best COI for each waypoint of the path. Each COI is set according to the direction of maximum visibility, obtained after having rejected those directions of the camera pointing at areas already covered from preceding locations along the path. As a result, visual overlapping is avoided, increasing the amount of terrain covered during the flight. A. Photographs Taken by the Onboard Camera The flight path generated by VPP at the end of Stage-4 consisted of 19 primary waypoints. The UAV will take a photograph from each of these primary waypoints but, in addition, more photographs can be taken on the way from one waypoint to another, e.g., every 150 m approximately, with these new points being the secondary waypoints (Ws). This distance is chosen to ensure that the processing of each image is completed before reaching the following location. This method leads to a total of 235 waypoints along the flight path (between Wpand Ws) where the camera’s AOV is crucial to maximize the coverage of the region. B. Additional Data Structures The following structures are required for this approach as follows. 1) RS stands for ring-sectors and is a look-up table where each row corresponds to a particular sector (from 0oto ns= 360o) and each column represents the distance to the given reference location. The first column (d=0)of each row is used to store the number of set values (visible locations) for the corresponding sector. The stored value for a given sector sand distance drepresents the state of the location, whether it is visible from the reference location. 2) AOV is a Boolean array with 360 cells (one per degree) that represents the camera’s angle of view, i.e., the sectors captured by the UAV onboard camera from a given waypoint of the path. 3) CC-SVS is the camera captured singular viewshed and contains the viewshed result from a given waypoint of the path in a similar way as the SVS structure but only analysing the flagged sectors in the AOV structure (sectors captured by the onboard camera). 4) PL-CVS is the point line cumulative viewshed and accumulates each viewshed result stored in CC-SVS as the UAV flies along the path. This structure also works as a Boolean mask that contains a set value in each cell corresponding to a location already covered by the UAV. C. Finding the Best COI for Each Waypoint Computing the best COI for each waypoint of the path is key tomaximizing visibilityduring flight.Once the flighthas started, we have to avoid pointing the camera in a direction where a high proportion of the terrain has already been covered from previous locations. SANCHEZ-FERNANDEZ et al.: VPP: VISIBILITY-BASED PATH PLANNING HEURISTIC FOR MONITORING LARGE REGIONS 951 Fig. 7. Viewshed computation from a reference point of view (POV) of h height and only one sector s, for the sake of clarity, showing: the ground profile, zenithal view and lookup table RS. The visible points in the ground profile are represented in green, whereas the red points correspond to hidden locations. The zenithal view shows the ring-sector shape obtained from the ground profile. The RS structure is filled following the results shown in the ground profile. We define a lookup table called RS that contains the number of covered points from a given waypoint and for each sector. RS has as many rows as sectors (from s=0 oto ns= 360o) and columns as the maximum possible distance between two points (measured in cells of the DEM). Fig. 7 shows how the RS structure is filled for a single sector: given a reference waypoint and a target location, if the target location is visible from the waypointand it hasnotbeen coveredyet—checking the Boolean value inside PL-CVS—its corresponding cell in RS is flagged. The total number of flagged cells in a particular row is stored in the first column of the RS structure, which also represents the weight of the sector. Finally, a fixed number of consecutive sectors (naov) will be captured by the camera at each waypoint of the path in a process represented using the AOV structure. AOV works as a Boolean mask: it enables visibility processing for some sectors, whereas disabling processing for the remaining ones (not captured by the camera). Therefore, only those consecutive sectors that are flagged will contribute to the coverage result, where the COI is the middle sector. The best set of consecutive sectors for each waypoint in AOV is chosen based on their weights and seeking to maximize the terrain coverage by avoiding visual overlapping. The weight of each sector is measured as the total number of points visible in the sector and not yet covered (previously stored in the first column of the RS array corresponding to d=0). In the end, the set of consecutive sectors holding the highest overall weight will be flagged in AOV for each waypoint. The overall weight of eachpossible groupingof naov consecutivesectors isobtained by following an iterative process: we add the weights from s=0 o to s=naov, then from s=1 oto s=naov +1 oand so on until the highest overall weight is found. The last step involves computing the CC-SVS and PL-CVS maps for each target waypoint sequentially to obtain the individual and accumulated terrain coverage results, respectively. D. Workflow for Simulating the Camera Behavior During Flight Once all necessary data structures have been defined, we can present the general workflow for any path and DEM to simulate the camera behavior during flight. 1) For each waypoint in the flight path, do the following. a) Fill RS based on the current visibility and the PL-CVS map. b) Fill AOV according to the set of consecutive sectors with the highest overall weight. c) For each point in the DEM, do the following. i) Compute the angular difference (Ad) and Euclidean distance (Ed) between the waypoint and the point. ii) Index the AOV Boolean array using Adto check whether the camera captures the current sector from the waypoint. iii) If this condition is met, do the following. A) Index the RS look-up table (using Adas row index and Edas column index) to retrieve the state of the target point, i.e., whether it is visible from the waypoint. B) If so, the corresponding cell is flagged in the CC-SVS map. d) Accumulate the result in the PL-CVS map. For the sake of clarity, four iterations of the proposed methodology are shown in Fig. 8 as a basis for explanation.2From the inputDEMandthefirstwaypointP1,wecanfilltheRSandAOV structures and compute the first CC-SVS map [see Fig. 8(a)]. At the beginning of the process, the CC-SVS map coincides with the PL-CVS map as there are no previous results [see Fig. 8(b)]. Then, from the data stored in PL-CVS and considering again the DEM, AOV, and RS structures, we can compute the CC-SVS for P2[see Fig. 8(c)]. After having processed the first two waypoints, the PL-CVS map is as shown in Fig. 8(d). Finally, repeating these steps result in the CC-SVS maps for P3and P4 [see Figs 8(e) and (g)] along with the data in the PL-CVS maps [see Figs 8(f) and (h)]. With the presented method, we manage to avoid overlapping viewsheds between the waypoints included in the flight path, thus maximizing the terrain covered by the onboard camera throughout the flight. V. EXPERIMENTS AND RESULTS This section evaluates the performance of VPP based on the terrain coverage captured by the UAV onboard camera considering three scenarios: two flight simulations over two complex terrain regions of 48 and 202 km2and a real flight over a reduced area of 1 km2. A. Experimental Setup 1) Systems and Algorithms: For the simulations, we used a system with Ubuntu 16.04.5 LTS and an Intel(R) Xeon(R) CPU E5-2698 v3 @2.30 GHz with 16 cores (32 threads) and 256 GB DDR4 RAM. To connect the waypoints of each flight path, we solved the TSPusingthe Network Analyst extensionfrom ArcGIS[38].On the one hand, the design of this path has not considered restricted visibility as appears, e.g., in [31]. Current camera technology allows high-definition image processing with minimal loss of definition. On the other hand, the obstacle avoidance problem 2The onboard camera’s angle of view and the height of the UAV flight are set to 84oand h=30m, respectively. 952 IEEE JOURNAL OF SELECTED TOPICS IN APPLIED EARTH OBSERVATIONS AND REMOTE SENSING, VOL. 15, 2022 Fig. 8. Simplified sequence of operations showing the Camera Captured Singular Viewshed (CC-SVS) and Point Line Cumulative Viewshed (PL-CVS) maps obtained after simulating the UAV flight over the first four waypoints of the path in the area of the Montes of Malaga Natural Park. (a), (c), (e), and (g) show the first four CC-SVS maps. (b), (d), (f), and (h) show the first four PL-CVS maps. TABLE I MAIN CHARACTERISTICS OF THE THREE REGIONS USED IN THE EXPERIMENTS aLatitude band designator. has also not been considered for generating each path because there will be no obstacles between two locations if we establish a sufficiently high flight height. 2) Key Features of the UAV: We took as a reference for the simulation the characteristics of the well-known DJI Phantom 4 Prodrone[39].Accordingly,thecasestudyonboardcameraused is the same as the one installed in that UAV. We set the camera’s AOV parameter to 84oand the flight height to h=30m. 3) Memory Optimization: Given a reference location, the viewshed computation involves checking the elevation data in the DEM, resulting in many cache misses in the system. This problem is caused by a lack of locality in memory, resulting in a deterioration in performance. To deal with this problem, we used a modified version of the sDEM algorithm described in [40] to obtain the viewshed result from each point.3Locality increases using this procedure by performing sequential memory accesses in processing. For more details on this particular optimization, please refer to the original article, as it lies beyond the scope of this research. 4) Main Characteristics of the Target Areas: Table I presents the UTM coordinates and elevation statistics of the case study 3The run-time of the viewshed computation can be found in [40]. areas. The values in this table reflect the abrupt orography of the regions studied based on the high value of the standard deviation of the elevation compared to the mean. B. Flight Simulation 1: Montes De Malaga Natural Park The first experiment involves a flight simulation over the Montes de Malaga Natural Park using a single UAV for monitoring. This park was previously used in Sections III and IV to explain the stages needed to generate the path and set the onboard camera behavior, respectively. Declared a protected natural space in 1989, this park near Malaga city (Spain) has 4800 hectares of complex terrain with areas from 80 to just over 1000 m above sea level. These areas host different protected flora and wildlife species, as well as many water resources. All these facts make the Montes de Malaga Natural Park a suitable scenario for fire prevention analysis and evaluation. Once we have generated the path using VPP and set the COI foreachwaypoint, we can simulate the UAV flight and obtain the finalterrain coverage value.Fig. 9showsthearea capturedby the UAV onboard camera after flying along the path and travelling it counterclockwise. The color scale indicates the terrain covered and the distance from the starting point where the photograph