Using faster and exact routing engine? (monav)

[Rutger Nijlunsing]

Hi all,

I'am using OsmAnd regularly for offline routing, and it still gives non-optiomal results in some situations:

- over the exit and then next entry onto the same highway (I see this always at exit 'Heteren': 51.945181,5.767848)

- recalculating routes seems to do something different from re-entering the same route, resulting in non-optimal routes

- calculating routes over long distances is either slow, or non-exact.

Now if we would have a routing engine which would be:

- always very fast

- always generate exact results

- run on the mobile device itself

...all these heuristics would not be needed. So this would need to be completely different from most A*/Dijkstra algorithm kind of things, since the time complexity is too large for larger distances and/or a higher density of nodes as is the case for OSM data.

(Sidenote: Google Maps also suggests along the lines of think-differently to solve this problem at http://googleblog.blogspot.nl/2007/11/road-to-better-path-finding.html )

Searching on the web for such an algorithm I found 'monav':

   http://wiki.openstreetmap.org/wiki/MoNav

   http://code.google.com/p/monav/

which claims to have these properties by using magic 'Contraction Hierarchies' to create the routing graph on multiple resolutions, where on the higher levels long distance routes are pre-calculated.

The upsides seem to be great:

- fast routing (according to the thesis, always sub-second on a mobile device). 

- always the same, exact route

- runs with limited resources (10Mb RAM)

- routing deamon is already seperate

- already works with OpenStreetMap data

The downsides seem to be surmountable:

- needs to pre-process data on a powerful PC

- depends on Qt: so not Java.

- MoNav contians also GUI, which we can disregard

- port to Android not mature, but has been done at least once: https://groups.google.com/forum/?fromgroups=#!topic/monav-dev/chuXf1bU4tw

- MoNav needs to have the routing data in its own internal format, so it about doubles the offline-map-size

So my question: Did anyone look into using MoNav for OsmAnd?

The first logical step might be to have MoNav run on the desktop, and produce a result compatible with CloudMade/YOURS/OpenRouteService output. What would be the simplest way for this?

Regards,

Rutger.

[Max]

'Contraction Hierarchies' depends very much on preprocessing.
So it seems not to be very flexible?
If we change routing profile, we have to recalculate the precomputed data?
Thus users can hardly customize their routing profile (routing.xml), e.g. change priorities/weight of way types?

[Rutger Nijlunsing]

O yes, you're completely correct in that the pre-computing means that dynamic routes are impossible (the changing of routes.xml would mean a new prereprocessing of the input data). Though I see this usage as a more advanced usage which most users won't use. One place where dynamic routes are essential is for dynamically changing conditions, like 'a road block in 10km, please find route around block' or 'avoid current traffic jams'. So we would always need to be able to fallback to a dynamic approach like we now have, or have a smart mix.

For myself I have the problem that I've seen the current algorithm is unstable (recalculating makes things worse for example, or it gives 'empty result'), and I would love to have a stable, non-heuristic based approach which I can trust. Just like I trust the result of Google Maps routes, and I distrust routes of my Garmins. The distrust in Garmin made me look into OsmAnd in the first place: Garmin's format is reversed engineered, which means that the application 'mkgmap' exists which converts OpenStreetMap data into Garmin maps. However, each device has its own heuristic, which meant fighting against the heuristics by tweaking the map-generation process with your own parameters, and most of the times losing.

So what I'm wanting to explore is the easiest way to integrate the results of MoNav into OsmAnd. First as a service-on-desktop-server, then service-on-mobile-device itself, and potentially tighter integrated into OsmAnd if it works well.

Regards,

Rutger.

[Arndt]

Am Donnerstag, 3. Januar 2013 17:44:57 UTC+1 schrieb Rutger Nijlunsing:

 

Though I see this [dynamic] usage as a more advanced usage which most users won't use. ... So we would always need to be able to fallback to a dynamic approach like we now have, or have a smart mix.

So what's the message? Road-blocks, ferry exclusion, or think of alternatives (=semi exclusion of first choice result), dynamic aspects everywhere, so these fast routing machines that preprocess the preferences into the database are academic toys for bored scientiests without practical use. Is that what you want to say in the second part?

I would love to have a stable, non-heuristic based approach which I can trust.

So not talking about speed here. But exactness and the absence of bugs don't call for contraction hirachies, but for good engeneers.

So what I'm wanting to explore is the easiest way to integrate the results of MoNav into OsmAnd. First as a service-on-desktop-server, then service-on-mobile-device itself, and potentially tighter integrated into OsmAnd if it works well.

I faced the same problem, though with a different motivation (wanted bike routing I can trust and I can configure to my needs). I found a solution which is not very handy, but works for the time beeing: a simple file interface reading the favorites-file and writing back the gpx into OsmAnd's track directory. See my thread on "External Bike Routing interfaced to OsmAnd".

So you could do two things:
- do it that way
- help convinicing Victor that a smooth interface to external offline routers would be a cool thing

For the speed subject: this is mainly an issue for dynamic recalculations if you got of the track. But I think for that case, some simple trick for doing a short-distance re-routing on the original track would do?

Regards, Arndt

 

[Nelson A. de Oliveira]

If this get implemented
http://code.google.com/p/osmand/issues/detail?id=954 then this issue
is partially solved: OSRM uses Contraction Hierarchies.

[Rutger Nijlunsing]

Am Donnerstag, 3. Januar 2013 17:44:57 UTC+1 schrieb Rutger Nijlunsing:

 

Though I see this [dynamic] usage as a more advanced usage which most users won't use. ... So we would always need to be able to fallback to a dynamic approach like we now have, or have a smart mix.

So what's the message? Road-blocks, ferry exclusion, or think of alternatives (=semi exclusion of first choice result), dynamic aspects everywhere, so these fast routing machines that preprocess the preferences into the database are academic toys for bored scientiests without practical use. Is that what you want to say in the second part?

Currently, OsmAnd does not support dynamic routing (where dynamic routing is defined as routing results depending on runtime changes like 'time is 9:05, so ferry1 is now earlier than ferry2', 'traffic information'), and is already very useful on its own. So (almost) static routing works for me, and I would bet for most people out there. For example, Google Maps has 6 different static costs functions: 4 for cars (with/without freeways, with/without toll), 1 for by bike and 1 for by foot. This is apparently good enough for the majority users (and for me).

This might change in the future, but that's a concern for then, and yes you're right, that's indeed easy to get accademic on. [Although a TomTom button like 'road block in 0.1/1/10/100km on current route' would be very useful feature to have, and be really dynamic]

 

I would love to have a stable, non-heuristic based approach which I can trust.

So not talking about speed here. But exactness and the absence of bugs don't call for contraction hirachies, but for good engeneers.

Assuming a uniform distribution of nodes and edges, performing Dijkstra on a source point will yield O(n^2), where n is the distance. That explodes time-wise, which is a reason to have heuristics as OsmAnd does in the first place. Heuristics has it different set of problems, since it will take shortcuts where it should not have done so. To solve this either use a non-heuristic algorithm ('contraction hierarchies' seem to have the right papers for this), or improve the heuristics to be 'good enough'.

Having implemented a lot of heuristics myself (in a different, but related domain: image processing), I prefer a solution which does not require heuristics by far since I've seen heuristics which-obviously-are-right fail over and over again :)

 

So what I'm wanting to explore is the easiest way to integrate the results of MoNav into OsmAnd. First as a service-on-desktop-server, then service-on-mobile-device itself, and potentially tighter integrated into OsmAnd if it works well.

I faced the same problem, though with a different motivation (wanted bike routing I can trust and I can configure to my needs). I found a solution which is not very handy, but works for the time beeing: a simple file interface reading the favorites-file and writing back the gpx into OsmAnd's track directory. See my thread on "External Bike Routing interfaced to OsmAnd".

So you could do two things:
- do it that way
- help convinicing Victor that a smooth interface to external offline routers would be a cool thing

:) I will read into that thread, thanks. That's indeed the main motivation: no-one knows whether a different routing engine will be better. But having an easy way to try it out it helpful.

 

