Implement more flexible turn weight function

[chaupow]

Goal

Have a turn weight function that allows more flexible setting of turn weights.
This takes places during the extraction phase and (probably?) in the lua profiles.

The function should enable implementing turn weights that are able to regard

• mode changes penalty for mode change & crossing roads? #592
• way types using way types to calculate turn penalties #477
• restricted access Penalize turns onto ways with restricted access: fees, customers #3745
• bike lanes Bike profiles route through alleys in Montreal - this is less than desirable #3971
• speeds Factor in speeds for turn penalties #1735

and others such as slip roads (#3133), traffic lights (#96), turn lanes (#607), stop signs (#3009).

Implementation completed in PR #4789

What the PR does:

• expose information about source and target when turning
  • restricted, mode
  • is_motorway, is_link, number_of_lanes
  • highway_turn_classification, access_turn_classification
  • speed
• expose information about other roads at intersection when turning
  • whether on the left or right of turn
  • is_restricted
  • is_motorway, is_link, number_of_lanes
  • highway_turn_classification, access_turn_classification
  • speed
  • is_incoming, is_outgoing

What the PR does not do:

• information on stops/give ways/priority Stop Signs for Profiles #2652 Priority Roads for Profiles #3003
• information about roads of other profiles at intersection (e.g. knowing the car speed when routing bikes)
• information about non-routable lines (e.g. knowing that rails have to be crossed when walking)
• implement virtual turns allow node_function() to add penalty to a segment #3862
• consider nodes on roads such as traffic_calming. A related issue would be Take Traffic Calming Road Furniture Into Account #3021 .

Prior Work

Prior work exists that got stale at some point and were never merged:

• Improve Turn Function #2912
• Road Priorities: Stop Signs, Give Ways #3009

Approach

Implementation probably involves changing the turn function such that osm tags are available. Better description/information will be inserted here as soon as I have a better scope of things.

New API Proposal

Old and deprecated approach:

#### `setup` We add two additional variables to the profile table that can be set during setup: * `highway_user_classification_table` * `access_user_classification_table`

The user can set an arbitrary integer/classification to edges based on highway tag and access tag.

process_turn

process_turn(profile, turn, source, target)

• profile is the profile table setup during setup
• turn gives specific information about the turn and includes

Attribute	Read/write?	Type	Notes
angle	Read	Float	Angle of turn in degrees (0-360: 0=u-turn, 180=straight on)
number_of_roads	Read	Integer	Number of ways at the intersection of the turn
is_u_turn	Read	Boolean	Is the turn a u-turn?
has_traffic_light	Read	Boolean	Is a traffic light present at this turn?
weight	Read/write	Float	Penalty to be applied for this turn (routing weight)
duration	Read/write	Float	Penalty to be applied for this turn (duration in deciseconds)

• source and target are information on the road involved in the turn and include

Attribute	Read/write?	Type	Notes
restricted	Read	Boolean	Is a restricted access road? (See definition in process_way)
mode	Read	Enum	Travel mode. Defined in include/extractor/travel_mode.hpp
highway_user_classification	Read	Integer	Classification based on highway tag defined by user during setup
access_user_classification	Read	Integer	Classification based on access tag defined by user during setup
is_motorway	Read	Boolean	way is a motorway
is_link	Read	Boolean	way is a slip/link road
number_of_lanes	Read	Unsigned	total number of lanes in way

this would result in a breaking API change

Docs are here

New accessible attributes in process_turn

  const double angle;
  const int number_of_roads;
  const bool is_u_turn;
  const bool has_traffic_light;
  const bool is_left_hand_driving;

  // source info
  const bool source_restricted;
  const TravelMode source_mode;
  const bool source_is_motorway;
  const bool source_is_link;
  const int source_number_of_lanes;

  // target info
  const bool target_restricted;
  const TravelMode target_mode;
  const bool target_is_motorway;
  const bool target_is_link;
  const int target_number_of_lanes;

  const std::vector<ExtractionTurnLeg> roads_on_the_right;
  const std::vector<ExtractionTurnLeg> roads_on_the_left;

  double weight;
  double duration;

ExtractionTurnLegs have the properties

    const bool is_restricted;
    const bool is_motorway;
    const bool is_link;
    const int number_of_lanes;
    const int highway_turn_classification;
    const int access_turn_classification;
    const int speed;
    const bool is_incoming;
    const bool is_outgoing;

The order of the roads in roads_on_the_right and roads_on_the_left are counter clockwise. If the turn is a u turn, all other connected roads will be in roads_on_the_right.

Todos

• Understand how turn functions works in OSRM at the moment
• Check out approaches in prior PRs
  • Improve Turn Function #2912
  • Road Priorities: Stop Signs, Give Ways #3009
• Identify needed parameters for the turn function to address/enable most cases above
• Implement turn function
• Test
  • Unit tests
  • Cucumber tests
    • correct incoming/outgoing info
    • correct speed
    • correct highway and access turn classification
    • correct source/target info
• Update profiles.md
• Cut follow up issues

Anyone with hints/great ideas/comments will be appreciated ❤️
@TheMarex @daniel-j-h

[emiltin]

this would be very useful for bicycle routing, as mentioned in the referenced #477 and #592

[chaupow]

Preliminaries

Understand how turn functions works in OSRM at the moment

1) There is the lua world in which the user needs to set turn weights:

