Graphhopper: average_speed was infinite error in PathDetail calculation

[easbar]

I am running into this error:

https://github.com/graphhopper/graphhopper/blob/e72c67d7fdad39c5cd1b3ecaeb91ec65ae5d9eb2/core/src/main/java/com/graphhopper/util/details/AverageSpeedDetails.java#L37-L41

I think the error is thrown whenever the edge distance is below a certain threshold (because then calcMillis will return zero). What mechanism is supposed to prevent this error ? We'd have to exclude edges below a certain distance or something (which as far as I know we do not) ?.

And another question: Why are we calculating speed=distance/time here ? Can we not just use the averageSpeedEnc to obtain the speed directly from the edge ?

[otbutz]

I think the assumption "edge traveltime is greater than zero" should be pretty safe and change AbstractWeighting:

return (long) Math.ceil(edgeState.getDistance() * 3600 / speed);

[karussell]

I think the error is thrown whenever the edge distance is below a certain threshold

Do you have a unit test for recreating the scenario? Because if distance is 0 than I would expect NaN (0/0) instead of infinity (x/0).

What mechanism is supposed to prevent this error

At import time we should prevent this here: https://github.com/graphhopper/graphhopper/blob/master/reader-osm/src/main/java/com/graphhopper/reader/osm/OSMReader.java#L705

Can we not just use the averageSpeedEnc to obtain the speed directly from the edge ?

No longer. See #1551 and the recent fix #1798.

[easbar]

Do you have a unit test for recreating the scenario?

No, not yet. But I ran measurement on bayern-140101.osm.pbf and got the error with many different seeds (I did not even find a seed so it did not happen, and it failed for many different edges as well so really suprised this did not cause any problems so far). But sure, I'll try to build a failing test case.

Because if distance is 0 than I would expect NaN (0/0) instead of infinity (x/0).

The distance was not zero, for example it was 0.014 in one case (so still above 0.001, the minimum tower node distance in OSMReader). Still, calcMillis can be exactly zero, because it uses a cast to long.

No longer. See #1551 and the recent fix #1798.

Ah ok this makes sense yes.

[karussell]

Still, calcMillis can be exactly zero, because it uses a cast to long.

Hmmh, probably the solution proposed from @otbutz makes most sense. The question is if 0.49ms should be really rounded to 1.00ms or if we introduce other problems.

[karussell]

I think we need to handle this better in the path details class, because calcMillis==0 is totally legitimate (high speed on a short edge can be easily under 0.5ms).

Update: or we change the return type from long to a double ... which would be a bit special for a time type.

[otbutz]

high speed on a short edge can be easily under 0.5ms

Traveling 5cm with 200km/h is about 1ms.

[otbutz]

https://github.com/graphhopper/graphhopper/blob/9e05cf36d2fa75ec9a5bbac5cedd57d033f1d53e/reader-osm/src/main/java/com/graphhopper/reader/osm/OSMReader.java#L701-L712

0.1mm seems like an odd choice for treating the first case if the other one defaults to 1m.

[easbar]

I did not cut it down to a small unit test, but if you want to reproduce the error you should be able to get it using this extract from Geofabrik's bayern-140101.osm.pbf:

https://gist.github.com/easbar/e0331a7230f8bba6252a528cba331106

using this query:

http://localhost:8989/maps/?point=49.209397%2C12.040039&point=49.209555%2C12.040211&locale=en-US&vehicle=car&weighting=fastest&elevation=false&turn_costs=undefined&calc_points=true&disable.ch=true&details=average_speed&use_miles=false&layer=OpenStreetMap

I set min(OneWay)SubnetworkSize to 1.

[karussell]

Can we reduce this to a normal bug status :)? As this does not appear for a recent map and also only for details=average_speed, I guess?

Traveling 5cm with 200km/h is about 1ms.

5cm is a bit big, but maybe increasing the minimum 0.0001 to 0.01 (=1cm) instead to reduce the chance that this happens again and at the same time don't hinder a indoor use case?

[easbar]

Can we reduce this to a normal bug status :)

Ok, sleep well ;)

[easbar]

As this does not appear for a recent map

If this is so special about bayern-140101.osm.pbf it would be good to know how exactly it can happen. Yes without average_speed details it should not happen.

Why not do a special handling for calcMillis=0 in AverageSpeedDetails ? I think all the speed is used for is to decide whether or not there is an extra instruction. If this happens so rarely its probably not a problem at all. I would argue that if calcMillis might return 0 any code that does a division by calcMillis is responsible to handle the zero case.

