Avoid unnecessary u-turns

[karussell]

Sometimes u-turn artifacts are introduced. A good description with data and screenshots is available in the forum

[beyondfun]

Any update for the issue? I met the problem also, cannot find a way to solve it.

[karussell]

(You can try to change the gps_accuracy)

[beyondfun]

Changing gps_accuracy DOES make the output a little different, but the result is still weird. I changed gps_accuracy param from 40 to 200, and not gotten a acceptable result.

During the process of tuning the parameter, I cannot guess which one is better. I cannot tell to enlarge the param or reduce it based on the output.

So my question is if there is something like a guideline for tuning the param, or is there some walk around for it?

Thanks in advance.

[karussell]

Currently there is no other workaround that I know.

[beyondfun]

I managed to remove the loop path.

But there come another problem, what if the real path is a loop? I will remove the real route in this case.

So I guess whether I can get the relationship of original route and snapped route? Is there any way I can achieve this?

[karussell]

Yeah, would be nice if we find a solution. But maybe instead of a post processing step, there is an algorithmic solution - maybe @stefanholder, @michaz or @kodonnell have an idea? (Currently this and #51 are the most requested features, quality-wise.)

So I guess whether I can get the relationship of original route and snapped route? Is there any way I can achieve this?

What do you mean here? Something like discussed in #64 ?

[stefanholder]

There might be a general problem with the normalization in the normalized transition metric. Can you please try to change this line toreturn Math.abs(linearDistance - routeLength); and set transition_probability_beta to 2.0?

[karussell]

Thanks @stefanholder - I'll try with my examples.

And @beyondfun would you mind to try this too?

[kodonnell]

I wonder if it's not the HMM, but the data we're giving it. E.g. as per here, the routed distance is simply the distance between nodes, and doesn't (?) take into account the actual position of the candidate relative to the node. So I wonder if changing to e.g. from.getQueryResult().getSnappedPoint() will give better results? I will have a look now (though it may take me a while as I haven't used the web UI before).

As an aside, I've created a bespoke UI for inspecting results (for a project at work), which animates the route (including step-by-step) and shows the candidate points at each step ... which would be rather useful in this case. @karussel, if you're interested, I can add a new issue.

[stefanholder]

@kodonnell is right. A candidate should not be a node but a road with an offset and a direction. The candidate position should be computed as the closest point on the road to the GPS position.

[kodonnell]

@stefanholder, the candidates are snapped (and the correct distance is used for emission probabilities), but it looks like it isn't being used for the transition probability. Turns out my idea isn't so trivial ... algo.calcPath only takes IDs, not snapped points. @karussell - is there any easy way to do what I'm thinking?

FYI validated issue appears with accuracy = 20m on the first example file.

[kodonnell]

On second thought ... are we both wrong, given the whole virtual node business? I.e. will the closest node actually be the snapped location?

[karussell]

So I wonder if changing to e.g. from.getQueryResult().getSnappedPoint() will give better results?

This getClosestNode is the virtually created node, so this should be okay IMO.

I.e. will the closest node actually be the snapped location?

Yes

[karussell]

@karussel, if you're interested, I can add a new issue

This sounds really interesting. Debugging tools are always very nice to have :) ... is it web or Java swing based?

Turns out my idea isn't so trivial ...

What exactly is your idea :) ?

doesn't (?) take into account the actual position of the candidate relative to the node.

I've still not tried the suggestion from @stefanholder but maybe the location lookup is not returning all possibilities? Normally if would get only a 'too perfect snap' (to the incorrect edge) this would explain the U-turns but we should also get some 'imperfect snaps' to at least one of the correct edges which will give overall better results.

[kodonnell]

web or Java swing

web - coincidentally using leaflet too, so should fit with what's currently there. I will add an issue to discuss further.

What exactly is your idea

Using snapped points - which, as above, sounds like they wouldn't achieve anything.

maybe the location lookup is not returning all possibilities

I'm going to try to filter the input route to a minimal example still exhibiting the behaviour, then will check all the locations found per GPX entry.

[karussell]

Using snapped points - which, as above, sounds like they wouldn't achieve anything.

We are already using snapped points: the location index searches for close edges and we pick some candidates but also the best snap. The QueryResult then contains the snapped point as coordinates and also a newly created node (created in the QueryGraph only), that is the reason we call QueryResult.getClosestNode (all algorithms operate on graphs and do not know what to do with coordinates). So the location index 'converts' coordinates into node IDs and often has to introduce new (virtual) nodes with an ID >= graph.getNodes.

