* Faculty       * Staff       * Contact       * Institute Directory
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Events       * Institute Events      
* Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Path Planning on a Compressed Terrain

By Daniel Tracy
Advisor: W. Randolph Franklin
April 30, 2009

We present an algorithm for path planning on complex terrain in the presence of observers, and define several metrics related to path planning to evaluate the quality of various terrain compression strategies.

The path-planning algorithm simulates a smugglers and border guards scenario. First, we place observers on a terrain so as to optimize their visible coverage area. Next, we compute a path that a smuggler would take to minimize detection by an observer, path length, and uphill movement. The smuggler is allowed the full range of Euclidean motion on the 2-dimensional plane, unlike alternate path planning schemes that strictly avoid obstacles. We use two runs of the A* algorithm to efficiently compute this path.

Our path-planning routine is used to evaluate the quality of terrain compression on the smugglers and border guards scenario.

We also present an extension of the ODETLAP compression method to include slope equations, rather than using elevation data only, to specifically target the compression of terrain slopes.

Effective terrain compression strategies have become even more crucial with limited bandwidth capacity and the increasing size of elevation datasets. We introduce new application-specific error metrics for evaluating lossy terrain compression. The target terrain applications are the optimal placement of observers on a landscape and the navigation through the terrain by smugglers. The error metrics compare the observer visibility and the cost of the optimal smuggler's route on the reconstructed terrain to the original terrain.

* Return to main PhD Theses page