Work towards more configurable vehicle profiles

[karussell]

For the next version 0.14 we plan to start work on “external vehicle profile definitions”. In previous work this was called “flexible branch”, but the profile stuff is also handy for CH e.g. for defining the weighting, vehicle and U-turn cost for the CH-profile, see this discussion and this new issue.

Here some other open source routing engines and how they do it:

• OSMAnd defines profiles via xml and supports language features in it like this “if” and “select” stuff: https://github.com/osmandapp/OsmAnd-resources/blob/master/routing/routing.xml
• valhalla allows tweaking the profiles per request in the API: https://valhalla.readthedocs.io/en/latest/api/turn-by-turn/api-reference/
• OSRM defines profiles via lua profiles. Possible only for import: https://github.com/Project-OSRM/osrm-backend/tree/master/profiles
• BRouter has its own scripting language and allows to define profiles: http://brouter.de/brouter/costfunctions.html

Although it is very cool to have the scripting feature (see the flexible branch) we’ll not include this, at least not at the beginning due to the security implications. So more like OSMAnd does it. Or less flexible, but easier for users like valhalla.

The short term goal is to make it possible to change profiles without Java knowledge, so probably we need to define kind of unit tests in a non-Java way too like OSRM does, but I’m unsure. The long term goal could be to make creating profiles possible without compiling GraphHopper (not sure if this is really required).

When we introduce this profile stuff we’ll go with an iterative procedure, start quickly and see what is possible. We’ll very likely also break old API, so this stuff will have breaking changes in 0.15 (coming from 0.14). We’ll allow the profile definition e.g. in the config.yml or one file per profile. Additionally it should be somehow possible to create a hierarchy e.g. define motor vehicle and use this as base in car and use car in the truck profile definition or something like this to avoid starting from scratch.

It will be possible to include such a “profile” per request and send this via yml or json data as a POST request. Also, when you have tuned it enough it will be possible to use exactly the same content to define a CH profile e.g. via a separate file or part of the config.yml. This means that we need an endpoint that supports POST requests. We’ll start with a new endpoint for that and improve not only the request stuff but likely also the response like commented in this issue. Due to these changes the endpoint needs a new name, e.g. /routing instead /route? This is hard …

On Android this will be possible via a FlexModel class and so no jackson should be necessary as separate dependency to parse the YML and JSON. But this is not yet 100% clear because we need the YML parsing at import and CH preparation time. Maybe we have to split CH core to avoid this or find another solution.

If anybody has input, questions or suggestions, please let me know about them

[otbutz]

Very interesting topic!

I’d say we should split this whole block into a few subquestions:

1. What is our targeted feature set for the MVP(speed profiles, max width, turn-costs, etc) *
2. Which format is the best for our use case? Ease of use, validation, modelling complex rules(SpEL?), tooling
3. How do we deal with versioning? Introducing new and deprecating old features
4. Do we want to recreate the current profiles(car, foot, bike) and only good forward with the new approach?

The request stuff should be the last step IMHO.

*: commercial vehicle routing would be a good testcase. Different vehicles tend to have different profiles and we need to deal with lots of tags and rules. If the model works good for this usecase it should work for others aswell.

[easbar]

Did you try to create a parameterized profile that can be tweaked such that it can match all (or maybe most) of the current profiles ? If yes maybe this would be a really good starting point because it would allow us to specify all the current profiles and everything in between. I would be surprised if this wasn’t ‘enough’ to get started with flexible profiles, but if it isn’t what are the major things that need to be added ? If it is not possible (or too hard) to create such a universal parameterized profile what are the main obstacles that keep us from creating it ? Is there anything that can be left out to make it easier for the start and would the result still be useful for the flexible profile scenario ?

Also what is a ‘profile’ exactly ? For me it is some kind of hybrid of a ‘FlagEncoder’ and a ‘Weighting’. In any case it should give us edge- (and turn-) weights (and times) for all edges/turns based on the ‘properties’ of an edge (the encoded values). Is this what you have in mind ? Flexible profile = flexible way to map encoded values and/or OSM tags to edge/turn weights/times ?

Another question: You are talking about specifying the profile per request, but doesn’t this also depend on the way the map was imported ? Say you specify a weighting that uses some OSM tag that was not included during the map import, how should this be handled ? And what about ‘external’ data that should is not included in the ‘edge properties’, but should be included for the weight calculation nonetheless (like traffic information ?).