[kodonnell]

Yup - that's why I meant my idea wouldn't achieve anything = )

FYI, here is a minimum example at accuracy=20m. It also produces similar looking behaviour at the start of the route (which you can avoid by uncommenting the first trkpt). Using http://download.geofabrik.de/europe/serbia-latest.osm.pbf.

[kodonnell]

There might be a general problem with the normalization in the normalized transition metric. Can you please try to change this line toreturn Math.abs(linearDistance - routeLength); and set transition_probability_beta to 2.0?

This didn't seem to change anything.

maybe the location lookup is not returning all possibilities? Normally if would get only a 'too perfect snap' (to the incorrect edge) this would explain the U-turns but we should also get some 'imperfect snaps' to at least one of the correct edges which will give overall better results.

This is match for above GPX:

Candidates:

gpxentry (top in image): 45.24563039977332,19.713944233953953,382.0, 1262264393000

• 70043-91802 45.24563634138896,19.713805130453018,NaN
• 91807-91802 45.245590886002574,19.713801213662354,NaN
• 91797-91802 45.245590886002574,19.713801213662354,NaN

gpxentry (middle in image): 45.244210260171826,19.713515080511566,382.0, 1262264393000

• 70031-91808 45.244295487453236,19.713481572670876,NaN
• 70024-70031 45.24420110087588,19.71367797926625,NaN
• 70031-70040 45.244336766995566,19.7136933665058,NaN
• 70031-91797 45.244336766995566,19.7136933665058,NaN

gpxentry (right-most in image): 45.244905226540226,19.716197289526463,382.0, 1262264393000

• 70040-70031 45.24485071149828,19.71621966155419,NaN

That seems to be behaving normally to me.

[kodonnell]

OK, going to have to bail on this one for now. From the below I thought that it might have just been a visualization thing (the above is definitely misleading - it appears to show an entire edge even when only a portion of edge is travelled on) ... but no, it does say 'right onto Здравка Челара', so the U-turn is there (even though it doesn't actually give instructions for U-turning).

$ curl -XPOST -H "Content-Type: application/gpx+xml" -d @mm-uturns1.txt "localhost:8989/match?vehicle=car&type=json"
{"map_matching":{"original_distance":385.20577623266684,"distance":385.0550044929167,"time":46204,"original_time":0},"hints":{},"paths":[{"instructions":[{"distance":276.965,"sign":0,"interval":[0,2],"text":"Continue onto Бранка Радичевића","time":33235},{"distance":763.201,"sign":2,"interval":[2,5],"text":"Turn right onto Здравка Челара","time":91582},{"distance":0,"sign":4,"interval":[5,5],"text":"Finish!","time":0}],"descend":0,"ascend":0,"distance":1040.166,"bbox":[19.71123,45.243857,19.718147,45.246823],"weight":9.223372036854775E12,"time":124817,"points_encoded":true,"points":"sgdsG{jiwB|I\\rCJ~AlN_BmNuDyZ","snapped_waypoints":""}],"info":{"copyrights":["GraphHopper","OpenStreetMap contributors"]}}

[beyondfun]

@karussell

What do you mean here? Something like discussed in #64 ?

Yes, exactly.

[beyondfun]

And @beyondfun would you mind to try this too?

I have tried this, but the result is still not good(seems the changes has nothing impact). I attached result, the dead end is unnecessary.

[michaz]

Hmm, but isn't this behaviour just what we should be expecting?

In the picture from @kodonnell , the green links in their full extent are just visualisation. They are not part of the distance calculation. The U-turn part of the output route is just a few meters west, to the snapped point, and back. Not a lot of distance. We don't travel the whole link and then back.

To be clear: To the algorithm, the solution above looks exactly the same as if there was a second lane in the direction of the route, just next to the snapped point. It doesn't know about turns at all.

So if we want fewer U-turns, we either need

a) a U-turn penalty term in the transition probability, or
b) the snapped points need a heading (i.e. they would be snapped to a directed edge, and there would be two candidates, one for each directed edge), so that we will have to travel the whole link and come back (if we think U-turns are only allowed at real nodes). In which case the U-turn solution would not be picked.

[stefanholder]

I aggree with @michaz. If the green links in @kodonnell's picture are just visualization then this really explains the behavior. Conceptually, a candidate should not be a node but a road edge with offset and direction.

[michaz]

