CodePlexProject Hosting for Open Source Software

Version 2.01, DNH 2012-10-02

This document describes algorithms which can be used to model the growth of a wildfire perimeter in a simulation model run, and in some cases can be run in reverse so as to estimate the point of fire origin.

These algorithms are not a complete simulation model: they require integration within a larger system in order to render realistic behaviour. The ‘host’ system needs to provide three things:

- Starting fire: a mechanism for initiating the fire perimeter, either as a point or a path
- Simulation controller: a mechanism for invoking the growth/shrinkage parameter
- Spread rate calculator: a function which can return the rate of spread of the fire front in a given direction for any point in space at any given time.

The problem of how to provide these facilities is not detailed in this document: it is different from the question of how the perimeter growth modelling is performed.

It’s possible to combine the perimeter growth algorithms described here with various different ROS calculators, but note that the ROS calculator must return a directional rate: a spread rate with reference to a particular direction.

Tirailleur is a French word of Napoleonic military origin. The Tirailleurs were light infantry forming a skirmish line in advance of a column.

** **

A fire may have more than one active area. Each area is described by a perimeter: a closed polygon which outlines the area covered by the fire.

Each perimeter is called a ‘path’. Each path consists of a list of ‘nodes’, which are implicitly joined by internode vertices. The path is circular and the lines don’t diverge: each node in the path has exactly one node before it and one node after it. One node is nominated as the first node. The last node is therefore the one before the first node.

The nodes are linked in a clockwise direction, so that the area contained by the path is to the right-hand side of the line, and the outside area is to the left-hand side.

If the fire area is known, then this can be used to define the original path. If a single point location is the starting information, then a simple diamond path of four nodes is created around the start point.

As the simulation advances, the fire area may spread. The simulation proceeds in steps of varying length. In each simulation step, the nodes try to move outwards to form a new, larger perimeter.

Each node establishes a direction in which it tries to move. Then the fire front*
*spread rate for that node *in that move direction* is retrieved from some other part of the program. The node then moves a distance in that direction which is a product of the spread rate for that direction and the length of the simulation time
step. If the ROS is negative, the node does not move: nodes therefore cannot move backwards (rightwards) into the burned area when the perimeter is expanding.

The move direction for each node is determined by considering its two neighbours. If a line is drawn between the node before and the node after the moving node, then the move direction is perpendicular to that line (leftwards).

Since each node’s move direction is determined from its neighbours’ locations, the move cannot be immediately executed. In each simulation step, the move direction for each node must be first calculated and then the move distance evaluated. The move is then applied to all nodes at the same time after the calculation, before proceeding with the next round of movement.

Within each simulation step, the current simulation time (with precision of seconds) is known. The move direction has been determined geometrically, and the node location is of course known. Each node then invokes a function which can return the spread rate for that place, time and direction.

This speed function is external to the Tirailleur model: the host or context program is free to implement any appropriate spread rate calculation method. Typical input values for this calculation might be for example wind speed and direction, slope intensity
and direction, fuel type and fuel moisture. Tirailleur is perfectly ignorant about the mechanism for this calculation: all that it requires is a reference to a function which can provide the answer.** **

As the simulation proceeds, and the nodes move outwards, the distance between them increases. New notes can be inserted so that an adequate density of nodes is maintained to keep the perimeter flexible and descriptive. After each simulation step of node movement, new nodes are inserted between nodes whose inter-distance has increased above some threshold value. The new nodes are inserted mid-way along a line drawn between the two neighbours, and the neighbor assignments of the three nodes are adjusted to include the new node in the path.

In some parts of the perimeter, nodes may converge together. When they are too close, their information value is low. Extra nodes can be removed from the path. After each movement step, each node’s distance from its next neighbour is checked against a threshold value and if the distance is too short, then the neighbour is removed from the path. The remaining node and the node after the removed node are then joined together, so as to become adjacent in the path.

The model behaviour depends on the interaction between these two threshold distances. We’ve found that the removal threshold should be just less than half the insertion threshold. This avoids hysterical change in the node population.

The magnitudes of these threshold distances give the perimeter its precision and scale. What’s appropriate depends on the size of the fire and the resolution of the spatial data available. For Italian wild fires, we have found that an insertion threshold of four metres seems appropriate. It’s of course easy to adjust this value for experimentation or different cases.

Tirailleur supports a variable simulation time step, and the optimal approach is to adjust the time step constantly as the simulation proceeds. Because there is a separation between the movement calculation phase (direction and rate) and the implementation
of this movement, it’s possible to establish the maximum movement rate of the nodes in the path before their actual moves are executed. The time step can therefore be calculated to be as long as possible (for computational efficiency) while avoiding
the risk of introducing ‘tangles’ in the path by moving the nodes too far.
** **

