Master theses

Help amateur hikers to find their way through the woods

Keywords: Data Science, Algorithms, Graphs, Hiking, Route Planning

Supervision: Pieter Colpaert

Students: max 1

Imagine it’s the summer of 2020, you are allowed to go outside again but long-distance travels are still impractical. You decide to go hiking in the Ardennes, possibly for the first time since graduating high school. There are sites that publish hiking trails you can follow, so you pick one with good reviews that looks sufficiently challenging because you have barely left your house in half a year and want to feel alive again. The instructions say to follow the yellow triangle, which you do for a few hours, until you get to an intersection where you have to choose between a blue square or a red circle. Confusion fades into the realization that you missed a sign somewhere. You have always been able to rely on Google Maps to get you home, but this time it’s just showing you’re in the middle of an unnamed green shape as they never mapped these hiking trails. You are alone.

Chances are you’ll still find your way home, most hiking trails in the Ardennes aren’t that long and you there are plenty of other hikers to ask for guidance. Still, it would be nice to be able to have an application on your phone that could tell you which trails to follow if you want to get home. A more experienced hiker might already have a GPS tracking application on their phone, which they use to never get off-track -- but where is the fun in that? You went hiking to stop staring at screens the entire time, you want to look at the outside world for once.

What you really want is a route planning application that shows you the way, but can adapt the route when you inevitably make a mistake. Hiking trails aren’t well defined like regular roads are, so we cannot simply build a network graph and rely on established route planning algorithms. However, there are numerous sources of GPS traces of people’s hikes, and if we can extract an estimated network graph out of these, we can plan routes over them.

The goal of this research is to extract a network graph from GPS traces, building the actual route planning application is optional but welcome. Many municipalities and intercommunales publish traces on their own websites, which are free to use for any purpose. We would propose to focus on a single region with a sufficiently high amount of hiking trails, with traces from different sources as not all of the traces will be of the same quality.

As we would rely on open data, we want the resulting network graph to be publishable as open data as well. This would enable other applications, such as the OpenStreetMap project, to potentially integrate these trails as well. We currently have a Linked Data vocabulary to publish the road network from OpenStreetMap, which may be used as an inspiration to publish the hiking trails as well.