search

Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.3k stars 3.33k forks source link

negative values in distances matrix (v5.22.0) #5855

Open cyril23 opened 3 years ago

cyril23 commented 3 years ago

Background

This problem exists both in official OSRM server router.project-osrm.org, and I can find it in my own setup, too.

Here about my own setup:

Example (bicycle profile)

curl "http://127.0.0.1:5001/table/v1/car/6.917325,50.949002;6.89497,51.02085;6.903292,51.025422;7.004522,50.961342;7.004607,50.956687;7.08369,50.91637;7.050799,50.925633;7.002814,50.935468;6.97731,50.928274;6.97683,50.93066;6.964476,50.925211;6.964188,50.919921;6.95637,50.91763;6.950404,50.93562;6.950244,50.940655;6.911978,50.937178;6.90561,50.941806;6.917325,50.949001;6.917325,50.949002;6.917325,50.949001?annotations=duration,distance" > neg1.txt && grep -o -P -- ".{0,15}-\d+?.{0,15}" neg1.txt

image image neg1.txt

From this, I made a minimum example with just 2 points:

curl "http://127.0.0.1:5001/table/v1/car/6.917325,50.949002;6.917325,50.949001?annotations=duration,distance"
{"code":"Ok","sources":[{"hint":"ixYAgDz6CoCbAAAAnAAAAAAAAAAAAAAAnrqBQgnpgUIAAAAAAAAAAJsAAACcAAAAAAAAAAAAAAAlAQAAVIxpAMBrCQPNjGkAimsJAwAAfw3_2y9V","distance":10.415011,"name":"Sömmeringstraße","location":[6.917204,50.949056]},{"hint":"ixYAgDz6CoCbAAAAnAAAAAAAAAAAAAAACemBQp66gUIAAAAAAAAAAJsAAACcAAAAAAAAAAAAAAAlAQAAVIxpAL9rCQPNjGkAiWsJAwAAfw3_2y9V","distance":10.415011,"name":"Sömmeringstraße","location":[6.917204,50.949055]}],"destinations":[{"hint":"ixYAgDz6CoCbAAAAnAAAAAAAAAAAAAAAnrqBQgnpgUIAAAAAAAAAAJsAAACcAAAAAAAAAAAAAAAlAQAAVIxpAMBrCQPNjGkAimsJAwAAfw3_2y9V","distance":10.415011,"name":"Sömmeringstraße","location":[6.917204,50.949056]},{"hint":"ixYAgDz6CoCbAAAAnAAAAAAAAAAAAAAACemBQp66gUIAAAAAAAAAAJsAAACcAAAAAAAAAAAAAAAlAQAAVIxpAL9rCQPNjGkAiWsJAwAAfw3_2y9V","distance":10.415011,"name":"Sömmeringstraße","location":[6.917204,50.949055]}],"durations":[[0,0],[0,0]],"distances":[[0,-0.1],[0.1,0]]}

See: "durations":[[0,0],[0,0]],"distances":[[0,-0.1],[0.1,0]] edit: fixed minimum example

Another Example (car profile)

curl "http://127.0.0.1:5000/table/v1/car/7.210353,51.265175;7.210353,51.265178;7.206108,51.227533;7.20133,51.25279;7.1603,51.24005;7.15322,51.23908;7.123063,51.191963;7.13323,51.25664;7.216901,51.231529;7.21006,51.264117;7.096997,51.256183;7.1582,51.23588;7.134593,51.25603;7.210353,51.265175?annotations=duration,distance" | grep -o -P -- ".{0,15}-\d+?.{0,15}"

image neg-car.txt

Minimum example:

