The Road Not Taken: Creating a Path-Finding Tool Using Consumer-GradeGPS EquipmentAllison [email protected] [email protected] automate the organization of GPS datato create a visibility map with correctlyconnected intersections. For our exam-ple case study, we use GPS data collectedon the Swarthmore College campus. Af-ter the data is automatically organized andcleaned, a user is able to select points ona visual map to search for an optimal pathbetween those points.1 The Problem of NavigationSwarthmore College, set in the beautiful Scott Ar-boretum, has many scenic routes and winding pathsbetween the lovely stone buildings. This serene set-ting is wonderful for long walks, but can be trou-blesome in trying to navigate from one’s dorm to aclassroom when one is half-awake and running be-hind schedule. In order to assist the poor, sleep-deprived students of Swarthmore College, we cre-ate an interactive map of the campus to help usersdiscover the appropriate paths between the variousbuildings on campus. In doing so, we develop aset of tools that can easily create similar systems fordata collected in other locations.1.1 Previous WorkAnother group worked on a GPS path-planningproject for last year’s Senior Conference (Singletonand Woods, 2007). Because their data required quitea bit of manual editing, their system would not eas-ily scale to larger data sets. We also noticed thattheir interface was difficult to understand immedi-ately. Taking these challenges into account, we cre-ate a scalable, user-friendly path planning tool.We used a large amount of previous researchto build our tools. Most notably, Dijkstra’s algo-rithm (Dijkstra, 1959; de Berg et al., 1997) andthe more general A* search algorithm (Hart et al.,1968) have been developed to find appropriate pathsthrough our spatial graph. We also implement animproved version of the Douglas-Peucker line sim-plification algorithm (Hart et al., 1968).1.2 Approaches to Path PlanningPath planning is essentially a least-cost graphsearching problem, a task for which several algorith-mic variations have been developed. In the past, Di-jkstra’s algorithm has been widely used for this task,but we implement the A* search algorithm, which isa generalization of Dijkstra’s approach that is bothcomplete and optimally efficient. In typical situa-tions, A* performs slightly faster than Dijkstra’s al-gorithm because it uses a heuristic to help decidewhich search paths are most promising. This processminimizes the size of the subgraph to be explored.2 ImplementationThis project consists of three main parts: data collec-tion and processing, path planning, and UI develop-ment. The first two parts center on problem solvingusing computational geometry while the third pro-vides easy access to the results.2.1 Data Collection and ProcessingWe use self-collected GPS data for our finished map-ping system. Swarthmore College kindly providedtheir survey plans for use with this project, but dueto a lack of time, we were not able to complete anintegration of this data into our user interface. Weprioritized our work with the GPS data, even thoughthat data is not as precise, because we wanted oursystem to be useful in creating mapping systems inother situations where no such detailed survey planshave been prepared.2.1.1 GPS Data CollectionOur main dataset is GPS tracking data recordedby walking the paths of Swarthmore’s campuswith a consumer-grade GPS receiver, the GarminGPSmap 60CSx. For consistency, we carried theGPS receiver at about waist-height and walked onthe center of each footpath, recording tracks ofwhere we had walked and marking a waypoint eachtime we encountered a path intersection. We usedGPSBabel to transfer data from the Garmin unit tothe GPX format, an XML-based file format that in-cludes latitude, longitude, elevation, and timestampdata. We collected GPS data for virtually all exteriorpaved footpaths on the Swarthmore campus; in con-trast to last year’s project, we did not record indoorfootpaths because of the inability to collect GPS dataindoors with inexpensive equipment and our desireto avoid manual editing of the collected data (Sin-gleton and Woods, 2007).2.1.2 GPS Data ProcessingOur pre-processing algorithms find clusters ofpaths with geographically nearby endpoints. We as-sume that these paths intersect at a common point, sowe reassign the endpoint coordinates of all paths in acluster to the arithmetic mean of the endpoint coor-dinates in that cluster. While this approach is fairlynaive, we found that it works quite well in prac-tice with the relatively coarse resolution captured byconsumer-grade GPS equipment.We experimented with simplifying the data as afinal processing step, hoping to reduce the computa-tional power needed for both the user interface dis-play and our path-finding algorithms. We use theDouglas-Peucker line simplification algorithm to doso. This, however, was not particularly helpful forthis particular application in part because of the rela-tively infrequent position sampling provided by ourequipment. Also, we constructed our search graphon adjacent path intersections, ignoring the com-plexity of the path segment between those intersec-tions, which is an even more efficient simplificationfor searching purposes. It is important, however, toexplore the practicability of such simplification tech-niques for use with larger, higher-precision datasets.At the end of these pre-processing steps, the re-sulting data is saved as latitude, longitude, and ele-vation tuples for each meaningful point of each pathsegment. Figure 1 shows a clear difference betweenour raw data and the same data after being processedwith our programs.Figure 1: Before and after data processing cleanupon a subset of our GPS dataFigure 2: GIS overlay of our GPS data and the sur-vey drawings2.1.3 CAD Survey DrawingsThanks to the maintenance staff at SwarthmoreCollege, we also acquired survey-grade mappingdata for the Swarthmore campus in AutoCAD for-mat. We convert the several layers of data from thesedrawings to the Shapefile format and simplify thedata using the Douglas-Peucker algorithm. The fi-nal output data uses the same simplified data formatdescribed at the end of our GPS data pre-processingalgorithms. We had hoped to use information fromthese drawings as a base layer to help orient usersto the paths as displayed in our user interface, butran out of time before we could complete that ef-fort.