@stefanholder If I remember correctly, we are half-way there: A candidate is a "node", but not as in a node in the graph, but in an overlayed query-graph where all candidate positions have been inserted by splitting links.
So we have "offset". That works. To get "direction", we would need to (in the QueryGraph) split undirected edges into directed edge-pairs, insert candidates in each of them, and then we're done. I think.

If that is what we want. I mean, people do make U-turns in the middle of the road. Perhaps that should be part of the possible solution space?
Then we need an explicit U-turn penalty, so that U-turns in the middle of the road are unlikely but possible, and we don't need to add the directional-edge-splitting part.

[kodonnell]

To be clear: To the algorithm, the solution above looks exactly the same as if there was a second lane in the direction of the route, just next to the snapped point. It doesn't know about turns at all.

I'm not sure I follow completely. I (naively) think of the HMM approach as a distance minimisation problem, so I would expect A -> B -> C to be preferred over A -> B + delta -> B -> C, assuming delta is small, regardless of turns. I assume this would just be balancing beta/sigma ... but I may be completely misunderstanding things.

[michaz]

@kodonnell Yes, it trades off minimizing

• the difference between (the road route length) and (the direct distance between the measurements)
• the distance between the route and the measurements.

But that's consistent with your picture -- the bottom left point is very close to the link with the U-turn, and not so close to the correct route. And the length of the brown lines together is perhaps also closer to the "wrong" route than to the correct route. The only really bad thing about it is the U-turn.

The algorithm does not try to minimize the total route length. It doesn't assume people take shortest paths overall. (Perhaps this person did make a U-turn because he/she took a wrong turn!) It only assumes people take shortest paths between measurements, when we don't know anything.

If I were the algorithm and didn't know what a U-turn is, I would choose this solution as well.

[kodonnell]

Yes, it trades off ...

Thanks @michaz, that's what I thought. In the example above, there are (ignoring ones not relevant to the discussion), two choices (both for first-to-middle and middle-to-last edges):

• "U turn": travel, say, 220m to a point which is about 5m from the road.
• non "U turn": travel, say, 200m (i.e. 20m less than above) to a point which is 20m from the road.

Given the GPS accuracy is 20m in this case (so it's perfectly acceptable to have a point 20m from the road), I'd expect the algorithm to pick the second case (when configured with the "right" beta/sigma). I understand that may be a balancing act ... but have we ever actually tested what the "right" values are, aside from just taking what's on the paper (and hoping their implementation is the same as ours etc.)?

That all said - yes, we could make it easier by adding more information/penalties, as you've suggested. I have a third option though: penalise turns (regardless of whether they're "U" or not). That is, I don't think anyone has a problem with a U-turn being shown, in the following circumstance (device travelling from left, goes up road, does a U-turn, and then keeps going right):

                                 X|   |
                                  ^   v
                                  |  X|
                                  |   |
                               X  ^   v
                                  |   |X
-X-->--->--->--->--->--->--X->--->--->--->--->
                 X                        X

i.e. where there were "clearly" points leading up to the U-turn. Most of the issue is (rightly) with the following (as is the case under discussion) where the algorithm guesses a little detour and U-turn up the vertical road (as one of the points is closer to it):

                                  |    |
                                  ^    v
                                  |    |
                                  |    |
                           X      ^    v
                                  |    | 
-X-->--->--->--->--->--->--X->--->--->--->--->
                 X                        X

i.e. it's "clearly" simpler to go in a straight line than make a random turn up a single side road and perform a U-turn.

So, to my point about penalising turns: in the case of the latter, some of the candidate routes would involve two edges (i.e. one turn) to do a U-turn, whereas the "obvious" one only needs a single edge. In fact, I wouldn't even penalise turns in general - I'd only penalise them at the ends of each route between candidates. To continue my ASCII art, I'd penalise this:

X |________________________| X

(i.e. a short little turn near the candidate points), but not this

X_________|---|_______________X

(i.e. turns in the middle of the route - which presumably GH had a reason for choosing, and can have nothing to do with the whole GPS accuracy business). If I remember my calculus correctly, I'm effectively adding a constraint that the route be differentiable (i.e. smooth changes in direction) at the junction between the stepwise pieces (i.e. routes between candidates).

Thoughts?

[stefanholder]

I understand that may be a balancing act ... but have we ever actually tested what the "right" values are, aside from just taking what's on the paper (and hoping their implementation is the same as ours etc.)?