[karussell]

What is our targeted feature set for the MVP

I think either we recreate a car profile from scratch or add certain, more requested features like “avoiding” certain highways or ferries, or changing preferences of official bike routes.

Do we want to recreate the current profiles(car, foot, bike) and only good forward with the new approach?

Yes, at least at some point.

How do we deal with versioning?

Like we currently deal with backward compatibility: we would not do versioning and just introduce the change or remove features. That is the advantage of still being at 0.x

@easbar

Did you try to create a parameterized profile that can be tweaked such that it can match all (or maybe most) of the current profiles ?

No, not yet. My main goal was more to tweak the current flag encoders without Java.

and everything in between .

The task is already relative big, even without recreating FlagEncoders via “profiles” , so I’m a bit more leaned towards doing this later. But maybe this is the wrong approach. As you are definitely right that this would show the completeness of this approach. The big problem is that FlagEncoders do so many things like calculating “cached values” (like accessEnc, averageSpeedEnc) from tags, calculating turn restrictions and probably more that we would need to refactor. Furthermore there is no clear vehicle-hierarchy created that results in some duplication and duplicative tests (not necessary bad).

Still it would be a big win to clear this up and remove the too unflexible FlagEncoders.

@easbar

Also what is a ‘profile’ exactly ? For me it is some kind of hybrid of a ‘FlagEncoder’ and a ‘Weighting’.

Yes. I would still define a “profile” more like a Weighting that calculates the correct (potentially time-dependent) weight per edge and uses EncodedValues. This “profile” is then also used instead of the FlagEncoder for all EdgeFilter tasks like for location snapping. The task of handling the “cached EncodedValues” (accessEnc, averageSpeedEnc) would be also required to be done, i.e. feeding these EncodedValues on import time and using them at query time.

to create such a universal parameterized profile

It is very important to split profiles into smaller units (creating a vehicle hierarchy). The worst example is the DataFlagEncoder which is something that does too much and is at the end not very useful.

Another question: You are talking about specifying the profile per request, but doesn’t this also depend on the way the map was imported ?
Say you specify a weighting that uses some OSM tag that was not included during the map import, how should this be handled ?

If an OSM tag (i.e. EncodedValue) is not imported, you cannot use it at query time and it will give you an illegalargumentexception or something

And what about ‘external’ data that should is not included in the ‘edge properties’, but should be included for the weight calculation nonetheless (like traffic information ?).

There is no reason anymore why it shouldn’t go into an EncodedValue (except for variable length data like e.g. string names). Still having an option to define arbitrary parameters in the profile that are then used in the Weighting should be also considered. And allowing time-dependent parameters should be also in the scope of this task. Puh

[otbutz]

@karussell

The big problem is that FlagEncoders do so many things like calculating “cached values” (like accessEnc, averageSpeedEnc) from tags, calculating turn restrictions and probably more that we would need to refactor.

Sounds like our first goal for this milestone.

@karussell

If an OSM tag (i.e. EncodedValue) is not imported, you cannot use it at query time and it will give you an illegalargumentexception or something

Maybe we should define mandatory and optional values for profiles. There are a lot of OSM tags out there which might or might not influence routing decisions. But I go out on a limb and say that we can safely ignore some of them if they’re not present. eg creating a truck profile which is able to honor very specific tags could still work if they are not present. We should not force users to have a big graph if it’s not really necessary.

@karussell

except for variable length data like e.g. string names

Do we have a concept for addressing data “off-graph” ? Would be nice for fast changing traffic data or things which are to big to put it in the graph.

[karussell]

@otbutz

Do we have a concept for addressing data “off-graph” ? Would be nice for fast changing traffic data or things which are to big to put it in the graph.

You can always hold such information in a big array (or yet another DataAccess) where the index is the edgeId. But this is probably for another discussion

[easbar]

@karussell

I think either we recreate a car profile from scratch or add certain, more requested features like “avoiding” certain highways or ferries, or changing preferences of official bike routes.

@karussell

No, not yet. My main goal was more to tweak the current flag encoders without Java.

Ok, so creating a kind of fully parameterized profile that can be adjusted to all current profiles is still too ‘hard’ and for now we should rather make the single existing profiles ‘configurable’ then ? Makes sense to me. I guess extracting some of the hard-coded stuff from the current FlagEncoders into config files would be a step into the right direction then.

@karussell