curl "http://127.0.0.1:5000/table/v1/car/7.210353,51.265175;7.210353,51.265178?annotations=duration,distance"
# the output:
{"code":"Ok","sources":[{"hint":"5pM2g2f-U4QJAAAA1AAAAA0AAAAGAAAAJyHQQIMsE0O_MQ1B7WKIQAkAAADUAAAADQAAAAYAAAALlwAA0AVuAD0-DgNxBW4Alz4OAwEAjwPtuiYy","distance":12.008651,"name":"Lönsstraße","location":[7.210448,51.265085]},{"hint":"5pM2g2f-U4QJAAAA1AAAAA0AAAAGAAAADdHVQAP_EkO_MQ1B7WKIQAkAAADUAAAADQAAAAYAAAALlwAA0gVuAD4-DgNxBW4Amj4OAwEAjwPtuiYy","distance":12.271231,"name":"Lönsstraße","location":[7.21045,51.265086]}],"destinations":[{"hint":"5pM2g2f-U4QJAAAA1AAAAA0AAAAGAAAAJyHQQIMsE0O_MQ1B7WKIQAkAAADUAAAADQAAAAYAAAALlwAA0AVuAD0-DgNxBW4Alz4OAwEAjwPtuiYy","distance":12.008651,"name":"Lönsstraße","location":[7.210448,51.265085]},{"hint":"5pM2g2f-U4QJAAAA1AAAAA0AAAAGAAAADdHVQAP_EkO_MQ1B7WKIQAkAAADUAAAADQAAAAYAAAALlwAA0gVuAD4-DgNxBW4Amj4OAwEAjwPtuiYy","distance":12.271231,"name":"Lönsstraße","location":[7.21045,51.265086]}],"durations":[[0,0],[0,0]],"distances":[[0,-0.2],[0.2,0]]}

See: "durations":[[0,0],[0,0]],"distances":[[0,-0.2],[0.2,0]]

Same when using the current OSRM demo server:

curl "http://router.project-osrm.org/table/v1/car/7.210353,51.265175;7.210353,51.265178?annotations=duration,distance"
{"code":"Ok","distances":[[0,-0.2],[0.2,0]],"durations":[[0,0],[0,0]],"sources":[{"hint":"msmVkL7JlZAJAAAA1AAAAA0AAAAGAAAAJyHQQIMsE0O_MQ1BvzENQQkAAADUAAAADQAAAAYAAABoHgEA0AVuAD0-DgNxBW4Alz4OAwEAjwPis2Jc","location":[7.210448,51.265085],"name":"Lönsstraße"},{"hint":"msmVkL7JlZAJAAAA1AAAAA0AAAAGAAAADdHVQAP_EkO_MQ1BvzENQQkAAADUAAAADQAAAAYAAABoHgEA0gVuAD4-DgNxBW4Amj4OAwEAjwPis2Jc","location":[7.21045,51.265086],"name":"Lönsstraße"}],"destinations":[{"hint":"msmVkL7JlZAJAAAA1AAAAA0AAAAGAAAAJyHQQIMsE0O_MQ1BvzENQQkAAADUAAAADQAAAAYAAABoHgEA0AVuAD0-DgNxBW4Alz4OAwEAjwPis2Jc","location":[7.210448,51.265085],"name":"Lönsstraße"},{"hint":"msmVkL7JlZAJAAAA1AAAAA0AAAAGAAAADdHVQAP_EkO_MQ1BvzENQQkAAADUAAAADQAAAAYAAABoHgEA0gVuAD4-DgNxBW4Amj4OAwEAjwPis2Jc","location":[7.21045,51.265086],"name":"Lönsstraße"}]}

related issues

https://github.com/Project-OSRM/osrm-backend/issues/5306 seems to be related (maybe its fix doesn't work here?)

mjjbell commented 3 years ago

Short answer

This can happen if the coordinates are very close (less than 1 metre apart).

Long answer

This only happens if the source and target are assigned to the same edge in the network.

Edges are directed, so when source/target are snapped to the same edge, the source position will have to be "upstream" from the target position on the edge for a distance between them to be valid. I'm not 100% on this, but it looks like this is decided by comparing the "weights" of the two positions on the edge, where the weights are the distance between edge start and position.

The problem occurs because the weights use a truncated int32 representation. If the source/target weights both truncate to the same value, you can end up with the source being downstream from the target (hence the negative result) but still being deemed a valid distance.

So this can happen for all the weight value pairs where they both truncate down to the same int32. If the weights are represented by distances, and this problem only occurs when the source/target are on the same road edge, we're likely only dealing with coordinates that are less than 1 metre apart. I imagine there are other rare edge cases where the input coordinates are a long way from the road or it has a weird shape.

