Predicción de la Evolución de los Incendios Forestales Guiada Dinámicamente por los Datos

Abstract

Desde hace años los incendios forestales son una amenaza para la calidad de vida en nuestro planeta, dado que la cantidad y magnitud de los mismos se ha incrementado de forma alarmante. <br/>Actualmente, existe un intenso trabajo para la lucha contra estos incendios y la disminución rápida y efectiva de su avance, de sus consecuencias y de sus peligros. <br/>La predicción del comportamiento del fuego en incendios forestales es un tema que se está desarrollando hace tiempo en este marco. <br/>Desde la informática, se han desarrollado diversos simuladores del comportamiento del fuego en incendios forestales [3] [4] [5] [14] [17]. Estos simuladores calculan el avance del fuego, dependiendo de su estado inicial y de las características del lugar donde dicho incendio se desarrolla. Esto es, características de la topografía, vegetación [2], humedad del combustible, humedad relativa del ambiente, estado del viento, etc. <br/>Estos simuladores son utilizados para predecir el avance del fuego en un lugar y momento específicos. En este marco, una predicci ón es realmente útil si es de buena calidad (se corresponde con la real propagaci on del fuego) y si la respuesta est a dentro de un llímite de tiempo acotado. Por lo tanto, necesitamos simulaciones con alta calidad de respuesta, que realmente realmente reflejen el real avance del fuego, y respuestas que se obtengan velozmente, minimizando el tiempo de la misma. Estos dos factores son necesarios y determinan caracter ísticas importantes de nuestro trabajo<br/>Un problema frecuentemente encontrado en la utilización de estas herramientas informáticas para predecir el comportamiento del fuego es la cantidad y complejidad de los datos de entrada. Normalmente, este tipo de simuladores necesita numerosos datos de entrada, que describan de forma correcta el entorno donde se desarrolla el fuego. Topografía, meteorología y vegetación del entorno del fuego deben estar descriptos de forma adecuada en el nivel de abstracción y detalle que el simulador utilizado requiera. <br/>En la realidad, es muy difícil disponer de una correcta descripción de todas estas variables (y sus interacciones). Esta di&#64257;cultad radica principalmente en: naturaleza dinámica de algunos factores (que varían y siguen su propio patrón de comportamiento), parámetros que no pueden ser medidos directamente (por lo que se utilizan estimaciones de los mismos), parámetros que no pueden ser medidos en todos los puntos (utilizándose interpolaciones), mapas (topográ&#64257;cos, vegetación, etc.), los cuales pueden estar desactualizados, o utilizar discretizaciones que representan de forma incorrecta las características que están representando, etc. <br/>Es necesario disponer una correcta descripción del entorno del fuego, dado que predicciones con datos de entrada que no sean correctos, no serán útiles, pues predecirán un fuego en un entorno que no es el real. <br/>En este trabajo de investigación se ha propuesto un framework donde se tiene como objetivo mejorar la calidad de los datos de entrada del simulador utilizado. Además, se pone gran esfuerzo en minimizar los tiempos de respuesta. En este trabajo se utiliza el simulador &#64257;reLib [5], un simulador que implementa el modelo de propagación de fuego desarrollado por Rothermel [20] [21]. <br/>Para mejorar la calidad de los datos de entrada, se realiza un procesamiento sobre el espacio de búsqueda que es el resultado de considerar todas las posibles combinaciones de los parámetros de entrada en sus rangos de variación. Esto da como resultado un espacio de búsqueda muy grande. Con el objetivo de evitar que esta búsqueda penalice el tiempo de respuesta, se utiliza un algoritmo genético [16] [19] guiado dinámicamente por los datos: Dynamic Data Driven Genetic Algorithm [7] [8] [9]. <br/>Se ha desarrollado este framework que consta de dos etapas [1] [6]: etapa de ajuste y etapa de predicción. Durante la etapa de ajuste, se buscará la mejor combinación de los datos de entrada para el incendio que se desea predecir. Un individuo del Algoritmo Genético, es una combinación determinada de valores para los parámetros de entrada del simulador utilizado. El objetivo de la etapa de ajuste es encontrar el mejor individuo, el que minimice el error en la simulación del avance del fuego. <br/>Para esto, se consideran tres instantes de tiempo en el avance del fuego: ti, ti+1 y ti+2. Los primeros dos instantes, se utilizarán durante la etapa de ajuste para buscar valores correctos de los parámetros de entrada. A su vez, la predicciá para el ultimo<br/>on efectiva se realizar´´instante de tiempo (ti+2). <br/>De esta forma, se simula el avance del fuego desde el instante ti hasta el instante ti+1. El resultado de la simulación es comparada con el avance del fuego real para ese mismo instante de tiempo. El resultado de esta comparación sirve como feedback para mejorar la elección de los valores de entrada. El resultado de la etapa de ajuste es un unico individuo, <br/>él que ha mostrado la simulación de mayor calidad. Luego, este individuo es utilizado como entrada para la etapa de predicción, la cual recibe el mapa del incendio en el instante ti+1 para predecir el avance del fuego hasta el instante de tiempo ti+2. <br/>De esta forma, durante la etapa de predicción se está buscando un conjunto de parámetros de entrada que representen de forma correcta el entorno del fuego que se desea predecir. Estos valores que logran buenas simulaciones (por lo tanto, buena descripción del entorno del fuego), son utilizados en la etapa posterior para obtener la predicción. Esta forma de trabajo, se basa en la hipótesis de que las características del entorno se mantengan durante las etapas que dicho proceso involucra (etapas de ajuste y predicción). <br/>De esta forma, el algoritmo genético recorre el espacio de búsqueda y descubre buenos valores para los parámetros de entrada en base a la comparación con el mapa del avance real del fuego. Esta forma de trabajo, permite mejoras en el algoritmo genético y estas mejoras son las principales aportaciones de este trabajo. <br/>Se proponen y desarrollan dos métodos para guiar el algoritmo genético. Ambos se basan en conocimiento aportado por el análisis del mapa del fuego real. De esta forma, el avance real del fuego desde el instante ti hasta el instante ti+1, aporta características que permiten de&#64257;nir datos útiles del entorno, los cuales se inyectan de forma dinámica durante el algoritmo genético para guiar la búsqueda hacia zonas con valores correctos para los parámetros de entrada. <br/>Aunque muchos factores in&#64258;uyen en el comportamiento del fuego, es sabido que la pendiente del terreno y el viento son factores determinantes en la forma y la velocidad de avance del fuego. <br/>En nuestra aplicación, se considera que las características del terreno son conocidas (pendiente y orientación de la misma, parámetros estáticos en el tiempo). <br/>Mediante el análisis del avance del fuego real desde el instante de tiempo ti hasta el instante ti+1 se obtienen sus principales características, y gracias a la composición de esta información con los datos de la pendiente, se puede determinar cuáles son las condiciones necesarias del viento para lograr un avance similar al real observado. Entonces, en vez de que la combinación del viento y pendiente determinen el avance del fuego, en nuestro caso, conociendo el avance del fuego y la pendiente, determinamos los valores del viento necesarios para que haya ocurrido el avance del fuego observado. <br/>De esta forma, se inyecta este conocimiento para mejorar la calidad en los datos de entrada y converger de manera más rápida hacia buenos resultados. Teniendo en cuenta que el viento es un factor dinámico, que tiene su propio patrón de comportamiento (el cual es muy difícil de predecir en el entorno de un incendio), se está inyectando valores para el mismo obtenidos a partir de la propagación real del fuego. <br/>El framework desarrollado constó de una primera implementación secuencial y de otra paralela, la cual permite aprovechar los recursos de hardware paralelos disponibles en la actualidad. <br/>Además, se han desarrollado dos métodos para guiar dinámicamente el algoritmo genético [10] [11] [12] [13]: método computacional y método analítico. El método computacional es totalmente independiente del simulador subyacente y del framework en sí. Utiliza una base de datos con información de distintos incendios para encontrar los valores necesarios. A su vez, el método analítico fue desarrollado como método de validación del primero, y se basa en los cálculos hechos por el simulador, por lo tanto, totalmente dependiente del mismo. <br/>La implementación en paralelo del algoritmo fue realizada utilizando el paradigma master/worker [15] [18], donde el total de los individuos de cada población es distribuida entre los distintos workers. El trabajo se ha distribuido de forma tal que cada worker realiza la simulación y la comparación con el mapa real con un grupo de individuos de la población. De esta forma se han distribuido las poblaciones de individuos, donde la aplicación muestra más requerimiento de tiempo de CPU. Distribuyendo los individuos en grupos, se logra balance de carga y disminuir la comunicación, aumentando la granulaidad de la aplicación. <br/>Se han desarrollado distintas pruebas con mapas sintéticos (esto es, avances de fuegos simulados) como así también con mapas reales. Los resultados obtenidos son satisfactorios, guiar la búsqueda del algoritmo genético ha logrado aumentar la calidad de las simulaciones, por lo tanto de las predicciones. Los resultados del método computacional fueron corroborados por correlación con los resultados del método analítico. <br/>Además, el algoritmo paralelo permite utilizar poblaciones de mayor dimensión, lo que mostró mejorar los resultados sin penalizar el tiempo de respuesta. También, la disminución del error en las simulaciones en este método que incluye una primer etapa de ajuste mostró ser mucho más efectiva (más calidad de predicción) que cuando no se hace este preprocesamiento con los parámetros de entrada. Se ha logrado mejorar las predicciones, sin mejorar el simulador, sino, mejorando la calidad en los parámetros utilizados. El método propuesto se ha implementado de forma tal que el simulador se vea como una "caja negra", la cual se puede cambiar y el método sería aún útil (con los cambios necesarios en formato de entradas y salidas).