I was more thinking along the lines of:

- have MoNav generate same output as one of the other online routers CloudMade/YOURS/OpenRouteService (which has the simplest output by the way?)

- edit /etc/hosts (or OsmAnd source + recompile) on device to point cloudmade/yours/openrouteservice server to own server

- have own server as proxy between MoNav

So I might ask Victor to make the routing server host configurable, that would help.

For the speed subject: this is mainly an issue for dynamic recalculations if you got of the track. But I think for that case, some simple trick for doing a short-distance re-routing on the original track would do?

This simple trick of doing a short distance re-routing is exactly the heuristic which is biting me. I live between 2 exits of a freeway: OsmAnd suggests one, and I always take the other. It starts recalculating then, and adding small parts to the original track, which means it won't see that I am 1km from my home and still re-route 5km back to the freeway to the other exit.

 

If the routing engine would be fast enough, no such heuristics would be needed.

Regards, Arndt

 

Regards,

Rutger.

[Victor Shcherb]

>> - help convinicing Victor that a smooth interface to external offline routers would be a cool thing

No need to convince me :)

There are 2 problems...

1) How to provide route details from external offline routing (lane information, speed limit, roundabouts ....)

This class https://github.com/osmandapp/OsmAnd-core/blob/master/OsmAnd-java/src/net/osmand/router/RouteResultPreparation.java is responsible (it just need raw list of Osm ways with all tags and attached osm ways ).

