Recent wildfires in the United States have caused many lives and billions of dollars, destroying countless structures and forests. Fighting wildfires is extremely complex. It is difficult to observe the true state of fires due to smoke and risk associated with ground surveillance. There are limited resources to be deployed over a massive area and the spread of the fire is challenging to predict. This paper proposes a decisiontheoretic approach to combat wildfires. We model the resource allocation problem as a partially observable Markov decision process. We also present a data-driven model that lets us simulate how fires spread as a function of relevant covariates. A major problem in using data-driven models to combat wildfires is the lack of comprehensive data sources that relate fires with relevant covariates. We present an algorithmic approach based on large-scale raster and vector analysis that can be used to create such a dataset. Our data with over 2 million data points is the first open-source dataset that combines existing fire databases with covariates extracted from satellite imagery. Through experiments using real-world wildfire data, we demonstrate that our forecasting model can accurately model the spread of wildfires. Finally, we use simulations to demonstrate that our response strategy can significantly reduce response times compared to baseline methods.
In 2018, a large wildfire (named Camp Fire) in California
resulted in the loss of 88 lives, displaced countless more, and
destroyed more than 18,500 structures. The estimated cost
of the destruction was a staggering $15 billion. As we write
this manuscript at the start of the wildfire season in the state,
more than a million acres have already burned in California
this year alone due to more than 7,000 wildfires. Wildfires
have destroyed many towns and structures across the state.
At one point in August 2020, the entire northern half of the
state had been instructed to prepare for evacuation
Fighting wildfires is difficult. Rapid urbanization and the
effects of climate change make urban and suburban areas
particularly susceptible to wildfires. Known to be
notoriously unpredictable, sudden changes in wind directions or
weather can change the way fires spread
The problem of combating wildfires is an example of dynamic resource allocation. Such an approach to combat natural calamities like wildfires, floods, and earthquakes are difficult for several reasons. The dynamics of the events are unknown and complicated to model in closed-form. There are multiple covariates that affect the spread of fire like the vegetation, fuel, altitude, and wind, and the exact relationship between each covariate and fire spread is uncertain. Resource allocation is extremely challenging because of the difficulty of making predictions about the spread of fire and expected damage. Designing principled approaches to deploy resources is important to mitigate the effects of wildfires and emergencies in general (Mukhopadhyay et al. 2020).
Events like fires affect large areas, and it is difficult to correlate large-scale data from various sources to analyze and study fires. To the best of our knowledge, there exists no comprehensive data source that combines fire occurrence with geospatial features, fuel levels, and weather to allow the research community to develop approaches to combat wildfires. Finally, the problem of deploying resources to manage wildfires is full of uncertainties. As fires spread, it becomes increasingly difficult to observe the true state on the ground due to the presence of smoke. As a result, first responders only have imperfect information to allocate their resources.
Contributions: We make the following contributions in
this paper. 1) We present a decision-theoretic approach to
dynamically allocate resources in uncertain environments to
intervene against wildfires. Specifically, we model the
response problem as a partially observable Markov decision
process (POMDP) and present an approach to find
optimal actions for suppression for a given state of the
problem. Our approach accommodates the constraint that the
true state of the fire is difficult to observe in practice. 2)
Instead of focusing on physics-based models, we present a
data-driven approach that can simulate the spread of
wildfires. We extract relevant covariates such as fuel levels,
vegetation type, height of canopy, and elevation from satellite
imagery to drive the simulation. 3) The calculation of
accurate zonal statistics is a bottleneck for large scale
geospatial data analysis
The dynamics of fire spread are usually modeled
using physics-based models. Popular fire spread models
include BehavePlus
Response to wildfires traditionally uses simulation-based
approaches to select locations of intervention that maximize
the expected utility of suppression efforts.
We consider a spatial area divided into a set of spatial cells G. Let gi 2 G denote the ith cell. We represent the neighbors of a cell gi by Ni, for some definition of neighborhood (for example, neighbors of a cell can be the set of its adjacent cells). Consider that the total time in consideration is divided into T time steps. We assume access to historical data of fire incidents D, which is a vector of tuples f(t1; `1; u1; w1); (t2; `2; u2; w2); : : : ; (tn; `n; un; wn)g, where each incident di 2 D is identified by its time of occurrence ti, location `i (mapping to a cell in G), intensity of fire observed ui 2 R+, and a vector of spatio-temporal features wi 2 Rm. The features w capture potential determinants of fire such as weather and the type of vegetation in a cell.
Observing the true state of the world is almost always
impossible when wildfires occur. Gathering real-time
information by visiting the affected areas by land is
naturally difficult. Therefore, information must be gathered
through air surveillance obstructed by smoke. Consequently,
the true dynamics of wildfires are only partially
observable. We model the fire suppression problem more
realistically as a partially observable Markov decision
process (POMDP). A POMDP can be defined by the tuple
fS; A; O; Z; T; R; g
t g denote the status of the fire and fuel level in each of the cells in G, respectively. We consider the status of the fire X as a binary variable such that xit = 1 if uit 0 where uit 2 R+ denotes the measured intensity of the fire in cell gi 2 G at time step t. We consider that the fuel level F is a discrete variable, such that F 2 f0; 1; : : : ; mg. The exogenous parameters and m can be estimated from data or through domain knowledge. 2. Actions: A is a finite set of actions. The actions denote the different permutations of cell indices that fire suppression efforts can be applied to, up to a maximum number of cells specified as a resource constraint. 3. State Transitions: T defines conditional transition probabilities, with T (s0 j s; a) denoting the transition probability from state s to s0 when action a is taken. The transition model T includes the following three components: (a) Burning: If cell gi 2 G is burning at time step t, we assume that the fuel level decreases by one unit in the next time step. Therefore, Fti+1 = Fti 1 if xit . (b) Action effectiveness: At any time step t, if an action, i.e. fire suppression effort(s) is applied to a cell gi 2 G such that xit , there is probability q that the effort successfully puts out the fire. (c) Fire dynamics: We use a generative model to simulate the spread of fire. We represent spread dynamics by the probability distribution f (Xti+1 j xtj ; w), where gi 2 Nj . Therefore, given that a specific cell gj 2 G is on fire at time step t, f denotes the likelihood of its neighboring cells being on fire at the subsequent time step t + 1.
We assume that in each time step, fire from a cell can
spread only to its neighboring cells. This assumption aids
computational tractability, but is without loss of
generality because the decision-maker can discretize time fine
enough such that the assumption is realistic.
4. Reward function: R : S A ! R is the reward
function, such that R(st; a) = Pgi2G xitU (gi), where U (gi)
denotes the utility for a cell gi 2 G to be on fire.
Naturally, U varies across the cells. A cell with human
occupants is presumably more valuable and more costly to
burn than a cell composed of forested land. Cells can also
carry unequal ecological utilities
2 [0; 1] denotes the discount factor.
In a POMDP, the decision-maker cannot directly observe the state. Instead, they only have access to beliefs that are generated probabilistically based on the actions taken. Information about states can be inferred from the history (h) of observations and actions. It is common to maintain a distribution over states given the history; this distribution is known as the belief B, such that B(s j h) denotes the probability of being in state s given history h. The goal for the decision-maker is to find a mapping from belief states to actions that maximizes the expected future discounted reward.
In order to accurately simulate the spread of fire, we model the fire dynamics f using a data-driven model. Recall that f is a probability distribution over a cell being on fire in time step t + 1, conditional on its neighbors being on fire at the previous time step t. The goal of modeling the function f is to understand the effect of various covariates like wind, vegetation type, canopy height, altitude, etc. on fire spread. Typically, covariates in geospatial analysis are heterogeneous.
We use random forests
The general dynamic decision framework following the POMDP formulation is shown in Figure 2. Recall that the sources of uncertainty are the current state of the fire (S) and the dynamics of the spread (driven by the set of covariates w). At each time step, the available set of actions (A) is a combination of the fire location(s) to suppress. The decision-maker acts based on a belief distribution of the true state of the world and receives an observation. Utility (U) reflects a measure of the expected damage of having a fire in a specific cell (e.g. residence versus wildland).
Due to the large state space and action space (the
action space is combinatorial), we use the sampling-based
online Monte Carlo tree search (MCTS)
Although POMCPOW is shown to outperform other
algorithms
f1; : : : ; j b jg do random state in b G(si; a)
O(o j s0i; a) ; 1 b0 2 for i 3 si 4 s0i 5 wi 6 end 8 9 end 10 for i 11 7 if Pjib=j1 wi = 0 then wi = len1(w) ; wk
Add s0k to b0
12
13 end
14 return normalized b0
// reweight states
f1; : : : ; j b jg do
Randomly select k with probability proportional to
Data needed to model the spread of wildfires comes from
varied sources. The temporal and spatial resolutions of such
data sources are typically different. The data sources can
also be of different forms (vector or raster). The vector
model uses points and line segments to identify spatial
locations while the raster model uses a set of cells for the
same purpose. Combining large-scale vector and raster data
is known to be a difficult problem
We collected fire occurrence data in vector form from the
Visible Infrared Imaging Radiometer Suite (VIIRS) thermal
anomalies/active fire database
Canopy Base Height Canopy Cover Canopy Height Existing Vegetation Cover Existing Vegetation Height Existing Vegetation Type Elevation Slope Year(s) 2012, 2014, 2016 2012, 2014, 2016 2012, 2014, 2016 2012, 2014, 2016 2012, 2014, 2016 2012, 2014, 2016 2012, 2014, 2016 2016 2016
To reconcile the different spatial resolutions, we divide the state of California into a grid G of 375 375 meter cells. The center of each fire pixel from the vector data can therefore overlap with exactly one cell in G. To compute the feature vector associated with each data point, we compute zonal statistics for the vector data using the raster data. The method of zonal statistics refers to calculating summary statistics using a raster dataset within zones defined by another dataset (typically in vector form).
Traditional systems to compute zonal statistics require the data to be converted into the same format, either raster or vector. Automated tools can then be used to either vectorize the raster dataset or rasterize the vector dataset. The first approach converts each pixel in the raster to a point and then tests the point against each polygon in the vector data to find a match. This approach has a computational complexity of O(np log np c r), where np is the number of polygons in the vector data, and c and r are the number of columns and rows in the raster data respectively. The second approach Vector Data Raster Data
Input
Intersections Computation
Intersections Files
Distribute Zonal Statistics Computation rasterizes the vector data by converting each polygon to a raster (mask) layer with the same resolution as the input raster layer. It then combines the two raster layers to compute the desired aggregate function. Most systems that use this approach keep the mask layer in memory. If the input raster layer has a very high resolution, the size of the mask layer can become too large to be kept in memory. This approach has a computational complexity of O(np c r).
Neither of the two approaches mentioned above scale for
the high resolution raster and vector data due to the
requirement of converting between vector and raster formats.
Specifically, in our problem, the vector data consist of over 3
million polygons and each of the raster data sources consists
of over 1 billion entries. To deal with the large-scale
geospatial data, we create a fully decentralized approach to
compute large-scale zonal statistics based on
We used fire data from California, USA spanning 2012– 2018 for the prediction modeling. We divided the state into a set of 375 375 meter cells. Our goal was to capture how fire spreads given an initial occurrence of fire. As a result, we only considered cells and days that exhibited the possibility of fire spreading from an existing fire. Specifically, each cell in our data has a fire in its neighborhood. Our data has a total of 2,367,209 data points. Each row in our data represents a cell gi at a specific time t, a set of spatial-temporal features wit, and the status of fire uit as well as the spatial-temporal features wjt+1 and the status of fire ut+1 of gj 2 Ni, a j neighboring cell of gi at time step t + 1. To calculate the features for a specific cell gi 2 G at a specific time step, we calculated summary statistics (maximum, minimum, median, sum, mode, count, and mean of the feature values) using all raster cells within gi at time step t. To the best of our knowledge, our data is the first comprehensive open-source dataset that combines fire occurrence with relevant covariates extracted from satellite imagery. The data is available at https://wildfire-modeling.github.io. We used data from 2012 to 2017 as our training set and data from 2018 as our test set. We set the time step for our experiments to a day, based on the minimum time fidelity of the VIIRS dataset. All experiments were run on an Intel Xeon 2.2 GHz processor with 125 GB of memory.
We label a forecast as a true positive prediction when both the predicted fire intensity and the recorded fire intensity are greater than the pre-specified threshold . We observe that the random forest regression model is insensitive to the number of trees used (5, 50, 100, and 500). We also observed similar accuracy across training and test sets. We tested several realizations of to examine the robustness of our forecasting approach on different sizes of fire. Our results show that while it is relatively difficult to predict spread from extremely small fires ( = 0:5), our forecasting model achieves high accuracy (> 90%) in predicting spreads from relatively larger fires. We summarize the results in Table 2.
Our goal is to create a pipeline for modeling response to
wildfires by utilizing the data-driven model of fire spread
to optimize response decisions. However, in this paper,
we present experimental results based on a simple spread
model. Specifically, we simulate the spread of fire using
fixed environmental conditions (for example, we use a fixed
y
ti
itl 5,500
U
e
v
ti
eag 5,000
N
4,500
q=1
1,400
8,000
y
itlit
evU 7,000
it
a
g
e
N
6,000
q=1
wind direction and rate of spread in each simulation). We
calculate the probability of fire spread following a
simplified version of the deterministic fire dynamics model in prior
work
We conducted experiments on different sized square grids
(42; 62; 82; 102; 122 and 162). We varied the starting states
by random initialization of fire maps and cell types. We
experimented with 6 different initial states. For each
initial state, we created 256 spread scenarios by varying wind
and rate of spread. For each initialization, a fixed
percentage (10%) of cells was considered to be on fire. The
proportions of red, yellow, and green cells were set to be 20%,
30%, and 50% respectively, consistent with the distribution
of land use in California
Figure 4 shows the mean negative utility averaged across start states and spread scenarios. We also vary the action effectiveness q since in practice, suppression efforts do not always completely puts out wildfires. We see that our approach (referred to as “Uncertainty Aware Fire Response” or UAFR) consistently outperforms the baseline method in all scenarios with more significant improvements in larger grids and increased action effectiveness.
Discussion combat due to difficulties in surveillance and scarcity of resources. In this paper, we built a data-driven forecasting model by extracting relevant determinants of fire spread through satellite imagery. Then, we developed an approach to wildfire suppression that explicitly takes state uncertainty into account. To the best of our knowledge, we were the first to create a comprehensive dataset on wildfires that combines historical fire data with relevant covariates. Our dataset, with over two million data points, and our codebase are opensource for the research community to use.
There are some limitations to our current work. While our forecasting model shows high accuracy, we observe that the random forest regression model is insensitive to the number of decision trees in the ensemble. As a result, simpler methods like classification and regression trees (CART) (Breiman et al. 1984) might result in better generalization to unseen data. Second, our approach to suppression needs to be integrated with the data-driven fire spread model. Finally, while we simulated wind for our experiments, our open-source dataset does not contain information about wind. We are currently incorporating hourly wind data from the National Oceanic and Atmospheric Administration (NOAA)1 with our fire data to develop a more comprehensive dataset.
We would like to acknowledge the Department of Management Science & Engineering at Stanford University, USDA NIFA AFRI (Grant 2019-67022-29696), and the Center of Automotive Research at Stanford (CARS) for funding this research.
Wildfires have caused massive damage in the last decade. They are particularly challenging for first responders to 1https://www.climate.gov/maps-data/dataset/wind-rosescharts-and-tabular-data