Osrm-backend: support relations in lua profiles

[emiltin]

for our bike router we need to prioritize certain ways that are part of routes; green routes, regional routes, etc. the routes are marked in OSM using relations.

maybe the way function could get a list of relations that the way is part of?

this issue is a follow up on #300 by @karme.

[mjoris]

If it is really urgent you could try to replace the highway-tag-values of those way that are related to the routes, by for example 'greenroute' in the OSM-file. And next prioritize the highway type 'greenroute' in the OSRM speedprofile...

[emiltin]

you're right, that would be a potential work-around. but i would rather discuss what a more solid solution would look like :-)

[emiltin]

two ideas:

1. processing relations, and add custom tags to the ways, and then let the lua way_function handle those tags
2. when calling the lua way_function, pass in a list of the relations it's part of

a preprocessing step could be used for other things as well, like adding synthetic ways for connecting train lines and platforms that are part of stop_area relations, or for adding ways across squares.

[emiltin]

i implemented parsing of routes in this branch: https://github.com/ibikecph/Project-OSRM/tree/parse_routes

the lua way_function gets a list of the relation the way segment is part of, and can read the various relation tags. this way it's straightforward to modify setting on (for example) national cycle routes.

however, the ability to modify speed and impedance separately is still lacking, leaving you basically no other option than to change the speed, at the cost of getting unrealistic travel times.

to see it in action run: cucumber -t @route

@prozessor13

[emiltin]

i tried processing data for Denmark (110M pbf), where it increased extraction time by a few seconds only. i guess it doesn't affect ram usage a lot either, since there are few relations compared to ways and nodes.

[emiltin]

there are some problem with how data is read using threads. on real world data it seems some ways are parsed before relations. still experimental..

[karme]

another solution would be to use the denormalized data produced by the waysplit tool

[emiltin]

the branch https://github.com/ibikecph/Project-OSRM/tree/parse_routes works correctly now

[karme]

Emil Tin [email protected] writes:

the branch https://github.com/ibikecph/Project-OSRM/tree/parse_routes works correctly now

i think using the denormalize relations on ways approach would be
simpler / more general, but i don't have a real preference here

[emiltin]

how would you handle a way being part of two similar types of way relations? you would have to use an akward tagging scheme. it would also be akward to handle route member roles.

[karme]

Emil Tin [email protected] writes:

how would you handle a way being part of two similar types of way
relations? you would have to use an akward tagging scheme. it would
aalso be akward to handle route member roles.

at the moment all key value tags of all relations a way is member of are
added as key value tags where the original key is prepended with
"rel[x]:" (where x is some number):

rel[0]:key1 val1
rel[0]:key2 val2
...
rel[0]:keyn valn
rel[1]:key1 val1
...
rel[n]:keyn valn

[emiltin]

thanks. you can see the relation object approach at https://github.com/DennisOSRM/Project-OSRM/blob/experimental/route_relations/profiles/bicycle.lua.

i think it's more straightforward to pass the route objects themselves, instead of having to copy all the tags to all the involves ways.

it might also be faster, since you don't need to store new tags, just keep pointers to the relation objects? did you do any performance test on your code? for Denmark, the object approach adds a few percent of processing time, if i recall correctly.

btw, your scheme above doesn't mention the member roles. for example, some parts of routes are only forward or backward.

[karme]

Emil Tin [email protected] writes:

thanks. you can see the relation object approach at
https://github.com/DennisOSRM/Project-OSRM/blob/experimental/route_relations/profiles/bicycle.lua.

nice

i think it's more straightforward to pass the route objects
themselves, instead of having to copy all the tags to all the involves
ways.

it might also be faster, since you don't need to store new tags, just
keep pointers to the relation objects? did you do any performance test
on your code? for Denmark, the object approach adds a few percent of
processing time, if i recall correctly.

no, didn't do any benchmark specific to that part

btw, your scheme above doesn't mention the member roles. for example,
some parts of routes are only forward or backward.

will take a look at that

your solution is just fine

the motivation of my approach was/is:

• it was really simple to do
• for the waysplit¹ it is much better to get rid of osm relations
  altogether as early as possible (otherwise you have to fix way
  references in relations - at the moment i only do that for restriction
  relations)

all the best
karme

¹ splitting ways at way intersections

[karme]

Jens Thiele [email protected] writes:

Emil Tin [email protected] writes:

