Routing changes!!!

[Victor Shcherb]

Hi All,

I finally fixed one issue (very suspicious) I never met it before till now but anyway it could be helpful one day :) I hope I didn't introduce more issues...

So according to my last tests the main problem was one of the "heuristics" - dynamic road prioritizing.

It causes at the end of roads very weird endings/ U-turns ... Especially on long distances! 

So I disable it however it causes more memory consumption at the end, according to my measurements +50%. 

1. Double road processing issue fixed. (never see real route problem)

2. Dynamic road prioritizing (temporary) disabled.

3. Routing tests introduced ! :) Finally.

All people who gathered xml's now can compare and enjoy automated testing :) 

XML tests can be gathered in one file or in multiple here is the example : 

https://github.com/osmandapp/Osmand/blob/master/DataExtractionOSM/src/net/osmand/router/test/nl_test.xml

To run Tests .sh/.bat file is introduced (in latest OsmandMapCreator) : 

https://github.com/osmandapp/Osmand/blob/master/DataExtractionOSM/runRouteTests.sh

It takes multiple routing_xml absolute paths  as parameters, all other parameters should be specified in MapCreator (!) like where to get '*.obf' files and where 'routing.xml' exists.

How it works : 

It takes best_percent correlation (I setup to 5) and tries to compare 4 critical for routing metrics and check if they are in best_percent interval.

complete_time="7332.0825" loadedTiles = "165" visitedSegments = "1783" complete_distance = "207917.34"

I know it is very limited solution but let me know what improvements could be done there :) 

Keep collecting these "good" as you think roads with good coefficients, I think we will include all them in Continuous Integration Jenkins job.

Best Regards,

Victor

[Hardy]

Routing results look pretty good at first sight ...!

I really wish we could improve the Out-of-Memory issues on many
devices somehow.

[Jindřich Makovička]

On Fri, Jul 6, 2012 at 12:49 AM, Victor Shcherb
<victor....@gmail.com> wrote:
> Hi All,
>
> I finally fixed one issue (very suspicious) I never met it before till now
> but anyway it could be helpful one day :) I hope I didn't introduce more
> issues...
> So according to my last tests the main problem was one of the "heuristics" -
> dynamic road prioritizing.
> It causes at the end of roads very weird endings/ U-turns ... Especially on
> long distances!

Great, now it finally seems to give decent results for routing between
two larger cities connected by a motorway, where the ends are the
reason for using a navigation.

Congratulations!
--
Jindřich Makovička

[Gints Polis]

I am at travel with nightly version. So far have to admit, works good.

Thank you.

[Victor Shcherb]

I will not be so happy now :) I just measured some 500 km and it is enormously slow (10 times slow). 

I think we need to get back dynamicRoadPrioritizing in some sense.

First of all if you have setup and record (Route tests) so we can measure our 4 metrics (loadedTiles, visitedSegments and completeDistance, completeTime).

Why  dynamicRoadPrioritizing  doesn't work sometimes?

Imagine you have 2 cities and direct line between them goes to the east however "highway" lays on the west. So routing algorithm will start to go east and after several attempts it will find west highway but it will never revisit shorter way to highway (just going to west in the beginning). That's why you will see some weird "road artifacts" in the ending. 

Why  dynamicRoadPrioritizing  calculates efficiently? 

Because it doesn't revisit whole graph and that's heuristic :)

Possible solution :

Decrease roadPriorities closer to 1. This will work for short distances but not for long distances! because 1.1 coefficient on short distance gives small time addition but on long it is crucial and blocks some roads to visit. I'm trying a different approach and it probably gives better result apply dynamicPriority coefficient only for first 10km of routes (I will make at as a parameter). It is fair because for highway we can expect following 10km the same type of highway and be the same priority. However... probably we need different heuristic...

But we shouldn't trust much to heuristics we need to measure everything! I suggest to start with long road tests because they are very representative.

Victor

2012/7/6 Jindřich Makovička <mako...@gmail.com>

[Horst Müller]

Well, from my own experience (old routing and short distances - pedestrian <3km and a specific car route <60km) I noticed, that very low priorities (0.1 for each) and untouched dynamicpriorities lead to a good result. I still had to use a high heuristiccoefficient (1.5 for cars, 1.0 for pedestrians) but then the suggest car route was optimal. I used this specific route, cause Google Navigation formerly suggested exactly the same "wrong" route as OsmAnd now does (with old routing). Changing the priorities to these extreme values helped to come back to the "optimal" route, like other navigation systems would suggest, too.

Maybe it's worth investigating, maybe not. I was just in the mood telling you this :)))

Regards,

Horst

2012/7/6 Victor Shcherb <victor....@gmail.com>

[Hardy]

All in all, from my circle of test users, I draw more fire for
ridiculously wrong routes than for the deficit of maybe not being able
to calculate long routes at all.

Looks like most people feel that if a long route fails to calculate,
they at least can always manually select interim destination points,
but if short routes are totally wrong, there is no good workaround for
that.

So we may want to keep this in mind for our future rlease strategy:
Let's start with poducing reliable short routes (seems we have now),
and try to not make the app crash (or even crash the device) when long-
route calculation approaches the low memory state.

[rodolfo]

Most of my test routes (< 50km) show optimal results today. Some are even more correct now than Cloudmade or ORS routing, so please cherish this achievement in the  process of improving long distance routing.

[Hardy]

Hello rodolfo, I can only substantiate that! Trouble is perhaps that
we pay a high price in calculation time and/or memory consumtpion for
this. But as I said above: Better good results (or none), than
permanently ridiculous errors ... :-)

[Victor Shcherb]

Well I introduced 10km technique that gives much better results but still not enough sometimes :( I even discovered one route that gives 10km highway deroute and I simply can't avoid it with any configuration need to go deeper in implementation level.

Please collect/prepare and send good tests for 100-300km car routes they will be included in automatic test framework. Please also specify what countries are used there.

Victor

2012/7/6 Hardy <hm.gg...@gmail.com>