It’s possible for the perimeter to become tangled, so that the path crosses itself. Then the modelling becomes messy and unstable. This is a well-known problem with perimeter movement algorithms such as Tirailleur. In Tirailleur, the problem can arise because of an acute invagination caused by a node which is moving slower than its neighbours. If the node’s neighbours are not neatly aligned, then the move direction for the lagging node can be deflected. If there is a sudden acceleration of the lagging node, then it can jump across the line, causing a tangle. See the diagram below.

We have experimented with various ways to avoid this problem. The variable time step approach described above is an effective way to prevent these cross-overs, as well as making the overall simulation run more efficiently. The time step is limited so that no single node will move so far as to make cross-over possible (in practice this means half the minimum distance between two nodes). So regardless of the direction of movement, the nodes will not cross other sections of the path. The proximity node removal then makes sure that ‘danger’ nodes will be removed from the path.

The fire perimeter may develop areas of invagination (where the fire has been held back in one place by local conditions) and areas of extrusion (where the fire in one place has surged ahead of the main fire line).

Extrusions are useful and significant parts of the fire behaviour and need to be maintained. This is an important mechanism for rapid fire advance.

Invaginations are also a real ecological feature, and may be useful for some kinds of fire operations modelling. For example, they might indicate areas which would be left unburned completely or could be successfully defended.

If the fire line surges past the slow rate are and recombines, then it presents a problem. As the nodes converge, the invagination becomes an island, and the nodes will actually cross the fire line and introduce a tangle or contortion.

Our algorithms detect when the invagination is about to be closed by examining the proximity between non-neighbouring nodes, and detaching the invagination from the main fire line. This is a computationally intensive task, which must be performed after each round of node movements. We have introduced various methods which optimise the operation.

The task consists of parsing the nodes and discovering when two non-adjacent nodes are spatially proximate. Then it must be determined whether the intervening segment of line is an invagination (problem) or extrusion (not a problem). Finally, the intervening nodes need to be removed from the line by reassigning the spatially proximate nodes to be sequential neighbours.

It’s possible to maintain the detached segment of the path as a new path, and continue simulating its development. The detached path is automatically a new path with nodes arranged in an anti-clockwise order. If their movements are simulated, then the path contracts as the island of unburned fuel is gradually consumed.

Maintaining these paths in the simulation might be useful and interesting in some cases, but is not handled in our current version of the algorithm.

As the path grows to include many hundreds - or thousands - of nodes, the computations demanded to perform all these checks become more time-consuming. We’ve found that even with non-optimised implementations of the code, the performance remains acceptable until the fire grows to be larger than those normally encountered in Mediterranean Europe.

The simulation algorithm described here is more or less deterministic (assuming that the ROS calculator is not using any random methods). Information is lost when nodes are created and destroyed, but generally the line form is evolved without lossy transformations. This allows the simulation to be run in reverse.

Given an active fire perimeter, it is possible to run the simulation backwards. If the ROS values match those when running forwards, the nodes’ movements will approximately match a forward running simulation, and may eventually lead back to the fire origin.

The reverse simulation is achieved by reversing the spread rate for each node (multiplying by -1). The spread direction is still ‘outwards’, but the spread distance becomes negative outwards: i.e. inwards, and the perimeter contracts. This is a significant point: it’s not a matter of reversing the direction, but of reversing the spread rate. We can use the same rules for node population adjustment (proximity thinning and insertions) as for an expanding line. In most cases these work appropriately.

There are several limitations. If the fire perimeter is in places completely inactive (the spread rate is exactly zero), then there will be no reverse movement. For this reason, spread rates of zero should probably be represented as near-zero. If parts of the perimeter were extinguished at different times, then the reverse simulation will not match correctly. Node construction and destruction are not evenly balanced in this method, so running forwards and backwards will give differences in the population history. Finally, if there is a slow-burning island in the fire area, and this slow burning island is eventually burned out, then the reverse simulation will not model this correctly.

If these limitations are kept in mind, the operation of this model in reverse is perfectly sensible and may yield correct and useful results.

We have uploaded a reference implementation of the algorithm to the CodePlex public source code repository at http://tirailleur.codeplex.com/. There are two projects: a core implementation of the algorithms (organised as a DLL) and a small demonstration program which illustrates how the algorithms can be used.

The code is written in Microsoft Visual Basic for Microsoft Visual Studio 2010. It should be possible to inspect, run and compile the code using the freely available Express Edition of Visual Basic 2010 (http://www.microsoft.com/visualstudio/eng/products/visual-studio-2010-express).

Ends.

Last edited Oct 5, 2012 at 7:06 AM by DuncanHeathfield, version 4