btw, your scheme above doesn't mention the member roles. for example,
some parts of routes are only forward or backward.

will take a look at that

i now preserve the member role
=> changed the scheme slightly:
key-value tags are now of the form
rel[x]:role role-value
rel[x][rel-tag-key] rel-tag-value

do you have an example where the role is relevant for the routing?

[emiltin]

it's relevant when a route follow different ways in each direction, for example, due to oneways. on bike you might not want to prioritize pushing a bike against oneways, even though the section is part of a route (but in the wrong direction)

[emiltin]

i think your tagging scheme is getting a bit wild :-)

[karme]

Emil Tin [email protected] writes:

it's relevant when a route follow different ways in each direction,
for example, due to oneways. on bike you might not want to prioritize
pushing a bike against oneways, even though the section is part of a
route (but in the wrong direction)

oh i had a misconception of role here, thanks!

[emiltin]

just listing roles is not enough, when there is more than one relation, you need to know which tags belong to which relation/role

way --> roles --> relations

i think it's really simpler to just provide the role/relation objects, rather than try to cram it all into tags on the way

[karme]

Emil Tin [email protected] writes:

just listing roles is not enough, when there is more than one
relation, you need to know which tags belong to which relation/role

way --> roles --> relations

sorry but i don't just list roles
there is a 1:1 mapping between relations and roles

i wrote a small function to convert my tags to your objects

demo (pure lua):

-- fake a way with some tags
some_tags = {}
rawset(some_tags, "rel[0]:role","forward")
rawset(some_tags, "rel[0][type]","route")
rawset(some_tags, "rel[0][route]","bicycle")
rawset(some_tags, "rel[1]:role","backward")
rawset(some_tags, "rel[1][type]","route")
rawset(some_tags, "rel[1][route]","foot")
some_way = { tags = {Find = function(dummy,x) return some_tags[x] ; end}}

-- function to show equivalence to:
-- https://github.com/DennisOSRM/Project-OSRM/blob/experimental/route_relations/profiles/bicycle.lua
function way_routes(way)
local i=0
return { Next = function()
if not way.tags:Find("rel["..i.."][type]") then return nil end;
local role = way.tags:Find("rel["..i.."]:role");
local idx="rel["..i.."]";
local route={
tags = {Find = function(dummy,x)
return way.tags:Find(idx.."["..x.."]") ; end }};
i=i+1;
return role,route;
end }
end

-- demo
-- should print:
-- forward bicycle
-- backward foot
-- nil
routes=way_routes(some_way)
role, route = routes:Next()
print(role, route.tags:Find("route"))
role, route = routes:Next()
print(role, route.tags:Find("route"))
print(routes:Next())

but hey, if you don't like it, you don't like it ;-)

i think it's really simpler to just provide the role/relation objects,
rather than try to cram it alll into a tags on the way

don't know

[systemed]

@emiltin: This looks really promising. Very much looking forward to this being included in core.

One query: the tests say "Testbot multiplies the speed gain of overlapping routes". Is this right? If a route is (for example) part of NCN 8 and NCN 42, that shouldn't mean it's twice as good for cycling as it would be if it were just NCN 8. Or have I misunderstood?

[emiltin]

thanks. i think dennis might be doing some planet-size test to see if performance is still good.

you can use the routes to setup weights any way you like. testbot is just a profile that's used for testing, which is why is set it up to multiply. but you don't have to do that in car or bike profile.

[emiltin]

any news on this? i see you're working on osmium-based import.

[DennisOSRM]

Yep, that's going to be the basis once it's stable

[emiltin]

ok cool. will that affect relation parsing?

[DennisOSRM]

Yes, it will bring relation support. Right now we are bringing the branch up to speed by essentially recreating all features. Once this is done the relation parsing will be added

[eleu]

+1
(any update on this one?)

[Skippern]

Actually remaining on a route instead of going off to a different route and later return to the same route would partly solve my #1414 issue, where routing prefer leaving a national main highway and pass through urban areas and later return to the same national main highway later.

[emiltin]

hi @TheMarex what's the status on relation parsing?

[TheMarex]

Didn't take a look at it yet. Also not really on my todo list for the foreseeable future. Happy to help if anyone wants to give it a stab.

[emiltin]

i implementation a working solution, but alas, with osmium that's probably outdated

[systemed]

@emiltin's solution is really good - I'm using it at cycle.travel. (But that's why I'm still running off 0.3.10!)

