=Paper=
{{Paper
|id=Vol-2146/short59
|storemode=property
|title=Locating fuel breaks to minimise the risk of impact of wild fire
|pdfUrl=https://ceur-ws.org/Vol-2146/short59.pdf
|volume=Vol-2146
|authors=Adan Rodríguez,Begoña Vitoriano,Marc Demange,Ignacio Leguey
|dblpUrl=https://dblp.org/rec/conf/rsff/RodriguezVDL18
}}
==Locating fuel breaks to minimise the risk of impact of wild fire==
https://ceur-ws.org/Vol-2146/short59.pdf
Locating fuel breaks to minimise the risk of
impact of wild fire
Adán Rodrı́gueza Begoña Vitorianoa Ignacio Legueyb
Marc Damagec
a b
Complutense University of Madrid (UCM) Polytechnic University of Madrid (UPM)
c
Real Melbourne Institute of Technology (RMIT)
Extended abstract
Abstract
In order to respond the question “Where to locate fuel
breaks?”, a peculiar location model is presented involving
stochastic mixed integer nonlinear optimization, Bayesian
networks and directional statistic inference. From a first sim-
ple approximation to the large model, will be shown what
motivates follow models and its complexity incorporated.
Also, a case study with real data about Corsica region is
presented.
Keywords— stochastic programming, mixed integer programming, nonlinear programming,
Bayesian inference
1 Introduction
The problem consists in provide a tool to decide where to locate a FSZ (fight support zone) in
order to minimize the global risk of fire.
Discrete Location deals with the problem of deciding which site have to be used, from a finite
set of possibilities, in order to optimize an objective. These site are usually plants or facilities.
The Euclidean distance doesn’t use to be appropriate in some context, thence a network is used
for model distances ([Garvey et al., 2015]).
Insomuch as a FSZ consist on reduce the fire spread between two areas, FSZ problem can be
seen as what arcs modify to minimize the global fire risk. We will see that the problem divides
in two parts: measure the fire risk based on the probability of burn, and optimize what changes
in the network minimize the risk of burn.
c by the paper’s authors. Copying permitted for private and academic purposes.
Copyright ©
In: G. Di Stefano, A. Navarra Editors: Proceedings of the RSFF’18 Workshop, L’Aquila, Italy, 19-20-July-2018,
published at http://ceur-ws.org
2 Methodology
2.1 First approach
The main idea is to split the region we want to consider in homogeneous areas, and define the
connectivity between those areas with the probability of the fire to pass from one to other. With
this idea in mind, the first problem is how to compute the probability of fire in a node known
ignition probabilities and spread probabilities.
Given a network (N, A) with
N = {n1 , . . . , nm }
A⊂N ×N
being N the set of all nodes representing homogeneous areas of the land and A the set of
directed edges connecting N . Also we denote as aij = (ni , nj ). The simplest way to compute
the probability of fire in node ni (fi ) is assuming independence on those events, this is:
1 − f1 = (1 − ig1 ) (1 − f2 · a21 ) ... (1 − fm−1 · am−1,1 ) (1 − fm · am1 )
1 − f2 = (1 − f1 · a12 ) (1 − ig2 ) ... (1 − fm−1 · am−1,2 ) (1 − fm · am2 )
.. .. .. .. .. ..
. . . . . .
1 − fm−1 = (1 − f1 · a1m−1 ) (1 − f2 · a2m−1 ) ... (1 − igm−1 ) (1 − fm · amm−1 )
1 − fm = (1 − f1 · a1m ) (1 − f2 · a2m ) ... (1 − fm−1 · am−1m ) (1 − igm )
Being fi the probability of fire in node ni , aij the probability of spread between node ni and
node nj and igi the probability of ignition in node ni .
Note 1. In order to facilitate the reading, we will use an abuse of notation. For example
aij is defined as an arch of network (N, A), but in the previous system is used as a number
(probability). Also we will see aij as an event (fire spread). In general, events and them
probabilities are represented with same symbols, the context will give as the meaning in every
case.
With this formulation we can solve the problem to compute the probability of fire in a node
with a nonlinear model (NLP). Adding binary variables, the model is transformed into a decision
model.
m
min z = f i · vi
i=1
s.a
m
1 − fi = (1 − igi ) · (1 − fj · aij · xij ) for i = 1, . . . , m
j=1 (1)
j∕=i
m
xij · cij ≤ B
i,j=1
i∕=j
fi ∈ [0, 1], xij ∈ {0, 1}
(1) minimize expected loss cost, being vi an estimation of the losses if ni burns. Also, xij
represents the decision of build a FSZ in arch aij and cij costs of locate a FSZ there. Locations
of xij must be bounded by a budget B.
In the case of a graph with cycles this approximation can be far from reality. Let us see an
explanatory example.
Example 1. Consider the simple graph
G = (N = {n1 , n2 },
A = {a12 = (n1 , n2 ), a21 = (n2 , n1 )})
a12
n1 n2
a21
Now suppose a12 = a21 = 0.8, ig1 = 0.1 and ig2 = 0. The solution of the system
1 − f1 = (1 − ig1 ) · (1 − f2 · a21 )
1 − f2 = (1 − ig2 ) · (1 − f1 · a12 )
is
f1 = 0.236
f2 = 0.189
In this case it’s easy to see this result is far from the correct solution. Note that the probability
of the region represented by G having a fire is 0.1.
Even more, if we consider the definition of event there is a fire in node ni as follows
f1 = ig1 ∪ (f2 ∩ a21 )
(2)
f2 = (f1 ∩ a12 ) ∪ ig2
i.e. fi burs if there is an ignition there or if its neighbor burns and fire can pass from it to fi .
The equation Boolean system doesn’t have unique solution, see [Levchenkov, 2000]. This is,
there a couple of sets fi∗ satisfying (2).
2.2 Stochastic
One of the main problems is the existence of loops in G. In order to eliminate loops on the
model we can consider wind scenarios. For every scenario the graph Gs to be optimize must be
an acyclic graph.
Let’s suppose there are four relevant types of wind in region: S = {n, s, e, w} and for every wind
Gs is acyclic. Then the Stochastic optimization model based on (1) would be
m
min z = fis · vi
i=1
s.a
m
for i=1,...,m
1 − fis = (1 − igi ) · 1 − fjs · asij · xij for s∈{n,s,e,w}
j=1 (3)
j∕=i
m
xij · cij ≤ B
i,j=1
i∕=j
fis ∈ [0, 1], xij ∈ {0, 1}
Using meteorological data of the region, and fitting wind direction data on a density function,
like in [Leguey et al., 2016], it is possible to provide a couple of wind scenarios, and provide a
solution for the problem avoiding loop issues. The scenario are based on risky days, those days
were humidity, temperature and wind velocity are favorable for fire appearance and propagation.
Even without loops, the independence assumption is too hard. It can be proved that ran-
dom variable F = {f1 , . . . , fm } is a Bayesian network. Using exact or approximation al-
gorithms, it is possible to improve model formulation (3), this methodology is showed at
[Cheng and Hadjisophocleous, 2009].
3 Conclusion and future work
Keeping the mind between the mathematical model and the real problem can be an effort,
however, focusing only on one, the result could be useless. On one hand, this work faces several
mathematical challenges. On the other hand, even being able to compute an exact solution for
the complex model, it doesn’t have sense if the parameters are not realistic.
Input parameters, ignition probabilities and spread probabilities, are based on historical fire
database from Corsica firefighters, and meteorological information. In future works, it is planned
to use, topography and vegetation data as well as expert knowledge.
Finally, a sensitive analysis is required to claim imprecisions on the input data doesn’t change
a lot optimize location.
References
[Cheng and Hadjisophocleous, 2009] Cheng, H. and Hadjisophocleous, G. V. (2009). The mod-
eling of fire spread in buildings by bayesian network. Fire Safety Journal, 44(6):901–908. PT:
J; NR: 23; TC: 15; J9: FIRE SAFETY J; PG: 8; GA: 477OZ; UT: WOS:000268529700009.
[Garvey et al., 2015] Garvey, M. D., Carnovale, S., and Yeniyurt, S. (2015). An analytical
framework for supply network risk propagation: A bayesian network approach. European
Journal of Operational Research, 243(2):618.
[Leguey et al., 2016] Leguey, I., Bielza, C., and Larranaga, P. (2016). Tree-structured bayesian
networks for wrapped cauchy directional distributions. Advances in Artificial Intelligence,
Caepia 2016, 9868:207–216. PT: S; CT: 17th Conference of the Spanish-Association-for-
Artificial-Intelligence (CAEPIA); CY: SEP 14-16, 2016; CL: Salamanca, SPAIN; SP: Spanish
Assoc Artificial Intelligence, BISITE, Univ Salamanca, Springer Team, AEPIA; NR: 25; TC:
0; J9: LECT NOTES ARTIF INT; PG: 10; GA: BG2XK; UT: WOS:000387750600019.
[Levchenkov, 2000] Levchenkov, V. (2000). Solution of equations in boolean algebra. Compu-
tational Mathematics and Modeling, 11(2):154–163.