[karussell]

it would be good to know how exactly it can happen.

Maybe it is a mapping bug (a node with 0 distance to its neighbour) and we set the minimum length to 0.1mm which then translates into 0ms for something like ~50km/h?

BTW: zero length edges could also be introduced due to how we handle barriers. But in case of measurement only one vehicle is imported and traveling such a zero length barrier is only possible if there would be another vehicle that is not blocked.

I would argue that if calcMillis might return 0 any code that does a division by calcMillis is responsible to handle the zero case.

If we define the range of calcMillis to start at 0ms, then yes. But in theory it should never get 0 and only gets 0 due to the loss of precision.

[karussell]

If we define the range of calcMillis to start at 0ms, then yes. But in theory it should never get 0 and only gets 0 due to the loss of precision.

But maybe handling it in the path details for now would be ok. It has a small impact surface :)

And do you think we should additionally change the minimum edge distance to 1cm or at least make NaN-case behave like the minimum case?

[otbutz]

5cm is a bit big, but maybe increasing the minimum 0.0001 to 0.01 (=1cm) instead to reduce the chance that this happens again and at the same time don't hinder a indoor use case?

I wasn't aware of the indoor use case but even for this anything lower than 10cm doesn't make any sense IMHO.

Maybe it is a mapping bug (a node with 0 distance to its neighbour) and we set the minimum length to 0.1mm which then translates into 0ms for something like ~50km/h?

Exactly my thought.

zero length edges could also be introduced due to how we handle barriers.

If we define the range of calcMillis to start at 0ms, then yes. But in theory it should never get 0 and only gets 0 due to the loss of precision.

A zero length edge will result in a zero duration. We should enforce a sane minimum distance and probably switch the return type of calcMillis to double if we _really_ need to track ants :grin:

[easbar]

Maybe it is a mapping bug (a node with 0 distance to its neighbour) and we set the minimum length to 0.1mm which then translates into 0ms for something like ~50km/h?

No, the distance was not below 0.1mm, but still it was so small that calcMillis returned 0. This depends on the speed. In my example distance was 0.014=1.4cm and speed was 65km/h so we got 0.014*3600/65 = 0.77, and (long)0.77=0.

[easbar]

which would be a bit special for a time type.

whats the difference between time and distance with regards to choosing long vs. double ?

[easbar]

Maybe it is a mapping bug (a node with 0 distance to its neighbour)

Sure its some kind of mapping 'bug', but we cannot change this and things like this can always happen. Still, I wonder how its possible because its not only that two nodes are close to each other, but they must be tower nodes as well.

[otbutz]

Still, I wonder how its possible because its not only that two nodes are close to each other, but they must be tower nodes as well.

Maybe we should log cases like this?

[easbar]

Another thing: This

 if (towerNodeDistance < 0.0001) { 
     // As investigation shows often two paths should have crossed via one identical point  
     // but end up in two very close points. 
     zeroCounter++; 
     towerNodeDistance = 0.0001; 
 } 

makes hardly any sense, because it will result in distance=0 anyway for the current INT_DIST_FACTOR=1000d when setting the distance on the edge state.

  int integ = (int) Math.round(distance * INT_DIST_FACTOR);

Btw this happens very frequently. For Bayern-140101.osm.pbf I got zeroCounter:11721.

[otbutz]

Which means that we cannot track any distance smaller than 0.5cm. I'd argue that we should enforce a minimum towerNodeDistance of 1cm which should be enough for all reasonable use cases?

[easbar]

     // As investigation shows often two paths should have crossed via one identical point  
     // but end up in two very close points.

Do we have an example for this ?

[easbar]

minimum towerNodeDistance of 1cm which should be enough for all reasonable use cases

1cm is still too small for the minimum, see my example above for 1.4cm (if this is the approach we choose). Just relying on the import is also not ideal imo.

[otbutz]

1cm is still too small for the minimum, see my example above for 1.4cm

We can solve the speed calculation if we switch to double but not if the distance is already zero.

[easbar]

Yes for distance=0 there is no reasonable speed to be calculated, but then again so far we do not even need the speed calculation. The method that causes the issue is just trying to find out whether or not the speed has changed to decide whether or not there should be an instruction or not.

Its also not clear to me yet if it should be possible to have edges with zero or some minimal distance, because I do not yet understand where they are coming from (except the special case where distance=0 is (mis)used to represent barriers).

[otbutz]

Its also not clear to me yet if it should be possible to have edges with zero

