Set up router based on OHM road network

[1ec5]

The main OHM website should integrate a routing service that calculates routes over the historical road network in OHM.

Background

openstreetmap-website integrates with several routing services to help mappers visualize and debug the routing implications of their navigation mapping. Users can access this functionality by pressing a button beside the search bar, or by visiting the /directions page. Most mappers go for years without ever noticing the Directions button; it’s one reason why discussions about navigation mapping can sometimes be a bit ungrounded from reality.

OHM has yet to set up a routing service. OpenHistoricalMap/ohm-website@c3b40d9c3409297a1787dc8b08120812e796c7d3 removes the button, but it remains possible to access the built-in OSM routing integration by visiting /directions. #506 tracks removing this endpoint.

Rationale

From a modern perspective, it can be difficult to appreciate reductions in travel time enabled by road development or by the opening of a specific thoroughfare. For this reason, historians often mention how long it used to take to travel from one place to another as context when explaining a sequence of events. Sometimes these estimates factor into important world events. These estimates are often based on records and historical accounts mentioning departure and arrival times. However, these records only cover rare, exceptional occasions. An OHM-based router could improve spatial understanding based on how humans actually navigate on the ground, not just from a bird’s eye view.

Historical routing can also potentially help to model future epidemics of communicable diseases based on understanding the spread of previous epidemics.[^Michail15]

Feasibility

Temporal routing graphs are algorithmically significantly more complex than conventional routing graphs.[^MichailSpirakis14] However, several OSM-based routing engines already support a limited form of time-dependent routing based on the conditional restrictions tagging scheme. Each router skirts algorithmic complexity by taking strategic shortcuts. For example, OSRM and Openrouteservice only resolve conditional restrictions at the time they build the routing graph. None of these routers dynamically recomputes the available edges after completing each step. Some routers only compute accessibility with daily precision.

These are severe limitations when it comes to OSM data, but it should generally be fine when working with OHM data that’s less precise from a navigation perspective. In fact, the only reason I bring up OSM’s conditional restriction tagging scheme is to suggest that we co-opt it for storing start and end dates, which are more important in the grand scheme of things. The idea is to configure one of these routing engines to translate start_date=1950-10-14 end_date=1940-11-07 into access=no access:conditional=yes @ (1950 Oct 14 - 1940 Nov 7).[^TacomaNarrows] Both GraphHopper and Valhalla appear to support full date ranges in access:conditional=*, though GraphHopper doesn’t support time ranges: graphhopper/graphhopper#374. Time ranges would only be necessary if we attempt to support start_date:edtf=* and end_date:edtf=*.

Both GraphHopper and Valhalla come with walking profiles, but we might also want to develop profiles for riding on horseback or driving cattle. We’d be writing a custom profile anyways to handle the tag transformation from start_date=* and end_date=* to access:conditional=*.

[^Michail15]: Michail, Othon (2015). “An Introduction to Temporal Graphs: An Algorithmic Perspective.” Patras: Computer Technology Institute & Press “Diophantus”. [^MichailSpirakis14]: Michail, Othon; Spirakis, Paul G. (2014). “Traveling Salesman Problems in Temporal Graphs.” Budapest: International Symposium on Mathematical Foundations of Computer Science. [^TacomaNarrows]: The infamous original span of the Tacoma Narrows Bridge, if you’re wondering.

[1ec5]

The idea is to configure one of these routing engines to translate start_date=1950-10-14 end_date=1940-11-07 into access=no access:conditional=yes @ (1950 Oct 14 - 1940 Nov 7).

Based on some cursory code inspection, in GraphHopper, we’d need to modify the core codebase to check the date keys. In Valhalla, the tag rewriting can happen in Lua without needing to recompile the engine. Another possibility would be to transform the tags ahead of time in the PBF.

[ianthetechie]

A few random notes after giving this a read through...