The task is already relative big, even without recreating FlagEncoders via “profiles” , so I’m a bit more leaned towards doing this later. But maybe this is the wrong approach. As you are definitely right that this would show the completeness of this approach.

Yes, I see. If we can allow ourselves to do this step-by-step I would also prefer to start with smaller
changes. It will probably mean that the way profiles are defined will change multiple times (easier for development, harder for users).

@karussell

Furthermore there is no clear vehicle-hierarchy created that results in some duplication and duplicative tests (not necessary bad).

Why do you think we need a hierarchy of vehicles ?

@karussell

Yes. I would still define a “profile” more like a Weighting that calculates the correct (potentially time-dependent) weight per edge and uses EncodedValues. This “profile” is then also used instead of the FlagEncoder for all EdgeFilter tasks like for location snapping. The task of handling the “cached EncodedValues” (accessEnc, averageSpeedEnc) would be also required to be done, i.e. feeding these EncodedValues on import time and using them at query time.

There seems to be a mismatch between the new ‘profiles’ that shall be added and the existing classes in GH. A ‘flexible way to map OSM tags to edge- and turn weights’ would have to be represented by a combination of at least FlagEncoder, EdgeIteratorState and multiple nested Weighting instances (TurnWeighting, AvoidEdgesWeighting, … and the ‘actual’ Weighting like FastestWeighting).
How should we map the things specified in the ‘profiles’ to these things ?

@karussell

The task of handling the “cached EncodedValues” (accessEnc, averageSpeedEnc) would be also required to be done, i.e. feeding these EncodedValues on import time and using them at query time.

What do you mean here exactly ? What is cached and where ?

@karussell

It is very important to split profiles into smaller units (creating a vehicle hierarchy).

Why is this so important ? To reduce duplication ? I do not think splitting into smaller units necessarily requires the creation of a vehicle hierarchy (think composition vs inheritance). Also I do not understand how this is supposed to work. I can easily imagine situations where rather than ‘inheriting’ most of the configuration from an existing profile I would like to assemble different bits of the configuration from multiple different other profiles. Then again I am sure taking all the configuration from an existing profile like car and only doing a small change (like excluding ferries) should also be easy to do (because it might be needed by many).

@karussell

The worst example is the DataFlagEncoder which is something that does too much and is at the end not very useful.

Can you explain a bit more what the problem with DataFlagEncoder is ?

@karussell

And allowing time-dependent parameters should be also in the scope of this task

You mean in the long run ? Can we not restrict this task to constant time weights (for now) ? It seems complicated enough Maybe later we can make the whole selection of the profile time-dependent (specify a different profile for each point in time rather than making every property of a single profile time-dependent).

@otbutz

Maybe we should define mandatory and optional values for profiles. There are a lot of OSM tags out there which might or might not influence routing decisions. But I go out on a limb and say that we can safely ignore some of them if they’re not present. eg creating a truck profile which is able to honor very specific tags could still work if they are not present. We should not force users to have a big graph if it’s not really necessary.

Hmm but can we not force users to adjust the profile if it uses things that are not present in the graph ? I think I would prefer an error in case some encoded values are used that are not present.

Can we come up with a list of minimum things that should be configurable ? Maybe some future decisions can be based on this.

[karussell]

@easbar

Ok, so creating a kind of fully parameterized profile that can be adjusted to all current profiles is still too ‘hard’ and for now we should rather make the single existing profiles ‘configurable’ then ? Makes sense to me. I guess extracting some of the hard-coded stuff from the current FlagEncoder s into config files would be a step into the right direction then.

Why do you think we need a hierarchy of vehicles ?

It is not required. But the process will lead us to this. At least I think it will. E.g. when you create a car profile then for truck you define base:car (Or maybe even the opposite that car is a truck with small dimensions or something). And for motorbike you probably don’t want a base:car but more base:motorvehicle and then also use this for car to avoid repeating stuff. The access rules for OSM “suggests” this hierarchy: Key:access - OpenStreetMap Wiki

There seems to be a mismatch between the new ‘profiles’ that shall be added and the existing classes in GH. A ‘flexible way to map OSM tags to edge- and turn weights’ would have to be represented by a combination of at least FlagEncoder , EdgeIteratorState and multiple nested Weighting instances

I wouldn’t call it mismatch. But such a new profile would influence multiple parts of the code, yes.

What do you mean here exactly ? What is cached and where ?