I think that this depends on the graph algorithms being used as the weightings are distance based.

I do not yet understand where they are coming from

Yes, we should investigate a bit more to fully understand what's exactly the cause here.

[karussell]

The method that causes the issue is just trying to find out whether or not the speed has changed to > decide whether or not there should be an instruction or not.

This is not the reason. The path detail class here returns a list of interval+speed values. But we could return the same infinityJsonValue in this case like we do for DecimalDetails.

Its also not clear to me yet if it should be possible to have edges with zero or some minimal distance, because I do not yet understand where they are coming from

They are coming from junction nodes being too close to each other (often on top of each other). The problem there is no recent example is likely that we and other routing engine authors have removed those cases and they are only present in older files.

I think that this depends on the graph algorithms being used as the weightings are distance based.

From an algorithm perspective zero should not make problems but yeah for CH I think we had similar problems earlier ("Setting weights smaller than"...), but even those problems are no longer existent in the recent data.

1cm is still too small for the minimum, see my example above for 1.4cm

Ah, yeah 1cm is too small for the current "(long)" cast. Only if we would use Math.round then we would get 1ms for up to 70km/h :D (or up to 100km/h for 1.4cm)

@Test public void testMinTime() {
        FlagEncoder tmpEnc = new CarFlagEncoder(10, 1, 0);
        GraphHopperStorage g = new GraphBuilder(EncodingManager.create(tmpEnc)).create();
        Weighting w = new FastestWeighting(tmpEnc);
        IntsRef edgeFlags = GHUtility.setProperties(g.getEncodingManager().createEdgeFlags(), tmpEnc, 100, true, false);
        EdgeIteratorState edge = GHUtility.createMockedEdgeIteratorState(0.014, edgeFlags);
        // change AbstractWeighting.calcMillis to use Math.round instead of the long cast then this passes:
        assertEquals(1, w.calcMillis(edge, false, EdgeIterator.NO_EDGE));
}

[easbar]

This is not the reason. The path detail class here returns a list of interval+speed values. But we could return the same infinityJsonValue in this case like we do for DecimalDetails.

I don't understand, this method throws the error and it just returns a boolean telling us whether or not the edge is 'different' compared to the last:

https://github.com/graphhopper/graphhopper/blob/e72c67d7fdad39c5cd1b3ecaeb91ec65ae5d9eb2/core/src/main/java/com/graphhopper/util/details/AverageSpeedDetails.java#L37-L41

Ah I see, but as a side effect it also sets the decimalValue which is later used as path detail...

[easbar]

I would just handle calcMillis=0 here, when dividing by a number one has to think of the zero case and handle it properly. Or we strictly exclude zero distance/time edges everywhere, but this seems to be a bigger task.

[otbutz]

This is not the reason. The path detail class here returns a list of interval+speed values. But we could return the same infinityJsonValue in this case like we do for DecimalDetails.

Do we even want to expose these strange values in the path details? I'd say we should skip it if the distance is below a certain threshold. Being told that you're moving at infinite speed because you passed a barrier is kinda confusing because it's merely a detail of the implementation and has nothing to do with the actual routing.

[easbar]

Yes I agree, maybe all we need to do is

if (edge.getDistance() < threshold) {
    return false;
} 

in above method

[karussell]

Sounds indeed like a good solution.

[easbar]

Maybe like this ?

 public boolean isEdgeDifferentToLastEdge(EdgeIteratorState edge) {
        // for very short edges we might not be able calculate a proper value for speed. dividing by calcMillis can
        // even lead to speed=Infinity -> just ignore these cases here, see #1848
        final double distance = edge.getDistance();
        if (distance < 0.1) {
            if (decimalValue > -1) {
                return false;
            } else {
                // in case this is the first edge we still have to set some value, but which one ?
                decimalValue = distance * 3600;
                return true;
            }
        }

Unfortunately there is a special case we have to take into account: The short edge might be the first and in this case we have to set some value, otherwise we'll run into this error in PathSimplification:

if (detail.isEmpty() && pointList.size() > 1)
                throw new IllegalStateException("PathDetails " + entry.getKey() + " must not be empty");

Is there some way to return some special value meaning "no path detail available for this edge" instead of showing a (rather useless) speed value for the very short edge ?

[karussell]

Is there some way to return some special value meaning "no path detail available for this edge" instead of showing a (rather useless) speed value for the very short edge ?

Yes, we could return null. See:

https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/util/details/DecimalDetails.java#L31