The idea is to configure one of these routing engines to translate start_date=1950-10-14 end_date=1940-11-07 into access=no access:conditional=yes @ (1950 Oct 14 - 1940 Nov 7).3 Both GraphHopper and Valhalla appear to support full date ranges in access:conditional=*, though GraphHopper doesn’t support time ranges: https://github.com/graphhopper/graphhopper/issues/374.

This is clever. I think it'll work. I don't think access:conditional itself is explicitly tested as such today, but there is a great test for mode-specific restrictions here.

Both GraphHopper and Valhalla come with walking profiles, but we might also want to develop profiles for riding on horseback or driving cattle. We’d be writing a custom profile anyways to handle the tag transformation from start_date= and end_date= to access:conditional=*.

Yeah, that makes sense. Unfortunately, making a new profile in Valhalla isn't exactly easy, but it's certainly possible. This unfortunately requires writing oodles of C++. I'm not sure how much better that is than grokking 2500 lines of Lua spaghetti, but just FYI ;)

Another thing to be aware of are that, while Valhalla should be quite extensible in terms of costing modes, there are some limits at the moment re: number of modes of travel, and my open PR will use the last bit.

In Valhalla, the tag rewriting can happen in Lua without needing to recompile the engine.

While you won't need to touch C++ code per se just to change the lua scripts, these do actually get compiled down. This is probably splitting hairs, but at a high level, the pipeline goes something like 1) prepare data, 2) build graph tiles, and 3) run the Valhalla service pointed at the graph tiles. This has a few interesting properties that might not be obvious.

1. To change how tags are processed, you ned to edit the Lua file, recompile the valhalla_build_tiles target (Lua gets compiled into a C++ header which is invoked by C++ code using the LuaJIT runtime). You don't need to recompile the engine here unless you are adding new info to the tiles. If you're just using existing fields and remapping, then you're good. (Also note that while the first pass of stuff happens in Lua, some C++ is involved to transfer properties into into internal structures; you can see my PR for details, but this probably isn't a concern unless you are adding new fields).
2. You don't need to recompile the engine in this case as long as you haven't broken binary compatibility of the tiles. You can usually add new stuff to the graph tiles using free bits and retain backward compatibility. Old code will simply not look at those bits. (It's a really dense binary format.)
3. When you write a new costing mode, you need to ensure that the graph tiles have useful data in any new bits of data you're looking at (otherwise I guess you could risk bad behavior). If you are not referencing any new information but only interpreting existing info in the graph, you can reuse old tiles of course.
4. After tiles are built (mappings from Lua -> binary graph tiles) with all info that a costing model needs, you can iterate on the costing model as much as you like without having to rebuild the graph tiles. You just need to rebuild the engine.

Finally, re: feasibility, this feels like it's scopable for a motivated student. For context, I wrote the golf cart profile in about a week and a half (sans present effort to upstream the changes for general public use, which is going to take almost as many dev hours haha). I started with a pretty understanding of the domain and Valhalla itself (had hacked on it on and off for ~5 years prior). Multiply that a few times for unfamiliarity and uncertainty, and I think it's a reasonable summer project.

Hope this helps!

[1ec5]

This idea pretty much assumes that any change to a street is mapped as a separate way. Fortunately, this is how most streets are being mapped in OHM presently.

By contrast, #94 proposes to map most attributes as relations on a shared way instead. Some mappers would like that approach because it would keep them from having to untangle a mess of overlapping ways in the editor. However, it would greatly complicate any routing solution, since we’d have to either synthesize edges during postprocessing or somehow modify the core routing engine to assign weights and other attributes conditionally, not just access restrictions. Valhalla’s guidance engine would probably be heavily affected too.

For now, I’d ignore the relation-based approach since there are too many open questions about how to even render it, let alone route over it.

[1ec5]

For completeness, there is some prior art: in 2014, @sk53 experimented with setting up OHM-powered instances of GraphHopper, OpenTripPlanner, and Routino in Buenos Aires.