[emiltin]

it's in the branch: https://github.com/Project-OSRM/osrm-backend/tree/experimental/route_relations.

code changes can be seen here: https://github.com/Project-OSRM/osrm-backend/commit/46d19ac8b4a7a387d6e6b965754ebe4a7c6b0d0b

[emiltin]

The approach is to build a (wayid->relation) map when parsing the data. Later when processing each way, the wayid is used to lookup and pass to LUA all releations that the way is part of. From LUA you can then interate the relations and read the tags and roles of each.

The approach adds little processing overhead, since few ways are part of relations. It gives LUA full access to the route data.

[emiltin]

@TheMarex would you want to merge the above solution if it was ported to current develop branch?

[TheMarex]

@emiltin I'll take a look at the old code. Porting this should be some effort as we moved to libosmium.

[emiltin]

yes unfortunately. but the main approach still holds i think.

[emiltin]

much of the old code deals with the parsing of the pbf file. this could now be handled by osmium. the lua code could be ported almost as-is i think. what needs updating is the handling of the map between ways and relations.

[TheMarex]

Had some time to look at the code. The approach seems sound. In general the number of roads that are part of a cycle route is quite small. This probably doesn't even impact memory consumption on import too badly.

[emiltin]

My previous test on a 110MB pbf file for Denmark increased processing time by only a few seconds.

[TheMarex]

I did look a little deeper into this in the last days so here is a small brain dump:

• biggest problem is here we parse ways, nodes and relations block-wise in no particular order
• if we want to provide relation information to the way_function we need to parse all relations first
• we have a similar problem with #1102
• @joto thinks that multiple parsing passes would not be too slow
• rather straight forward: add code for testing if its a turn restriction or route relation and corresponding parsing code
• mapping relations to ways: simple unordered_map way id -> relation id should be fine (there are not that many route relations and they are rather small)
• this is currently blocked by PR #1450 which refactors some code in that area

[emiltin]

any news on this? #1450 has been merged.

[Nomoos]

Any news on this?

[MichalPP]

as a workaround, I've created myself a postgresql query, which produces lua script to add highway tags if they are present only on relation (and not on the way). I just copy this into the way_function().

select 'local '||highway || '={[' || string_agg(distinct parts::text, ']=true,['::text)||']=true}; if ' || highway ||'[way:id()] then highway="'|| highway || '"; end' from (select highway,unnest(parts) as parts from (select osm_id, highway from fresh_osm_polygon union select osm_id, highway from fresh_osm_line ) as f,fresh_osm_rels where osm_id*-1 = id and osm_id < 0 and highway is not null) as t group by highway;

in my case, the output is small, fast, etc. And I already have the data imported into postgis DB.

[emiltin]

we still miss the ability to process relations. the use case for our ibikecph.dk service is being able to prioritise cycle routes.
e.g ways like this which is part of a cycle route relation, but otherwise has no special tags itself: http://www.openstreetmap.org/way/24988369

[MichalPP]

hi, if you have osm data in a postgis DB via --slim parameter, this shell script will create a lua script
prefix='fresh_osm_'; echo "select 'route_ways={' || string_agg(distinct concat('[', parts::text, ']=\"', highway, '\"' ), ', ') || '};' from (select highway,unnest(parts) as parts from (select osm_id, highway from ${prefix}polygon where highway is not null union select osm_id, highway from ${prefix}line where highway is not null) as f,${prefix}rels where osm_id*-1 = id and osm_id < 0) as t;" | psql -t mapnik > route_rels.lua

then just require("route_rels") in the beginning of the lua profile and if route_ways[way:id()] then highway=route_ways[way:id()]; end in the function way_function