Here's a minimal test case that reproduces it.

    Scenario: Truncated weights
    Given the node locations
        | node |  lon     | lat |
        | a    | 0        | 51  |
        | b    | 0.01     | 51  |
        | 1    | 0.005    | 51  |
        | 2    | 0.005005 | 51  |

    And the ways
        | nodes |
        | ab    |

    When I request a travel distance matrix I should get
        |   |  1   | 2   |
        | 1 |  0   | 0.4 |
        | 2 | -0.4 | 0   |

Note that this issue exists for both MLD and CH /table queries.

Mitigation/Fix

As a mitigation, you could check the input coordinates to see if they are very close together, and use that to decide what to do when a negative value is returned.

The reason the car profile differed from the bike profile in your example is because that particular road is one-way for cars, so it's just luck that in that direction the problem does not occur.

In terms of a fix, checking this edge-case at the start of the table search should suffice (changing the data types is probably not an option). Interestingly, the /route requests don't have this problem. The distance calculation must be performed differently.

danpat commented 3 years ago

Sounds like this might be a manifestation of https://github.com/Project-OSRM/osrm-backend/issues/5151#issuecomment-639842558 - we're using a few (3?) different length calculation algorithms throughout the codebase, and haven't put checks in place to guarantee consistency.

cyril23 commented 3 years ago

