Deriving New Minimum Cost Pathways from Existing Paths

Beginning of article

Introduction

Geographic Information System (GIS) "based cost spreading techniques are widely used to find minimum cost paths from specified starting point(s) to specified ending point(s). These raster-based techniques assume that the costs of traversing each raster cell within the area of interest are known. In general, cost spreading algorithms require as inputs:

* The locations of the starting and ending point(s);

* A raster database that describes the cost of traversing each raster cell in the study area; and in the case of anisotropic costs;

* Additional databases and/or mechanisms that allow the cell traversing costs to be modified to account for the direction of travel.

The output of cost-spreading analysis is typically a new raster database showing the minimum-cost path connecting the starting point/ending point pair that produces the smallest total traversing cost of all possible pairs of starting and ending points. The cost-spreading algorithms that generate these outputs employ a form of dynamic programming, which offers a reliable and relatively efficient way of solving what on its surface appears to be a fairly formidable problem (Huriot et al. 1989; Smith 1989).

Cost-spreading techniques have been used in applications as diverse as finding routes for forest access roads (Dean 1997) to analyzing networks of blood vessels in medical imagery (Olabarriaga et al. 2003). However despite their apparent differences, all previous applications of cost spreading share a common assumption; specifically, they all assume that traversing costs are known a priori. This reliance on a priori cost definitions has prevented cost-spreading techniques from addressing at least one common set of problems. These unaddressable problems require deducing traversing costs from existing minimum cost pathways and then using these deduced costs to find new pathways. For example, consider a situation commonly encountered by natural resource managers. These managers are frequently required (often by law but always by the dictates of good management practices) to develop and evaluate a range of alternative management plans before selecting a final plan to implement within the area under their control (Cutter and Renwick 2004). Each of these alternative plans may involve the development of new access roads and/or trails. If conventional cost-spreading techniques are to be used to find minimum cost routes for these new paths, it is necessary to conduct in-depth studies to determine path building costs throughout the area of interest. This is often financially impractical (Dean 1997; Liu and Sessions 1993). However, the study area often includes existing roads and/or trails. Clearly, managers in these situations could benefit from a mechanism whereby they could use existing roads and/or paths to deduce traversing costs, and then use these deduced costs in standard cost-spreading procedures to identify minimal cost paths for new proposed roads and/or paths.

This study presents a technique for estimating traversing costs from an existing minimum cost path. It is assumed that an existing minimum cost path is present and that the components of traversing costs are known (e.g., road-building costs may be a function of slope, gradient and soil type), and that traversing costs are a linear combination of their component costs (e.g., road-building costs from the previous example could be computed as a linear function of slope, gradient, and soil type). Unknown will be the parameters of the linear equation that constructs traversing costs from its components. I will start by presenting techniques for estimating these parameters in the isotropic case. I will then extend these techniques to include the anisotropic case. Both cases will be illustrated using example problems.

Case 1: Isotropic Traversing Costs

Assume that a minimum cost path exists from starting point [P.sub.s] to ending point [P.sub.E] . Let the set of raster cells that make up this minimum cost path be set [[theta].sub.MC]. Further, let all other possible sets of cells making up non-minimum cost paths connecting [P.sub.s] and [P.sub.E] be sets [[theta].sub.1], [[theta].sub.2], [[theta].sub.n], where n is the number of possible unique, non-minimum cost paths connecting [P.sub.s] and [P.sub.E]. Note that these sets may be nonexclusive; i.e., it is possible for any given raster cell to occur in multiple paths, and thus fall into multiple [[theta].sub.x] sets. However, no two [[theta].sub.x] sets can be identical; identical sets would represent duplicate paths, which are not allowed.

Also assume a raster database of cell traversing costs is available. Each cell within this database contains the cost of traversing the length of the cell. Since the current discussion concerns isotropic costs only, the cell traversing costs recorded in this database apply regardless of direction of travel; e.g., traversing 10 meters through a raster cell that is 10 meters on a side and contains a traversing cost of TC costs TC units, regardless of whether the traversing involved occurs north to south, east to west, or northeast to southwest. Finally, assume that these cell traversing costs are uniformly distributed throughout each cell. This allows us to make the critical assumption that if a cell of width W has a cell traversing cost of TC, traversing a distance of 1/2 W costs 1/2 TC, and so on.

The total cost of traversing any given path is the sum of the costs of traversing from the center of each cell in the path to the center of the subsequent cell along the path (Dean 1997). Furthermore, by definition, the cost of traversing the minimum cost path must be less than the cost of traversing any of the non-minimum cost paths. If the cost of traversing the [i.sub.th] cell along any path, which occurs in row [r.sub.i] and column [c.sub.i], is denoted as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] * and a function called Diag([r.sub.i], [c.sub.i], [r.sub.i+1], [c.sub.i+1] is defined to assume a value of 1 if cells [r.sub.i], [c.sub.i] and [r.sub.i+1], [c.sub.i+1] are directly adjacent to one another, and [square root of 2], if they are diagonally adjacent, these two observations lead to Equation (1).

(1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] For all non-minimum cot paths k

The first summation in this equation walks through all the cells along the minimum cost path and computes the total cost of traversing this minimum cost path. Each item within this summation computes the cost of traversing from the center of the current cell along the path (the cell in row r and column c,) to the center of the subsequent cell along the path (the cell in row [r.sub.i+1] and column [c.sub.i+1). The cell-center-to-cell-center cost is the average of the traversing costs of the current and subsequent cells, multiplied by Diag. This follows from the definition of cell traversing costs and our assumption that traversing costs are uniformly distributed throughout each cell. Recall that a square raster cell that is W linear units on a side and contains a traversing cost of TC indicates that the cost of traversing a linear distance of W units through that cell costs TC cost units. Since the distance from the center of a cell that is W units wide to the edge of the cell is 1/2W, the cost of traversing that distance must be 1/2TC. Furthermore, the distance of traversing from the center of a cell to any of its corners is 1/2 [square root of term]2 W, and the cost of traversing that distance is 1/2 [square root of term]2TC (Figure 1) (Dean 1997).

[FIGURE 1 OMITTED]

The second summation in Equation (1) is identical in concept to the first but walks through the cells in non-minimum cost path k (and thus computes the total cost of traversing path k) rather than the minimum cost path. Thus, the inequality in Equation (1) reflects the obvious truism that the minimum cost path must be less costly to traverse than any non-minimum cost path.

Given our previous assumptions, traversing costs are linear combinations of their constituent components. Thus, for any cell i:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE …