Support for conditional restriction and/or speed limits

[oxidase]

To handle conditional tags like restriction:conditional support for opening hours must be added into osrm-extract/osrm-contract

Tasks:

• qi opening_hours grammar Added opening_hours grammar #3415
• data type discussion/implementation for time ranges
• grammar extension with semantic actions
• added handling of restrictions https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/restriction_parser.cpp#L58
• added weights updates in osrm-contract

/cc @daniel-j-h

[daniel-j-h]

To clarify here: we don't strictly have to implement this in osrm-backend. It could be a little executable reading a pbf file and generating two csv files for every 5 minutes: one file for speed updates, one file for turn penalty updates.

We then can use these csv files in combination with the Traffic feature. Check the format here:
https://github.com/Project-OSRM/osrm-backend/wiki/Traffic

[daniel-j-h]

We also have to convert the local time in OSM tags to UTC. For this I used

http://efele.net/maps/tz/world/

ogr2ogr -f CSV output.csv world/tz_us_mask.shp -lco GEOMETRY=AS_WKT

before. It's all quite hacky but should work .. I think internally we might have timezone handling already, maybe ping @danpat in chat.

[danpat]

@oxidase This is great. Let me sketch out how I think we could use this so that people could support conditional restrictions.

The basic approach would be:

1. Generate "traffic data files" that set certain road speeds to 0 when conditions require it.
2. Use the "traffic data" features of osrm-contract to load these simulated traffic files.

The limitations are:

1. Data size - it's not feasible to re-contract the whole planet every 5 minutes to keep up with short-term closures.
2. Time-dependent routing - we can only mark closures "now" - if you request a 45 minute route, we will consider the conditions "now" everywhere, even if part of the route may close during the trip.

osrm-contract lets us replace road segment weights by loading CSV files. We can load many files, and they're loaded in the order supplied on the command line - if conflicting data appears, it's last-one-in-wins.

We could have a tool, say, osrm-extract-conditionals, that does the following:

1. Parses the .osm.pbf file, looking for ways and relations with conditional tags.
2. When it encouters one, detect the timezone that coordinates reside
3. Then, generate a record for every 10 minute window for the next year - write these to separate buckets (there are about 105,120 buckets for a year). If the record indicates "closed", set the speed to 0. If the record indicates "open", discard the record (don't add to bucket).

Let's assume for now that these buckets are CSV files in some directory structure. Once the above is complete, we can then do:

osrm-contract --segment-speed-file closures/$(date +%s | round_date).csv whatever.osrm

Other aspects

• Conditional maxspeed - I think we would want to separate maxspeed changes from oneway/closures. If real traffic data is available, it should be preferred over any maxspeed conditional, but actual closures should probably be prioritized over any traffic data.
• Ways/relations/nodes - The above is just a rough sketch - we may need slightly different mechanisms to support conditional tags on the different OSM object types.

I think the next step is to look at the conditional tags and figure out which ones we would want to support (let's do the easiest ones first, eh?)

[karenzshea]

After tooling around with the osrm-extract-conditionals tool and the current restriction parsing in extraction, I've figured out what could be a reasonable way to move forward:

• move conditional restriction parsing into osrm-extract in that osrm-extract has a new flag like --parse-conditional-restrictions and takes a time range of minutes, e.g. 2880 for 48 hours, in which to parse relevant conditional restrictions. That is, extraction will only extract conditional restrictions that will be relevant in the given time window.
• osrm-extract writes all conditional restrictions into a new file like osrm.conditional_restrictions the osrm.restrictions file and no longer writes unconditional turn restrictions to the file. The write to disk then immediate read back into memory of unconditional turn restrictions was leftover from the osrm-extract/prepare merge.
• osrm-contract later consumes this file and, with a couple new flags like --conditional-restrictions-file and --conditional-range, reads in a conditional restrictions file, reads a given time range of minutes, e.g. 2880 for the next 48 hours, and applies weight updates for restrictions that apply during that time range.

Having the tool as part of the osrm-extract step reuses the existing access to Lua profiles for access tag configuration. It also makes keeping the time windows in sync with the extracted data easier and more relevant. Processing more time in advance (like a year) would mean that we miss additional restrictions and would have to account for seasonal time changes and leap year offsets.

This will add a few more iterations (i.e. processing time) over extracted objects because restrictions will need to be parsed out of ways and nodes in addition to relations.

To start it will be simplest to only support restriction:{mode}:conditional tags.

cc @oxidase

[oxidase]

@karenzshea the approach looks good to me, Saving conditional restrictions in osrm-extract is required because {mode} can be taken only from the profile. Also converting via node coordinates to timezone names can be implemented in osrm-extract if a TZ shape file is provided. If it is not provided osrm.conditional_restrictions will be useless and should not be used.

One thing that i would like to add.
osrm.conditional_restrictions must have unresolved conditions like "Mo-Fr 07:00-14:00". osrm-contractor or osrm-customize can use these conditions to check if the condition is active in a pseudo function like (1488380258 is a dummy UTC time date +%s):

• is_condition_active("Europe/Berlin", 1488380258, "Mo-Fr 07:00-18:00") -> true
• is_condition_active("America/Los_Angeles", 1488380258, "Mo-Fr 07:00-18:00") -> false
• is_condition_active("US/Eastern", 1488380258, "Mo-Fr 07:00-18:00") -> true

and update edge weights/durations from the osrm.conditional_restrictions file.

[TheMarex]

Integration into osrm-extract makes sense to me as well. However as @oxidase already pointed out they need to be kept unresolved until the actual application in osrm-contract/osrm-customize since we want to keep osrm-extract free of any assumptions about time (like now or in 48 hours).

Since that would mean we introduce code to check if restrictions apply in the hot code path of time dependent updates it needs to be fast. So I would prefer if the representation of time ranges would be basically integer range checks and normalize to UTC+0. Storing whole strings like "Mo-Fr 07:00-18:00" will add a lot of lookup time.

If we normalize this into distinct filter ranges: Month, Weekday, Hour we can represent every (sensible) restriction as integer ranges: (1-12) (Month) (1-7) (Weekday) (0-24) (Hour) as we all know from how dates are represented.

Mo-Fr 07:00-18:00 would become: Month: 1-12 Weekday: 1-5 Hour: 7-18.
So we would have a collection of (month_range, weekday_range, hour_range) that we would need to save for every restricted turn. This is what we could save in the osrm.conditional_restrictions file normalized to UTC+0.

In osrm-contract we would need to do the following:

1. Compute the month, weekday hour from a given timestamp
2. Read in the osrm.conditional_restrictions file
3. Find all turns where our current point in time matches all three ranges.
4. Disable those turns by setting the weight to INVALID_EDGE_WEIGHT

However (3) might become slow depending on the number of restricted turns. If a linear scan is too expensive we should switch to implement a Segment Tree for each month, weekday and hours. That way you could get a list of all turn edges by doing three segment tree queries and intersecting the resulting lists.

[oxidase]

@TheMarex points 1,2,4 are already implemented in osrm-extract-conditionals. For point 2 opening hours strings are always parsed to OpeningHours structure. It is possible to add binary (de)serialization for ConditionalRestriction and OpeningHours to save time and parse strings once.

For point 3, almost all time conditions are periodic and some conditions can be stacked and combined, like on some weekdays but not on some specific dates. So only a bounded time range for pre-generated intervals can be used. I am for the linear lookup as the first implementation, and when use-cases will be well-defined make an interval tree implementation if it will be needed.

[oxidase]

Closed via #3841