Running into the unknown with RunAhead

Finding pleasant running tours and intuitively navigating through them

The use of combinatorial optimization and UX design, together with head-tracking technology, provides a non-intrusive way of helping runners to discover new itineraries.

Running is one of the most popular forms of exercise around the world. It doesn’t require special equipment or complex organization and can be practised almost anywhere. In principle, runners have the freedom to just put on their shoes and go.

However, runners often refrain from doing this—especially in unknown environments—when they don’t know where to go or fear getting lost (1). Indeed, in new environments, it’s not easy for runners to find a pleasant itinerary that matches their constraints and targets in terms of distance and difficulty. Even in the instance that they do manage to find an itinerary that suits their needs, they may not want to try it out due to related challenges (i.e. needing to remember the route or having to rely on cumbersome navigation support to follow it). As we will see, itinerary identification and efficient navigation support for running are in fact pretty complex and complementary problems.

As outdoor sport enthusiasts and scientists, we asked ourselves the question: How can we help runners find pleasant itineraries that match their personal preferences, and then smoothly guide them along these routes?

Among the currently available commercial systems, most (e.g. Garmin, Strava and RunGo) propose itineraries by exploiting user-generated content (i.e. existing collections of running traces) combined with standard visual map-based or voice-based navigation support. However, these approaches have many limitations. First, in terms of itinerary generation, relevant running traces are not always available in a given area. Even in densely populated areas, people are increasingly likely to want to protect their privacy and might therefore prefer not to share their traces. Constructing a tour based on a limited number of traces can be difficult, or even impossible. Although there are a few approaches that generate itineraries using only map data, most of them remain quite basic (e.g. they are based on geometric approaches that don’t take the environment into account, or they consider the environment but limit the user preferences to the distance only). Second, existing navigation support systems are problematic because even those that allow a user to follow an itinerary are often distracting and can disrupt the running activity (2, 3). Visual map-based navigation requires runners to regularly look at their phone or smartwatch, while voice-based guidance requires constant attention from users, who otherwise risk missing an indication.

The objective of our work was to create a solution that generates novel and pleasant itineraries (4, 5), without requiring the availability of running traces, and that provides efficient navigation support which reduces disruption and is pleasant for the runner.

Before designing our solution, we carried out a user study to better understand runners’ needs. The results showed that as well as searching for itineraries that match their personal objectives, runners also desire itineraries to be flexible. In other words, they prefer itineraries that they don’t have to strictly follow from beginning to end, and from which they can deviate during their run. We therefore designed our solution with this additional feature in mind.

Generating pleasant running tours

With the aim of generating pleasant itineraries, we began by formalizing what makes a path pleasant for a runner. We consider the pleasantness, or quality, of an itinerary as the extent to which its characteristics match runners’ preferences. We split this quality into two aspects: the quality of the path segments that compose the itinerary; and the form, or geometry, of the whole path. The quality of every path segment depends on various criteria (e.g. whether it’s a pedestrian path, as well as its environment and proximity to traffic) that must be translated into a numerical score that can be used as input to the itinerary-generation algorithm.

Using OpenStreetMap (OSM) data and standard routing libraries, we began by building a routing graph. The nodes of this graph are the road crossings, and the arcs are the road segments that link the crossings. Then, based on OSM attributes, we computed a pleasantness score for each arc according to standard runners’ preferences. For example, paths along hiking trails, parks or riversides were assigned a much higher score than paths close to main roads or motorways.

Given the scored routing graph, a starting point, a target distance and an elevation gain, we focused on generating appropriate tours—i.e. loops of the requested length—that maximize the pleasantness score on the visited arcs. We formulated this optimization problem as an arc-orienteering problem, which can be seen as a combination of two well-known NP-hard problems: a knapsack problem, where the goal is to select the best locations on a map for the runner within a (distance) budget constraint; and a travelling salesman problem, where the goal is to find the shortest route that visits these locations.

To solve this problem, we proposed a heuristic algorithm based on a greedy randomized adaptive search procedure (6). Starting from a trivial short tour, the algorithm iteratively computes possible extensions of the current tour and randomly selects one among the best of these to increase its length. This procedure can be repeated until no improvement is found, or the processing time limit is reached (see Animation 1(a) below). There’s a trade-off parameter that balances the greediness and randomness of the algorithm to allow for an efficient exploration of the solution space; the algorithm can be executed in parallel with different trade-offs to produce a variety of results.

While this method allowed the computation of high-scoring tours, we observed that some artefacts can appear, such as artificial detours (those that a user would never choose to take) and generally unnatural-looking paths (involving many unnecessary turns). This wasn’t surprising, since we were only focusing on the score. To improve the geometry of the results, we designed a post-processing step that smoothens the tours: see Animation 1(b). We were also able to rank the generated tours according to their geometric properties (e.g. number of turns) to favour the simpler, more natural-looking ones.

As pointed out by our user study, runners appreciate flexibility in their itineraries and like to feel free to modify them as they go. Sometimes, they’re simply unable to follow the proposed path due to unplanned factors (e.g. construction work, the weather or tiredness). Also, since it’s impossible to account for the subjective preferences of every runner, we believe it’s important to acknowledge that users know best. To ensure they get the most pleasant run, we should support them by adapting the proposed itinerary to suit their needs.

To support such flexibility, we provide a set of alternative paths—see Animation 1(c)—that may be interesting to explore for the runner with each computed tour. The idea behind this is to highlight alternatives to subsections of the original tour that are roughly equivalent, or better, in terms of pleasantness. In addition, we allow users to change their duration or distance targets at any time, and dynamically update the tour accordingly, using a variant of our main heuristic. This makes it possible for runners to deviate and explore beyond the precise initial itinerary, while still ensuring that the quality of the run matches their preferences.