Excluding specific roads at query-time

[TheMarex]

This issue is a planning ticket for upcoming features in the 5.9 series.

Exclude Overlays

Goal

Enable users to exclude certain classes of roads at query time. The typical use case for this is excluding highways or ferries.

API changes

Lua profile

Instead of hard-coding specific classes we want to keep this more general. This requires us to have an interface in the profiles to:

1. Specify the existence of a exclude flag combinations and what classes they cover
2. Mark ways with true/false if they fall into that exclude category. #4203

This is a sketch of what the interface could look like:

profile {
-- defines combination of classes that should supported for the exclude flags
"excludable": Sequence { Set { "motorway" }, Set { "ferry" }, Set { "motorway", "ferry" }},
"classes": Set {"motorway", "ferry", "restricted", "toll"}
}

function way_function(way, result)
   result.forward_classes['motorway'] = way:get_value_by_key('highway') == 'motorway'
   result.forward_classes['ferry'] =  way:get_value_by_key('route') == 'ferry'
end

HTTP/node

We need a new query parameter to select which avoid layer (if any) to use.

• exclude Array of String Name of the classes to exclude. (Default: none)

Example: http://router.project-osrm.org/-100.063476,37.230328;-100.898437,35.817813?exclude=highway,ferry

{
   "coordinates": [[-100.063476,37.230328], [-100.898437,35.817813]],
   "exclude": ["highway", "ferry"]
}

Implementation changes

1. While parsing the OSM ways we need to keep track of all referenced exclude classes and save all ways that are marked with true.

2. Flags need to be propagated up EdgeBadedGraphFactory and should be indexed by EdgeBasedNode (e.g. a node in the turn based search graph)

3. The algorithm dependent tools need to be extended:

   • osrm-customize will run the customization for every exclude layer (and with no exclude flags at all).
   • osrm-contract will create an own (filtered) graph for every exclude layer and contract it

4. We need to modify the engine to accommodate multiple overlays:

   • When exclude is passed the RTree should not snap on nodes with a matching exclude flag
   • CellStorage needs to be able to store multiple weight vectors (one for each exclude overlay)
   • We need a way to go from string to ID of the exclude layer in the CellStorage
   • We need an interface to get exclude flags for the base graph
   • The search function needs to be able to take advantage of optional exclude flags

EDIT: The flag got renamed from avoid to exclude to make the behavior more explicit and avoid (hah) confusion.

[emiltin]

cool. a use case relevant for us is routing for cargo bikes, where you need to avoid steps (you can push a bike on steps if needed, but not with a cargo bike), certain cycle-barriers, etc. instead of running a separate profile for cargo bikes, we could use the normal one and just avoid these when the user requests a route for cargo bike.

however, these barriers are tagged on nodes. so it would require avoid flags on nodes as well as ways.

[MichalPP]

another use case is opening_hours for parks/places/barriers or unlit footways at night.

[TheMarex]

Updates the draft at the top after a discussion with @danpat and @oxidase. We now only set classes in the way function and you need to explicitly define which combinations need to be supported.

[danpat]

@TheMarex I'd suggest that the Lua profile property name is avoidable or avoidable_class_combinations, not just avoid.

I think that property names should generally be adjectives or nouns, avoid is a verb and sort of implies that some kind of avoidance action will be taken during profile processing. It's only a semantic issue, but it'll make the profiles easier to understand without extra docs.

[danpat]

Another implementation note: if profile['avoidable'] is an empty array, we could consider not storing any class information - this would make the memory overhead optional for folks that don't want this feature.

That said, access to road class flags in the debug tiles could be nice to have, even if avoidance overlays aren't available.....

[emiltin]

profile.avoid is already used for things that should always be avoided.

[TheMarex]

Some more notes on this feature after a discussion with @oxidase and @karenzshea:

1. We want to limit the maximum number of avoid combinations to 8 (meaning we can pack this information into an 1 byte value per edge).
2. We want to implement it an a way that makes it transparent to the algorithms what avoid flags are used: Each avoid flag combination gets an own Datafacade.
3. We want to make this generic for both MLD and CH, but the focus is on MLD.
4. For MLD the implementation is simple: One overlay per avoid flag. For CH: We have the choice between two approaches: One graph hierarchy that is valid for all avoid combinations (needs changes to the witness search) or one separate hierarchy per avoid flag.

