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 notifications@github.com 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 notifications@github.com 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 notifications@github.com 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 karme@karme.de writes:

Emil Tin notifications@github.com 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 notifications@github.com 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 notifications@github.com 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?

[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: Expand shield coverage beyond the United States mapbox/mapbox-navigation-ios#334
• Suffixing highway refs with cardinal directions in continue instructions: Use relations parsed from OSRM from to include cardinal direction in instructions osrm-text-instructions#119

#482 (comment) 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

3. 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 Location-dependent left hand driving flag #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 .