Energetic Path Finding Across Massive Terrain Data

Before there were airplanes, cars, trains, boats, or bicycles, the primary means of transportation was on foot. Unfortunately, many of the trails used by ancient travelers have long since been abandoned. We present a software tool which can help visualize and predict where these forgotten trails might lie through the use of a human-centered cost metric. By comparing the paths generated by our software with known historical trails, we demonstrate how the tool can indicate likely trails used by ancient travelers. In addition, this new tool provides novel visualizations to better help the user understand alternate paths, effect of terrain, and nearby areas of interest. Such a tool could be used by archaeologists and historians to better visualize and understand the terrain and paths around sites of historical interest. This thesis is a continuation of previous work, with emphasis on the ability to generate paths which traverse several thousand kilometers. To accomplish this, various graph simplification and path approximation algorithms are explored to construct a real-time path finding algorithm. To this end, we show that it is possible to restrict the search space for a path finding algorithm while not disrupting accuracy. Combined with a multi-threaded variant of Dijkstra's shortest path algorithm, we present a tool capable of traversing the contiguous US, a dataset containing over 19 billion datapoints, in under three hours on a 2.5 Ghz dual core processor. The tool is demonstrated on several examples which show the potential archaeological and historical applicability, and provide avenues for future improvements.

Name thesis:degree_name

MS in Computer Science

Discipline thesis:degree_discipline

Computer Science

Year dc:date.available

2009

Author dc:creator

• Tsui, Andrew N

Contributors dc:contributor

• Zoë Wood

• Graphics
• Massive Data
• AI
• GIS
• Archaeological Anthropology
• Artificial Intelligence and Robotics
• Graphics and Human Computer Interfaces

Identifier

10.15368/theses.2009.67

OAI identifier oai:identifier

oai:digitalcommons.calpoly.edu:theses-1124