(and probably change where highway is not null to where route='bicycle'

of course, native osrm code would be nicer..

[Nate-Wessel]

I just want to add another use case to this issue. I'm doing research on public transit using historical GPS data from transit agencies. I'm trying to map-match transit services to the street network, with the understanding that vehicles don't always complete their posted route and/or may turn back, detour around an obstruction, etc. I suspect it would improve the quality of my results if I could prioritize known routes (tagged with relations as type=route,route=bus), while still allowing for occasional deviation.

I hope there will be some work on this issue in the near future! In the meantime, I may have to try this postgis workaround.

[1ec5]

Route relation support would also unblock the following use cases:

• Reliably displaying graphical route shields based on a step’s ref: mapbox/mapbox-navigation-ios#334
• Suffixing highway refs with cardinal directions in continue instructions: Project-OSRM/osrm-text-instructions#119

https://github.com/Project-OSRM/osrm-backend/issues/482#issuecomment-14515610 suggests that it might be feasible to pass around references to the relation itself. If it isn’t, would it be feasible to implement route relation support by copying relation tags (and roles) onto the member ways in a preprocessing step reminiscent of rewrite-exit-destination-signage?

[emiltin]

yes, the implementation i did passing relation objects worked very well and had little impact om processing time. example use in a profile can we been at https://github.com/Project-OSRM/osrm-backend/blob/experimental/route_relations/profiles/bicycle.lua#L335

[oxidase]

As discussed with @AlexanderMatveenko and @deniskoronchik another possibility to process relations will be processing nodes and ways before relations and processing relations in lua callbacks for registered relation types. The relation-processing callback function will have non-constant access to indexed extracted nodes and ways. Such approach will generalize relations processing with different types that can have nodes and ways with different roles.

For example, restrictions handler can be moved into a profile callback that will fill resulting_restrictions vector. For cardinal directions, a callback will change a new direction field of ExtractionWay

Relations processing also can be done in-memory to recurse down superrelations like https://www.openstreetmap.org/relation/7204541

/cc @TheMarex

[TheMarex]

The main problem with parsing ways before relations is that we need to keep the concept of a way until we finished processing all relations. Right now ways are really transient objects that only exist for the duration of: Parse (libosmium) -> Process (lua) -> Split into edges (ExtractorCallbacks).

Changing that to Parse (libosmium) -> Process (lua) -> Cache, Cache -> Process Restrictions -> Split into edges would have some downsides. The main problem I see is that it would need a lot of data to keep both the lua result and the libosmium data round.

The control flow I would propose is the following:

1. Prase all relations using a filtered libosmium pass.
2. Call process_relation(relation, result):

function process_relation(relation, result):
    if relation.get_value_by_key("restriction") then
       -- calls to current C++ handler
       result.restriction = parse_restriction(relation)
    end

    if relation.get_value_by_key("route") then
       -- the way that is marked with role "east" will get additional data "name"
       -- in its invocation of process_way
       result.roles["east"].data["name"] = relation.get_value_by_key("name")
    end
end

1. Parse all nodes/ways and pass in the preserved relation data:

function process_way(way, result, location_data, relations):
    if relations.roles["east"] then
       result.name = relations.roles["east"][0].name .. " East"
    end
end

That way we only need to keep the minimal amount of data we need for the processing around.

[deniskoronchik]

The main idea, that we could use such pipeline:
Parse with libosmium (cache relations) -> Process with lua ways and nodes -> Process with lua relations -> Split into edges

When processing relations, we just need to save in memory ExtractionNode and ExtractionWay structures. So they will be available to access for relation processing from lua, because they can just be sorted by id and usage of binary search allows to find any of it fast. This mechanism allows to change them when you process relation in lua like this:

function process_relation(relation):
    if relation.get_type() == 'any type':
         -- change ways and nodes that are members of relation
         -- relation.get_members_by_role('any role') to get set of members and change them if we need
         -- because they have ExtractionWay, ExtractionNode types.
    end
end

Also this way allows to work with relations, that has another relations as members, because they cached in memory.

Restrictions also can be made with this approach, via function add_restriction(from, to, via), that can be available from lua script. So you parse relation, and if it restriction call this one function.

This approach just increase memory usage for caching relations (but it can be made very efficient if memory is a bottleneck).

@update There are some advantages of this approach:

• it doesn't depend on relation type (so you can process any type of relation, and change ways and nodes depending on it);
• it supports relations, that has another relations as a members;
• passing new functions like add_restriction into lua you will be available to do more and more with new relations, without refactoring.

/cc @TheMarex @oxidase

[TheMarex]

Capturing from a slack conversation with @deniskoronchik we are probably going to go with parsing relations first to avoid caching ways and nodes.

Scope

The goal is to be able to support the following use case for now:

• Pass data from the relation to one of its members. This is needed for:
  
  
  
  • Cardinal directions in way names
  
  
  • Marking bicycle ways that are part of cycle-relations
  
  
  • Use route-names over way names to remove ceremonial names
  
  
• Handle parsing turn restrictions more gracefully: Replace the use_turn_restrictions flags and restrictions settings with being able to mark a relations as a restrictions directly.

What we do not need to support:

• Relations as members of relations. It's unclear if we ever will have a use-case for this.
• Location dependent data: We chose to pass that data in externally with #4415

Lua API changes

• Deprecate use_turn_restrictions
• Deprecate restrictions
• Add process_relation(relation, result) function where result is of type ExtractionRelation with the following properties:
  
  
  
  • restriction (bool): If set call the current turn restriction handler on the osmium::Relation.
  
  
  • data (table): Keyed by member id. Data added here will be passe to the way/node reference in the relation.
  
  
• Add parameter relation_data to process_way.
• Add parameter relation_data to process_node
• Access to relation_data could be done via relation_data["route"] which would return a list of lua tables of all relations with type route that added data to this way.

Architectural changes

• Split relation handling from https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/extractor.cpp#L290-L431
• The PBF file will be parsed twice, osmium has filters for parsing only certain entities which can help.
• Run relation parsing first. It should be possible to use a similar setup with tbb::paralle_pipeline.
• Data for ways/nodes from relations is aggregated by way/node id
• During parse nodes/ways we lookup if there is relation data for the object, if yes we retrieve it from the storage and pass it into process_node, process_relation

Examples

This profile is a sketch of the API above that show-cases some of the use-cases.

function process_relation(profile, relation, result)
    local t = relation:get_value_by_key("type")
    local name = relation:get_value_by_key("name")

    if t == "restriction" then
        result.restriction = true
    else if t == "route" and relation:get_value_by_key("route") == "road" then
        for member in relation.members() do
            if member:role() == "north" then
                result.data[member:ref()]["direction"] = "North"
            end
            if name then
                result.data[memer:ref()]["name"] = name
            end
        end
    else if t == "traffic_signals" then
        -- lua has no way of counting number of table entries
        local count = 0
        for member in relation.members() do
            count = count + 1
        end

        for member in relation:members() do
            result.data[memer:ref()]["synchron_signals"] = count
        end
    end
end

function process_node(profile, node, result, relation_data)
    local highway = node:get_value_by_key("highway")

    -- Example application: Lessen traffic light penalties for synchronus signals.
    if highway == "traffic_signal" then
        result.penalty = profile.traffic_light_penalty
        local synchron_signals = 1
        for lights in relation_data["traffic_signals"] do
            synchron_signals = lights["synchron_signals"]
        end
        result.penalty = result.penalty / synchron_signals
    end
end

function process_way(profile, way, result, relation_data)
    local name_postfix = ""
    local route_name = ""
    for route in relation_data["route"] do
        if route.data["direction"] then
            name_postfix = route.data["direction"]
        end
        if route.data["name"] then
            route_name = route.data["name"]
        end
    end

    result.name = way:get_value_by_key("name")
    -- Example application: Remove ceremonial names
    if route_name ~= "" then
        result.name = route_name
    end
    -- Example application: Add directional post-fixes
    if name_postfix ~= "" then
        result.name = result.name ..  " " .. name_postfix
    end
end

[deniskoronchik]

There were some strange relations found:

• https://www.openstreetmap.org/relation/128066 - has ways and relations as a members
• https://www.openstreetmap.org/relation/77612 - in this one we have direction information encoded in relation names

Will update with a strange relations

[joto]

Just a heads-up to whomever is going to implement this: There is lots of code in libosmium that can help with storing relations or matching up relations with their members etc. But its not that easy to understand how it all fits together and what makes sense to use in which case. I'd be happy to advise if that's wanted.

[1ec5]

https://www.openstreetmap.org/relation/128066 - has ways and relations as a members

Looks like a couple ways were unintentionally added to the superrelation instead of child relations. Unfortunately, it isn’t difficult to make this mistake, but it’s something that a validation tool could catch.

https://www.openstreetmap.org/relation/77612 - in this one we have direction information encoded in relation names

This is another tagging error; the child relations should have direction tags. I don’t think it would be appropriate to parse directions out of names, but the relation could still be used for some of the other purposes described above.

[emiltin]

can be closed, since relations are now supported in lua profiles?

[1ec5]

I’ll defer to the others here, but note that #4434 is the next step for route relation support.

[danpat]

Yeah, this can be closed - OSRM know nows how to pass relevant relations to the way_function, any future work will be related to supporting specific relation types, like #4434 .