We have been using the HMM lib with another map (so no Graphhopper is involved). In our experience the sigma should be chosen to reflect the real GPS accuracy or a bit more because real GPS noise is not exactly Gaussian distributed. If the non-normalized metric is used then beta=2 works for GPS time intervals between 1 s and 30 s (this should be independent of the used map). I tried to find a metric that does not depend on the time difference of GPS positions and came up with the normalized metric but we had some cases where this didn't work. So would I suggest to change the code to the non-normalized metric.

We first restricted U-turns to real nodes and later relaxed this constraint but added a U-turn penalty for inner-link U-turns. Both worked well.

I'd penalise this [...] but not this [...]

U-turns in the middle of a link should definitely be penalized. The intuition is that it actually takes time in reality to perform a U-turn and this should be modeled within the algorithm. U-turns (and possibly also other turns) at real nodes could also be penalized but from our experience this is not necessary.

[kodonnell]

... added a U-turn penalty for inner-link U-turns.

Can you expand on this a little, e.g. what 'inner-link U-turns' are, and how you penalised U-turns? I don't think we can do it with transition probabilities (as that's A -> B and we need A -> B -> C to detect turns). Must the change be in hmm-lib?

What about a penalty for A -> B -> C based on the angle ABC: 0 gets no penalty (i.e. straight line), and 180 gets the maximum penalty (i.e. U-turn).

[karussell]

Added you both as contributor with write access (you should be able to create a new branch).

@karussell - what's the plan?

The plan is to trust our new contributors ;) ... I'm currently involved in other parts too much, so I can only help to improve documentation or concepts/architecture.

[stefanholder]

Thanks @karussell.

Can you please briefly comment on Graphhopper #885? Should @kodonnell and I try to fix this ourselves?

[karussell]

Re 885 - yes, please. This is probably just a missing if around the two setUnfavored calls (but I might have missed the core essence)

[kodonnell]

I would rename GPXExtension to MapMatchCandidate

I initially created my own candidate class, but then realised that's what GPXExtension was being used for. Agreed that we should tidy it up to make the code a bit more obvious to understand (there are a few other issues too). That said, in the interests of clarity of commit history etc., I'm tempted to implement the feature using this API first, then tidy it up later.

I would assert ...

Indeed - there are probably a few other assumptions too. Off the top of my head, I think I did see more than two virtual candidates once. Maybe that's what @karussell was referring to here.

I think it makes sense that @kodonnell ...

Yus! I'm very green to open source contributing, so I'm tickled pink to help. Let us ride the wave of my enthusiasm as long as we can = ) I'll work on something this morning (NZ time).

Re 885 - yes, please

@stefanholder I'll work on it now, then do the rest of the map-matching stuff. Still not sure how to get it actually working, so may have to tap out for a bit.

[stefanholder]

I'm tempted to implement the feature using this API first, then tidy it up later.

Sure.

Maybe that's what @karussell was referring to here.

I think @karussell meant that for the final map matching output we need to translate virtual nodes to pillar nodes or to the OSM way geometry if there is no pillar node nearby. However, preventing inner-link U-turns should eliminate this problem except for the first and last GPS position.

I'll work on it now, then do the rest of the map-matching stuff

Great, go ahead. When you're finished (even if it's WIP), please create a pull request to branch issue_70 (you could also just push your changes but it's easier to discuss a pull request). The branch is based on the same commit as your "play code", so there should be no problems.

[kodonnell]

Done, except I did it on issue70 branch instead of issue_70 - the issue_70 seemed to be old, and didn't have my play code in it, so I wasn't sure about it. If you created issue_70, maybe delete it (I don't want to as I didn't create it etc). Let's carry on the discussion at PR #83.

[stefanholder]

Sorry, my mistake. I created issue_70 based on the last commit in the master of @kodonnell's forked map matching repository but this was the wrong one. I just deleted issue_70.

[karussell]

Can we close here now that #88 is merged or is there still room for improvement?

[kodonnell]

Can we close here now that #88 is merged

At this stage it's pretty untested (both in unit tests and by users). However, it looks good to me, so I'd probably prefer to close this and then re-open it (or start a new issue) if it arises. Not sure what's standard practice though.

is there still room for improvement?

I think #88 closes this issue well, and the only improvements are probably performance/API related or the like, which I think are separate.

[karussell]

At this stage it's pretty untested (both in unit tests and by users).

Why do you think it is untested by unit tests? All previous stuff works. And as we'll deploy this soon into production we'll get back user reports quickly.

[karussell]

However, it looks good to me, so I'd probably prefer to close this and then re-open it (or start a new issue) if it arises. Not sure what's standard practice though.

Yes, lets keep every issue as small as possible and reopen it later or similar.