Techniques for improving routing by exploiting user input and behavior

Abstract

This dissertation explores innovative techniques for improving the route finding process. Instead of focusing on improving the algorithm itself, I aim to improve the other factors that make the route finding experience better: personalization, map data, and presentation. I do so by making extensive use of user input (both explicit and implicit) and crowdsourcing strategies. This research uses Cyclopath, a geowiki for cyclists in the Twin Cities, MN, as a case study for the various techniques explored.The first challenge is the lack of personalization in route finding algorithms. Aside from start and end points, algorithms usually know very little about users. However, user preferences can greatly affect their ideal routes. I studied the use of community-shared tags that allow users to specify preferences for those tags instead of doing so for each individual road segment, allowing them to easily express preference for a large number of roads with little effort. Correlation between individual road segment ratings and ratings deduced from tag preferences was evidence of the utility of this technique for making personalization easier.The second challenge is missing data. The best routing algorithm is only as good as the map data underneath it. Unfortunately, maps are often incomplete. They might not have updates on the latest construction, might be missing roads in rural areas or might not include detailed information such as lanes, trails, and even shortcuts. I present an HMM-based map matching algorithm that uses GPS traces recorded by users to generate potential new road segments. Tests within Cyclopath confirmed the abundance of missing roads and the ability of this algorithm to detect them.Finally, I look at the issue of unnatural presentation of routes. The way computers relay route directions is very different from humans, who use landmarks most of the time. However, gathering useful landmarks can be difficult and is often limited to points of interest. In this research, I tested methods for crowdsourcing different types of landmarks. I show that POIs are not sufficient to represent landmarks and that there is no objective truth regarding which landmarks are more useful to users.