• Turns are processed in process_turn in profiles, having two input parameters profile and turn https://github.com/Project-OSRM/osrm-backend/blob/master/profiles/car.lua#L420

• The process_turn function processes every possible turn in the network, and sets a penalty depending on the angle and turn of the movement.

• The following attributes can be read and set on the result in process_turn:

Attribute	Read/write?	Type	Notes
direction_modifier	Read	Enum	Geometry of turn. Defined in include/extractor/guidance/turn_instruction.hpp
turn_type	Read	Enum	Priority of turn. Defined in include/extractor/guidance/turn_instruction.hpp
has_traffic_light	Read	Boolean	Is a traffic light present at this turn?
source_restricted	Read	Boolean	Is it from a restricted access road? (See definition in process_way)
target_restricted	Read	Boolean	Is it to a restricted access road? (See definition in process_way)
angle	Read	Float	Angle of turn in degrees (0-360: 0=u-turn, 180=straight on)
duration	Read/write	Float	Penalty to be applied for this turn (duration in deciseconds)
weight	Read/write	Float	Penalty to be applied for this turn (routing weight)

• The different lua functions setup, process_node, process_way and process_turn have different accesses to osm tags.

• in short, setup is used when osrm still has access to osm tags.
  • tags are whitelisted, restricted, included
  • speeds depending on surface, way type etc is set
• the process functions do not have access to osm tags anymore but only to the data that is provided by the API

2) There is cpp land in which process_function is fed

• Depending on version number, turn_function is called here : https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/scripting_environment_lua.cpp#L968
• Input parameters are two objects context.profile_table and ExtractionTurn turn
  • contest.profile_table is a sol::table object and seem to be values set in the setup functions of lua profiles. not completely sure here
  • ExtractionTurn is a handy object https://github.com/Project-OSRM/osrm-backend/blob/master/include/extractor/extraction_turn.hpp#L15 storing all information such as has_traffic_light that can be used in luaworld later on
• the graph_compressor does something I don't quite understand, feeding ProcessTurn for every node here https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/graph_compressor.cpp#L234
• Edge based graph factory generates ExtractionTurn objects here https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/edge_based_graph_factory.cpp#L601 and calls ProcessTurn afterwards 🎉 looks like the right place to be

Enough digging. This should cover the most I need to know about turn functions. (Maybe...)

Open questions

• What does graph_compressor do regarding the turn function
• At what point do we process the actual OSM tags? taginfo.json?

[TheMarex]

the graph_compressor does something I don't quite understand, feeding ProcessTurn for every node here https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/graph_compressor.cpp#L234

This is a hack that was introduced in the wake of the via-way-turn-restriction work to extract the traffic light turn penalty. We should probably think about a better implementation there.

[chaupow]

Prior work

Check out approaches in prior PRs

PR 3009

• adds additional memvars to struct ExtractionWay and to struct InternalExtractorEdge

  bool is_priority_road_forward;
  bool is_priority_road_backward;
  

