Improve speed limit inference

[SiarheiFedartsou]

Description

There are a lot of cases when speed limits are not available as explicit maxspeed tag, but can be inferred from other tags(e.g. in Poland there is 50 km/h limit in urban area if there is no speed limit sign). We already partially handle such cases using tags like maxspeed=at:rural, but it applies only if this tag explicitly present for way. Also we have fallback to default speed limit by road type, but it doesn’t take country specific details into account https://github.com/Project-OSRM/osrm-backend/blob/b17cbb4c4723d2ecfb3f145734b3a0e1f2089405/profiles/car.lua#L262. At the same time there is this quite interesting tool https://github.com/westnordost/osm-legal-default-speeds which parses OSM documentation and then infers maxspeed by “implicit” tags. For example if we know that this particular road is in Belgium, there are no tags about max speed, but we have highway=motorway tag, we can infer 120 kmh limit, just because it is default limit for motorways in Belgium.

So the idea is that we could try to re-use this idea in OSRM in order to improve quality of max speed data we get from pbfs(it will be difficult to directly re-use tool I mentioned above though - it is written in Kotlin).

Video from the author of that tool https://www.youtube.com/watch?v=FH98z24PQGs&t=2s

I would appreciate any thoughts on this.

[mjjbell]

Could extend the geojson data functionality to set max speeds in a similar way.

[jcoupey]

Worth noting there is also this approach followed by the Valhalla team as an independent project. My understanding is that the scope is a bit different as the aim is to derive typical expected speeds from GPS traces rather than "just" legal max speed values.

[nilsnolde]

There's also this discussion over in the Valhalla repo in case it's of interest: https://github.com/valhalla/valhalla/issues/3334#issuecomment-1261602765.

@SiarheiFedartsou

it will be difficult to directly re-use tool I mentioned above though - it is written in Kotlin

It's apparently a "multiplatform" library according to the author, and as I understand you can use that directly in C++ (via extern C blocks). I have never done that myself either, guess/hope one finds easy examples online.

as the aim is to derive typical expected speeds from GPS traces rather than "just" legal max speed values

I think both properties/projects are nice to have. OpenStreetMapSpeeds describes a more realistic speed that you'd probably rather use for costing/ETA (with density indication in the JSON schema Valhalla can make use of, I guess OSRM not yet). @westnordost 's returns very detailed legal speed limit tags, which also have important use cases for navigation signage/maneuver instructions or fill-in lacking more realistic speeds, also possibly for costing/restrictions (though no one uses it that way yet I think..). It'd be super nice if one could use one of the projects at runtime, so the graph wouldn't have to store so many speed values. Maybe e.g. storing the OpenStreetMapSpeeds more realistic ones in the graph and having osm-legal-default-speeds fill in the holes with legal speed limits and/or use it to set a legal speed limit for maneuver instructions. Maybe that's asking for too much though, not sure what the performance penalty would be to have the Kotlin lookup during the algo's expansion (though it seems to be pretty simple in-memory lookup). What do you think? EDIT: actually there's a better approach, Kevin just made me aware: during graph build we can take the output of osm-legal-default-speeds to set the legal speed limit and default the edge's speed to it when there's no better speed source available in OSM (like maxspeed(:practical)). Further down in the graph build we overwrite the edge's speed with the output of OpenStreetMapSpeeds if there's coverage. Then it can all stay in the graph and (at least for Valhalla) there's no extra cost at runtime.

FWIW, Valhalla already uses OpenStreetMapSpeeds, but the coverage is very flaky so far. I'd like to find some time to try out an implementation of osm-legal-default-speeds (and/or improve OpenStreetMapSpeeds), but can't see that happening in the next weeks. Anyways, I'll watch here and update if I/we should try it before you do.

Also, I just now had the time to look in detail into osm-legal-default-speeds, and wow, really tons of work! Nice wiki too. Congrats @westnordost !

[westnordost]

One more use case of osm-legal-default-speeds is upper speed limits for other vehicle classes such as trucks, buses, hazmat, motorcycles etc. which would likely not be capturable precisely with OpenStreetMapSpeeds. These limits then actually would have an applicationfor costing/ETA, at least for these vehicle classes. And in any case, osm-legal-default-speeds will provide a fallback when OpenStreetMapSpeeds does not return anything.

Regarding Kotlin Multiplatform - I haven't used it either except for running the unit tests in native. I've also not seen (or searched for) any examples how to include kotlin multiplatform dependencies into a C/C++ project.

[SiarheiFedartsou]

Regarding Kotlin Multiplatform - I haven't used it either except for running the unit tests in native. I've also not seen (or searched for) any examples how to include kotlin multiplatform dependencies into a C/C++ project.

It definitely should be possible - I know people who did something like this, but I guess we will have to add Kotlin runtime as a dependency - not sure we want to do that 🤔

@westnordost as author of this library what do you think will it be difficult to port it to C++? I briefly looked over the code and it seems to be relatively simple, but may be I didn't notice something?

[westnordost]

It's about 1000 SLOC, not counting the unit tests. (Kotlin code is quite concise however, probably you should count with 1500 SLOC in C++)

[westnordost]

