Accession Number : ADA325056

Title :   Shortest Path Planning on Topographical Maps.

Descriptive Note : Master's thesis,

Corporate Author : MISSOURI UNIV-COLUMBIA

Personal Author(s) : Vanputte, Michael A.

PDF Url : ADA325056

Report Date : MAY 1997

Pagination or Media Count : 56

Abstract : This thesis introduces a new algorithm for quickly answering repetitive least cost queries between pairs of points on the Earth's surface as represented by digital topographical maps. The algorithm uses a three step process; preprocessing, geometrically modified Dijkstra search, and postprocessing. The preprocessing step computes and saves highly valuable global information that describes the underlying geometry of the terrain. The search step solves shortest path queries using a modified Dijkstra algorithm that takes advantage of the preprocessed information to 'jump' quickly across flat terrain and decide whether a path should go over or through a high cost region. The final step is a path improvement process that straightens and globally improves the path. Our algorithm partitions the search space into free regions and obstacle regions. However, unlike other algorithms using this approach, our algorithm keeps the option of passing through an obstacle region.

Descriptors :   *COST ANALYSIS, *MATHEMATICAL PROGRAMMING, ALGORITHMS, OPTIMIZATION, TWO DIMENSIONAL, THESES, TOPOGRAPHY, DIGITAL MAPS, PREPROCESSING.

Subject Categories : Operations Research
      Economics and Cost Analysis

Distribution Statement : APPROVED FOR PUBLIC RELEASE