• basically wires the two vars through a lot of code. important places touched are
  • taginfo.json - probably related to the actual osm tags
  • graph_compressor.cpp
  • extractor_callbacks.cpp
  • edge_based_graph_factory.cpp
  • node_based_graph.hpp
  • node_based_edge.hpp

PR 2912

• Introduces turn_penalty.hpp and std::int32_t GetTurnPenalty()
• Regards turn angle, approach_road_speed, exit_road_speed
• Files touched are mostly the same as in other PR

[chaupow]

Beware

❗️ Docs were outdated. Updating docs first, then revisiting this comment.

Theory

Identify needed parameters for the turn function to address/enable most cases above

This is probably the part that should be use-case/request/community driven.

Important implementation background information:

Exposing more information to luaworld does not come free. Exposing more tags means needing more storage during the extraction phase.
However, we have some information that we are storing anyways because we need it for guidance. Exposing these would be free (aside from implementation work).

These are found in class RoadClassification https://github.com/Project-OSRM/osrm-backend/blob/master/include/extractor/guidance/road_classification.hpp:

• motorway_class
• link_class
• may_be_ignored
• road_priority_class
• number_of_lanes

We should consider this when making choices.

Issue	Already available	Comes free	comment
Divebomb prevention	❌	✅	to do
Mode change #592	✅	✅	done / profile needs update
Number of lanes #477	❌	✅	to do
Intersection size #477	✅	✅	done / profile needs update
Highway tag #477	❌	❌	tbd, could be solved introducing a user enum
Access tag #477	❌	❌	tbd, could be solved introducing a user enum
Customer access #3745	❌	❌	tbd
Speeds #1735	❌	❔	tbd
Alleys #3971	❌	❌	should be a process_way attribute
traffic light #96	✅	✅	done / profile needs to update weight
stop signs / give way #3009	❌	❌	tbd

[chaupow]

@emiltin regarding the issues you mentioned:

• I guess using way types to calculate turn penalties #477 can be solved by knowing the number of lanes?
• What tags/information would be involved to correctly identify a mode change as in penalty for mode change & crossing roads? #592?

edit: apparently travel mode is already available in process_turn. provided, I understood correctly and my proposed docs are correct, @emiltin can you check out the new docs and see whether that would work for your use-case? https://github.com/Project-OSRM/osrm-backend/blob/bc57b2d1e99ba68c8ade375f9d7ea617ac8a2be9/docs/profiles.md#process_turnprofile-turn

[emiltin]

the number of lanes is rarely tagged explicitly, and alone it is therefore not enough to describe the road type.

the use case described in #477 is that you don't want to suggest crossing (either turning across, or going straight across) a bigger road, if there is no traffic light. this includes motorway, trunk and primary roads, also in cases where number of lanes is not specified. probably also secondary and tertiary probably with a lower penalty.

other things to consider are tags like oneway, maxspeed, access, vehicle and motor_vehicle which affect the amount, density and speed of traffic you ned to cross. note that you probably also need sub tags, eg. maxspeed:forward, oneway:car, etc.

you also need to know if there's traffic lights at the intersection. if there is, there should probably not be any additional penalty beyond what the the traffic light itself incurs.

if there's no traffic light, it would be useful to know about stop and yiels signs.

tags related to bus, tram and pedestrian crossings could be useful.

if live traffic data is used, that information would also be useful. higher speeds probably mean it's harder to cross. of course live traffic volumes would also be very useful, if it was available.

[emiltin]

for mode change i think it's ok, since mode before and after the turn is available.

[chaupow]

Considering all discussions I am proposing this approach for this ticket. Open for discussion/feedback please ❤️

New API Proposal

setup

We add two additional variables to the profile table that can be set during setup:

• motorway_user_classification_table
• access_user_classification_table

The user can set an arbitrary integer/classification to edges based on motorway tag and access tag.

process_turn

process_turn(profile, turn, source, target)

• profile is the profile table setup during setup
• turn gives specific information about the turn and includes

