Small rotorcraft unmanned air vehicles (sUAVs) are valuable tools in solving geospatial inspection challenges. One area where this is being widely explored is disaster reconnaissance . Using sUAVs to collect images provides engineers and government officials critical information about the conditions before and after a disaster . This is accomplished by creating high- fidelity 3D models from the sUAV’s imagery. However, using an sUAV to perform inspections is a challenging task due to constraints on the vehicle’s flight time, computational power, and data storage capabilities . The approach presented in this article illustrates a method for utilizing multiple sUAVs to inspect a disaster region and merge the separate data into a single high-resolution 3D model.
Small rotorcraft unmanned air vehicles (sUAVs)are valuable tools in solving geospatial inspection challenges. One area where this is being widely explored is disaster reconnaissance . Using sUAVs to collect images provides engineers and government officials critical information about the conditions before and after a disaster . This is accomplished by creating high-fidelity 3D models from the sUAV’s imagery. However, using an sUAV to perform inspections is a challenging task due to constraints on the vehicle’s flight time, computational power, and data storage capabilities . The approach presented in this article illustrates a method for utilizing multiple sUAVs to inspect a disaster region and merge the separate data into a single high-resolution 3D model.
Brigham Young University’s (BYU) Research in Optimized Aerial Monitoring (ROAM) Lab has been inspecting areas affected by disasters with 3D models generated using optimized autonomous aerial imaging. When these models are high-fidelity, they can be used to inspect terrain and infrastructure . Current industry practices for infrastructure and geospatial inspections create sub-optimal models that frequently contain holes or warping, making them difficult to effectively analyze . ROAM’s custom algorithm selects optimal camera imaging positions to drastically improve the quality of the resulting 3D digital models .
Using multiple sUAVs for disaster reconnaissance provides advantages that will be illustrated using data collected in the city of Pescara del Tronto, Italy. This town was devastated by earthquakes in August and October 2016. Pescara del Tronto was chosen because it was inspected with sUAVs on three different occasions. The first two inspections were performed after the August earthquake (moment magnitude (M) of 6.2)  and October earthquake (M 6.6) . The third inspection was completed in July 2018 to analyze the long term changes in structural decay and soil movement. The 3D models for each visit can be accessed at . The Pescara del Tronto inspection site covers roughly 0.5 km2.
Figure 1 shows a portion of the 3D models of Pescara del Tronto generated from each of the three collection dates. These models show the immediate consequences of the earthquakes as well as the long-term effects that persist years afterwards. From the models it is evident that the second earthquake (occurring between the left and middle frames) caused most of the remaining structures in this area to collapse, and the slope that is unprotected by the retaining wall to fail. The failing slope is highlighted by the red oval. Almost two years later this same hillside continues to slip. The black area on the slope face is a new mesh retaining cover being placed to prevent further failure.
This article outlines a methodology for performing disaster reconnaissance using multiple sUAVs. Data from actual flights performed by a single drone at Pescara del Tronto was used in simulations for multiple sUAVs. This provides comparison results of the multi-vehicle methodology directly with a single-vehicle in-field test. In-field multi-vehicle tests will be conducted once further safety measures are factored into the algorithm, primarily collision avoidance. The simulations presented here provide substantial evidence of the benefits of using multiple sUAVs in inspections. These benefits reduce in-field time and set the stage for dynamic mission planning.
Multi-Vehicle Disaster Reconnaissance
The inspection workflow for multiple sUAVs, shown in Figure 2, has steps to: (a) incorporate location-specific data, (b) triangulate this data and identify surface normals, (c) use the surface normals to select optimal camera locations, (d) assign vehicle routes to the camera locations, (e) fly those routes, and (f) create 3D models using structure from motion (SfM):
Location Data: Creating sUAV routes requires previously acquired geospatial data of the inspection location. This data is obtained from two sources: 3D point clouds of prior inspections and terrain data exported from Google Earth. Point clouds give a very detailed representation of both topography and infrastructure. Google Earth terrain data gives a general elevation and fills in any gaps missed in the point cloud. In the July 2018 inspection at Pescara del Tronto, both terrain and point cloud (model from the October 2016 inspection) data were used.
Potential Camera Point Identification: Using the spatial data, potential camera positions are identified. First, a triangulated mesh is generated using the location data. For each face in the mesh, a potential position is selected at a user-specified distance normal to the face.
Optimized Point Selection: The subset of camera locations to be used are identified by selecting points with high coverage until at least 95% coverage is achieved. Higher-priority camera locations are those that view more area on the surface within a 45 degree view angle of the camera’s location. In Pescara del Tronto, 801 camera locations were selected from thousands of potential locations. The selected points are visible in Figure 3 as the black dots over a coarse elevation model of the inspected area.
Task Assignment and Path Planning: To plan paths for multiple sUAVs, two complementary approaches are used: a centralized vehicle routing problem solver (VRP)  and a decentralized market-based assignment algorithm. The centralized algorithm provides sUAV routes when all the inspection points are known a priori. The decentralized planner updates routes when additional inspection points are discovered while the sUAVs are in flight and will be discussed in detail in the next section. For both methods, since we are using quadrotor sUAVs and the vehicles must stabilize each time they take an image, the paths are computed as waypoint lists.
The VRP is a generalization of the traveling salesman problem that considers multiple salesmen. It has been well-researched with effective open-source solutions. We use Google’s Operations Research Tools (OR-Tools)  to run on 150 camera locations randomly selected from the 801 points in the Pescara del Tronto dataset. A maximum flight distance of 1500 meters was used to ensure the flight paths were feasible. The pathways for ten sUAVs flying waypoints allocated by the OR-Tools solver are shown in Figure 4. Examination of these shows that the vehicles visit different numbers of camera locations. A comparison of distance traveled, points visited, and flight time for these pathways is given in Figure 5. Each vehicle has a different total workload, indicated by percentage of total estimated flight time, but all of the flight times are within 6% of each other.
Figure 6 illustrates the potential reduction in flight time by showing the simulated total flight time for all of the Pescara del Tronto camera locations, given different numbers of sUAVs. The operation crew in Pescara del Tronto spent an estimated 140 minutes with their single sUAV flying, which can be reduced significantly with the addition of multiple sUAVs flying concurrently.
3D Models: Once imagery is collected of a region, the photographs are used to build a 3D model of the area using SfM . SfM is a photogrammetric modeling method that stitches together twodimensional images into a three-dimensional object. The SfM algorithm identifies the same points in multiple images and calculates the distance that point moved between photos. With these distances, the software generates a 3D mesh and overlays the images to create a life-like 3D model of the region imaged.
Dynamic Tasking With Market-Based Assignment Algorithm
It is common to have pre-existing terrain data for inspection sites, but there are many instances when this data lacks information about structures such as trees or buildings within the inspection areas. When this is the case, inspection points will not be optimally planned to image those structures, causing holes in the final 3D model. Our solution to this challenge is to perform an initial inspection at high altitude, producing a low-fidelity model of the region that captures the location and general shape of structures. The low-fidelity model is used to select optimized camera locations for producing a higher-fidelity 3D model. Currently, these steps occur over multiple site visits, with a single sUAV operating during both the low- and high-fidelity inspections.
To improve this workflow, we are developing techniques for performing low- and high-fidelity inspections concurrently, with the low-fidelity vehicles informing the highfidelity vehicles of new inspection points. These dynamically-received inspection points must be assigned to and planned for in the routes of the high-fidelity sUAVs. The assignment and path planning occurs in a decentralized market-based planning algorithm, as described in the next subsection. To simulate a typical flight of the high-fidelity vehicles, we use the OR-Tools VRP solver to generate an initial set of paths, then allocate additional points using a market algorithm.
A market algorithm is an approach to allocating tasks between independently acting agents (modeled after economic markets) where agents make bids on tasks based on their own value for that task . There are several advantages to using a market-based algorithm, due to the fact that each agent acts individually based on its own knowledge and a small amount of information is shared between agents. These advantages include: ease of decentralizing the computation, bids customized to the capabilities of individual agents, and the ability to operate with a low communication bandwidth. Simple market-based algorithms can result in highly non-optimal solutions of the NP-Complete problem. However, advanced implementations are near the optimality of other VRP solvers .
In our implementation, we form an auction-style market, where each task is bid upon by all agents (each agent represents a specific sUAV) and all agents are trying to obtain tasks without overspending. The algorithm receives as inputs a set of agents A and a list P of points (pi) to allocate to A. Each agent has a constant spending limit, keeps track of the total amount it has spent, and maintains a list W of points (wk) it has won, with the list being sorted in the flight path order. Iterating through P, bids are solicited for every point pi from all of the agents in A. To make a bid on pi, the agent searches through W to find the point wk having the lowest cost with respect to pi. It then finds the additional cost of travelling to pi and returns it as a bid.
Figure 7 shows simulation results of using the market algorithm to allocate an additional 50 camera locations to agents with existing flight paths. The solid lines are the initial flight paths and the dashed lines are the updated paths after the market algorithm executed. It can be seen that logical allocation of points occurs. This algorithm is a proof of concept that can be incorporated into a distributed framework to allow agents in communication with each other to auction dynamically-received camera positions.
Conclusions and Future Work
Inspecting disaster areas with sUAVs provides a safe and accurate method for assessing damage. The sUAVs perform autonomous aerial imaging, optimized for photogrammetry, to construct high-fidelity 3D models. These high-fidelity models enable decision makers who can then predict and prevent further damage. With current practices, inspections are completed with a single aerial vehicle. This article provides methods for obtaining routes for multiple sUAVs. The routes may be planned a priori (using a centralized algorithm) when pre-existing data is available or dynamically (using a decentralized, market-based algorithm) when new inspection points are discovered. Multi-vehicle inspection decreases the time needed to collect data while the information gained increases. Additionally, in-field safety is improved as the demand for analysts to venture into high-risk areas is reduced by sending sUAVs instead.
As development of this work flow continues, we will perform infield testing of multi-vehicle flights. A necessary step prior to flight experimentation is to ensure collision avoidance among the vehicles. Vehicle routes will be evaluated and adjusted to ensure that sUAVs will maintain a user-specified separation distance. Hardware will also be incorporated into the sUAVs to provide communication among the vehicles, enabling execution of the dynamic market-based planner. After this is accomplished, all the components necessary to enter an unknown territory and construct flight paths dynamically will be present.
This research was supported through the Center for Unmanned Aircraft Systems (C-UAS), a National Science Foundation-sponsored industry/university cooperative research center (I/UCRC) under NSF Award No. IIP-1650547 along with significant contributions from C-UAS industry members.
About the Authors
Jacob Willis graduated with a BS in Computer Engineering from Brigham Young University in April 2019. He is now pursuing an MS in Electrical Engineering from Brigham Young University, emphasizing in Guidance, Navigation, and Control.
Cammy Peterson is an Assistant Professor in the Electrical and Computer Engineering Department at Brigham Young University. She received a PhD from the University of Maryland in Aerospace engineering. Her current research includes cooperative control, autonomous systems, and detection and estimation applications.
John Hedengren is an Associate Professor at Brigham Young University in the Department of Chemical Engineering. He received a PhD from the University of Texas at Austin and worked for 7 years in advanced process control in industry. His current work is on optimization algorithms, primarily for aerospace and energy applications.
Kevin Franke is an Associate Professor at Brigham Young University in the Department of Civil and Environmental Engineering. He received a PhD from Brigham Young University in 2011. Prior to that, he worked as a consulting professional engineer for 6 years in the areas of earthquake engineering, foundation design, embankment design, and levee/canal analysis. His current research focuses on probabilistic liquefaction hazard analysis and UAV applications for civil engineering.