2) Time :) if you create pull-request that will definitely help or I can help you where it is possible to plug.

P.S. : Precomputing routes will kill dynamic features and/or increase file a lot. Imagine you want to have truck navigation/taxi .../ prefer highway/avoid motorway. Probably Monav (which is used in OSRM) will eliminate this conceptual problems. Currently we use fast A* algorithm.

Victor

2013/1/3 Arndt <abre...@googlemail.com>

[Rutger Nijlunsing]

On Fri, Jan 4, 2013 at 1:26 AM, Victor Shcherb <victor....@gmail.com> wrote:

>> - help convinicing Victor that a smooth interface to external offline routers would be a cool thing

No need to convince me :)

There are 2 problems...

1) How to provide route details from external offline routing (lane information, speed limit, roundabouts ....)

This class https://github.com/osmandapp/OsmAnd-core/blob/master/OsmAnd-java/src/net/osmand/router/RouteResultPreparation.java is responsible (it just need raw list of Osm ways with all tags and attached osm ways ).

2) Time :) if you create pull-request that will definitely help or I can help you where it is possible to plug.

Thanks for your input, Victor! This is the kind of input I'm waiting for before looking into it: some conceptual input on the current state of OsmAnd.

Before there is anything to git-pull, I want to find a way to prototype this first in a time efficient manner. What I read from your answer is that the online routing services (which I've not used at all) give less integrated results than the internal routing engine, is that correct?

Are there more differences between the online and offline routing modes? (for example, threshold before we start recalculating)

What do you mean with 'raw list of Osm ways'? Does that include the node locations and/or node tags, or only references to the nodes?

Does this also mean that the routing map must be of exactly the same version as the map used in other parts of OsmAnd?

If so, how does OsmAnd currently handle different versions of the map? (for example, a map of the Netherlands which is of 2012-10-01, and a map of Belgium which is of 2012-06-03) How are those maps merged into one routable map?

Given the fact that we already have to support different versions of maps at the same time: Would it be difficult to convert a list-of-lat-lon-coordinates to a list of ways?

 

P.S. : Precomputing routes will kill dynamic features and/or increase file a lot. Imagine you want to have truck navigation/taxi .../ prefer highway/avoid motorway. Probably Monav (which is used in OSRM) will eliminate this conceptual problems. Currently we use fast A* algorithm.

Yes, indeed. It's either dynamic + heuristics, or pre-computing, or a smart combination. Google Maps 'only' has 6 routing combinations, so the amount of absolutely required combinations is not that large to be useful for a large public. I don't know how MoNav's file format handles this, though (6x filesize is a larger problem on a mobile device than a Google Cloud).

 

Regards,

Rutger.

[Arndt]

Am Donnerstag, 3. Januar 2013 21:53:37 UTC+1 schrieb Rutger Nijlunsing:

For the speed subject: this is mainly an issue for dynamic recalculations if you got of the track. But I think for that case, some simple trick for doing a short-distance re-routing on the original track would do?

This simple trick of doing a short distance re-routing is exactly the heuristic which is biting me. I live between 2 exits of a freeway: OsmAnd suggests one, and I always take the other. It starts recalculating then, and adding small parts to the original track, which means it won't see that I am 1km from my home and still re-route 5km back to the freeway to the other exit.

 

If the routing engine would be fast enough, no such heuristics would be needed.

So this is a "too simple trick" (re-routing to the closest-distance node of the old route?).

What I had in mind is to do real the real thing (=long distance-processing with O(n^2) scaling) with a timeout and register for each node of the old track that is hit in the new processing at what cost it is hit. The new result then is the minimum sum of hit-cost + remaining cost along old route. The only heuristic in that algorithm is the timeout (=assuming the remote part of the new route is identical to the old one)  

Am Freitag, 4. Januar 2013 01:26:06 UTC+1 schrieb Victor Shcherb:

>> - help convinicing Victor that a smooth interface to external offline routers would be a cool thing
No need to convince me :)