Attribute	Read/write?	Type	Notes
angle	Read	Float	Angle of turn in degrees (0-360: 0=u-turn, 180=straight on)
number_of_roads	Read	Integer	Number of ways at the intersection of the turn
is_u_turn	Read	Boolean	Is the turn a u-turn?
has_traffic_light	Read	Boolean	Is a traffic light present at this turn?
weight	Read/write	Float	Penalty to be applied for this turn (routing weight)
duration	Read/write	Float	Penalty to be applied for this turn (duration in deciseconds)

• source and target are information on the road involved in the turn and include

Attribute	Read/write?	Type	Notes
restricted	Read	Boolean	Is a restricted access road? (See definition in process_way)
mode	Read	Enum	Travel mode. Defined in include/extractor/travel_mode.hpp
highway_user_class	Read	Integer	Classification based on highway tag defined by user during setup
access_user_class	Read	Integer	Classification based on access tag defined by user during setup
is_motorway	Read	Boolean	way is a motorway
is_link	Read	Boolean	way is a slip/link road
number_of_lanes	Read	Unsigned	total number of lanes in way

Usage of new API

• divebombs can be prevented by adjusting weight using road_classification.motorway_class and road_classification.link_class information
• mode changes detectable by comparing source.mode and target.mode
• turn duration can be set considering road_classification.num_lanes , number_of_roads and has_traffic_light
• using way types to calculate turn penalties #477 @emiltin adjustments for crossing can be then done using highway_user_class and/or access_user_class
  • e.g. for a walking profile we might consider motorway, trunk and primary as [1] big roads, secondary and tertiary as [2] middle-sized roads, and residential, living_street and pedestrian as [3] normal roads
  • we can then set the following during setup:

   highway_user_class = {
     motorway      = 1,
     trunk         = 1,
     primary       = 1,
     secondary     = 2,
     tertiary      = 2,
     residential   = 3,
     living_street = 3,
     pedestrian    = 3 
   }
  

  • depending on the highway tag, source.highway_user_class and target.highway_user_class will be set to 1, 2 or 3 and can be used to set a turn weight in the lua profile.

Open Question

• Should we add additional is_stop and is_give_way to the turn parameter?

this would result in a breaking API change

Feedback highly, highly appreciated @TheMarex @emiltin @daniel-j-h
Also, thanks for the guidance until now.

[emiltin]

With this approach it seems you only have information about the source and destination leg of the turn. So if you cross straight over a road (say a you cross a trunk road as a pedestrian) you would not get any information about the road you cross?

You get the turn angle and the number of legs in the intersection, but you actually don't know about the geometry and thus which legs/roads you cross.

I'm a bit concerned that classification of just two tags (highway and access) will be too limited. A more general approach where you can use more tags would be preferable, but I understand there are resource limitations.

The naming of motorway_user_class is confusing since it's based on the 'highway' tag. Also the naming *_class seems a bit odd for Boolean values?

[chaupow]

So if you cross straight over a road (say a you cross a trunk road as a pedestrian) you would not get any information about the road you cross?

facepalm Yes, of course you would need it too. Will add information about the street that needs to be crossed

I'm a bit concerned that classification of just two tags (highway and access) will be too limited. A more general approach where you can use more tags would be preferable, but I understand there are resource limitations.

I will take another look at the extraction phase. I still haven't got a full overview of when we have or lose access to certain information/tags. Let me see whether I can make it more general.

The naming of motorway_user_class is confusing since it's based on the 'highway' tag.

Ugh. I keep confusing highway tag and motorway key. I meant highway all the way through! Thanks!

Also the naming *_class seems a bit odd for Boolean values?

I agree. It is actually the same values that we have in process_way at the moment. This should be refactored & naming should not be continued in process_turn.

Thanks for the super rapid fast feedback

expect a second version of the proposal by the end of the day

[TheMarex]

What you might want to think about is having an abstraction between the source of the values (various guidance related structs) and the API you actually expose in Lua.

For example you can save the value of road_classification.motorway_class in a new property of ExtractionTurn that could be called source_is_motorway or something similar like that. This would protect us against internal changes to our code that make rename/change the encoding of these values.
Some values like road_classification.may_be_ignored seem very guidance specific in their meaning and I would worry that if we change guidance code it would affect the API.

