Wrong bike routing with "elevation data"

[clementcontet]

Description

On a particular street (https://www.openstreetmap.org/way/22664165), the bike routing goes crazy when enabling "use elevation data".

Note that I use default bike routing options, except for the additional "no stairs" option.

I understand that enabling "use elevation data" may create a longer route but with less slopes, but that's not the case here:

• the route without the "use elevation data" is 325m long with one slope at 5%
• the route with "use elevation data" is 1.13km long with two slopes at 7% then 9% ==> it makes no sense to advise this route

How to reproduce?

Activate the "no stairs" option. Toggle the option "use elevation data" on and off on this particular route.

Your Environment

OsmAnd Version: 3.9.6 (also tried today's nightly) Android/iOS version: Android 10 Device model: OnePlus 5

Maps used (online or offline):
Offline: Europe>France>Auvergne-Rhône-Alpes>Métropole de Lyon, from February 1st 2021

[alisa911]

This has been fixed and will work in the next version of Osmand

[clementcontet]

@alisa911 the route you're showing is the one using the "stairs" (btw, it also makes no sense to advise the stairs at 20% slope instead of the regular street at 5% slope).

If you check the "avoid stairs", what do you have?

[alisa911]

Yes, after enabling "avoid stairs" my route became the same as yours.

[vshcherb]

So, then there is no issue. Penalty for stairs is quite high and that's why it displays like that. If there is no stairs and it's a nice bicycle road, you can correct it on osm.org

[clementcontet]

No @vshcherb that's the other way around.

There is a nice bicyle road (https://www.openstreetmap.org/way/22664165) that, for some reason, gets a high penalty:

• if you enable stairs, the advised route is to take the stairs (23% slope) instead of the "nice road" (5% slope)
• if you disable stairs, the advised route is to take a very long list of roads (4 times longer, with two slopes at 7% and 9%) instead of the "nice road"

The route use only the "nice road" if I disable the "use elevation data".

So enabling this "use elevation data" seems to give the "nice road" a high penalty, but I don't see why in the data.

[vshcherb]

It turns out that "stairs" road is very steep by the data due to low precision of SRTM data and narrow distance between roads, the graph doesn't display that steepness cause it does a bit smoothing, so that issue will be closed as is.

[clementcontet]

Thanks for the investigation @vshcherb . Is there a way for me to contribute to "fix" the SRTM data?

[clementcontet]

Hi again @vshcherb I've scratched my head again with this issue and started to dig into the app code to better understand it. I get that SRTM data is too imprecise (I can see the wrong values in the heightArray) and create artificial penalties on this particular road.

But another experiment really surprised me (I don't understand the code enough to debug it myself :( ).

So the road gets high penalties and is avoided by the router. But if I set the start point further from it, then finally the road gets chosen by the router. It doesn't make sense, if the "long road" is better that the "short one", it should still be true when I set the start point further!

See screenshots with same conditions (bicyle + avoid stairs + use elevation data > relief_smoothness_factor_plains) on 3.9.10:

BTW, I saw how the incline (and thus the obstacle_srtm_alt_speed) is computed from the SRTM data, but if the "incline" tag is present on OSM data, is it used instead?

[clementcontet]

@vshcherb , I've dug a little more (using latest code from master).

I still don't understand clearly the implementation of 2-ways A*, but I've found that when I force the "one way routing" by setting planRoadDirection to 1, suddenly the correct route is computed.

So for the exact same start and end points (the ones in the screenshot), with planRoadDirection to 1, I get the correct route:

F>Road id 22664165 name Montée du Lieutenant Allouche ref  dir=0 ind=9 ds=442.71866 es=0.0 pend=9 parent=Road id 22664165 name Montée du Lieutenant Allouche ref 
Final segment found

with the default planRoadDirection to 0, I get the long bizarre route:

F>Road id 522736223 name Boulevard de la Croix-Rousse ref  dir=0 ind=0 ds=533.9889 es=0.0 pend=0 parent=Road id 522736223 name Boulevard de la Croix-Rousse ref 
Final segment found

We could argue that restricting the routing to "one way" ignores the better route, but we can see that's the other way around. The distanceFromStart is shorter with planRoadDirection to 1 than with planRoadDirection to 0 (442.71866 < 533.9889).

So I fear that it's not just incorrect elevation data, there may be something with the routing engine too :(

[vshcherb]

I think it 's much simpler , we suspect if you modify these numbers (https://github.com/osmandapp/OsmAnd-resources/blob/master/routing/routing.xml#L1208)

50 -> 25
74 -> 25

It should work fine.

Obviously planRoadDirection = 0 / 1 / -1 should produce the same route though for bicycle there is heuristicCoefficient="1.4" (https://github.com/osmandapp/OsmAnd-resources/blob/master/routing/routing.xml#L908) so the algorithm is not precise 100%, to make 100% precise please lower it to 1.0

[clementcontet]

50 -> 25 74 -> 25

I've even tried lowering the obstacle_srtm_alt_speed to 2 for all incline values => the long route is still computed (which makes sense since the SRTM data add lots of artificial downhill and uphills).

please lower it to 1.0

Even with heuristicCoefficient at 1.0, the short route is correctly computed with planRoadDirection to 1, but with planRoadDirection to 0, it still computes the wrong long road:

Short one:

F>Road id 22664165 name Montée du Lieutenant Allouche ref  dir=0 ind=9 ds=442.69836 es=0.0 pend=9 parent=Road id 22664165 name Montée du Lieutenant Allouche ref 
Final segment found

Long one:

F>Road id 522736223 name Boulevard de la Croix-Rousse ref  dir=0 ind=0 ds=533.9203 es=0.0 pend=0 parent=Road id 522736223 name Boulevard de la Croix-Rousse ref 
Final segment found

I'll try to take some more time to understand how the nodes in the graph are evaluated and/or discarded.

[vshcherb]

that weird well you can always take the route with minimum "routingTime" this should be optimal with hc <= 1.0. Note for some very small segment routes it could has flaws.

[clementcontet]

Hi, a few things for tonight!

1/ I think I found why the router seems to behave differently when working forward or backward, and when changing starting point. From what I understand, when computing the last segment that will reach the opposite path, the last obstacles computation is lost. If I switch the lines https://github.com/osmandapp/OsmAnd/blob/master/OsmAnd-java/src/main/java/net/osmand/router/BinaryRoutePlanner.java#L460-L463 I have my route that is correctly computed with the same value, wether it's computed forward or backward (the 442.69836 vs 533.9203 that I had earlier become the same values).

2/ Contrary to what I said, lowering obstacle_srtm_alt_speed indeed works (I was modifying the values in relief_smoothness_factor_more_plains section whereas I'm using the default relief_smoothness_factor_plains) So removing the last value 48s/meter for incline>25% solves my issue. On my opinion the height penalties for bicycles are really prohibitive. 48secs for one meter of altitude seems really too much. Are there public metrics for such values? (used by other bicycle routing engines?)

3/ Is there a way for contributors to fix the SRTM data? Or does the "incline" tag in OSM gets used by OsmAnd if present, instead of the internal computation based on heights?

Anyway, thanks for the time you spent on my case. I don't regret buying the app :)

[vshcherb]

It still looks like a bug in routing engine, instead of zigzag (routing time 461sec) we have long route (511 seconds), so 50 seconds difference is quite a lot and we will still need to investigate.

[clementcontet]

Well I think that the bug is that we add the final segment to the graph, without taking into account its obstacle and heightObstacle (cf. https://github.com/osmandapp/OsmAnd/blob/master/OsmAnd-java/src/main/java/net/osmand/router/BinaryRoutePlanner.java#L460-L463).

So that if there is a height gap on this last segment, the route is artifically shorter (the 461sec). And depending on wether the route is computed forward or backward, the final "obstacle-free" segment may be placed on different steps of the route: hence the different routing times for the same route.

If I add the obstacle and heightObstacle before calling checkIfOppositeSegmentWasVisited, the forward and backward methods correclty compute the same routing time.

And what about the ways to improve the height data? (can we edit SRTM/ASTER ? or should we add OSM incline tags ?)

[vshcherb]

Can you please create pull-request so it fixes this issue ;-)

СС @xmd5a2 I'm not sure if we can edit it manually (Answer: no, only use better imagery). Probably we can improve for certain roads to not use SRTM data and use OSM tag but it's not supported yet.

[vshcherb]

PR was reverted - some tests are broken

[clementcontet]

Ah sorry, I didn't look at the tests results. I will look into that.

[vshcherb]

Actually there is no bug, I debugged and it is consistent with routing.xml. So straight road with height_obstacles on. Routing time straight is 612.17 (measured by adding avoid roads), the best time around is 208.68 (much shorter). So actually there is no issue.

To reduce 612 to 200 and change it, you can try routing.xml:

--- a/routing/routing.xml
+++ b/routing/routing.xml
@@ -1231,15 +1231,15 @@
                                        <select value="2"/>
                                </gt>
                                <gt value1="7" value2=":incline">
-                                       <select value="8"/>
+                                       <select value="10"/>
                                </gt>
                                <gt value1="13" value2=":incline">
-                                       <select value="16"/>
+                                       <select value="10"/>
                                </gt>
                                <gt value1="25" value2=":incline">
-                                       <select value="32"/>
+                                       <select value="10"/>
                                </gt>
-                               <select value="48"/>
+                               <select value="10"/>
                        </if>
                </way>

[vshcherb]

Summary: there is no bug in routing engine, the configuration dictates routing time. Routing engine finds the route with routing time.