Indoor Routing with Valhalla

I have recently done some work on Valhalla’s indoor routing capabilities. There was basic support for it, but many things weren’t working as expected. I believe I was able to improve some aspects, yet there are still loose ends. This blog post is my attempt at describing what changed, where indoor routing with Valhalla is today and what’s yet to be implemented.

Generally, indoor routing was first enabled by simply adding the objects of interest (most notably corridors, stairs, and elevators) to the graph build. Thanks to the OSM schema already encoding topology, this is enough to simply add these components as nodes and edges to the graph. But there are particularities about indoor routing that need special handling, and most of my time was spent on problems specific to level traversal.

Valhalla has functionality to aid with finding candidates on the graph for given input locations. These mostly use the location’s lat/lon plus some additional search criteria to further filter out candidates that may be geographically close to the input location, but are otherwise unfit. This is important for indoor routing, because when you’re on the 3rd floor, it’s not much help when the nearest candidate in two-dimensional space is on the 14th floor.

So the first thing we need to find meaningful indoor routes is to give the user a way to say “I want to start on floor A and want to get to floor B”. Luckily, Valhalla has a notion of search filters and OSM has the widely adopted “level” tag that we can leverage here.

Note on levels in OSM: These can be comma separated single level values or ranges, with support for negative and fractional values. See here for more info.

Hence, I added a new search filter for level that can be used in the following way:

{
  "locations": [
    {
      "lon": 6.999364,
      "lat": 50.964164,
      "search_filter": {
        "level": 2
      }
    }
  ]
  ...
}

This will choose candidate edges that either are on level 2 or that traverse level 2. In order to get the best results, I advise playing with the node snap tolerance. The default of 5m may be a bit high for indoor environments, an can lead to misleading routes when snapping to elevator nodes. Also, bear in mind that using the level search filter will limit the default geographical search space from 35km to 1km. If this is still too much, you can set the search_cutoff per location to something more sensible.

Costing

One of the reasons Valhalla is so widely used is due to its idea of dynamic costing: the user can easily control which edges to favor and which ones to avoid. The same thing should apply to indoor: some users might favor the stairs, some the elevator or the escalator. But here again, the third dimension bites us, since cost is no longer just some function of length and node/edge type, but also of vertical distance traveled. For elevators, there is a difference when traveling 12 floors or just one. Here again, levels can help out: when the user specifies an elevator penalty, we can try looking at the incoming edge and the outgoing edge and multiply the penalty by the number of floors traveled.

For stairs, looking at where we’re coming from and where we’re going is a bit trickier, because Valhalla only looks at the previous and the current edge when deciding the current edge’s cost. This means we would have to keep additional state during graph traversal, which is expensive (especially because of fractional levels, so we can’t just use 8 bit integers). This leaves us with a per-edge penalty. In order for this to reliably work, stairs would need to be modeled as one way per level change in OSM, which is not what the Simple Indoor Tagging schema dictates. For ease of mapping, stairs can be mapped as a single way with a levels range, with corridors on each floor sharing a node with the stairs.

To put it short: considering vertical distance in costing is tricky. If you want to level the playing field and apply cost evenly between stairs and elevators, you need to ignore what the Simple Indoor Tagging schema mandates and go through the extra work of representing stairs as one way per level change.

You can play around with elevator and stair penalties like this:

{
  "locations": [
    // ...
  ],
  "costing_options": {
    "pedestrian": {
      "step_penalty": 300,
      "elevator_penalty": 500
    }
  }
  // ...
}

Display

In order for an end user to reason about level changes along a route, it’s important to mark where they occur. Ideally, we can tell the user exactly which part of the route is on which floor. For this, a level changelog was added, which is a sparse array of shape indices and levels traversed to. It is only present when Valhalla detects level changes along the route. Here’s an example route response:

{
  // ...
  "summary": {
    // ...
    "level_changes": [
      [0, 1], // [shape_index, level]
      [15, 4]
    ]
  }
}

This can be interpreted like this: The route starts on level 1, and changes to level 4 at shape index 15. From there on until the end, it stays on level 4. Note that individual changes are always left out (in this case traversal of levels 2 and 3).

Guidance

Lastly, the per-maneuver instructions should include information about levels. As of the time of writing this, instructions for level traversing maneuvers include information about the target level. E.g. “Take the elevator to level 2”.

What’s missing?

All of this is largely inspired by OSM’s Simple Indoor Tagging schema, but support for it is by no means complete. There are a couple of things mentioned in the schema Valhalla don’t/can’t currently support:

  1. multiple levels and multiple junctions on a single stair way. Take the following example:
       F             G
       |             |
A------B-------C-----D----E---H

Where the way ABCDE is tagged with highway=stairs and levels=1-2,4. This currently will result in edges AB, BCD and DE all with the same level tag (1-2, 4), because there is no easy way for Valhalla to pull the level information apart for each edge (maybe if BF, DG and EH have the corresponding single level tags).

  1. repeats_on: this tag was introduced to make mapping of multi story buildings easier when each floor’s layout is approximately the same, but it does not include the topology that Valhalla so heavily relies on when building the graph.

  2. Anything not tagged on the edges/nodes themselves. There are some useful tags that provide information that could be helpful for indoor routing, that we cannot easily put onto the graph data structures because it’s tagged on the building only. One example here is the per-level height to know about the vertical distance traveled.

With these last points in mind, Valhalla’s indoor routing capabilities won’t just work on OSM data from the wild. It seems that the simple indoor tagging scheme was not primarily intended for the purpose of routing, but for easy mapping and map rendering. Depending on the use case though, bringing your own data to the party should give you a basic but reliable indoor routing experience with Valhalla.