[TheMarex]

Thinking about this a little more we can also use this to expose any user-defined class on a per-edge basis:

1. Every edge/segment needs will get a byte associated with it that encodes the class. Each class will correspond to a bit that is set in the byte. This would limit the number of classes to 8.
2. Every combination of avoid flags would map to a mask that encodes a combination of classes.
3. We can still limit the number of avoid combination to 8, because everything else would just be insane memory wise.

[TheMarex]

Current brain dump on how this will work and where I see problems:

1. Having a dedicated Datafacade per avoid flag: Problems:

   • We would need to transparently hide nodes in the base graph
   • This requires checking at runtime if an node can be used or not (using a mask on the ClassData)
   • We don't want to change the performance for the case where we don't use avoid flags
   • The routing algorithms access the base graph over calling GetAdjacentEdgeRange or BeginEdge and EndEdge. It is hard to insert something there that checks if an edge should be shown. Possible alternatives:
     • Pull avoid flags down in the search algorithms.

2. The API layer needs a way to translate from string to ClassData mask. For this we need data that is only in the Dataface. Kind of a chicken-egg problem.

3. We need to validate a request based on user-defined strings for which we also need the Datafacade.

[jellevictoor]

could this be extended for a more granular usage? say i want to avoid the center of avignon in all my queries during juli without having to regenerate my graph?

[frodrigo]

@jellevictoor You can achieve this by preprocess the data and add a tag to all ways in centre of Avignon, then use this tag as class. But whit this feature you can't do this in a generic way. As the maximum number of class if 8 and must be done before building the data.

[mohsen3]

+1 for this issue. I am actually looking for routing around a fixed obstacle polygon similar to #892, but I am fine if the polygon can be specified at the preprocessing stage too. This is specially useful in cities with environmental avoidance zones. This issue is a good way for resolving the polygon avoidance problem.

[danpat]

@mohsen3 This issue is about avoiding certain classes of roads (e.g. highways, etc) that you can identify during pre-processing. It does not enable totally dynamic selection of edges at query time.

There is a different pull request https://github.com/Project-OSRM/osrm-backend/pull/4167 that is about enabling polygon lookups during pre-processing, which would allow you to penalize ways within certain regions, but that change is not yet merged.

[TheMarex]

I've been thinking about how to implement this for CH and this is what I've got so far:

Option 1: Completely separate CHs

By filtering the graph for each avoid combination we can create multiple graphs and contract each one independently. This will require a lot more memory/disk and pre-processing time. Since these graphs don't differ too much (only few nodes are actually avoidable) most of this will just be duplicated data/computation. The upside here, this is super simple to implement and straight forward to integrate. Also the query speed will not be impacted at all.

Option 2: Only separate CHs for the avoidable nodes

The main idea here is to have one CH for all non-avoidable nodes and for each avoid-combination only a CH of the usable nodes.

1. We force all "avoidable" nodes to be the highest nodes in the contraction hierarchy.
2. During contraction we terminate when there are only avoidable nodes left.
3. For every avoid-combination we will make a copy of the core-graph implied by the current nodes.
4. Filter the core graph for each avoid-combination and contract the resulting sub-graph.

Now the interesting challenge here is how we piece together a whole CH from these pieces during query time. We have some constraints, for example introducing new node IDs will leads to a lot of problems with unpacking and indexing of other data structures. Storing avoid-CHs as completely different graphs means we need to keep track of when we switch graphs and makes the whole query algorithm quite complicated. What we ideally want is to have everything stored in one graph data structure but only allow the search algorithm to see the "right" subgraph. We could do this by selectively hiding edges from the search. (one std::vector<bool> indexed by EdgeID for every avoid combination)

[mohsen3]

Thanks @danpat & @TheMarex

1. I am not familiar with the internals of OSRM. Is there any good document about it?
2. That would be great if OSRM supports a way to dynamically enable/disable each obstacle at query time. Specifying all possible combinations at compile time may work for many cases, but consider that there are 2^n possible combinations.

[danpat]

This landed with #4427 and #4315