if you create pull-request that will definitely help or I can help you where it is possible to plug.

I will definitly come back to that (but will take some weeks)

Regards, Arndt
 

[Rutger Nijlunsing]

On Fri, Jan 4, 2013 at 10:51 AM, Arndt <abre...@googlemail.com> wrote:

Am Donnerstag, 3. Januar 2013 21:53:37 UTC+1 schrieb Rutger Nijlunsing:

For the speed subject: this is mainly an issue for dynamic recalculations if you got of the track. But I think for that case, some simple trick for doing a short-distance re-routing on the original track would do?

This simple trick of doing a short distance re-routing is exactly the heuristic which is biting me. I live between 2 exits of a freeway: OsmAnd suggests one, and I always take the other. It starts recalculating then, and adding small parts to the original track, which means it won't see that I am 1km from my home and still re-route 5km back to the freeway to the other exit.

 

If the routing engine would be fast enough, no such heuristics would be needed.

So this is a "too simple trick" (re-routing to the closest-distance node of the old route?).

For some use cases, the trick is great, for others not so.

For example, when driving a long route to your holiday destination, you wander of the routed track into a parking lot some distance from the route. In that case, rerouting back to the calculated route is a good thing to do (since the calculation took a long time, right?).

But in other use cases, it is not so great: sometimes you know a traffic jam is coming up, or there is another reason to get to the next-best-route, then you want to drive away from the shortest route and you hope your navigation system picks up the next-best-route automatically and swiftly. And then you get a little annoyed when the navigation system suggests going back to the road block everytime :)

That's the main problem with heuristics: there is no one-size-fits-all. And it gets to clutter the UI (just like 'check this box for long routes' we have now). You might get a 'recalculate button' on the UI to force complete recalculation.

What I had in mind is to do real the real thing (=long distance-processing with O(n^2) scaling) with a timeout and register for each node of the old track that is hit in the new processing at what cost it is hit. The new result then is the minimum sum of hit-cost + remaining cost along old route. The only heuristic in that algorithm is the timeout (=assuming the remote part of the new route is identical to the old one)  

 

This is quite easy to achieve with Dijkstra: normally it is single-source routing algorithm by setting the cost of the start (or end)point to zero, and then calculate the distance to this point, you can set the cost of all points along the route to zero to get this behaviour. But be aware: this way you still greatly subsidize the initial route, which is not always what you want.

Another question: you mentioned that the routing algorithm had been optimized. I've got some ideas (from practice) for optimization, which I don't know whether those have been implemented. Might be good to look into:

- one way to double the speed of Dijkstra it to start both at the start as well as the end point at the same time, which means you grow 2 'circles' to the point of touching. This reduces the area of the circle with a factor of 2, resulting in a factor 2 speedup.

- you want to fit as much as possible in the CPU L1 cache, so small structures, which in turn means a routing network with only the route-relevant information. You might want to have a separate routing graph in memory. How is this implemented?

This is real fun area to explore. Does anyone have any experience with Davlik and high-performance algorithms?

Then again, going from O(n^2) to something less than quadratic is a major shift resulting in a major enhancement, which is why I want to look into this...

 

Am Freitag, 4. Januar 2013 01:26:06 UTC+1 schrieb Victor Shcherb:

>> - help convinicing Victor that a smooth interface to external offline routers would be a cool thing
No need to convince me :)

if you create pull-request that will definitely help or I can help you where it is possible to plug.

I will definitly come back to that (but will take some weeks)

Regards, Arndt
 

Great! What are you exactly thinking of? It would be good to draft an API (without implementation) for the discussion.

Regards,

Rutger.

[Victor Shcherb]

Hi,

There is no difference between Online Routing and Offline Routing conceptually. Main difference all Online Routing provide much less results and this is important!

For example, Max Speed, Roundabout (lots of online routing doesn't return if it is roundabout and what is turn-angle), Lane information, Keep Left/Right + lane.

There is no way to synchronize local map data with ids sent from server. I mean it would be too difficult and we don't need to look into that direction.

Victor

2013/1/4 Rutger Nijlunsing <rutger.n...@gmail.com>