Using Historical Data to Dynamically Route Post-Disaster Assessment Unmanned Aerial Vehicles in the Context of Responding to Tornadoes

Featured Application

This paper demonstrates the intelligent and specific use of historic meteorological data can be used to better route disaster assessment unmanned aerial vehicles so they can complete their mission in a quicker amount of time.

Abstract

Responding to tornado disasters resides at a unique intersection of search and rescue operations: it has attributes of wilderness and maritime search and rescue operations and search and rescue operations in the aftermath of earthquakes and hurricanes. This paper presents a method of attempting to leverage historical data to more efficiently identify the extent of the area damaged by a tornado. To assist in building and understanding the historical data, we also develop a method to generate tornado areas that react similarly to the limited historical data set. The paper successfully demonstrates the method of creating artificial tornado instances that can be used as a testing sandbox for the further development of tools when responding to tornado-type disasters. These artificial instances perform similarly in some important metrics to the historical database of tornado instances that we produced. This paper also shows that the use of historical tornado trends has an impact on the response method outlined in this article, typically reducing the standard deviation of the time it takes to fully identify the extent of the damage.

1. Introduction and Literature Review

The majority of search and rescue (SAR) literature, in particular when using unnamed aerial vehicles (UAVs) in assisting SAR personnel, typically responds to disasters that involved earthquakes or hurricanes. A detailed breakdown of the use of UAVs in disaster response and SAR operations can be found in the previous literature [1,2]. The two main axes of the use of UAVs for SAR operations can be separated into locating missing individuals or post-disaster damage assessment. Examples of the former can be broken down into wilderness SAR operations [3] and mountain rescue operations [4]. Examples of the latter, UAVs were used in earthquake response [1,5,6,7,8] and hurricane response [9,10]. There is a limited amount of work incorporating UAVs in response to tornadoes [11,12]. Therefore, when UAVs are being used in assisting SAR personnel in disaster assessment operations, most of the literature aims at responding to disasters that involved earthquakes or hurricanes.

How UAVs can be incorporated into the response to tornadoes can be found in the intersection of the two axes. There are many overlaps of wilderness SAR, maritime SAR operations, and earthquake/hurricane response and the response to tornadoes; post-tornado search and rescue operations provide a unique setting that is ripe to develop dynamic routing algorithms to more effectively search an area that has been impacted by a tornado.

Wilderness and maritime SAR operations often involve systematically searching an area to identify a single entity (vessel in distress, missing hikers) or responding directly to a distress call. There exist search rules that searchers will use to effectively cover an area and ensure that searchers rigorously examine an area and that the human searchers balance the time investigating any given small area versus the overall potential area a person in aid might be. In addition, knowledge of general ocean currents can aid searchers in their efforts by allowing searchers to prioritize their areas of inspection [13].

In response to large-scale disasters (such as earthquakes, hurricanes), search and rescue operations are often conducted as damage assessment operations from the sky and/or require the use of search dogs, cameras, and reports of where missing people may be [1,14]. However, there is a growing body of work proposing the use of “wireless sniffers” to help identify where victims may be by passively detecting cell phones [1,15,16,17]. Even with this innovative technology, the response (search) in the aftermath of earthquakes or hurricanes will still involve assessing an area on the size of a city, county, province, department, or region.

Tornadoes, and responding to tornadoes, provide a situation that is not adequately covered by the response literature. One of the ways of allocating search areas is by using meteorological data for creating a search area [11] (For a deeper understanding of the meteorological attributes of tornadoes, we direct the reader to search meteorological literature or to consult the National Weather Service (NWS) extensive online library on the subject). Previous work used storm-based warnings (SBWs) and local storm reports (LSRs) to identify and route post-disaster UAVs. SBWs are polygons that are drawn over an area that meteorologists expect there could be severe weather. SBWs can indicate many kinds of severe weather; however, we are only explicitly looking at the SBWs that are drawn to indicate the presence of tornadoes (not severe thunderstorms, not hail, not snowstorms). LSRs are observations to where severe weather is presently occurring. Their paper only considers LSRs observations to indicate the presence of tornadoes. The intersection in both time and space of this spatial information delineates the search area [11].

The strategic aspect of SAR operations—such as the location and allocation of SAR teams, vehicles, and equipment—can be seen in previous works [12,18]. Specifically, there is a discussion of the location of United States Coast Guard helicopters that conduct SAR operations in the Atlantic Ocean [18]. In other literature, the search area is further identified by the named road network under the assumption that anyone in need of rescue would be close to the road network of a state. That is, in areas where there are large open fields, the UAV would not search throughout a–for example–cornfield. They used the road network to create a series of waypoints that can be used to route one or several UAVs through a disaster area [12].

Where tornado response begins to differentiate from other SAR response operations is that the area impacted by a tornado (that is, where people may be need of aid) is significantly smaller than the search area in an earthquake, hurricane, or even the area defined in previous work. Only about 1–5% of the area defined by a SBW is damaged. This aligns more with the wilderness and maritime SAR operations as rescuers are trying to identify a missing person or vessel in distress and identifying this is disproportionally smaller than the area needed to be searched, that is, like a “needle-in-a-haystack”. However, wilderness and maritime SAR operations fall short because once a portion of the damaged area has been identified, the extent of the damage must also be identified.

When formulating the problem as a mathematical optimization problem, the most common formulations appear to be in the form of a traveling salesperson problem [19,20], a vehicle routing problem [21], or as a simpler shortest path problem or pathfinding problem—where returning to the start is unnecessary [22,23,24,25]. While the latter papers in the literature may on the surface appear simple, the goals put forth in the papers are often to create a coverage network in an attempt to identify victims and find paths to them [25,26], or to set up a connectivity network to a victim [24,27].

