STATISTICS AND SOCIAL SCIENCES STATISTICS AND SOCIAL SCIENCES[Ed: Links to web pages and/or e-mail addresses which have become inactive since the publication of this article have been enclosed in curly brackets { }. Replacement links have been provided where possible.]
Computer mapping -- more technically known as GIS (geographical information systems) -- is one of the hot computer fields. Another, of course, is the World-Wide Web.By this time we all know that the Web is entertaining and makes masses of information available. But it can also be a serious tool. The single interface of the graphical Web browser now serves as a front end for numerous applications, and the Web's CGI (common gateway interface) scripting offers the possiblity of using that interface to control many other applications. The potential to do complex computing through a Web browser makes the Web page a serious platform-independent computing tool.
At ACF, a prototype Web page is being designed that allows an Internet visitor to act as a planner using GIS to find a politically and financially acceptable route for an oil pipeline.
The problem at hand is to select a route for an oil or gas pipeline -- in this case to connect two towns in the mountains of western South Dakota, an area for which a wealth of detailed data is freely available. This is a real-life land-use problem fraught with political snares, roadblocks, and pitfalls. Favoritism becomes an issue as land values are suddenly distorted near the route; economic development has to be weighed against damage to the environment, scenic devastation, and health concerns -- the real issues are far-reaching and complex. Anyone from a concerned citizen to a government official to a utility engineer might be involved in such decisions and would be affected by the outcome. Ideally, a tool like this Web page will allow infrastructure to develop to the benefit of all.
What, briefly, makes up "spatial data"? Two things -- a map of whatever places are of interest, and data attributable to the places on that map. A place might be a whole state or a ZIP code area or a single house. The attribute assigned to a given place might be virtually anything -- population or water-table depth or sale price or altitude or election district. A GIS uses the location references to reveal relationships within the data.
Most importantly, then, a GIS is a place to store and manage a warehouse of data on a map. Usually, the data are arranged in layers -- tax structure on one, addresses on another, rivers on another, and so on -- and the GIS can display any number of layers together. (Most printed maps display several layers of data, in fact; a common road map displays routes, rivers, populations, borders, etc.) A GIS will also provide functions to answer questions involving the relative locations of the data. A few examples:
These relationships are difficult to calculate with traditional computer tools (programming languages, spreadsheets, databases), and the answers to the questions are more meaningful when the solutions are displayed on a map.
The focus of the GIS research being done at NYU has been on finding the best routes for linear surface-transportation objects, such as oil pipelines.
We all do route-planning all the time, figuring out how to get from home to work, or from one building on campus to another. And we set criteria: we may try out various alternatives and settle on the one that's quickest, or most pleasant, or cheapest, depending on our criteria.
Any route calculation is subject to debate: one that's best under one set of criteria (cheapness, say) won't be by another (time spent); and factors that are ignored in one calculation (environmental impact, political fallout) may have to be factored into another. Projects of this kind can become incredibly complex. In finding the best place for a major construction project like a pipeline, an enormous number of variables come into play. Environment, wildlife, maintenance -- any such factors might ultimately make a selected location seem questionable.
The traditional method of designing these routes has been for an expert to interpret any data and maps available and then to choose the route for a corridor. In order to find an optimal route, one has to keep in mind countless bits of information, such as soil types, slopes, forests, maintenance facilities. And how can someone decide on one route if he has to consider which is better -- to destroy a fragile ecosystem or ensure a long-term energy supply?
Until greater minds than ours attack the problem, a common measure of cost must be assigned to every factor being considered. Any other approach leads to warfare -- spiking old-stand trees to stop loggers, or endless court battles to enrich lawyers. Agreeing to assign dollar costs allows us to come to mathematical solutions and to determine a unique "best." Let's examine this very important conclusion.
As we worked on the best-route problem here at NYU, we came to agree with the literature -- that dollar costs could often be assigned to even the most unlikely situations. Two opponents can't rationally debate the cost to the beauty of a valley when a corridor is cut through the hills. But once alternative routes are costed out, opponents can agree on how much it costs to protect the valley's beauty -- that is, the increase in the project's cost if the less direct route is used. If the county planning team is committed to preserving bird habitats, the cost of using open land in one area can be calculated as the cost of acquiring and "wilding" adjacent farmland.
Contentious issues can be resolved only if a common ground is found. If the common ground is a decision to use dollars as the common metric, to find or assign costs for every variable, the discussion can become more rational. And then both sides win.
(Right) An X-Windows interface developed, using GRASS xgen, by Dr. Yakov Smotritsky for his EARL (Environmentally Acceptable Route). On a Unix machine, the full power of the suite of programs can be brought to bear on the route-planning problem.
Dr. Yakov Smotritsky has been working in the field of computational mapping since his graduate-school days at the Moscow Physics-Engineering Institute. In 1980, Ralph Grishman brought Dr. Smotritsky into a research group at CIMS. Later, Ed Friedman made the ACF high-performance scientific computers available for him to continue his work on what became EARL (Environmentally Acceptable Route Location). In 1993, Smotritsky joined the Statistics and Social Sciences group, which supports GIS at Academic Computing. The same year, he was awarded a National Science Foundation SBIR grant to help further his research. With this funding, he was able to bring students and other researchers, including the authors of this article, into his project. An in-house internship underwritten by Brooklyn Union Gas has supported the Web programming done by two CAS computer-science seniors, Kirill Karpelson and Igor Zheleznyak.The initial focus of the EARL project was on improving the computational methods used by commercial GISs to compute a unique "shortest path." All GISs contain functions or modules that find the "shortest" or "least-cost" path, but existing solutions ignored certain problems that EARL addressed.
The cost of grading depends not only upon the slope of the land but it also upon the soil type and the hydrology. The frequency of anchoring structures is affected by the slope of the land too, but it is also a function of the number of streams the pipeline crosses. Thus the slope of the land contributes to the cost in many ways.
A GIS sees a map as many transparent layers, each involving one mappable attribute, such as slope, existing roads, rivers, or soil type. For our problem we used "grid" maps, in which the map layer is a grid of cells, each 30 meters square. The attribute data for a slope layer would be the average slope of each cell.
Each of the several costs derived from a knowledge of the slope can be calculated on a copy of the slope layer. A table is used to assign the cost of grading the 30x30-meter cells for each slope value. If we add up the slope costs for each cell, we have the total construction costs derived from slope data.
And the sum of all the individual cost layers gives a "total-cost" layer, whose data can be used by the GIS "least-cost" function in its calculations.
Two GISs -- ArcInfo and GRASS (for more details, see the details in the box on GIS programs available at NYU) -- calculate these total-cost layers. They then each calculate a "best" path between the two towns. But their calculus is too simple -- probably written for a slower generation of computers. The path goes from the center of one grid cell to the center of one of eight adjacent cells (four at the sides plus four at the corners), so each vector crossing a cell is limited to eight directions. The paths therefore become jagged (at a micro level), and the results have more error built in than necessary. Smotritsky's work allows the vectors to take any direction, and the results may be as much as five percent better than those of the established packages. In extreme cases, completely different routes may result.
But creative planners can include costs other than buying and building into a cost layer. Giving weights for environmental or aesthetic factors is, of course, more difficult; yet the problems are not insoluble. For example, in the case of wetlands, we may be mandated to follow a rule that there may be no net loss of wetlands within a state, so we assign the value of a wetland to be the cost to replace it elsewhere in the state. And if an area is absolutely untouchable, it can be assigned an infinite cost.
Maintenance costs can also be included in the calculations. One projected route may have a low initial cost but higher maintenance costs than another. Another may be expensive at first but bring benefits to the area in the long run. For example, routing a roadway around a visually valued site would preserve the beauty, which in turn might well bring an increase in tourism or traffic that support new jobs.
Second only to the cost of collecting data, assigning weights to different factors and translating the weights into dollar costs are the most difficult portions of computerized route selection.
(Right) This Web page provides another interface for EARL, as well as for GRASS. Here the Web visitor can change the values for various land types, then see what the "best route" GRASS calculates, and compare that with the one from EARL.
Now all these solutions are being incorporated into a single interactive Web application that allows planning sessions to occur anyplace, anytime. In an NSF report, Professor James Mellet, an NYU geologist, wrote that this method might allow participants in a town meeting to see the issues more clearly. They could immediately see whose backyard the route was traveling through, and what it would cost to make any changes. This could democratize the whole planning process: no more decisions made in smoke-filled back rooms.The visitor to the Web page can get a feeling for this with a protracted session. Economic, ecological, and quality-of-life concerns may be changed by manipulating the data grid between the two towns. The illustration shows the table used to change the data in a specific layer -- in this case, the layer showing soil types. Each soil type has an associated cost for constructing a pipeline across each 30x30-meter cell; a different value can be assigned to any of the soil types, modifying the input to the algorithm, and thus the ultimate "best" path. Other layers can also have costs assigned and reassigned, also affecting the end results: put a wetland here, a mountain there, a historic Native American site in the line of the shortest path. The user may choose to increase the cost of crossing specific land types, say old-stand forests, to infinity, in order to see how much it costs to act on our concerns (that is, Can we afford to put our money where our mouth is?).
Then the visitor runs the route-selection program. Three different answers are returned: three "least-cost" or "shortest-path" routes are computed and displayed, using GRASS, ARCInfo, and EARL. The costs for the three pipelines may then be compared if the visitor is interested in computational differences between the packages. More likely, visitors will be more interested in changing the costs again, in acting like participants from various interest groups. They pose economic and ecological questions that can be answered by manipulating the data grid between the two towns.
Projects of this type can reach hundreds of miles in length and have a significant impact upon the environment. They represent enormous capital investments -- and political minefields. Perhaps GISs and EARL offer a way to clear the fields and arrive at mutually acceptable solutions.
![[ C ]](../icons/CSmSum96.gif){kind=icon}
Posted 20 May 1996. Revised 24 May 2004.
 |
 
|
|
|