In this paper we present an ongoing research activity dealing with predictability properties for complex systems. We propose to apply the results derived in [FDSDB18] to predict critical situations occurring in the context of wildfires. We model fire spreading by means of a nondeterministic cellular automaton, to the aim of considering the more general case where uncertainties are present due to an imperfect knowledge of the environment. The long-term objective of this research is to optimize the fire emergency management decision support system.
To compensate for this advantage, bushfire prediction can be reformulated as a safety problem for modern control systems, as explained in the following.
When dealing with safety issues for modern control systems, it is fundamental to be able to understand if the system’s behavior belongs to a given subset of the state space (called critical set) on the basis of the observations. The safety problem can be addressed in two ways, that is either by detecting the occurrence of states belonging to the critical set within a finite time interval (diagnosability property), or by predicting in a deterministic way the occurrence of specific states belonging to the critical set, in advance with respect to their occurrence (predictability property). Predicting the future occurrence of particular states of interest is of paramount importance in a huge number of applications. Indeed, this allows pro-actively performing operations on the system to enhance its reliability, optimize performance or ensure safety by avoiding abnormal behaviors. Motivated by this need, predictability has been studied both for discrete event systems (see e.g. [GL09], [ZL13] and references therein, [TK17]) and continuous systems (see e.g. [MB97]).
In [FDSDB18] we introduce and characterize the notions of eventual and critical predictability for nondeterministic finite state automata in a full set-membership approach. Critical predictability requires prediction of the critical states at every occurrence, whereas eventual predictability requires the prediction of the critical set at every occurrence after a transient of finite duration, without false alarms. In [FDSDB18] we characterize the predictability property by also defining bounds on the time interval within which the prediction can be performed. Furthermore, we provide algorithms to check these properties with polynomial time algorithms. In [FDSPDB18] we also introduce the notion of approximate predictability for the general class of metric systems, that allows capturing heterogeneous dynamics arising in modern control systems (see e.g. [Tab09]), and we describe how to check this property for symbolic metric systems.
We propose to apply our results to predict the behavior of fire spreading in inhomogeneous forests, modeled by non-deterministic cellular automata. Our objective is to optimize fire emergency management, by providing the tools to characterize the amount of time within which the intervention is required, and to assess the risk related to different regions inside the forest.
The paper is organized as follows. In Section 2 we provide a brief description of the formalism used to model fire spreading. In Section 3 we recall definition and characterization of predictability properties. The way in which this notions can be used for fire spreading prediction is described in Section 4. Conclusions and future research activities are mentioned in Section 5.
Notation. In this paper we use the following notation. The symbol N denotes the set of nonnegative integers. Given sets A and B, let A\B indicate the relative complement of set B with respect to set A, that is the set of elements in A but not in B. For a set A ⊂ B, where the symbol ⊂ has to be understood as subset (not necessarily strict), A denotes the complement of A in B, i.e. A = {b ∈ B : b ∈/ A}. The symbol ∅ denotes the empty set. Given a finite set of events E, E∗ is the set of all finite strings of elements of E, including the null string. Given L ⊂ E, L∗ = {ǫ} ∪ L ∪ LL ∪ . . . , that is, an element of L∗ is composed by the concatenation of a finite (but possibly arbitrarily large) number of elements of L. For a string σ, |σ| denotes its length, σ(i), i ∈ {1, . . . , |σ|} is its i−th element, and σ|[a,b] denotes the string σ(a)σ(a + 1) · · · σ(b − 1)σ(b). 2
Forest fire spreading is a complex physical phenomenon and many efforts have been devoted to the efficient modeling of wildfires. Indeed, a good compromise must be found between the mathematical model’s accuracy and the computational complexity needed to simulate it. Cellular Automata (CA) proved to be a good modeling formalism for spatial dynamics simulation, due to their intrinsic discrete (both in time and space) nature [EEW+07],[YDS08]. In [DM04], the authors propose a hierarchical modeling framework. Specifically, they perform a landscape’s discretization in cells of uniform dimension describing the landscape. Then, fire propagation is modeled at a higher level of abstraction, by means of interactions between neighboring automata. A finite automaton MF = (S, s0, Σ, δ) is associated with each cell, where: • S = F × T × W is the state space, where: – F = {unburnt, burning, burnt} is the state of the fuel in the corresponding location; – T = Sl × O represents the terrain in terms of its slope Sl = {f lat, slight, mid, steep} and orientation
O = {n, s, e, w}; – W = {f, n, nw, w, sw, s, se, e, ne} is the wind direction; • Σ is an alphabet represented different actions (based on ignition); • δ ⊂ S × Σ × S is the next-state transition relation.
The automaton state represents the spatial information associated with the corresponding cell, thus enabling an heterogeneous description of the landscape. Once an automaton is associated with each cell, fire spreading is modeled by taking into account interaction between automata. In particular, the communication of fire spread is allowed between connected automata, i.e. between automata for which a spatial neighboring relation exists. Thus, the next state of a cell is determined by the state information of its neighbors, as in the classical cellular automata approach.
The fundamental parameters that influence the spread of fires are climate, LULC (land use - land cover) and morphology. Within them it is possible to identify many variables to be associated with deterministic or non-deterministic models. The advantage that multispectral and multitemporal (remote sensing) analyzes provides is that of coding many of these environmental variables into indices of the biophysical state of vegetation (NDVI, EVI, NDWI, LAI). Moreover, the high frequency of data acquisition allows to continuously update the status of the automaton. By increasing the number and the frequency of the measurements, a more accurate characterization of the survey context can be obtained. The set of acquired parameters could be translated into geographical data (raster layer) and coded into a unique parameter, giving an evaluation of the ”velocity of diffusion”. In this way, it will be possible to generate a set of scenarios, corresponding to different situations. However the focus of this paper is not in refining the model, but on the analysis of the system in order to be able to design a ”predictor”, i.e. an algorithm that, given the model and given the on-line information coming from sensors in the environment, is able to estimate in advance the safe time before some critical event occurs, which in case of fire emergency management could be represented by the fact that some critical location has been reached by the fire. To this aim we need to transform the cellular automata formalism into a finite state machine (FSM) formalism, describing the entire area, where the state of the machine represents the product of the states of the cellular automata and the transition relations describe the interaction between automata. In general, the number of states of the resulting FSM is exponential in the number of cellular automata, and hence the problem could become intractable in most cases. However, this state explosion does not occur if we assume few fire starting points, and if we assume that once a portion of land is burnt, it cannot be unburnt at the next step. We highlight the fact that we are assuming incomplete information, i.e. the sensors do not cover all the monitored area, or some sensors could be offline. Our general result about predictability for finite state machines applies to the case of nondeterminism in the evolution, and we will work to translate our result in a probabilistic framework, which could be more appropriate for the specific application we are considering in this paper. 3
In this Section we provide the main definitions and the conditions to check the predictability property.
We start by introducing nondeterministic FSMs, as follows.
Definition 1 A Finite State Machine (FSM) is a tuple
M = (Q, q0, Y, h, E) (1) where Q is the finite set of states, q0 ∈ Q is the initial state, Y is the finite set of outputs, h : Q → Y is the output function, E ⊂ Q × Q is the transition relation.
The FSM introduced in Definition 1 is also called Moore Machine, where the output function associates a discrete output to each discrete state, no output is associated to discrete transitions. Instead, the FSM associated with each cell introduced in Section 2 is a Mealy Machine, i.e., the measurable signal is associated with each discrete transition, no output is associated to discrete states. It is possible to transform a Mealy Machine into a Moore Machine, and there exists a vast literature dealing with this transformation (we refer to [DSDB16] for description on this topic and on a procedure to perform the transformation). Therefore, without loss of generality, in the rest of this paper, we will refer to Moore automata as described in Definition 1.
We pictorially represent an FSM by means of a graph, where the set of nodes coincides with the set of states Q, and the set of edges represents the transition relation E between discrete states. Two labels are associated to each discrete state: the number inside the node is the state label, whereas the letter above the node is the output symbol (belonging to the set Y ). For a state qi ∈ Q, we can define the set of its successors succ(qi) = {qj ∈ Q : (qi, qj ) ∈ E} and the set of its predecessors pre(qi) = {qj ∈ Q : (qj , qi) ∈ E}.
Any finite or infinite string x with symbols in Q that satisfies the conditions:
x(1) ∈ Q x(k + 1) ∈ succ (x(k)) , k = 1, 2, . . . , |x| − 1 is called a state execution (or state trajectory, or state evolution) of the FSM M . The singleton {q ∈ Q} is a state execution. Let X ∗ be the set of finite state executions of M , X be the set of all (finite and infinite) state executions of M , Xq0 be the set of state executions x ∈ X with x(1) = q0, and let Y be the set of strings with symbols in Y . Let y : X → Y be the function that associates to a state execution the corresponding output execution, as y(x) = h(x(1)) · · · h(x(n)), with n = |x|. Moreover, y−1(y(x)) = {xˆ ∈ Xq0 : y(xˆ) = y(x)}, x ∈ Xq0 .
We can also define a state to be persistent if it may be visited after an arbitrarily long sequence of events, see e.g. ([DSDB16]).
Definition 2 Given the FSM M = (Q, q0, Y, h, E) a state qi ∈ Q is persistent if for any kb ∈ N, there exists x ∈ Xq0 such that x(k) = qi ∧ k ≥ kb. The set of persistent states is denoted by Qp.
For a finite x ∈ X ∗, Cx denotes the set of all its finite ”continuations”, i.e.: For x ∈ X ∗, the set of its prefixes is:
Cx = {z ∈ X ∗ : xz ∈ X ∗} .
Px = nzn ∈ X ∗ : x|[1,n] = zn, n = 1, . . . , |x|o . (2) (3) (4) A prefix z ∈ Px is proper if z 6= x.
Without loss of generality, we assume that all the states are reachable from the initial state. 3.1
We now recall the critical predictability property’s definition proposed in [FDSDB18] in a full set-membership approach, by leveraging the ideas upon which different diagnosability notions have been defined and characterized in [DSDB17]. The property is given in a general form that is parametric with respect to the length of the time interval within which the prediction of a critical state is performed. The property is defined with respect to the subset of the state space, called critical set. In particular, we are interested in predicting whether the system’s state belongs to the critical set, without distinguishing among different states in the critical set. Definition 3 Given n ∈ N, n ≥ 1, the FSM M is critically n−predictable with respect to a set Ω ⊂ Q (shortly, critically (n, Ω)−predictable) if for some k ∈ N, and k ≥ n, the following conditions are satisfied for any state trajectory x ∈ Xq0 ending in Ω with |x| ≥ 1: (i) (|x| > n) ∧ (x(k) ∈/ Ω, ∀ k ∈ [|x| − n, |x| − 1]) (ii) ∃ p ∈ Px, with |p| ≤ |x| − n, such that ∀ v ∈ y−1 (y(p)) and for any sufficiently long s ∈ Cv (ii.a) v (|p|) ∈/ Ω; (ii.b) (n > 1) =⇒ s (k) ∈/ Ω, ∀ k ∈ [1, n − 1] ; (ii.c) ∃ kb ∈ n, k : s kb ∈ Ω.
The FSM M is critically (0, Ω)−predictable if for some k ∈ N, and k ≥ 0, the following condition is satisfied for any state trajectory x ∈ Xq0 ending in Ω with |x| ≥ 1: (iii) ∃ p ∈ Px, such that ∀v ∈ y−1 (y(p)) and for any sufficiently long s ∈ Cv (v (|p|) ∈ Ω) ∨ ∃ kb ≤ k : s kb
It is important to notice that the critical (n, Ω)−predictability requires prediction of the critical states at every occurrence.
We can also rephrase the classical definition (introduced in [GL09]) in our framework, as follows. Definition 4 The FSM M is predictable with respect to a set Ω ⊂ Q (shortly, Ω−predictable) if for any state trajectory x ending in Ω, there exists z ∈ Px such that for any v ∈ y−1 (y(z)), v(k) ∈/ Ω, ∀k ∈ [1, |z|], and any sufficiently long s ∈ Cv has a state in Ω.
Remark 1 The critical predictability notion allows generating an alarm signal whenever a critical state has been predicted, but also to estimate a safe horizon, that is the maximal number of steps before the predicted event can occur. Therefore, critical predictability implies predictability as defined in Definition 4. 3.2
We now recall the conditions for checking predictability properties above introduced (proofs are provided in [FDSDB18]). In particular, the characterization is based on the following subsets of the state space Q.
Given a set Ψ ⊂ Q, the symbol R−n (Ψ) denotes the set of states from which it is possible to reach the set Ψ after n steps, but not before, that is:
R−n(Ψ) = {q ∈ Q : (∃x ∈ Xq, x(n + 1) ∈ Ψ) ∧ (∀x ∈ Xq, x(i) ∈/ Ψ ∀i = 1, ..., n)} .
Let the symbol Fn (Ψ) denote the subset of R−n(Ψ) such that any trajectory starting from q ∈ Fn (Ψ) reaches the set Ψ in finite time, that is:
Fn(Ψ) ={q ∈ R−n(Ψ) : ∀x ∈ Xq, x(i) ∈ Ψ, i ∈ N, i ∈ [n + 1, ∞)}.
The definition implies that F0 (Ψ) = R−0 (Ψ) = Ψ, R−n (Ψ) ∩ Ψ = ∅ and Fn (Ψ) ∩ Ψ = ∅, if n > 0. If Fn (Ψ) 6= ∅ it will be called n−precursor of Ψ. In [FDSDB18] an algorithm for the computation of Fn (Ψ) is given. The set F (Ψ) = [ Fn (Ψ) n≥0 is called precursor of Ψ. It is easy to verify that Finally, let us define the set
Fn (Ψ) ∩ Fn+1 (Ψ) = ∅, ∀n ≥ 0.
Fˆn(Ψ) = {q ∈ Fn(Ψ) : pre(q) ∩ Fn(Ψ) 6= ∅}.
We can now give the following statement.
Lemma 1 The FSM M is critically (n, Ω)−predictable only if Fn (Ω) 6= ∅ and R−n (Ω) = Fn (Ω).
For the ease of understanding, we recall some notions concerning indistinguishability property of state executions (see ([DSDB17]) for more details).
Definition 5 Two state trajectories x1 ∈ X and x2 ∈ X are called indistinguishable if y(x1) = y(x2).
In the following, we will use some of the sets defined in ([DSDB17]) under the assumption that an output symbol is associated to each state in Q, i.e. ǫ ∈/ Y .
Given the FSM M = (Q, q0, Y, h, E), we define the set Π = {(i, j) ∈ Q × Q : h(i) = h(j)}. Let S∗ ⊂ Π be the set of pairs of states reachable from q0 with two indistinguishable state executions.
Proposition 1 Given n ∈ N, suppose that Fn (Ω) 6= ∅ and R−n (Ω) = Fn (Ω). The FSM M is critically (n, Ω)− predictable if and only if where:
S∗ ∩ Fˆn (Ω) × Dn (Ω) = ∅ Dn (Ω) = F (Ω) [
[
(5) (6) (7) (8) (9) (10) (11)
Finally, we characterize the property of Definition 4. To this aim, given the FSM M = (Q, q0, Y, h, E), define the FSM Mf = (Q, q0, Y, h, Ee), where (qi, qj ) ∈ Ee if and only if (qi, qj ) ∈ E and qi ∈/ Ω. Remark 2 As shown in [FDSDB18], the above-described characterization allows checking predictability properties by means of polynomial time algorithms. 4
In this Section we outline how the results on predictability for FSMs, recalled in Section 3, can be helpful in designing effective wildfire management operations, to the aim of preserving natural resources, and saving lives and costs [TWDM13]. The first step is constituted by the derivation of an appropriate model of the region of interest, by also integrating data obtained from Geographic Information Systems (GIS) [YDS08]. Then, predictability properties of the resulting FSM can be checked by means of the tools described in Section 3.2. This verification can be used both off-line and at run-time. Specifically, it can be exploited off-line to properly identify subregions that could potentially have/constitute higher risks. Instead, at run-time the possibility to predict in a deterministic way the fire spreading would result in an optimization of fire management interventions, by focusing emergency agents in the most critical regions, while avoiding to waste resources in less critical zones. 5
In this paper we describe the early stage of a research activity dealing with smart fire emergency management. By taking into account a non-deterministic finite state automaton modeling the fire spreading, we apply the results proposed in [FDSDB18] to characterize the possibility to predict in a deterministic way the future occurrence of critical states. As there exists a direct relation between the automaton and the physical cells of the region of interest, the above-described properties can be used to predict the fire spreading behavior with the objective of programming effective emergency interventions.
Future research directions will include the practical implementation of this proposal. Specifically, for a given region of interest, a probabilistic cellular automaton based on GIS will be developed to the aim of having a more realistic representation of the environment. It is therefore of fundamental importance to parameterize the environmental variables in finite states of the automaton. With the same objective continuous processes (such as diffusion ones) will be integrated in the model and, in that case, approximate predictability property will be characterized by using the results developed in [FDSPDB18]. To the aim of optimizing the emergency management, diagnosis techniques (developed in [DSDB17]) will also be used for the identification of starting ignition points. Furthermore, by modeling the emergency management decision support system as a finite state automaton, we will explore the possibility of applying our results to the composition of this automaton with the automaton modeling the fire spreading, thus obtaining a smart fire emergency management system.