@danpat wow, so awesome, thanks for the release! Very happy!!! (not related to this issue, but I've been looking forward to a new release version since a long time!)

do-me commented 10 months ago

I also just tripped over this issue and can confirm what @cyril23 said: it's happening very rarely in let's say <0.1% of my cases.

Logic-wise as a duration can never be negative, would there be any problem by just replacing any negative value in the matrix by 0 @mjjbell? This would make for an easy fix on OSRM in case and would protect others from the banana skin.

For anyone on Python as a workaround just use numpy to replace all negative values by 0:

import numpy as np
matrix = np.maximum(np.array(matrix), 0)
asaveljevs commented 5 months ago

According to our research and applying it to our particular use case (which is VRP optimization), simply replacing negative values with 0 would not be a good workaround. To understand that, consider the following two points:

image image image

According to OSRM, the distance between them is -8.7 meters (note that we care about the side of the road, so in this case we use the opposite approach from #5616):

$ curl -s 'http://127.0.0.1:5000/table/v1/driving/24.58692410,57.08066170;24.58728370,57.08056260?approaches=opposite;opposite&annotations=distance,duration' | python3 -mjson.tool
{
    "code": "Ok",
    "distances": [
        [ 0, -8.7 ],
        [ 8.7, 0  ]
    ],
...
    "durations": [
        [ 0, -0.4 ],
        [ 0.4, 0  ]
    ],
...
}

If -8.7 would be replaced with 0, then in VRP optimization the upper point could be sequenced just before the lower point, but that would be incorrect and would cause problems during routing, because the distance is not 0 at all - a vehicle would have to drive around the block, for example, to reach the lower point from the upper point.

So in our VRP solution we replace negative values with 100 meters and 30 seconds - with the idea that there is some route between the upper point and the lower point, but it has an unknown distance and duration. This workaround prevents the wrong sequencing of points.

asaveljevs commented 5 months ago

Another idea that we had was, if we meet a negative distance or duration in the matrix, then ask routing for real values.

However, it does not work either, because routing gives 8.7 meters in both directions, which is wrong:

$ curl -s 'http://127.0.0.1:5000/route/v1/driving/24.58692410,57.08066170;24.58728370,57.08056260?approaches=opposite;opposite&overview=full&geometries=geojson&annotations=distance,duration&generate_hints=false' | python3 -mjson.tool
{
    "code": "Ok",
    "routes": [
        {
...
            "weight_name": "routability",
            "weight": 0,
            "duration": 0,
            "distance": 8.7
...
}
$ curl -s 'http://127.0.0.1:5000/route/v1/driving/24.58728370,57.08056260;24.58692410,57.08066170?approaches=opposite;opposite&overview=full&geometries=geojson&annotations=distance,duration&generate_hints=false' | python3 -mjson.tool
{
    "code": "Ok",
    "routes": [
...
            "weight_name": "routability",
            "weight": 0,
            "duration": 0.4,
            "distance": 8.7
...
}
mjjbell commented 5 months ago

@asaveljevs can you elaborate on why the route output is wrong? Are you expecting a particular constraint on the route that is taken?

With regards to the original issue, despite improvements to the consistency of distance calculations in #6315, it still hasn't fixed the underlying weight truncation problem mentioned in my above post.

The truncation leads to two waypoints on the same edge having the same weight, even when the source is "down stream" of the target. Some pre-calculated distances to the end of the road are used to calculate the net distance, which ends up being negative.

The only solution is to add some special case logic to the table plugin. We know this can only happen when the snapped waypoints are on the same edge-based node and they have the same weight, so it should be straight-forward enough to identify.

Routing does not have his problem, as it does distance calculations on coordinates as part of generating a response. https://github.com/Project-OSRM/osrm-backend/blob/367933fc1a9705e8ea852b8470f9db2d0f6f73fb/include/engine/guidance/assemble_leg.hpp#L173-L175

mjjbell commented 5 months ago

@asaveljevs can you elaborate on why the route output is wrong? Are you expecting a particular constraint on the route that is taken?

I can see you're using a custom build that supports the opposite approach. If you can share your build/branch I can take a look at the interaction between support for opposite and the negative distances/durations.

asaveljevs commented 5 months ago

@mjjbell, yes, I am glad that you already noticed that for both points the opposite approach is used and I assume that no further elaboration is necessary. The only thing I would add is that routing gives 8.7 meters and 0.4 seconds from the lower point to the upper point, but 8.7 meters and 0 seconds (not 0.4!) in the other direction.

We are using https://github.com/asaveljevs/osrm-backend/tree/custom/opposite-approach for our build of OSRM, which is the opposite approach patch for OSRM v5.27.1. We also have the old branch https://github.com/asaveljevs/osrm-backend/tree/custom/opposite-approach-v5.22.0 for OSRM v5.22.0.

mjjbell commented 5 months ago

@asaveljevs with your branch or the newly minted master containing #6842, I'm not able to reproduce your output. Instead of the negative values, I get the expected "shortest u-turn" route.

image

If you can explain more about your setup, that will help. When I did the original analysis, I estimated that the input locations need to be within a metre of each other to trigger the weight truncation issue. So 8.7m seems higher than expected, but it will depend on the weight function used.

The fix for negative values is relatively simple (although not very satisfying), so I may submit that change anyway, and we can see if your issue is also addressed.

mjjbell commented 5 months ago

Irrespective of the reproducibility, I believe I have a test case that represents the problem you are suggesting.

Here I use a one-way street that mimics the type of restriction the approaches could make.

@routing @car
Feature: Car - truncated

    Background:
        Given the profile "car"

    Scenario: Truncated weights route

     #
     # d---------------c
     # |               |
     # |               |
     # a--->--12--->---b
     #

    Given the node locations
        | node |  lon     | lat   |
        | a    | 0        | 51    |
        | b    | 0.01     | 51    |
        | c    | 0.01     | 51.01 |
        | d    | 0        | 51.01 |
        | 1    | 0.005    | 51    |
        | 2    | 0.005005 | 51    |

    And the ways
        | nodes | oneway |
        | ab    | yes    |
        | bc    |        |
        | cd    |        |
        | ad    |        |

    When I request a travel distance matrix I should get
        |   |  1      | 2   |
        | 1 |  0      | 0.4 |
        | 2 |  -0.4   | 0   |

    When I route I should get
        | from | to | distance | weight |   time  | route  |
        | 1    | 2  | 0.4m     | 0      |     0s  | ab, ab |
        | 2    | 1  | 0.4m     | 0      |     0s  | ab, ab |

For 2->1 table, the distance value is clearly wrong as it's negative. For the 2->1 route, the correct distance should be 3628.6m, but instead we get 0.4m, with an indication that we can effectively take the reverse direction on the one-way street.

Looking at the routing code, the distance and duration is not available during the search, so this could be potentially trickier to fix than in the table requests.

asaveljevs commented 5 months ago

@mjjbell, the requests with -8.7 meters that I previously mentioned were from some months ago and they were most probably not on OSM data. I have just tried searching for an example on the latest OSM network, but about half an hour into it and I did not find a case with more than a negative meter. So I currently do not have a new example for you, but I can keep it in mind.