use compass bearing/direction when selecting start way

[emiltin]

for mobile use, it would be very useful if you could pass the compass bearing when specifying the start location.

otherwise GPS imprecision can easily cause the start point to be located in the wrong direction of way that's split into two oneways. this results in confusing routes that start out in the wrong direction.

it could be an optional parameter to the nearest, locate and/or viaroute requests. i imagine something like:

1. location is used to identify candidate ways
2. bearing is used to score the candidate ways
3. highest scoring candidate is selected
4. the location is projected onto the way.

idea originally mentioned in:
#204

OpenLR does something similar, but uses other information too:
http://openlr.org/

[emiltin]

this is also needed in order to support 'turn around' instructions - if you're going in the wrong direction, and the first thing you need to do is to turn around.

[emiltin]

might even make computing paths faster, since you start the search in just one direction instead of both as is done now?

[woodbri]

I think that this needs to be extended to consider the case where the start is on a two way street, but you want the route to start in the bearing given other wise there may be an implied u-turn if the route start in the opposite direction indicated by the bearing. You might NOT want to make a u-turn but rather continue forward. think of a vehicle on a narrow street like a delivery truck of trash collection truck.

[emiltin]

wouldn't the decision to use a u-turn or not be indicated by the profile settings? with a delivery truck you might almost never want to do u-uturns, while it could be ok with a bike or on foot.

[woodbri]

Well yes, I guess from a behavior point of view, but I'm not sure how that translates into the routing engine. In one case you want the routing engine to say your shortest distance requires you to turn around, in the other case you are not allowed to turn around and the route MUST start in the direction of the bearing and continue forward finding the best path to the next point which might be behind you and require you to drive around the block to get to it. There is a big difference (in my mind) from computing the shortest path and inserting a instruction to turn around vs computing a path that starts in a given direction and not in the reverse direction which might be shorter if you didn't care.

I'm good with the idea, just pointing out a potential issue/difference that might need to be addressed.

[emiltin]

Maybe the profile could have a penalty for u-turns at start and via points?

[DennisOSRM]

Maybe the profile could have a penalty for u-turns at start and via points?

yes, I was thinking of applying a U-turn penalty depending on the deviation from a true 180 degrees turn.

[emiltin]

that could be handled by the turn penalty function? maybe we could pass an argument to the turn function indicating whether the turn is happening at a via point or start point?

[woodbri]

Comments from #1413 by @woodbri :
We have a need to be able to specify the direction of travel when arriving or departing from starting, ending or via point. This is somewhat related to #1389 and maybe some other issues. The use case for this is that on two way roads if we have a location that is say on the right or left side of the street and we want to arrive at or depart from that location on that side of the street there is no easy way to control this. The use cases for this is pickup or delivery services. Think about children or handicapped and not wanting them to cross the street or package delivery or trash collection. All these cases require some means to the direction of approach/departure from the location. This issues was also discussed on osrm-talk.

Comments from #1413 by @systemd
Would also be really useful in the dual-carriageway case.

i.e. when planning a route from (lat1,lon1 heading east) to (lat2,lon2 heading east), start with the carriageway nearest to lat1,lon1 which has an eastbound one-way direction, even if the other carriageway is slightly nearer lat1,lon1.

[woodbri]

Adding another idea and use case.

When computing routes we need to be able to indicate which side of the street the stop or via location is on so that the route can only approach the stop moving in a direction that puts the passenger side of the vehicle facing that side of the road.

The use case for this is bus stops or trash collection containers or delivery van, taxi, etc on a two way streets.

One way of handling this conceptually without breaking the existing api, is to add a flag to indicate the behavior is desired, then when a point is used to create a phantom node, extend that structure to indicate side or the implied direction based on the side and chase that through the code.

[TheMarex]

Current brain dump on how to implement this:

• Add new parameter bearing to RouteParameters that contains the bearing for each loc (similar to the t parameter for timestamps that are used in the match plugin)
• Add an optional bearing parameter to StaticRTree::IncrementalFindPhantomNode
• Compute bearing of edge that is added to the result vector
• Deactivate either the forward or backward direction by setting forward_node_id or backward_node_id to SPECIAL_NODEID

[emiltin]

see #515 for an issue related to left/right side of the road

[Selikoff]

Besides routes, I suggest having bearing/direction added to the /match and /locate OSRM resources too, as it could help improve accuracy for those resources.

[emiltin]

good point

[TheMarex]

This has been implemented.

[emiltin]

great

[Selikoff]

Awesome. Is there a release version or do I just grab the latest version of the source to test?

[danpat]

It's currently sitting in the develop branch, it'll be part of the next release.

[Selikoff]

Is the match plugin also updated to include this as an input or output parameter?

[danpat]

It is only the match plugin that exposes this behaviour right now. It should be easy to add to the other plugins how that the RTree changes are in place, I just haven't made the time. Patches welcome.

Example usage:

/match?loc=1,2&b=22&loc=3,4&b=12

By default, if you supply a bearing, it will match edges that are +/- 10 degrees of the supplied value. That value is hard-coded at the moment.

[emiltin]

it would be great to have this for viaroute as well. in fact this issue originally referred to that usage, so not sure it should be closed?

choosing the best matching way, rather than using a fixed angle might be useful.

[danpat]

@emiltin We discussed that, but couldn't come up with a good heuristic for "best way". The r-tree search iteratively finds edges ranked by distance. What's better? A nearby match with a poor bearing, or a far away match with a tight bearing? In the end, we decided to simply make it a filter, rather than a ranking criteria.

[emiltin]

my feeling is it should be possible to find a sensible heuristic. did you try somethink like distance^2 * angle_distance^2?

[emiltin]

if several ways are below the angle treshold, which will be picked?

[emiltin]

my experience is that bearing from mobile devices is often quite inaccurate. i think a filter of 10 degrees would mean you most of the time would get no match (thinking about the viaroute use-case here)

[danpat]

It's a currently a simple filter. The closest way that's below the threshold will be chosen.

The use-case that motivated doing this was map-matching OpenLR (http://www.openlr.org/) traffic section descriptors against the map. OpenLR supplies a heading hint, and it's not based on real-world sensor data, it's a strict bearing based on the map geometry.

I wonder if what we really need here are two different types of bearing parameters:

bf - bearing filter - simply remove candidate edges outside the range
br - bearing rank - use a heuristic to choose the "best" edge

What we've done is bf (currently parameterized as b=), the process for br would be different (we would need to perform an unfiltered r-tree search, then sort the results).

[emiltin]

i see about openLR.
yes, for navigation based on sensor data, i think ranking is required to make the feature useful. want me to open a new ticket, or want to keep this open?

[danpat]

I think a new, more specific ticket would be best.

[Selikoff]

Thanks everyone. Does the new version of the match plugin also return the corrected bearing along with lat/lon for each point? Assuming I send a bearing with each lat/lon/t parameter, I'd like to see the mapmatched/corrected bearing in the response.

[Selikoff]

Does anyone have an anticipiated release date for when the next version of OSRM Backend that includes this feature will be created?