In CarFlagEncoder we define speedEncoder and accessEncoder that are only usable for this specific car and both “cache” the interpretation of a few OSM tags. E.g. if I want a new police_car I would define base:car but the “cached” accessEncoder is no longer usable from car as police_car can go the one-way streets backwards. So for police_car we need the pure data (several access related OSM tags) and also a way to find out if we can use e.g. the “cached EncodedValues” like accessEncoder or speedEncoder of the base class.

Why is this so important ? To reduce duplication ?
Can you explain a bit more what the problem with DataFlagEncoder is ?

The DataFlagEncoder was meant to provide a base for every use case like car and bike etc. And the plan was that you just need to create and configure it. But at the end it is a suboptimal truck profile and heavily dependent on the GenericWeighting class and all the features like access restrictions are still not configurable (except default speeds)

requires the creation of a vehicle hierarchy (think composition vs inheritance)

Ah, sure. If we find a way to do composition this would be even better.

I have played a bit around how a profile could look like and if we can use yaml or should create our own scripting language. Everything has pros and cons. Have written my findings here and will continue there.

With the following variables: access, speed, delay and priority we can likely cover most of the use cases:

calcMillis:
  time = distance_in_m / speed_in_kmh * 3.6 + delay_in_sec
calcWeight:
  weight = access? time * priority : infinity

The problem is a bit the dependencies. E.g. if we state “access=true if road_class==motorway” then a speed value is required if this is not known from the base profile. We could also remove the access variable and let the user define speed=+0 for these cases but IMO this is wrong as both have separate meanings.

Another tricky thing are the speed values itself. Should users be able to only set the allowed maximum speeds e.g. per road_class and we estimate the average speed values from those max speeds? Or should they define the “lower level” average speed values directly? Or both should be possible?

@easbar

I think I would prefer an error in case some encoded values are used that are not present.

[boldtrn]

@karussell

The access rules for OSM “suggests” this hierarchy: Key:access - OpenStreetMap Wiki

I think reflecting the OSM hierarchy is a good idea .

[karussell]

I think reflecting the OSM hierarchy is a good idea .

I would not always copy the OSM concepts without thinking as this makes us too dependent on OSM (although OSM is ok for access). Hopefully most features will also work for other data formats like TomTom or Here Maps. This is also the reason we do not have a strict OSM tag to EncodedValue mapping and avoid stuff like motorroad=* (which is basically highway=trunk + access restrictions) and we have things like “road_environment” that are not existing in OSM. Of course the disadvantage of this approach is that mappers do not feel home right away.

[karussell]

Have created a proof of concept for the simple scripting language https://github.com/graphhopper/graphhopper/compare/gscript#diff-b7900253b294045b932b231780743a9aR19

Basically it is able to look for a certain encoded value (selected enum or Decimal) and then assigns an (average) speed or a priority.

This should be self-explanatory:

speed:
     road_class == 'motorway' ? 80
     road_class == 'primary' ? 70
     road_environment == 'ferry' ? 10
     100 # unconditional => catch all => default
priority:
     road_class == 'service' ? 30 # factor 30 => try hard to avoid it
     1 # default

[easbar]

@karussell

I wouldn’t call it mismatch.

I just meant to say there is a difference (the concept of a ‘profile’ is not reflected in the code currently).

@karussell

Another tricky thing are the speed values itself. Should users be able to only set the allowed maximum speeds e.g. per road_class and we estimate the average speed values from those max speeds? Or should they define the “lower level” average speed values directly? Or both should be possible?

Hmm, I think it should definitely be possible to specifies that are actually used by the engine. Maybe we can allow maximum values as you describe on top of this.

@boldtrn

I think reflecting the OSM hierarchy is a good idea .

Yes for the access rules/road types this also makes sense to me, but I do not think this will work for the whole ‘profile’. For example what if the ‘profile’ includes blocked areas (that are blocked for multiple different motorized vehicles for example). It would be inconvenient to specify these areas for many profiles and inheriting from a base profile just because it has the same blocked areas will often not work because of other properties of the profile that the vehicles do not share. I think this problem is the same for some advanced turn cost configuration etc. : There will be cases where you want to ‘inherit’ something from one profile, but something else from another. Therefore I think it would be ideal to have some kind of library of (community-made) profiles that I can use to assemble my own profile (take the weighting from one profile, some specific turn cost configuration from another and so on). Unfortunately at the moment I do not know how this can be done, but maybe there is some yaml processing tool that allows using a key into another file ?