But ofc I would advise against it as long as the Kotlin Native stuff is not completely unusable. It then becomes double the effort to maintain. I found this in the Kotlin docs: https://kotlinlang.org/docs/native-dynamic-libraries.html#compile-and-run-the-example-on-linux-and-macos

[nilsnolde]

It's getting a bit off-track, but just thinking about how to integrate that project while building/linking.. To reduce duplication across repos, either a CMakeLists.txt for the kotlin project and/or a (external?) conan recipe could be good right? Both OSRM & Valhalla are using conan already, so minimal effort once that'd stand. Never wrote a recipe before and no idea what's lurking when writing a stable recipe for most archs/platforms. Also the example uses gradle, so that's smth a user who wants to build this locally, would need.. That does sound a little detracting, at least to me.. Only alternative I can think of is to expect the user to install the project system-wide and let CMake find it, not super nice either, sounds like potentially many annoyed (& annoying) bug reports.

Any other thoughts on integration? Maybe I'm thinking too complex..

[westnordost]

Sorry, I have no knowledge of the project setup / build pipeline stuff in the C/C++ world. If the linked docs above do not help (then they should be improved and) then I guess it can only help to find some examples of kotlin multiplatform libs used in native projects on the internet.

[nilsnolde]

Maybe @SiarheiFedartsou has a point and it might be easier for us to use when it's ported into a e.g. header-only C++ lib that we all could use. I don't think this has to be a linked library, just complicates it quite a bit, apart from all the basics like having gradle installed. Header-only would be super easy to integrate. Maybe we don't even need some of the more advanced functions with fuzzy matching, not sure though. The serious work is probably more in the JSON you put together, writing a tiny C++ parser for it might be less work than extending the build pipeline for gradle/kotlin.

[westnordost]

The major part of the library actually consists of parsing the tag filter expressions as are used here: https://wiki.openstreetmap.org/wiki/Default_speed_limits#Road_types_to_tag_filters

See the code here: https://github.com/westnordost/osm-legal-default-speeds/tree/master/library/src/commonMain/kotlin/de/westnordost/osm_legal_default_speeds (And test code is here: https://github.com/westnordost/osm-legal-default-speeds/tree/master/library/src/commonTest/kotlin/de/westnordost/osm_legal_default_speeds )

[SiarheiFedartsou]

@westnordost yep, but we still can use this part of the library "as is", but only have "matching" part rewritten in C++.

[westnordost]

Not sure what you mean. That code, "as is", is written in kotlin. Why would you be able to use that code written in kotlin but not the other part written in kotlin?

[SiarheiFedartsou]

Not sure what you mean. That code, "as is", is written in kotlin. Why would you be able to use that code written in kotlin but not the other part written in kotlin?

Sorry, I read your previous message wrong - when I was saying "part of the library" I was referring to this Python script https://github.com/westnordost/osm-legal-default-speeds/tree/master/parser (i.e. we can generate JSON and just re-use it from any language) - tbh not sure about tag filter expressions if it will be needed or not.

Btw I can even imagine that instead of having deep integration with OSRM it can be simple external tool which just preprocesses .osm.pbf and fills maxspeed tag where possible. After that it can be used as input for OSRM without any changes in OSRM itself.

[westnordost]

tbh not sure about tag filter expressions if it will be needed or not.

It is needed. Otherwise no matching of OSM tags to road types is possible.

[DennisOSRM]

I think having something like this would be a nice addition.

[ftrebien]

An idea: once thinking about the Valhalla algorithm, I obtained blobs for urban areas in GIMP using simple median filters. I started with the streets rendered as thick black lines (eg. Stamen's Toner) against a white background, filtered with settings to expand them until they merge into on big blob per city, then filtered again with roughly inverse settings to contract a little more than the same amount so that the roads between cities disappear, leaving only city blobs. Custom rendering rules would allow skipping the first filter if the streets were rendered thick enough for them to merge. The missing (though apparently easy) step would be vectorization, which would produce a geometry that could be used to check, during map processing, whether a way is inside or outside a built-up area. I haven't investigated, but it may be possible to do all this with just vectors (instead of raster images) in QGIS using the buffer tool. City boundaries don't change much, so built area boundaries may be updated infrequently, say, once a year.

[nilsnolde]

I guess you're relating to how to determine "urbanity/density" to factor that in the speed calculation? The Valhalla (but also Graphhopper) way is to perform tiny mini Dijkstras from every road-accessible way and use the proxy of "how many unique other ways do I expand on within 2 or so km" to try and answer the question of "how urban/likely slow traffic is it at this location". Relying on OSM admin boundaries, especially those high-level ones like city boundaries, is shaky grounds as 1) those kind of admin geometries are notoriously bad and changing super frequently, they're often vandalized and 2) it's not painting the full picture, i.e. there's dense areas that are not cities (or other formally attributed boundaries), they exist everywhere and I think density is a fairly good proxy for increasing traffic.

The density stuff is easily the most annoying part of what I had in mind, as it needs either a graph structure or a huge spatial index. I won't forget about this, but it'll take quite a bit more time before I will get active with anything. Also I kinda wanna see how this whole Overture thing is behaving over the next months, though I'm not holding my breath too much on that one..