this would result in a breaking API change

We currently version the Lua API so if we need to break the API we can do that. Though maybe we can think about what it would mean to avoid breaking the API for these changes?

Since most of the issues mentioned here are quite generic, I would try to find a few examples for each heuristic you want to implement. That should give you an idea how often these cases occur and maybe help you to prioritize.

[MichalPP]

some other things that would be nice to have:

• node tags on the crossing (eg when pedestrian crosses a highway on traffic_calming=table, it should have lower penalty) - maybe an enum defined similarly to highway_use_class?
• some ability to add exclude classes: eg child exclude class would exclude crossing major roads without a traffic_light
• virtual turns (allow node_function() to add penalty to a segment #3862) : things like traffic_calming=bump would add a penalty (even though it's not a turn)
• exclude classes and virtual turns: that would allow to exclude kerbs for wheelchair routing

[chaupow]

node tags on the crossing (eg when pedestrian crosses a highway on traffic_calming=table, it should have lower penalty)

Good point. I'll consider it. I need to makes tests to see how much storage consumption will increase when I add new attributes/keys and I am afraid that traffic_calming is very specific. Is it? I am not sure.

some ability to add exclude classes: eg child exclude class would exclude crossing major roads without a traffic_light

Currently, you can set the turn weight to infinity by setting

turn.weight = constants.max_turn_weight

So as long as the turn function is able to identify the turns you want to exclude, you can exclude it by setting it's turn weight very high. I will think about an exclude method for turn functions but I am afraid it's not easily designable. In contrary to the way function for example, where you can just exclude certain highway tags, the turns do not have an easy identifier that you can use to exclude things. If you have an idea, let me know!

exclude classes and virtual turns: that would allow to exclude kerbs for wheelchair routing

I see! Being able to identify kerbs for wheelchairs seems a legit/important case. From the design point of few, I feel like this shouldn't be a turn function related issue though. Instead, it would make more sense to do it when processing ways. (is this correct/do you agree?). I am guessing that wheelchairs would not want to take any roads/ways with kerbs. So those ways should be excluded in the beginning. If the way is excluded, then there is no need to exclude turns into such ways because the ways are excluded anyways.

I think,

• if a road should be routable in general, but only a certain turn into this road needs special exclusion/penalty it should be handled in the process_turn function.
• If a road needs to be excluded/penalized independent on how you turn into the road, it should be handled in the process_way function

If you agree I can write up a ticket thinking about how process_way can identify ways with nodes that have certain tags on the way.

[MichalPP]

Exclude class: the one that I can set with exclude=toll (or similar) at the URL. the advantage is, that with single effort, I have two-three separate routing engines (like normal foot, wheelchair, child at a single OSRM instance). from my point of view, I just add result.forward_classes['wheelchair'] = true; in my lua profiles :)

another examples except for traffic_calming=table are various traffic lights (with button, with sounds, ...), whether highway=crossing is present,