Forest &#64257;res are part of natural balance in our planet. Natural &#64257;res are provoked by natural factors combination: dry seasons, favorable fuel moistures, electrical storms, volcanoes, earth¬quakes, etc. Natural forest &#64257;res can devastate overall forests as well as productive forest areas, farms, etc. <br/>Nowadays, human is arduously working on this problem in order to avoid and to reduce forest &#64257;res damages. As results of this effort there exist different kind of studies, strategies and tools used to prevent &#64257;res, to de&#64257;ne risk areas and to reduce the &#64257;re effects when a disaster occurs. <br/>Forest &#64257;re control and manage are complex tasks, due to forest &#64257;res are related with weather, topography, human population, &#64257;re aspects, etc., having all of them its own behavior pattern. Furthermore, there exist several behavior interactions between them, that determine additional behavior characteristics, resulting in very complex &#64257;re behavior pattern. <br/>This problem is nowadays studied by di_erent areas. Technology is not an exception, and informatics tools are continuously developed. <br/>One of the most important computer tool for forest &#64257;res are forest &#64257;re behavior simulators. These kind of simulators determine the advance of the &#64257;re line, taking into account beginning &#64257;re state, topography conditions, weather aspects, fuel characteristics, etc [3], [4], [5] [14] [17] <br/>[20] [21]. <br/>Furthermore, this kind of problem has the additional requirement that time constraints add. A forest &#64257;re prediction is really useful when it is available before the real &#64257;re propagation occurs and when prediction really describes real &#64257;re progress. In order to be reliable, it is necessary high quality predictions, it means, predicted &#64257;re progress must be as similar to the real &#64257;re as possible. <br/>During this work, we are going to use the forest &#64257;re simulator called &#64257;reLib [5] holding it in a framework that attempts to improve input parameter accuracy in order to increase prediction quality. <br/>Usually, a prediction is made using a forest &#64257;re simulator which receives several inputs (&#64257;re environment description) and it returns the state of the &#64257;re for a later instant of time. Input parameters usually include: initial &#64257;re front state, topography, vegetation [2], wind, fuel hu¬midities, and additionally, relative moisture, cover crown, cover clouds, etc. All these input parameters depend on the forest &#64257;re simulator used. <br/>Thus, having initial &#64257;re line and environmental characteristics, simulator uses some &#64257;re prop¬agation model in order to simulate &#64257;re behavior. Taking into account this classical prediction method, we can see that it is a straight, simply method and it has the advantage of performing just one simulation (what means low processor time requirements). But these advantages are in a sense the main weak point of the method: &#64257;nal prediction quality depends on the suitability of the unique simulation (that means, using a unique input parameters set). <br/>As we had mentioned during previous paragraphs, the accuracy of the input parameters are really open to debate due to having its actual values is not easy, some times it is impossible. Consequently, we are going to present a method where a search of better parameter values is performed in order to reduce input data uncertainty [1]. <br/>This method consists of two stages: a new stage was added before the prediction step. This new stage is called Calibration stage, and it allows us to &#64257;nd a set of input parameter values that achieve a good simulation from instant ti to instant ti+1. Then, we can use this good set of input parameters to predict &#64257;re behavior during the next instant of time (ti+2). <br/>Once a combination of values for the input parameters is founded, we consider that the environmental characteristics that are good described by these values at instant ti+1 will re¬main useful for the subsequent instant of time (from ti+1 to ti+2). Then we use these values for obtaining the predicted map for instant ti+2. This scheme is based on the premise that environmental features will be maintained during involved time steps. <br/>In addition, each of these input parameters have its own valid range where they can vary, and in fact, these ranges may be di_erent: they vary depending on the characteristic that it represents. Thus, the amount of di_erent combinations of these parameter values leaves us a very big search space. In order to avoid that this Calibration Stage becomes a bottle neck, we had developed a Dynamic Data Driven Genetic Algorithm [16] [19]. Strategies adopted through this application result in an e_cient search solution. <br/>Our Dynamic Data Driven Genetic Algorithm dynamically incorporates new data (from storage device or on line captured) promising more accuracy data analysis, more accurate pre¬dictions, more precise controls and more reliable outcomes [8] [9] [7]. Taking into account that two stages method needs the information of the real &#64257;re spread from instant ti to ti + 1, useful information will be obtained from the analysis of this real &#64257;re progress. This information will be used for steering searching process through genetic algorithm, in order to improve the values of the parameters. <br/>Our genetic algorithm intents to minimize our error function (individual &#64257;tness): error value determines the di_erences between real &#64257;re line and simulated &#64257;re line. Due to simulator imple¬ments a cellular automata model, all involved maps are a grid of cells, then, the error function is based on a cell by cell comparison (of real and simulated maps). <br/>When either slope nor wind are strong enough, &#64257;re grows forming a circular shape. But when wind or slope are presented (both or one of them), they in&#64258;uence &#64257;re growth in a de¬terminant way. Shape, velocity, direction, intensity, all of these &#64257;re features are in&#64258;uenced by wind and slope factors. Wind velocity and direction, slope inclination and aspect combination are crucial in &#64257;re spread behavior. <br/>Thus, knowing wind and slope decisive in&#64258;uences and knowing the real &#64257;re shape (by the analysis of real &#64257;re at instant ti+1 disposed in calibration stage), we can combine this informa¬tion in order to incorporate additional data that will be useful in order to improve &#64257;re spread simulations. This information will be used as feedback information in order to improve simula¬tion accuracy. <br/>Actually, slope and real propagation are known. This information is used to calculate wind speed and wind direction needed to generate the observed &#64257;re propagation in presence of the current slope features. Once wind main characteristics are calculated they will be used through two methods for dynamically steering our genetic algorithm: Computational and Analytical Methods. In particular, Analytical Method was developed in order to validate Computational Method operation. <br/>Computational Method uses di_erent forest &#64257;res information (including &#64257;re environment) in order to discover wind main features. Forest &#64257;res data can come from historical real &#64257;res, prescribed burnings, or synthetic simulated &#64257;res (using a forest &#64257;re simulator). Forest &#64257;re main characteristics are stored through a data base. <br/>Data base information must be as complete as possible, in order to re&#64258;ect the most amount of &#64257;re cases that can happen in the real world. In this data base several &#64257;re spreads are stored and we look for a &#64257;re progress similar to the real &#64257;re line observed for instant ti+1 in presence of similar or equal slope characteristics. <br/>Historical real &#64257;res information could be used in order to construct our application data base. Unfortunately, detailed real &#64257;res information was not available for us since we were deal¬ing with prescribe and synthetic &#64257;res. In order to generate a suitable data base the forest &#64257;re simulator &#64257;reLib was used for obtaining a high number of detailed burning cases. <br/>Computational Method is based on following process: real forest &#64257;re progress is analyzed at time ti+1, thus, &#64257;re progress direction, velocity and distance are obtained. Then, all real forest &#64257;re characteristics are used in order to &#64257;nd the most similar &#64257;re into the data base. When most similar &#64257;re is founded, wind direction and velocity are injected during genetic algorithm operation. <br/>Speci&#64257;cally, these wind values will be used to de&#64257;ne a subrange through the whole parameter valid range and, when mutation operator takes place, wind values will be assigned using a ran¬dom value limited by the new subrange (taking into account data base cases incompleteness). <br/>Analytical Method was created in order to evaluate the proper operation of Computational Method. This method is based on an exhaustive study of Rothermel model and &#64257;reLib sim¬ulator ([21] and [5]). This method is based on some calculus performed by the simulator in order to obtain &#64257;re direction and velocity, by the combination of wind, slope and environmental factors. Once the model and simulator was studied and understood, we use the steps performed by the simulator but in a suitable order, for obtaining wind characteristics from slope and real &#64257;re characteristics combination. <br/>When Analytical Method is applied, each simulation is performed using an individual (sce¬nario) and ideal wind values are calculated and stored together with such individual. Then, these values are assigned as individual wind velocity and direction when elitism or mutation operations take place during Dynamic Data Driven genetic algorithm execution. <br/>In practice, we expect that this method will be more precise than Computational Method but, by contrast, it is severely coupled to the underlying simulator (being this fact an important method drawback). <br/>Taking into account application response time limits, non simulation dependences and simu¬lations time requirements, proposed application was developed using the parallel paradigm [15] [18], dividing simulation processes and error calculus between di_erent parallel tasks. <br/>Master process performs genetic algorithm operations and distributes population individu¬als between worker processes. Every time a worker process receives a group of individuals, it performs the simulation and calculates the error function with each individual. <br/>In order to avoid that application communication pattern became a bottle neck, individuals are distributed by groups (chunks) instead of individual transmissions. When a worker &#64257;nal¬izes the evaluation of a speci&#64257;c chunk, this worker process returns the evaluated chunk to the master process. Then, master process sends another non evaluated chunk to it until all chunks are evaluated. <br/>During this work, two main objectives were considered: prediction quality improvement (what means prediction error reduction) and reduction of prediction process time requirements. <br/>Several times, these two aspects have mutual dependencies: suitable simulation accuracy can be achieved if enough time is available for prediction process. On the other hand, if prediction results are required in a short term of time, this feature can attempt on prediction quality. <br/>During this work, experimental results were analyzed and best application characteristics were studied. We could see that 2 stages prediction method achieve best results when they are compared with classical prediction. Performing a pre-search of input parameters values achieve an important error reduction due to the use of suitable input parameters values. <br/>Steering methods, Computational Method as well as Analytical Method, in most of the cases, reduce simulation errors, achieving more precise simulations during calibration stage, and consequently, more precise predictions [10] [11] [13]. These Methods reduce total execution time, on account of the acceleration of searching convergence. Using real &#64257;re progress knowledge, genetic algorithm is fast guided to promising individual search space zones [10] [11] [13]. <br/>In order to obtain real &#64257;re progress characteristics, additional methods were developed. These methods had showed good performance when they where used for di_erent kind of maps: linear maps, elliptical maps, real cases, synthetic cases, di_erent sizes of cells, etc. <br/>Parallel application proposed was tested in order to evaluate its scalability. Master and worker process times had decreased when number of computing elements had increased. "On demand" dealing of work, communication reduction (because of chunks communication), etc. achieve a good performance application [12]. <br/>For most of the performed tests similar behavior could be seen: Computational Method convergences more quickly to good individual zones. Then, fewer iterations can be executed and steering methods &#64257;nds good results. Thus, execution time of two stages prediction method can be reduced as well. <br/>Referencias/References<br/>[1] Abdalhaq B., "A Methodology to Enhance the Prediction of Forest Fire Propagation." PhD Thesis. Universitat Autònoma de Barcelona (Spain). June 2004. <br/>[2] Anderson H., "Aids to Determining Fuel Models For Estimating Fire Behavior." Intermountain Forest and Range Experiment Station Ogden, UT 84401. General Technical Report INT.122. April 1982. <br/>[3] Andrews P., "BEHAVE: Fire Behavior prediction and modeling systems -Burn subsystem." part 1. General Technical Report INT-194. Odgen, UT, US Department of Agriculture, Forest Service, Intermountain Research Station. pp. 130. 1986. <br/>[4] Andrews, P. "BehavePlus &#64257;re modeling system: past, present, and future.". Proceedings of 7th Symposium on Fire and Forest Meteorological Society, 23-25 Octubre de 2007, Bar Harbor, Maine, Boston. http://ams.confex.com/ams/pdfpapers/126669.pdf. Acceded on October 2008. <br/>[5] Bevins C., "FireLib User Manual & Technical Reference". http://www.&#64257;re.org/downloads/&#64257;reLib/1.0.4/&#64257;relib.pdf. Acceded on January 2006. <br/>[6] Bianchini G., "Wildland Fire Prediction based on Statistical Analysis of Multiple Solutions." PhD Thesis. Universitat Aut-onoma de Barcelona (Spain). July 2006. <br/>[7] Coen J., Beezley J., Bennethum L., Douglas C., Kim M., Kremens R., Mandel J., Qin G. and Vodacek A. "Wildland Fire Dynamic Data-Driven Application System." Center for Computational Mathematics Reports, University of Colorado at Denver and Health Sciences Center. November 2006. UCDHSC/CCM Report number 238. <br/>[8] Darema, F. "Dynamic Data Driven Applications Systems: A New Paradigm for Application Simulations and Measurements." ICCS 2004, LNCS 3038, Springer Berlin / Heidelberg, pp. 662-669. <br/>[9] Douglas C., "Dynamic Data Driven Application Systems homepage." http://www.dddas.org. Acceded on November 2007. <br/>[10] Denham M., Cortés A., Margalef T., Luque E., "Algoritmos Genéticos Guiados Para Predicción de Incendios Forestales". Actas del XVIII Jornadas de Paralelismo JP'07. Zaragoza (Spain), 2007. Vol II, pp. 733-741. <br/>[11] Denham M., Cortés A, Margalef T. and Luque E. "Applying a Dynamic Data Driven Genetic Algorithm to Improve Forest Fire Spread Prediction". International Conference on Computational Science (ICCS) 2008, Cracovia, Polonia. Computational Science -ICCS 2008. LNCS Volume 5103, Springer Berlin Heidelberg. Pp: 36-45. <br/>[12] Denham M., Cortés A, Margalef T. "Parallel Dynamic Data Driven Genetic Algorithm for Forest Fire Prediction." 16th European PVM/MPI Users' Group Meeting. Espoo, Finlandia, Septiembre del 2009. LNCS Volume 5759, Springer Berlin Heidelberg. Pp: 323-324. <br/>[13] Denham M., Cortés A., Margalef T. "Computational Steering Strategy to Calibrate Input Variables in a Dynamic Data Driven Genetic Algorithm for Forest Fire Spread Prediction". International Conference on Computational Science (ICCS) 2009, USA. LNCS Volume 5545, Springer Berlin Heidelberg. Págs: 479-488. <br/>[14] Finney M. "FARSITE: Fire Area Simulator-model development and evaluation. " Res. Pap. RMRS-RP-4, Ogden, UT: U.S. Department of Agriculture, Forest Service, Rocky Mountain Research Station, 1998. <br/>[15] Foster I., "Designing and Building Parallel Programs." (Online) Addison-Wesley ISBN 0201575949, chapter 8 Message Passing Interface. Disponible en http://wwwunix.mcs.anl.gov/dbpp/text/node94.html (1995) <br/>[16] Koza J. "Genetic Programming. On the programming of computers by means of natural selection". Massachusetts Institute of Technology. Cambridge, Massachusetts 02142. The MIT Press, 1992. <br/>[17] Lopes A., Cruz M. y Viegas D. "FireStation -An integrated software system for the numerical simulation of &#64257;re spread on complex topography." Environmental Modelling and Software 17(3): 269-285 (2002) <br/>[18] "MPI: The Message Passing Interface Standard." http://www-unix.mcs.anl.gov/mpi/ <br/>[19] Michalewicz, Z. "Genetic algorithms + data structures = Evolution Programs." ISBN 9783540606765, Springer 1996. <br/>[20] Rothermel R., "A mathematical model for predicting &#64257;re spread in wildland fuels". USDA FS, Ogden TU, Res. Pap. INT-115, 1972. <br/>[21] Rothermel R. C. "How to Predict the Spread and Intensity of Forest and Range Fires". Gen. Tech. Rep. INT-143. Ogden, UT: U.S. Department of Agriculture, Forest Service, Intermountain Forest and Range Experiment Station, 1983. pp. 1-5.