After graph-based formulations, another common model formulation is a set covering method [28,29]. It is a formulation well-suited to monitoring procedures as set covering formulations attempt to allocate the robots over a disaster scene to ensure connectivity [28] or to ensure an area is adequately searched [29]. Swarm-based methods (such as ant colony optimization or particle swarm optimization) are frequently used when multiple UAVs are used in completing their mission [28,29,30,31,32].

In addition to the mathematical optimization models proposed, several robot task allocation models and methods were used in the literature [1,33,34,35]. Robot task allocation can be implemented in a decentralized way and enable real-time reactions to new information present in the environment. The advantage of most robot task allocations (such as in [1,34,35]) is that they allow for the decentralized operation of many robots. Conversely, ref. [33] allow for robots to compete for performing the next task.

In addition to the well-established procedures outlined previously, some authors attempt simulation techniques such as Markov Decision Process [17,25,36,37].

One method of Markov Decision Processes is conducting a random forest to determine the next area for the UAV to explore to find a lost hiker [17]. However, the method they propose works well in spatially small search areas and the attraction of the WiFi sensor helps triangulate the missing person(s). There is also use a Markov Decision Process using land-based robots are navigating an interior environment (i.e., office space, school) [36]. There is also a a Markov model attempting to predict the rescuer’s needs and to deploy a UAV with wireless sensor networks and cellular networks to focus on maintaining connectivity for rescuers in a search area [37]. Markov Decision Processes can also be used to consider and map an unknown interior environment [25].

There is a large and growing body of work in using UAVs in disaster response applications, in particular with assisting SAR teams in identifying where people are in need of aid or transporting medical and first aid supplies to people in need of aid. The advent of wireless sniffer technologies allow for SAR UAVs to detect the presence of wireless devices (i.e., cell phones). With the adoption of cell phones in much of the world, the combination of these two technologies allows for the use of UAVs in responding to emergencies where people in need of aid may not have line-of-sight to the sky. When responding to emergencies and disasters, while there are some over-arching principals when developing SAR procedures, domain-specific data and knowledge can go a long way in creating searches that can be conducted faster (e.g., understanding ocean currents to identify where overboard and stranded sailors may be). In the context of searching after a tornado strikes, we can use broad understandings of tornadoes to better capture and identify the extent of the damage. A UAV equipped with wireless sniffers can also estimate the number of people that may be in need of aid at any given area, even if they are buried. To the best of our knowledge, there is very little research in utilizing meteorological and tornado data to help rescuers identify where victims may need aid [11,12]. In addition, these past works do not attempt to identify the extent of the damage as quickly as possible; they simply assume the entire area must be assessed.

This paper presents a method of attempting to identify the damaged area of a tornado quicker than trying to search the entire area. It also attempts to demonstrate that intelligently incorporating historical data into the decision-making process can assist the tools to make better decisions. The remainder of the paper is broken down into five sections. Section 2 contains the problem context and other rules and assumptions that are used in this paper. Section 3 discusses how the dynamic program will work. Section 4 details the experimentation, including a method for generating “artificial tornado instances” to provide additional cases for the paper. We test the method developed on historical cases in Section 5. We then conclude this paper in Section 6 by outlining our contribution and discussing research opportunities. Appendix A has additional results for Section 5 and Appendix B outlines the location of the publicly available data this paper is building on.

2. Problem Context

Given the existence and use of UAVs for assessing damage and identifying areas to deploy SAR teams to in the aftermath of a tornado, multiple methods can be used for routing deployed UAVs to identify damaged areas as quickly as possible. For example, the UAVs may be routed through the entire identified search area [11]. However, the actual damaged area is significantly smaller than a proposed search area.

An example of such an area can be seen in Figure 1. Here, we have a red polygon, which represents an area that may have tornado damage, with the cyan polygon representing the actual damage caused by the tornado. The objective of this paper is to identify the area denoted in cyan, in relation to the initial search area outlined in red. Note that the tornado damage area may not be totally encompassed by the SBW.

To effectively search the area, previous works assume that people in need of aid would be within some radius of a road, which has been denoted $r_{scan}$. The performance metrics outlined in [1,6,11,12] yield an $r_{scan}$ of 300 m. Using the road network as a proxy for the location of people (as in [11]), and heuristically finding the minimum number of waypoints with a radius of $r_{scan}$ that can cover the road network in a given area. An example of these waypoints can be seen in Figure 2. Given the context of Figure 2, a UAV that is scanning the area is attempting to identify the waypoints in green by searching through the collection of blue waypoints. The waypoints in green will not be known when the UAV is launched. Previously, the UAV only considers waypoints inside the SBW and will never inspect the damaged waypoints outside the SBW [11,12]. That is, “damaged waypoints” outside the SBW (for example, the waypoints west of the red box outlined in Figure 1 and Figure 2) would never be inspected in the previous literature. This paper attempts to allow the UAV to scan the entire area as well as identify damage that may occur outside of a search area.

3. Model Concepts and Dynamic Routing Setup

The following section breaks down the concepts and steps included in the dynamic routing of the UAV over the search area. The concepts are broken down into five sections. First, we propose a concept called the “base score of a waypoint”. The next section is a concept of an “Influence matrix”, which determines how much information gained from one waypoint has on another waypoint. The “influence matrix” and “base score” are combined to determine the “Computed Score of a Waypoint”, which is discussed in the third subsection. The next subsection discusses the details of how the UAV will route itself to its next waypoint(s) based on its computed score. Finally, “Evaluation of the quality of the solution” discusses the objective of the routing algorithm (find the extent of the damage as quickly as possible) and how this paper determines what subset of parameters works toward this goal.

