Using Regions of Interest for Personalized Route Planning

Abstract

There is an abundance of services and applications that find the most efficient route between two places, but people are not always interested in efficiency; sometimes we just want a pleasant route. Such routes are subjective though, and may depend on contextual factors that route planners are oblivious to. One possible solution is to automatically learn what a user wants, but this requires behavioral data, leading to a cold start problem. Moreover, this approach falls flat when someone wants to try something new, as users become locked in filter bubbles. An alternative approach is to let the user express their desires explicitly, effectively helping them create the most pleasant route themselves. In this paper we provide a proof of concept of a client-side route planner that does exactly that. We aggregated the Point of Interest information from OpenStreetMap into Regions of Interest, and published the results on the Web. These regions are described semantically, enabling the route planner to align the user’s input to what is known about their environment. Planning a 3 km long pedestrian route through a city center takes 5 seconds, but subsequent adjustments to the route require less than a second to compute. These execution times imply that our approach is feasible, although further optimizations are needed to bring this to the general public.

Introduction

Route planning applications have become so common that many, such as Google Maps, have almost become household names. The majority of these applications focus on generating the most efficient route, even though people are not always interested in efficiency. Some people may want to enjoy the first days of good weather by making a small detour through a local park, others may want to avoid the same park because of allergies. There are also pragmatic reasons for wanting to avoid certain places: shopping streets can get overcrowded on Saturday afternoons, and parks may also get overcrowded – which can be a problem during pandemics for instance.

The list of examples goes on, which is exactly the problem we address in this paper: the ideal route depends on personal preference and contextual factors, many of which are subjective and change over time. Instead of trying to predict what a user wants, we propose to let them specify their preferences explicitly through an interactive application.

Method

We propose to drop the assumption that user preferences have to be predicted, or learned, and instead develop a proof of concept application that asks the user for their preferences explicitly. Users have the ability to personalize their own route, which is not only a solution to the data availability problem, it also puts the user back in control of the results they see.

At the core of our approach lie Regions of Interest, which contain several Points of Interest (POIs) such as shops, public parks, restaurants, etc. These regions are then intersected with the road network to add additional weights to the route planning graph, based on the user’s preferences. We use the publicly available POI data from the OpenStreetMap project1, and apply density based clustering to aggregate them into discrete regions. Each region is semantically described, as illustrated in Listing 1, and the results are published through a Linked Data Fragments interface, similar to our existing Routable Tiles dataset [10].

The details of the regions are generated are out of scope of this paper; we focus explicitly on how they can be used. In fact, these details are also hidden from the route planner, and so are the exact POIs within each region. This is a conscious decision, because as discussed in Section 2, imprecision causes users to explore more actively.

[
    {
      "@type": "owl:Restriction",
      "owl:onClass": "osm:Entity",
      "owl:onProperty": "osm:hasTag",
      "owl:someValuesFrom": [
        "taginfo:shop=bicycle",
        "taginfo:shop=hardware",
        ...
      ],
      "@id": "_:CommercialEntity"
    },
    {
      "@id": "_:fuzzy_subject",
      "rdfs:subPropertyOf": "dct:subject",
      "truth:degree": 0.21052631578947367
    },
    {
      "geo:asWKT": "POLYGON ((3.0016827 51.2498880, 3.0018188 51.2496799, ...",
      "_:fuzzy_subject": "_:CommercialEntity"
    }
]

Listing 1: JSON-LD representation of a single Region of Interest. Each region is described using terms from the GeoSPARQL vocabulary, and a subject property from dcterms refers to a description of the region’s contents. These descriptions use OWL restriction classes to group similar kinds of POIs together. To reflect the nature of the density-based clustering, we use a self-defined truth:degree property to add a degree of truth to the subject property.

Demonstrator

The demo in Fig. 1 works on all devices with a modern web browser, including mobile devices (in landscape mode), and computing a route for the default scenario takes roughly 5 seconds with subsequent adjustments taking less than a second.

Fig. 1: By default the demo calculates a route from the historic center of the city of Ghent to the train station, roughly 3 km apart. The different kinds of Regions of Interest are visualized on the map: green indicates nature, blue indicates shops, and orange-red indicates historic buildings. The red route shows the most efficient route, the blue route incorporates the user’s preferences. Try moving the shops slider all the way to left, and hit the plan button.

Discussion

As mentioned in Listing 1, our route planner only has a limited view of reality. It has a vague idea of where the shops are, but not which shops exactly, or how many. This information could be added through an additional data source, however the imprecise aggregated data has some interesting implications. The obvious one is that using aggregated data is less resource intensive; there is less data to process, and the processing itself is easier. One could start from the raw data, but this would add more workload to the client, and as noted in Section 2, personalized route planners are already computationally intensive.

Working entirely with intentionally imprecise data can also be a pragmatic solution to working around data quality issues. For example, it does not matter if the base data contains 20 out of 50 restaurants on a single street – it’s a street with many restaurants. Clients are also shielded from the data model of the raw data, which means that even non-semantic data sources can be used, assuming some mapping happens during the aggregating.

The incompleteness of the results should also cause users to more actively explore their environment by presenting less complete information. Ultimately, this apparent loss of user experience should result in unexpected discoveries, users might be presented with serendipitous discoveries that are known to increase overall user satisfaction [11].

Conclusion

Our goal has been to provide route planners with the necessary information that is necessary for personalized route planning. We approach this problem by letting users provide their current preferences explicitly, which are then cross-referenced with a set of Regions of Interest to add additional weights to a road network. As a proof of concept, we have built a publicly available application that demonstrates the underlying principles while planning a route from the historic center of Ghent to the train station. Finally, we discuss how the aggregated regions of interest, although imprecise, should in theory yield a better user experience.

  1. Available as Linked Data Fragments, e.g. at https:/​/​opoi.org/14/8411/5485/