Avoid unnecessary u-turns

[graphhopper]

Avoid unnecessary u-turns

[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]

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]

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?

An inner-link U-turn is a U-turn that happens somewhere on a link between two real (i.e. non-virtual) nodes. Such U-turns can be penalized by adding a penalty constant of c meters to the route length between two subsequent candidates. Whether such a U-turn occurs between two subsequent candidates can be checked using their directions, e.g. if there are two candidates on the same link with different directions then a U-turn must have occurred. As @michaz pointed out above, we don't have directions for candidates (i.e. virtual nodes) yet.

The hmm-lib doesn't need to be changed. Only the route length passed to HmmProbabilities.normalizedTransitionMetric needs to be modified.

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).

As I wrote before, I would recommend starting with penalizing only U-turns within links, i.e. between two real nodes. In this case we always have 180° angles.

[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?

[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.

[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.

[stefanholder]

@kodonnell, I'm referring to your first example with three candidates A -> B -> C. In the transition from B to C, we would detect that the candidate at B is in north direction (more precisely towards the real node in north direction), so on the shortest path between B and C a U-turn must have occured (at B we first need to turn towards south). We would then add the U-turn penalty to the route length and pass this to HmmProbabilities.transitionLogProbability.

The increased route length leads to a reduced probability for the transition between B and C. Since the Viterbi algorithm finds the most likely sequence of candidates, it will choose A -> intersection node -> C instead of A -> B -> C if the U-turn penalty is high enough.

[kodonnell]

OK, it looks like there's already built-in support of enforcing direction, given graphhoppers PASS_THROUGH option (i.e. prevent U-turns when routing multiple waypoints). That is QueryGraph.enforceHeadingByEdgeId. If I'm right, this would make it pretty simple. However, the main issue is that (from what I can see) the candidates are always real nodes/edges, and hence this won't work.

@karussell, is that correct? (This seems to be what you're referring to here). If so, it looks like #50 (and PR #51) are probably the first requirement - correct?

[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 ?

[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.

[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.

[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]

I don't think we can do it with transition probabilities

We can utilize GH its turn costs support for non-CH but would need a post-import processing to analyze junctions regarding turns.

[kodonnell]

We can utilize GH ...

But isn't GH only used for A -> B, and B -> C, i.e. it has no knowledge of a turn at the candidate point B (and the angle ABC)? Maybe that's what you were referring to, in which case I think we're on the same page. The real question is where in the HMM process do we add such turn costs (regardless of whether they're calculated with GH or not)?

[kodonnell]

@michaz and @stefanholder: you are both suggesting we can include U-turn penalties in the transition probability. Going back to my example of three candidates A -> B -> C:

            |   |
            ^   v
            | B |
            ^   v
            |   |
            ^   v
            |   |
-->-A->-->-->-->-->-->-C->--

i.e. the total route A -> B -> C involves an inner-link U-turn at B. I am still unsure how we can use the transition probability, which only deals with information from two candidates (i.e. A -> B or B -> C), and not three (i.e. A -> B -> C which is needed to determine if a U-turn occurred at B).

Or are you referring to the below case i.e. the total route A -> B -> C -> D involves an inner-link U-turn on the route between B and C? Here you could deduce a U-turn from only two candidates (i.e. B and C, by e.g. detecting they are on the same edge but heading in different directions) and hence include it in the transition probability.

            |   |
            ^   v
            |B C|
            ^   v
            |   |
            ^   v
            |   |
-->-A->-->-->-->-->-->-D->--

As an aside, I think it is the former example that crops up more often (including in the original issue).

[kodonnell]

Ah, thanks for explaining @stefanholder - we save the direction in the candidate, and hence don't need the additional information. I'll have a play implementing now.

[karussell]

Thanks @stefanholder this makes sense, there is already a 'heading' we can put in as hint. The problem is that this heading could dependent on the previous different paths ... ah but we should probably just use the 'heading' calculated from the previous measurement ...

[kodonnell]

Right you are @karussell - I overlooked that problem.

... the 'heading' calculated from the previous measurement ...

Do you mean taking the current heading as the bearing from the previous gpxEntry to the candidate? That could work (as in this case) but it's also asking for trouble ... one can think of cases where the actual heading is very different to the bearing from the last candidate.

[kodonnell]

Well, that's nice:

I basically did as above. Using A -> B -> C again, when calculating the transition probability for a B candidate to a C candidate, calculate the difference in bearing between

• the bearing from A (the actual gpxEntry) to the B candidate, and
• the bearing from the B candidate to the C candidate

and subtract if from the final transition probability. That said, I'm pretty sure it's not a good solution ...

[stefanholder]

ah but we should probably just use the 'heading' calculated from the previous measurement ...

Assuming that a candidate is a link with an offset and a direction:

The candidate should not store a heading like 20° but the direction in which it is oriented on the link. For instance, if there is a bidirectional link between the real nodes A and B then a candidate somewhere on this link could either have direction "towards A" or "towards B".

When generating candidates for a GPS position, a candidate should be generated for each possible direction of each link within the radius. When the shortest route is computed between two candidates, the candidates' directions need to be considered, i.e. the route must start/end with the corresponding candidate directions.

Once this is implemented, we can go one step further and add inner-link U-turn penalties. This can be implemented by first changing the direction of the starting candidate, computing the route length to the next candidate plus the U-turn penalty and checking if this gives a shorter route length than without the initial U-turn.

Now getting to how we can represent candidates in Graphhopper:

My understanding of candidate nodes is that these can either be real nodes in the road network graph or virtual nodes, which correspond to a position on a link. This means if a real node is found during candidate generation, we would have to generate a candidate for every outgoing link. So in general we could represent candidates in Graphhopper with a node and an outgoing link as the direction.

[kodonnell]

Thanks for explaining @stefanholder. @michaz, you made the comment

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.

How would you implement penalties for inner-link U-turns without directional edges splitting? The approach of @stefanholder for inner-link penalties seems to make sense, but (I think) it requires directed candidates.

As an aside, has anyone considered higher order markov chains? That way I think we could make the transition probability for B -> C depend on the routes A -> B and B -> C, and hence not only resolve this (without directed candidates etc.) but also possibly allow further features in future. For example, if we prefer transitions where the A -> B + B -> C distance is closer to A -> C, then we can nicely get rid of inner-link U-turns, and maybe some other problems (?). (It's effectively smoothing the route, where possible, I think.) Alternatively, we could simply check whether the last/first edges are the same and directed oppositely, to implement a U-turn penalty. I've no idea how it'll perform, but from what I've browsed there are e.g. second order viterbi algorithms, or you can convert second order to first (and use hmm-lib as it is). And I don't think we'd then need to double (or more) the number of candidates.

[stefanholder]

How would you implement penalties for inner-link U-turns without directional edges splitting?

We don't need to modify the graph itself by splitting edges, we only need one candidate for each possible direction. This should be rather easy to implement.

As an aside, has anyone considered higher order markov chains?

Not really, but I would still suggest to start simple and to later extend the solution. This way we can always benchmark with the simple approach.

[kodonnell]

Ah, good. I'll have a play around in the next few days, unless anyone else thinks they can do it quickly and easily (@karussell?).

[karussell]

unless anyone else thinks they can do it quickly and easily (@karussell?)

Both not, no. I was able to follow the discussion only partly ;(

Please have a look into the edge based routing with the traversal keys: https://github.com/graphhopper/graphhopper/blob/master/core/src/test/java/com/graphhopper/routing/EdgeBasedRoutingAlgorithmTest.java

[kodonnell]

... has anyone considered higher order markov chains ...

Also this - online map-matching means they can use a 'momentum change function' which

.. can be described as a 'smoothing function' that penalizes infeasible transitions consisting of many abrupt turns ...

So there are a few possible approaches to this problem ...

[stefanholder]

the candidates are always real nodes/edges

In graphhopper-map-matching, candidates are always nodes obtained by QueryResult.getClosestNode(). They can either be real nodes or virtual nodes. If a candidate is a virtual node then this node is connected to virtual edges, which are translated back to real edges here. @karussell, please correct me if I'm wrong.

I think we can prevent inner-link U-turns, which should solve the original problem, like this:

• If a candidate is a virtual node + direction, we can enforce the direction during routing with QueryGraph.enforceHeadingByEdgeId. We can store the direction as the outgoing virtual edge id.
• If a candidate is a real node (tower node), we don't even need to store the direction with the candidate since we only want to prevent U-turns within real edges.

This will also help to add U-turn penalties later, if needed.

[karussell]

In graphhopper-map-matching, candidates are always nodes obtained by QueryResult.getClosestNode(). They can either be real nodes or virtual nodes

👍

I think we can prevent inner-link U-turns, which should solve the original problem, like this:

Best would be if we can avoid this separate handling (at least for a future version :) ). Currently it might be a problem for virtual edges as one has to explicitly pick the opposite, but this is something we will stumble over for other cases and we'd need to fix those too.

This will also help to add U-turn penalties later, if needed.

We already have one

If so, it looks like #50 (and PR #51) are probably the first requirement - correct?

Yes, although I'm not sure if PR #51 is the (full) solution

[kodonnell]

We already have one

That's U-turns within a route. I think we're talking about U-turns at the end of one route and the start of the next (which is, I believe, what the PASS_THROUGH option is for when using multiple via-points).

They can either be real nodes or virtual nodes

Right - looks like I was using an example (mm-uturns1.txt) where everything was a real edge, sorry. That said, maybe this is a bug ... when I look at the candidates, there are certainly those with virtual nodes (i.e. queryGraph.isVirtualNode(candidate.getQueryResult().getClosestNode()) returns true), but none have virtual edges (i.e. queryGraph.isVirtualEdge(candidate.getQueryResult().getClosestEdge().getEdge()) returns false). This seems odd (how can one have a virtual node without a virtual edge?), and is causing problems ... thoughts @karussell?

[stefanholder]

Best would be if we can avoid this separate handling (at least for a future version :) )

I think the solution is not that bad because it reduces the number of candidates for real nodes, which results in improved map matching performance because less shortest paths need to be computed.

I think we're talking about U-turns at the end of one route and the start of the next

Right. As discussed before, the easiest approach would be to prevent inner-link U-turns (i.e. U-turns within a real edge). The next step would be to penalize inner-link U-turns instead.

That said, maybe this is a bug ...

I think candidate.getQueryResult().getClosestEdge() always returns the closest real edge (this should be noted in the documentation). Virtual edges adjacent to a virtual node can be obtained using EdgeExplorer. See also the code for translating virtual edges to real edges.

[karussell]

This seems odd (how can one have a virtual node without a virtual edge?)

Hmmh, indeed this is unexpected. Can you print the adjacent nodes of this edge and this node in your example?

[kodonnell]

Sure. In computeTransistionProbabilities:

System.out.println("query result: " + to.getQueryResult());
System.out.println("closest node: " + to.getQueryResult().getClosestNode());
System.out.println("closest node is virtual: " + queryGraph.isVirtualNode(to.getQueryResult().getClosestNode()));
System.out.println("closest edge: " + to.getQueryResult().getClosestEdge());
System.out.println("closest edge is virtual: " + queryGraph.isVirtualEdge(to.getQueryResult().getClosestEdge().getEdge()));
System.out.println("closest edge base node: " + to.getQueryResult().getClosestEdge().getBaseNode());
System.out.println("closest edge adj node: " + to.getQueryResult().getClosestEdge().getAdjNode());  

Running the testSmallSeparatedSearchDistance[non-CH] test (i.e. using the test map/graph) the last candidate output is:

query result: 5590-5589  null
closest node: 31448
closest node is virtual: true
closest edge: 6515 5590-5589
closest edge is virtual: false
closest edge base node: 5590
closest edge adj node: 5589

[karussell]

Ah, now I understand the underlying reason: the lookup procedure works as follows:

• call LocationIndexTree.findClosest for every input point and return a QueryResult with a real edge and a real node (one of the closest nodes is picked)
• create QueryGraph and call QueryGraph.lookup with the previously calculated list of QueryResults.
  • Inside this call change the closestEdge if stored in 'wrong' direction - still the edge is 'real', also call queryResult.setWayIndex if it was the 'wrong' direction. (We define a direction here to make handling of multiple points per edge easier).
  • Then call queryGraph.setClosestNode(virtualNode) if the query is not on a junction.
  • Then create the necessary virtual edges and hide the real edge from the edgeIterator but leave the queryResult.closestEdge unchanged ('real') as we do not know which of the two virtual edges to pick

So, long story short: getClosestEdge is currently always real and getClosetNode is virtual or rarely real (if directly on a junction). Either we need to fix this discrepancy of real vs. virtual or better document this I fear.

[kodonnell]

... the underlying reason ...

That fits with what I was seeing (and tried to hack).

Either we need to fix this discrepancy of real vs. virtual or better document this I fear.

@karussell will this have wider implications? E.g. if an inner-link U-turn does actually occur, do we need virtual edges to correctly display it?

Can we get around the issue too? E.g. is there a way to get the virtual edges by using the virtual node? I tried EdgeIterator iter = queryGraph.createEdgeExplorer().setBaseNode(to.getQueryResult().getClosestNode()) but then e.g. iter.getEdge() fails if it's a virtual node.

[karussell]

E.g. if an inner-link U-turn does actually occur, do we need virtual edges to correctly display it?

Yes. But I wouldn't expose them somehow. That is the exact problem we have to solve: return e.g. just the geometry and potentially the more stable OSM nodes, but not our nodes and NEVER the virtual nodes or edges.

Can we get around the issue too?

Your way falls short if there are multiple nodes per edge (not uncommon for map matching)

[stefanholder]

I tried EdgeIterator iter = queryGraph.createEdgeExplorer().setBaseNode(to.getQueryResult().getClosestNode()) but then e.g. iter.getEdge() fails if it's a virtual node.

But this way always seems to work here, or am I missing something?

[kodonnell]

am I missing something?

Nope - turns out I was just the missing .next().

[kodonnell]

I've had a hack with directed candidates, but haven't resolved the original issue. To be frank, I'm just guessing how some of this direction/enforcement stuff works anyway - I think it needs someone with a greater appreciation of GH internals.

@karussell - what's the plan? @stefanholder has proposed a solution (and has a better idea than me of how to implement it!), but you didn't seem happy progressing it. So where to from here?

[stefanholder]

So where to from here?

I can try to do an initial implementation in the next few days, which we can then improve together.

[kodonnell]

I've dumped my stuff here if it's useful. It runs through, but something is clearly wrong.

Things I learned:

• this
• you need to get all candidates first, then look them up, then create time steps from them, hence the layout I have. Initially I tried to e.g. create the virtual edges in createTimeSteps, but that fails as you need to lookup first (and you can only lookup once).
• I think you only need two candidates (e.g. in A---X---B, then A->X and B->X), not four (i.e. A->X and X->A). You just chose incoming/outgoing as appropriate when routing the transitions.

[stefanholder]

@kodonnell's code looks already pretty good.

Some remarks:

• I would rename GPXExtension to MapMatchCandidate and instead of storing QueryResult there, I would store queryDistance, snappedPoint and closestNode directly in MapMatchCandidate. This also makes this code less dependent on Graphhopper internals.
• I would assert here that there are exactly two virtual edges. If this is not always true, it would be interesting to find out why.

Seems that Graphhopper #885 is now the main blocker for this issue.

I think it makes sense that @kodonnell creates a pull request of his code to an experimental graphhopper map-matching branch, e.g. issue_70. This makes it easier to work on this together. @karussell, can you please create such a branch?

[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.