3.1. Base Score of a Waypoint

Each waypoint receives a “Base Score” that follows a basic decision tree (the following decision tree is graphically represented in Figure 3 to aid the reader) based on the following attributes: whether the UAV has visited the waypoint or not (unvisited), whether the waypoint is initially in an SBW or not, and whether there is damage in the waypoint area. If a waypoint is not in the search area and not visited, the base score is 0.0. If a waypoint is in the search area and not visited, the base score is 0.5. If the waypoint is visited and not damaged, the waypoint base score is 0.0. If the waypoint is visited and damaged, the waypoint is given a base score of 5.0 (This value was initially set to 1.0; however, with initial testing, we quickly realized the score of 1.0 would not be sufficient). The base score is dynamic, but it only changes upon visitation with the UAV. Waypoints outside the SBW can be visited if the dynamic program decides to visit the waypoint, but will never receive the base score of 0.5: either the visitation will affirm the waypoint’s base score of 0.0 (no damage), or it will receive the damaged score of 5.0. A decision tree of this process can be seen in Figure 3.

3.2. Influence Matrix

The base score of a waypoint exerts influence on its neighbor waypoints as a function of distance. Waypoints that are spatially “close” to each other will more likely have the same attribute of being damaged or undamaged. The influence of one waypoint on another is a function of the distance between the waypoints. Let an influence matrix $\mathbb{I}$ be a $nn$ matrix that can be referenced as the influence waypoint j has on waypoint i. The value of any element ${\mathbb{I}}_{ij}$ is in the range of 0 to 1. For this paper, we used a linear relationship of influence; however, other functions (say, logarithmic or exponential) can be used. The objective is to inform the solver of the likelihood a nearby waypoint will share the same state (damaged or undamaged). We use the parameters minimum influence range (the distance from a waypoint where the influence is 1.0, typically $r_{scan}$) and maximum influence range (where waypoints beyond have an influence of 0.0). Samples of the symmetric case can be found in Figure 4.

In addition to the previous “symmetric influence matrix”, we have also developed a data driven influence matrix where the samples can be seen in Figure 5. Here, we use the historical data set of tornadoes to create an elongated matrix (along the 35–215 to 50–230 degree directions, south-west to north-east) to better reflect the typical direction a tornado might travel. The idea behind this data driven influence matrix is that since most tornadoes traverse along this half, there will be a greater chance of waypoints along this path to have identical conditions and attributes. Samples of this matrix can be found in Figure 5.

This is generated by using the frequency of the direction of tornadoes from the historical tornado database from 1950 until 2021. The radial histogram of this can be found in Figure 6. Here, the direction of a tornado is simply what is recorded as the start point and the end point, and the direction between those two points. This is the same direction used in this data driven influence matrix. It will not necessarily capture the path the tornado might take that may resemble an S or something else.

3.3. Computed Score of a Waypoint

In addition to the base score of each waypoint, each waypoint also has a computed score. The computed score is between 0.0 and 1.0 and is only computed and applied for unvisited waypoints. The computed score of a waypoint is used in the dynamic routing of the UAV. Simply, the computed score of a waypoint is the weighted average of all the waypoints weighted by the influence matrix score. Mathematically, let the computed score of waypoint i be $s_i$, the base score of waypoint j be $B_j$, and the influence of waypoint j on waypoint i be ${\mathbb{I}}_{ij}$. The computed score of waypoint $s_i$ is $s_i=\frac{{\sum }_j{\mathbb{I}}_{ij}{B}_j}{{\sum }_j{\mathbb{I}}_{ij}}$.

3.4. Routing the UAV: Parameters and Considerations

The overarching idea behind dynamically routing the UAV is for the UAV to fly directly to the waypoint with the highest computed score. If multiple waypoints have the highest computed score, the closest one is selected. In practice, waypoints along the route will have the ability to be scanned while a UAV is on route from waypoint k to the waypoint with the highest computed score (waypoint $k+1$). The decision was to include waypoints that are within a rectangle whose width is $2\times ϵ$ and length l is the length of the line between waypoint k and waypoint $k+1$. The value of $ϵ$ is the minimum of the length of $\frac{\ell }{2}$ or $2\times r_{scan}$, $ϵ=min\left[\frac{\ell }{2},2\times r_{scan}\right]$. Figure 7 illustrates the area and the waypoints that will be considered.

Figure 6. Radial histogram of the direction of tornadoes with the length indicating of tornadoes in each direction. Note: this chart does not indicate the intensity of the tornado, nor does it give any indication of the length or width the tornado took.

Figure 6. Radial histogram of the direction of tornadoes with the length indicating of tornadoes in each direction. Note: this chart does not indicate the intensity of the tornado, nor does it give any indication of the length or width the tornado took.

There is also the concept of Minimum Score to Consider (MStC). Given a computed score $s_j$, if the score is below a MStC, the waypoint is ignored, and not considered in determining the next waypoint to visit. Once all waypoints with a computed score above a MStC are visited, the UAV is considered to have completed its mission. This is an extension of the idea that once you have enough information about a waypoint’s neighbor waypoints, you can potentially safely ignore these waypoints even if they have not been visited. By default, the MStC is 0.0 (for example, waypoints outside of the initial search area have 0.0 s and will be below or equal to the MStC). MStC was selected and tuned in this paper to ensure that all damaged waypoints inside a SBW would be identified.

There is also the option to give an initial route. The initial route is a minimum Hamiltonian path through all the way points in the search area. This initial route was the standard search pattern in [11,12]. There are two options in the testing of this dynamic program on the historical and artificial test cases. Having the initial route allows for a systematic and shortest route to search an area. However, offering no initial route would allow the UAV to inspect the center of the search area and work outward. However, this may cause the UAV’s traveled route to cross itself searching for damaged areas.