virtual turns: maybe a better example is to add some penalty on any traffic calming for car profile. the traffic calming is sometimes on a crossing, sometimes in the middle of a road (if you look at #3862, there was some info on the implementation). maybe we could remove process_node lua function overall and make every node function a virtual turn?

[MichalPP]

on the crossed road(s), which is needed for bicycle/foot routing: maybe and extra array of highways with the same info as source plus angle (not sure about the angle if the highway goes through the node)

a very nice feature would be to have also non-routable lines, like removed highways (like primary highways with foot=no) and also fences (that sometimes have access tags and opening_hours), railways/trams, (maybe boundaries). I could add them an enum mode as proposed but set rate to 0. So just remove those with rate=0 and mode not nil after lua turn_function (and not right after way function).

[chaupow]

First Approach

I started implementation in PR #4789. I haven't decided on a final API yet but I started making changes to expose information to the turn function that does not really cost us more memory during the process (see the table in a former comment). I also left the parameters as they are to prevent a breaking API change.

The information exposed to the turn function as attributes of turn are:

  const double angle;
  const int number_of_roads;
  const bool is_u_turn;
  const bool has_traffic_light;
  const bool is_left_hand_driving;

  // source info
  const bool source_restricted;
  const TravelMode source_mode;
  const bool source_is_motorway;
  const bool source_is_link;
  const int source_number_of_lanes;

  // target info
  const bool target_restricted;
  const TravelMode target_mode;
  const bool target_is_motorway;
  const bool target_is_link;
  const int target_number_of_lanes;

  const std::vector<ExtractionTurnLeg> roads_on_the_right;
  const std::vector<ExtractionTurnLeg> roads_on_the_left;

  double weight;
  double duration;

The difference to the current version is is_motorway, is_link, number_of_lanes for source and target and information about other roads at the intersection with roads_on_the_right and roads_on_the_left.

The two vectors roads_on_the_right and roads_on_the_left give information about other outgoing edges at the intersection where the turn is made (should we do the same for incoming edges too?).

• todo: include incoming edges too

They are ordered geometrically counter-clockwise and are split to two vectors depending on whether they are to the right or left, when coming from source and turning into target. Each of these roads are presented by an ExtractionTurnLeg which includes

  const bool is_restricted;
  const TravelMode mode;
  const bool is_motorway;
  const bool is_link;
  const int number_of_lanes;

The PR is still WIP but it's a start. If you want you can use it to play around and see whether it can already solve one/some of your use cases (maybe partly).

Next Steps

For now I prioritized the attributes I would like to expose in the context of this issue as follows:

• highway tags (from source & target & other roads at intersection)
• access tags (from source & target & other roads at intersection)
• speed (from source & target & other roads at intersection)
• stop sign / give way at turn

I might try implementing all of them and see whether it is feasible or not.

edit: stops are not easy. might be out of scope for now. will also take a second look at the PR that targeted stops before.

Open issues

As for the many other things we have discussed here:

• exclude class: Implementing an exclude class for turns is a bit more complicated and out of scope for this ticket. This should be solved in another ticket. I think even finding a good API design is already hard
• traffic_calming: Same as exclude classes. Also I suspect, this is more related to the way process function somehow. Even if a node is tagged, in OSRM I guess traffic calming would be processed when processing roads semantically.
• have non-routable lines: this is actually a very good point. when processing turns, I am pretty sure OSRM does not know anymore whether you have to cross railroads or similar roads. Should be targeted/researched but not in this issue.
• virtual turns: There is already a ticket. I feel like this is also out of scope for this ticket at least.

I'll keep you all updated 😄

[emiltin]

The concept of crossing roads is a bit tricky, since all ways meet at a central node. Consider this simple situation:

  c
a n b
  d

If 'anc' is a big road, then going from d to c mean you cross a big road. If 'anc' is oneway, then one of the legs would be incoming and thus not included in the two vectors roads_on_the_right and roads_on_the_left. I think this shows we also need incoming legs.

If 'anc' is big and 'dn' and 'nb' are smaller sideroads, then going from d to c does not require crossing a big road (assuming right-side driving). To determine this you need to check if there's a big road on both sides.

Another case would be 'na' an d 'nb' being bigger roads but both oneways away from n. In that case you don't really cross a big road when going from d to c. Turn restrictions would really also need to be considered.

[chaupow]

PR #4789 is now open for review.

What the PR does:

• expose information about source and target when turning
  • restricted, mode
  • is_motorway, is_link, number_of_lanes
  • highway_turn_classification, access_turn_classification
  • speed
• expose information about other roads at intersection when turning
  • whether on the left or right of turn
  • is_restricted
  • is_motorway, is_link, number_of_lanes
  • highway_turn_classification, access_turn_classification
  • speed
  • is_incoming, is_outgoing

What the PR does not do:

• information on stops/give ways/priority Stop Signs for Profiles #2652 Priority Roads for Profiles #3003
• information about roads of other profiles at intersection (e.g. knowing the car speed when routing bikes)
• information about non-routable lines (e.g. knowing that rails have to be crossed when walking)
• implement virtual turns allow node_function() to add penalty to a segment #3862
• consider nodes on roads such as traffic_calming. A related issue would be Take Traffic Calming Road Furniture Into Account #3021 .

[chaupow]

Closing and update top comment to summarize