Mode Specific Turn Restrictions

[grant-humphries]

In OpenStreetMap one can specify that turn restrictions apply only to particular modes of travel. Turn restrictions are relations in OSM and are tagged with the following:

type=restriction restriction=* (i.e. no_left_turn)

When there are exceptions to which kinds of vehicles the turn applies to they also have the following tag:

except=*

the main four values for this tag are: bicycle, motorcar, psv (public service vehicle), and hgv (heavy goods vehicle) although OSM users can always introduce new values.

We need OTP to be able to implement these mode specific turn restrictions because there are several key intersections in Portland where bikes are allowed to make turns that cars are not.

[abyrd]

instead of being boolean, TurnEdge member 'restricted' could store a mode mask. The values for each mode are already defined in TraverseModeSet.

The only modes that are relevant when routing on streets are: private static final int MODE_BICYCLE = 1; private static final int MODE_WALK = 2; private static final int MODE_CAR = 4;

There is a potential increase in memory consumption when switching from boolean to a numeric type, but all the on-street modes fit in a signed byte. I do wonder how many bytes the JVM is already using for the boolean. It does some packing:

http://stackoverflow.com/questions/229886/size-of-a-byte-in-memory-java http://stackoverflow.com/questions/1907318/java-boolean-primitive-type-size/

[abyrd]

Mode-specific turn restrictions are implemented. (Tiny)TurnEdge.restricted is now restrictedModes, which holds a Set of restricted TraverseModes, or NULL if the turn is not restricted.

This is obviously overkill for turn restrictions where there are only two bits worth of information. I'm just trying out an approach that could potentially be used throughout OTP wherever modes are needed. There are already three ways of specifying modes: enum TraverseMode, TraverseModeSet bitmasks, and StreetTraversalPermission. I was hesitant to define yet another bunch of constants or borrow a subset of the bitmasks in TraverseModeSet.

I added a method to TraverseMode that provides shared, immutable sets of TraverseModes using Collections.unmodifiableSet() wrapped EnumSet. EnumSet looks like the proper Java way to approach bitmasks, and though there were apparently implementation mistakes in Java 1.5 the 1.6 version looks good. It does mean object references to the mode sets, but that may be the lesser of several evils.

I will of course switch back to a straightforward primitive field if this proves to be too slow or space-consuming.

Various additional mode-related thoughts:

The meaning of TraverseOptions.modes is kind of vague - it represents both the range of all modes to be considered in a search, and the current mode being considered. Retrying with the walkingOptions does the job for now but feels like a hack. I think mode-in-use may eventually need to be a member of State, and mode transitions represented with implicit edges (think bike locker or carshare parking support).

Someday we may want to make StreetModes and TransitModes separate enums, since they shouldn't ever need to be lumped together.

The ability to iterate over Sets in natural order could be used to successively try all enabled StreetModes, inserting implicit mode transition edges where needed. An EnumMap in the Options could store speed/slope parameters for the various StreetModes (including wheelchair), which would then be used in the edge traversal.

It might be practical to use OSM mode names in our enums so ValueOf() works directly on OSM tags. Specifically, renaming CAR to MOTORCAR.

TurnEdge.restrictedModes could potentially represent both the turn permissions and the mode permissions of the underlying street, though that might just make things more complicated.