Finally, given our two types of influence matrices (data driven and symmetric), we have four variations of the two influence matrices at our disposal: using symmetric the entire time; using the data driven matrix the entire time; starting with the symmetric and then switching to the data driven once damage is uncovered; and then using data driven and then switching to symmetric once damage is uncovered.

3.5. Evaluation of the Quality of the Solution

There are three attributes to assess the quality of the dynamic routing problem:

• How quickly the damaged area is identified;
• How quickly the extent of the damage is identified; and
• How quickly the UAV finishes assessing the area (confirms there is no more damage in the area).

To calculate how quickly the damaged area is identified and how quickly the UAV finishes scanning the area, we define the metric “Score of Finding Damage” and “Score of Completing route”. The former is the distance the UAV takes until the first damaged waypoint is uncovered divided by the number of waypoints initially in the SBW; the latter is the distance the UAV takes to complete its entire route divided by the number of waypoints initially in the SBW. This is to normalize the distance traveled to the number of waypoints, as there may be disparities between the initial number of waypoints initially in the SBW and may have grave effects on the length of the route. How quickly the extent of the damage is identified is defined as a “Score of Identifying Damage” and is computed by the distance the UAV took from identifying the first damaged waypoint to the last damaged waypoint divided by the minimum length that the Hamiltonian path would have taken to identify all the damaged waypoints. A score of 1.0 would be a perfect score and means that the path the program took matched the minimum Hamiltonian path; a score of 5.0 would mean the distance the program found was five times as long as the minimum Hamiltonian path.

4. Experimentation

While we have historical data for more than 300 tornadoes, we developed the ability to create a larger, artificial data set in order to test the routing algorithm that is developed. The method that we propose for creating these new scenarios is based on historical data (such as the direction, length, and width of historical tornadoes) in order to obtain realistic scenarios. These scenarios will be used as test cases with historical scenarios for the development of more advanced/better routing algorithms. Due to the limited number of historical cases available for testing, we developed a method for generating cases based on real world data for use in initial parameter tuning and testing. Due to the customizability of these generated cases, we were able to develop smaller tests sizes (that is, typically fewer waypoints). In this section, the subscript $GC$ (Generated Case) is added to variable names to differentiate them from notations elsewhere.

4.1. Generated Cases

A “Generated Case” is randomly created using a five-step approach, where Figure 8 graphically depicts this five-step process. In Step 1, some number of points $n_{points,GC}$ are randomly and uniformly generated within a bounding box (represented as blue points in Figure 8). These points are akin to the waypoints from the historical cases. In Step 2, a search area $SB{W}_{GC}$ is generated by creating a concave quadrilateral that is encapsulated between 33% and 67% of the $n_{points,GC}$ (represented as a red polygon in Figure 8). This is akin to the SBW. In the next three steps, a polygon to represent the damaged area is created. These steps of the process are using the base database of tornadoes from 1950–2021 [38]. Only tornadoes that have a start point and an end point were considered. In Step 3, a point is randomly selected within the search area (represented as a red triangle in Figure 8). Next, in Step 4, a “direction” is randomly selected from the NWS’s tornado database from 1950–2021. Finally, in Step 5, the widths and lengths of each tornado in the database were normalized to the range of the randomly generated points (the minimum axis of the bounding box). A random length and width are selected from this database. The damaged area is the rectangle created by the centerline defined by the randomly selected start point, the randomly selected length, and randomly selected direction. The sides of this rectangle are defined by offsetting the centerline half the randomly selected width, perpendicular to the centerline (represented a yellow line and polygon in Figure 8).

4.2. Testing on Generated Cases

To test our algorithm, the following procedure was used. First, an initial generated case is created as outlined in Section 4.1. Then, eighteen subcases were created based on three parameters: whether an initial route is used (Yes, No); the type of influence matrix policy used (data-driven-first, data-driven, symmetric-first, symmetric); and the minimum score to consider (0.0, 0.1, 0.2). The combination of the three tested parameters yields 24 subcases; however, when using an “initial route”, the change of use of the matrix before identifying damage is meaningless, and by removing these parameter combinations we are left with 18 subcases. Using this procedure, 1000 cases were generated.

4.3. Results on the Generated Cases

The first analysis is testing the efficacy of the method to identify the extent of the damage. Precisely, we define this metric as the distance the UAV took from identifying the first damaged waypoint to the last damaged waypoint over the length of the minimum Hamiltonian path it would take to identify all the damaged waypoints. Recall a score of 1.0 would be a perfect score and a score of 5.0 would mean the distance the program found was five times as long as the minimum Hamiltonian path.

Table 1. Assessment of quality of method.

Initial Route?	Matrix Type	MStC	Mean Score	Std Dev.
FALSE	data-driven-first	0.10	3.2596	1.8526
TRUE	symmetric	0.20	3.3282	3.1588
FALSE	data-driven-first	0.00	3.3695	2.1064
FALSE	symmetric	0.10	3.3883	2.6931
FALSE	data-driven-first	0.20	3.4128	2.5698
TRUE	symmetric	0.00	3.4198	3.5320
FALSE	symmetric	0.20	3.4329	2.3417
TRUE	symmetric	0.10	3.4422	4.1455
FALSE	symmetric	0.00	3.4642	3.1460
TRUE	data-driven	0.10	3.8732	3.1936
TRUE	data-driven	0.20	3.8860	3.0132
FALSE	data-driven	0.20	3.9305	3.7456
TRUE	data-driven	0.00	3.9545	3.2255
FALSE	symmetric-first	0.10	3.9703	3.7709
FALSE	data-driven	0.10	4.0058	3.8564
FALSE	symmetric-first	0.20	4.0516	3.8829
FALSE	data-driven	0.00	4.0698	4.3266
FALSE	symmetric-first	0.00	4.1296	4.9137

has the average and standard deviation of the 1000 cases.

Broadly speaking, the use of either the data-driven-first (symmetric second) or using the symmetric matrix for the entire program yield higher quality results than using data-driven matrices second (after the damage is uncovered). However, what is potentially more interesting is that when using the data-driven-first (symmetric second) matrices, they produce a markedly lower standard deviation than their symmetric only counterparts; three of the four lowest standard deviations are from the data-driven-first matrices. This can be viewed as the method that produces more consistent results. Given the information in Table 1, it is reasonable to draw the conclusion that the quality of this solution based on this metric is unaffected using the initial route and the use of the MStC.

Figure 8. Step-by-step process on creating a random case.

Figure 8. Step-by-step process on creating a random case.

Next, we assess the quality of the dynamic program to identify the damage and to complete its route (assert that there is no further damage to be identified). To complete this analysis, the distance of the route when the damage is first uncovered is divided/normalized by the number of waypoints in the SBW is one metric; likewise, the distance of the route when completed is divided/normalized by the number of waypoints in the SBW is the other metric. These results are shown in

Table 2. Scores of finding damage.

Initial Route?	Matrix Type	MStC	Mean Score	Score Find Damage
FALSE	data-driven-first	0.20	3.4128	7592
FALSE	data-driven	0.20	3.9305	7592
FALSE	data-driven-first	0.10	3.2596	7614
FALSE	data-driven	0.10	4.0058	7614
FALSE	data-driven-first	0.00	3.3695	7733
FALSE	data-driven	0.00	4.0698	7733
FALSE	symmetric	0.10	3.3883	8001
FALSE	symmetric-first	0.10	3.9703	8001
FALSE	symmetric	0.20	3.4329	8043
FALSE	symmetric-first	0.20	4.0516	8043
FALSE	symmetric	0.00	3.4642	8071
FALSE	symmetric-first	0.00	4.1296	8071
TRUE	symmetric	0.20	3.3282	9377
TRUE	symmetric	0.10	3.4422	9377
TRUE	symmetric	0.00	3.4198	9377
TRUE	data-driven	0.10	3.8732	9377
TRUE	data-driven	0.20	3.8860	9377
TRUE	data-driven	0.00	3.9545	9377

and

Table 3. Scores of finishing the route.

Initial Route?	Matrix Type	MStC	Mean Score	Score Finish Route
TRUE	symmetric	0.20	3.3282	36,269
TRUE	data-driven	0.20	3.8860	36,619
FALSE	data-driven	0.20	3.9305	38,403
FALSE	symmetric-first	0.20	4.0516	38,469
TRUE	symmetric	0.10	3.4422	40,480
FALSE	data-driven-first	0.20	3.4128	41,301
FALSE	symmetric	0.20	3.4329	41,349
TRUE	data-driven	0.10	3.8732	43,395
FALSE	symmetric-first	0.10	3.9703	48,069
FALSE	data-driven	0.10	4.0058	48,101
FALSE	data-driven-first	0.10	3.2596	49,230
FALSE	symmetric	0.10	3.3883	49,263
TRUE	symmetric	0.00	3.4198	50,218
FALSE	symmetric	0.00	3.4642	60,850
TRUE	data-driven	0.00	3.9545	60,895
FALSE	data-driven-first	0.00	3.3695	60,926
FALSE	symmetric-first	0.00	4.1296	64,801
FALSE	data-driven	0.00	4.0698	65,037

.

As expected, the relationship between not using an initial route and how quickly damage is identified is incredibly stark. It is additionally readily apparent that using data-driven influence matrices to identify damage is marginally better than using the symmetric to identify the damage areas. Visually inspecting the resulting route does demonstrate that the data-driven influence matrix forces the UAV to fly perpendicular to the common orientation of tornadoes.

Also as expected, allowing the UAV to terminate early allows the program to terminate once the computed scores of unvisited waypoints are sufficiently low. Implementation notes: Internal preliminary tests showed that when the MStC was 0.25 or greater, it was common for the UAV to miss damaged waypoints. In the 1000 tests executed, the UAV did not miss any waypoints up to the a MStC 0.20. As for why using an initial route, symmetric matrix (or a data-driven matrix), and a MStC of 0.10 performs similarly to using a MStC of 0.20, it is believed that the systemic search of the search area allows for many waypoints with no damage to be identified and excluded from the search in later stages.

Overall, these test cases demonstrate that our parameters operate as expected: higher MStC yields a search that is terminated earlier; not using a seeded route yields identifying damage quicker, using an initial route can help the search terminate earlier; and using a data driven search method has an effect and that effect largely helps initially identify the damage, but is detrimental after the damage is identified.

5. Testing on Historical Data

With a basic understanding of what parameters work better for the generated cases, we also run these on the collections of historical cases.

5.1. Data and Creation of the Historical Cases

The data was pulled from the historical meteorological data from March 2008 to June 2019 (inclusive) for the Weather Forecast Offices with the ID code of: OUN, TSA, AMA, SHV, LZK, LCH, LIX, JAN, MEG, HUN, BMX, MOB, FFC, TAE, JAX, CHS, PAH, OHX, MRX, LMK, JKL – which encompasses the US States of Alabama, Arkansas, Florida, Georgia, Kentucky, Louisiana, Mississippi, Oklahoma, South Carolina, Tennessee, and Texas (A map and list of WFO offices can be found at https://www.weather.gov/srh/nwsoffices, accessed on 1 February 2023). This and the location of all data used in this paper are in Appendix B in

Table A3. Location of data used in this paper.

What?	Where?	When?	Notes
Weather SBW Data	https://mesonet.agron.iastate.edu/	1 June 2022	For the WFOs: OUN, TSA, AMA, SHV, LZK, LCH, LIX, JAN, MEG, HUN, BMX, MOB, FFC, TAE, JAX, CHS, PAH, OHX, MRX, LMK, JKL
Road data for South Carolina	http://info2.scdot.org/GISMapping/Pages/GIS.aspx	2 May 2022	Statewide Highways; Statewide Other Roads
Road data for Texas	https://gis-txdot.opendata.arcgis.com/datasets/d4f7206d27af4358acb70cb1cc819d10_0/explore?location=31.008846%2C-100.055172%2C6.28	7 June 2022
Road data for Oklahoma	https://okmaps.org/OGI/search.aspx	19 June 2022	ODOT Roadways; ODOT Highways; ODOT Local Roadways
Road data for Kentucky	https://transportation.ky.gov/Planning/Pages/Centerlines.aspx	29 May 2022	Centerline Network >All Roads
Road data for Arkansas	https://gis.arkansas.gov/product/arkansas-road-inventory/	1 June 2023	Updated 2020-10-30
Road data for Tennessee	https://tn-tnmap.opendata.arcgis.com/datasets/37229399437446b9acd653f353f7decc_0/explore?location=35.785027%2C-85.962491%2C7.72	3 June 2022
Road data for Alabama	https://data-algeohub.opendata.arcgis.com/search?groupIds=b54e33ef0a114bacb2fa059fc0bf1340	19 June 2022	Need to download each county separately
Road data for Mississippi	https://www.maris.state.ms.us/HTML/DATA/data_Transportation/MDOTRoadCenterlines.html#gsc.tab=0	23 February 2022
Road data for Georgia	https://www.sciencebase.gov/catalog/item/5a5f36bee4b06e28e9bfc1ba	15 June 2022	TRAN_Georgia_State_Shape > Shape/Trans_RoadSegment_0.shp; and TRAN_Georgia_State_Shape > Shape/Trans_RoadSegment_1.shp
Road data for Florida	https://www.sciencebase.gov/catalog/item/5a86ea14e4b00f54eb3a1b55	15 June 2022	TRAN_Florida_State_Shape > Shape/Trans_RoadSegment_0.shp and TRAN_Florida_State_Shape > Shape/Trans_RoadSegment_1.shp; and TRAN_Florida_State_Shape > Shape/Trans_RoadSegment_2.shp
Road data for Louisiana	https://www.sciencebase.gov/catalog/item/5a5f36c4e4b06e28e9bfc1ca	15 June 2022	Trans_RoadSegment

. There were 182 days with tornadoes in this region. Of these 182 days, several had multiple tornadoes in multiple areas. If we separate these instances where multiple tornadoes occurred on the same day, we find there are 415 unique cases.

We applied the procedure explained before. The first analysis is testing the efficacy of the method to identify the extent of the damage, again the distance the UAV took from identifying the first damaged waypoint to the last damaged waypoint divided by the minimum Hamiltonian path to identify all the damaged waypoints. The table summarizing these results can be found in

Table 4. Assessment of quality of method, historical cases.

Initial Route?	Matrix Type	MStC	Mean Score	Std Dev.
FALSE	data-driven-first	0.20	6.3817	4.6151
FALSE	symmetric	0.20	6.5051	4.3033
FALSE	data-driven-first	0.10	6.7603	5.0457
FALSE	symmetric	0.10	6.7777	4.6675
FALSE	symmetric	0.00	7.1567	5.3666
FALSE	data-driven-first	0.00	7.1678	5.3796
TRUE	symmetric	0.20	7.4841	14.1935
TRUE	symmetric	0.10	8.0410	16.4381
TRUE	symmetric	0.00	9.2208	18.1696
TRUE	data-driven	0.20	10.0360	13.7550
FALSE	data-driven	0.20	11.1705	12.5204
FALSE	symmetric-first	0.20	11.4753	13.2841
TRUE	data-driven	0.10	11.6901	18.0052
FALSE	data-driven	0.10	12.0320	13.8424
FALSE	symmetric-first	0.10	12.1197	14.4577
FALSE	symmetric-first	0.00	12.8923	15.4161
FALSE	data-driven	0.00	12.9564	14.8083
TRUE	data-driven	0.00	15.3768	33.8396

.

It is immediately apparent that: (1) data-driven-first and symmetric influence matrices continue to be better than using data driven; (2) the lack of an initial route is much more positively impactful in the historical cases than in the artificial cases; and (3) there is very little difference in the scores of several pairs of cases.

Next, we assess the quality of the dynamic program to identify the damage in historical cases and to complete its route (assert that there is no further damage to be identified). These values are computed likewise to the generated cases. To complete this analysis, the distance of the route when the damage is first uncovered is divided/normalized by the number of waypoints in the SBW (metric 1); likewise, the distance of the route when completed is divided/normalized by the number of waypoints in the SBW (metric 2). These results are shown in

Table 5. Scores of finding damage, historical cases.

Initial Route?	Matrix Type	MStC	Mean Score	Score Find Damage
FALSE	data-driven-first	0.20	6.3817	615
FALSE	data-driven	0.20	11.1705	615
FALSE	symmetric	0.20	6.5051	641
FALSE	symmetric-first	0.20	11.4753	641
FALSE	data-driven-first	0.10	6.7603	666
FALSE	data-driven	0.10	12.0320	666
FALSE	symmetric	0.10	6.7777	684
FALSE	symmetric-first	0.10	12.1197	684
FALSE	symmetric	0.00	7.1567	702
FALSE	symmetric-first	0.00	12.8923	702
FALSE	data-driven-first	0.00	7.1678	709
FALSE	data-driven	0.00	12.9564	709
TRUE	symmetric	0.20	7.4841	814
TRUE	symmetric	0.10	8.0410	814
TRUE	symmetric	0.00	9.2208	814
TRUE	data-driven	0.20	10.0360	814
TRUE	data-driven	0.10	11.6901	814
TRUE	data-driven	0.00	15.3768	814

and

Table 6. Scores of finishing the route, historical cases.

Initial Route?	Matrix Type	MStC	Mean Score	Score Finish Route
TRUE	symmetric	0.20	7.4841	3456
FASLE	data-driven-first	0.20	6.3817	3631
FASLE	symmetric	0.20	6.5051	3658
TRUE	data-driven	0.20	10.0360	3984
TRUE	symmetric	0.10	8.0410	4083
FASLE	data-driven	0.20	11.1705	4206
FASLE	symmetric-first	0.20	11.4753	4261
FASLE	data-driven-first	0.10	6.7603	4481
FASLE	symmetric	0.10	6.7777	4517
TRUE	data-driven	0.10	11.6901	4816
FASLE	data-driven	0.10	12.0320	5304
FASLE	symmetric-first	0.10	12.1197	5347
FASLE	data-driven-first	0.00	7.1678	6890
FASLE	symmetric	0.00	7.1567	6892
TRUE	symmetric	0.00	9.2208	7255
TRUE	data-driven	0.00	15.3768	8172
FASLE	symmetric-first	0.00	12.8923	8194
FASLE	data-driven	0.00	12.9564	8203

.

Reflecting the generated cases, the relationship between not using an initial route and how quickly damage is identified is similar between the generated cases and the historical cases (Table 5). It is also apparent, however, that the MStC is a stronger indicator of a lower score to find damage than the matrix type. That is, using a MStC 0.20 along with not using an initial route produces results that produce a route that identifies the extent of the damage quicker than using similar parameters, but a lower MStC (0.10 and 0.00).

Also reflecting the results from the generated cases, allowing the UAV to terminate early allows the program to terminate once the computed scores of unvisited waypoints are sufficiently low (Table 6). Once again, using a symmetric matrix and a MStC of 0.10 performs similarly to using a MStC of 0.20.

Overall, these test cases demonstrate that our parameters operate as expected: higher MStC yields a search that is terminated earlier; not using a seeded route yields identifying damage quicker; and using a data driven search method has an effect and that effect largely helps to initially identify the damage but may be detrimental after the damage is identified.

As indicated previously, there are some instances where multiple tornado tracks do appear. We have separated these and denoted them as simple (one track) and complex (multiple tracks), while the explicit numerical values do change between simple and complex cases and the performance of “complex” cases are worse than “simple” cases, the substantive takeaways remain. A separation of these data is shown in Appendix A

Table A1. Results table, historical cases, and simple cases.

Initial Route?	Matrix Type	MStC	Mean Score	Std Dev.	Score, Find Damage	Score, Finish Route
FALSE	data-driven-first	0.20	4.8922	4.2596	694	3624
FALSE	symmetric	0.20	5.0110	3.7612	735	3664
FALSE	data-driven-first	0.10	5.0967	4.5166	770	4542
FALSE	symmetric	0.10	5.1201	3.8677	798	4592
FALSE	symmetric	0.00	5.2522	4.5352	826	7089
FALSE	data-driven-first	0.00	5.3132	4.6398	832	7083
TRUE	symmetric	0.20	6.4050	17.0184	962	3481
TRUE	symmetric	0.10	6.5172	19.5489	962	4116
TRUE	symmetric	0.00	6.7681	20.7267	962	7608
TRUE	data-driven	0.20	9.5569	16.3940	962	4061
FALSE	data-driven	0.20	10.8395	14.7529	694	4269
TRUE	data-driven	0.10	10.9968	21.4810	962	4923
FALSE	symmetric-first	0.20	11.3058	15.7532	735	4349
FALSE	data-driven	0.10	11.4801	16.3374	770	5378
FALSE	symmetric-first	0.10	11.6730	17.1360	798	5445
FALSE	symmetric-first	0.00	12.1823	18.2321	826	8476
FALSE	data-driven	0.00	12.2794	17.4458	832	8478
TRUE	data-driven	0.00	14.2036	40.4971	962	8643

and

Table A2. Results table, historical cases and complex Cases.

Initial Route?	Matrix Type	MStC	Mean Score	Std Dev.	Score, Find Damage	Score, Finish Route
FALSE	data-driven-first	0.20	9.3606	3.7923	457	3647
FALSE	symmetric	0.20	9.4933	3.7334	453	3645
TRUE	symmetric	0.20	9.6422	4.3476	519	3406
FALSE	data-driven-first	0.10	10.0876	4.3673	458	4360
FALSE	symmetric	0.10	10.0928	4.3638	455	4367
FALSE	data-driven-first	0.00	10.8769	4.8211	462	6504
FALSE	symmetric	0.00	10.9658	4.8593	455	6500
TRUE	data-driven	0.20	10.9943	5.4299	519	3830
TRUE	symmetric	0.10	11.0887	5.7820	519	4018
FALSE	symmetric-first	0.20	11.8142	5.8025	453	4086
FALSE	data-driven	0.20	11.8323	5.9181	457	4079
FALSE	symmetric-first	0.10	13.0132	6.2842	455	5150
TRUE	data-driven	0.10	13.0765	6.9395	519	4601
FALSE	data-driven	0.10	13.1357	6.3262	458	5158
TRUE	symmetric	0.00	14.1262	9.8253	519	6550
FALSE	data-driven	0.00	14.3103	6.8814	462	7655
FALSE	symmetric-first	0.00	14.3124	6.7930	455	7632
TRUE	data-driven	0.00	17.7232	12.3189	519	7229

as reference.

5.2. Comparison of Results

To easily compare both the historical cases and the generated cases,

Table 7. Summary and comparison of historical and generated cases.

Goal	In Generated Cases	In Historical Cases
Minimize the distance/time it takes to uncover extent of tornado	Use data-driven-first or symmetric influence matrix	Use data-driven-first or symmetric influence matrix
Reduce the standard deviation of distance/time it takes to uncover extent of tornado	Use data-driven-first matrix and not using an initial route	Do not use an initial route and use a data-driven-first or symmetric influence matrix
Minimize the distance/time it takes to initially identify tornado damage	Use data-driven-first or data-driven matrix Do not use an initial route and all else being equal a higher MStC helps	Do not use an initial route Use a higher MStC
Minimize the distance/time it takes to complete the mission	Use a higher MStC Using an initial route	Use a higher MStC

indicates which parameters the end user should use to achieve a specific goal. In Table 7, we have used boldface type to indicate matching parameters. The parameters that match both historical and generated cases are: to minimize the distance/time it takes to uncover the extent of a tornado, use data-driven-first or symmetric influence matrix; to reduce the standard deviation of distance/time it takes to uncover the extent of a tornado, use a data-driven-first influence matrix; to minimize the distance/time it takes to initially identify a tornado, do not use an initial route; and to minimize the distance/time it takes to complete the mission, use a higher MStC.

For reducing “the standard deviation of distance/time it takes to uncover extent of a tornado”, the effect of data-driven-first versus the symmetric influence is less pronounced on historical cases than it is on the artificially generated cases.

6. Conclusions

This paper presents both a (1) method of attempting to identify the extent of the damaged area in the aftermath of a tornado as quickly as possible and (2) a method for creating artificial cases that can be used to increase the number of cases available for testing. We have demonstrated that intelligently incorporating historical data into the decision-making process can assist the dynamic routing method to route and reroute a damage assessment UAV to determine the extent of damage as quickly as possible. In addition, we have developed a method for creating artificial instances that react similarly for key goals (that is, identifying the extent of tornado damage). The difficulty we encountered was that we successfully developed the algorithm to use only one UAV in identifying damage (rather than multiple UAVs in the previous literature).

These artificial instances perform similarly in some important metrics to the historical database of tornado instances that we produced; however, there is a gap that needs to be addressed. From the outset, we aimed to create a method to “Minimize the distance/time it takes to uncover extent of tornado” and the generated cases perform similarly. Recall this was our primary goal. However, the other goals outlined in this paper have slight differences between parameters in the historical cases data set versus the generated cases data set. For instance, using a data-driven influence matrix first helps identify damage in the generated cases, but this has less of an impact on the actual historical data set. This is possibly because the number of waypoints is larger than the generated cases. The nature of the data driven matrix strongly encourages the UAV to travel perpendicular to the typical direction of tornadoes before damage is beginning to be identified. That is, before damage is identified, the influence matrix encourages the UAV to fly in a northwest-to-southeast direction. This makes intuitive sense as, if you are trying to initially identify something that will typically be in a northeast-to-southwest orientation, you would systematically search in a northwest-to-southeast direction. The additional waypoints and size of the search area curtails this effect.

Second, we also show that the use of historical tornado trends has an impact on the response method outlined in this article. The method is interesting as the historical data typically has a positive impact on the discovery of damaged areas and a reduction in the standard deviation of uncovering damaged areas. That is, once the damage has begun to be uncovered, the information gained from the route prior to identifying damage can help (typically) reduce the extremes in time/distance it takes identifying the extent of the damage. However, using the data driven matrix after damage is identified performs worse regardless of any other parameters used.

Tornadoes are broadly considered to be a random and unpredictable phenomenon that are hard to predict and simulate. This paper demonstrates that, even given the unpredictable nature of tornadoes, the intelligent and directed use of historical tornado damage can help rescuers identify the area impacted by a tornado in a much more efficient manner.

Some main limitations and avenues for future research to still be explored include further sensitivity on the setup of the influence matrix (as a larger range of influence may be desired for spatially larger cases). The method outlined here is also ripe for introducing more real-time data into the method. For example: the press, storm chasers, or emergency calls reporting impacted areas can convert a waypoint with unknown attributes into a known waypoint, which can be updated immediately in the dynamic routing algorithm. We use one UAV to assess an area; practically, multiple UAVs can reduce the time it takes to search the entire area, and as indicated in the previous literature, when flying multiple UAVs over a disaster area the UAV with the greatest time aloft is what we attempt to minimize [11]. However it remains unknown how multiple UAVs would effectively assess the extent of a damaged area within the context outlined in this paper. In addition, it remains an open question if using/flying multiple UAVs over a disaster area would be better served by multiple UAVs assessing the same area or multiple UAVs assessing their own areas. The influence matrix only considers direction and frequency; the influence matrix lacks any context on tornado width and length. While the direction histogram remains constant through most of the contiguous United States, length, width, and severity vary with the tornado location so sensitivity of data used based on location can be performed. The minimum score to consider has the potential to be adaptive. Presently, there is also a lack of adequate research on whether these wireless sniffers can be used in practice. Assessing whether a waypoint is “damaged” is still a manual process, and aerial assessment may result in inaccurate damage reporting for some structures.