navit-project.org

forum for navit navigation tool
It is currently 20 Nov 2017, 13:27
View unanswered posts | View active topics


All times are UTC


Forum rules


Feel free to ask anything here related to the development process - coding, creating new features, fixing bugs and custom changes of Navit.

Note: For reporting bugs, use the bug tracker.



Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 07 Jul 2013, 11:57 
Offline

Joined: 07 Jul 2013, 10:08
Posts: 8
I'm very impressed with navit's speed and function - it's very quick to find a pretty good route round parts of the UK using my Raspberry Pi 8-) Which is great, because I aim to use it to build a SatNav for my old Jaguar XJS.

But... I read the discussion in bug #456 about routing algorithms. That says it uses Dijkstra, but that's not 100% of the story; it looks at a restricted part of the map - by default detailed (great depth) areas about the start, each waypoint, and end, and less detailed (low depth) in a larger area encompassing all those points. If that larger area isn't big enough, navit misses the best route.

Let's be specific. Use the UK map, find a route from Land's End to Milford Haven. It gives an error message; it needs a waypoint at say Bristol to get a route. The cause is the Severn estuary bisecting the map area that navit looks at. :( Increasing the size of that large-but-less-detailed area helps, but slows navit down.

As discussed in that bug, there's a well-known enhancement to the routing algorithm, "A*", which may allow navit to search the whole map without loosing performance. route.c looks like it could be changed to use A* relatively easily. I've started trying to code this (following the instructions for building navit in Eclipse), and will submit a patch if I can get it working.

Please can someone comment on the following approach to this:
IIUC, it now builds a graph for the areas (described above) by repeated calls to route_graph_update(), and then calls route_graph_flood() for the Dijsktra search. For A*, it would follow paths (still starting at the destination), and each time it hit a new point
(a) if necessary call route_graph_update() to ensure it had all the map data (at a great depth),
(b) calculate the straight-line distance for that point to the starting point, and
(c) do the A*/Dijsktra stuff.
The fiddly part is deciding step (a) if it needs to load more map data. It also needs route_graph_update() to leave existing path information untouched.

A simple approach is to load say 10km squares centred on the point, and record these squares in a table. Each time it hits a new point (where the distance in (c) is not yet calculated) look to see if it's in a square already loaded. This would be better if the squares it loaded had some relationship with the underlying map data, but that would tie the routing to a particular map implementation.

Passing through a waypoint might cause a problem, as the algorithm would meet points whose distances have been calculated for the preceding waypoint, but presumably that's already handled with the existing Dijkstra implementation.

The above approach to A* might produce a worse route than now, since it would try minor roads and cart tracks in the middle of a long journey. That's a question of the cost function that's being optimized (distance or time), and there are ways to attack that. I have an approach that I want to try (the original purpose that brought me to navit), but there's not a lot of point without removing the current algorithm's filtering out paths with great depth.

Is this totally mad :?:


Last edited by usul on 07 Jul 2013, 12:46, edited 1 time in total.
soft formating and highlightning


 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 07 Jul 2013, 12:41 
Offline
User avatar

Joined: 07 Jun 2013, 09:32
Posts: 200
Location: Rostock, North Germany
For everybody who isn't that familar with UK (as myself)
Made with http://project-osrm.org


Attachments:
UK_trip.png
UK_trip.png [ 82.11 KiB | Viewed 6083 times ]
 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 07 Jul 2013, 13:21 
Offline
User avatar

Joined: 07 Jun 2013, 09:32
Posts: 200
Location: Rostock, North Germany
As I'm not that within routing (or the codebase in general) I only can point you to this framework, which might help you to show the advantages/disadvantages of your approach?
http://code.google.com/p/trafficmining/


 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 07 Jul 2013, 15:56 
Offline

Joined: 07 Jul 2013, 10:08
Posts: 8
Usul, thanks for the formatting and link.


 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 08 Jul 2013, 19:18 
Offline
Site Admin

Joined: 22 Feb 2013, 20:48
Posts: 1
Hi Goverp,

thanks for your quite good analysis. The routing engine doesn't really work well for this case.
I don't have yet a good idea how to fix this. A* won't help much I am afraid since it just makes the search more directional, and in this case you have to actually work against the natural direction (or at least orthogonal to it).
I could imagine the following: For the cases where the routing engine fails it could do a bit more of an analysis of the situation. For example it could detect that there are no reachable nodes soon after destination in direction of the position and therefore the outermost search rectangle has to be made wider.

Don't know however whether this is a way to go.

Best regards,

cp15


 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 08 Jul 2013, 21:44 
Offline

Joined: 07 Jul 2013, 10:08
Posts: 8
cp15,

Many thanks for the analysis.

Not sure I agee though! In this case, all routing algorithms (Dijkstra, A*, releasing a hoard of homing weasels) will do the same, which is spread out from the destination (Milford Haven).

A* will concentrate on points that are nearest the start, and gradually move outwards and towards the start - it's not keen on moving away from the starting point. So it won't waste much time going North, but it will go East and West (until it runs out of land!). Once it gets to Bristol, it will get to Lands End very quickly.

In some respects, A* does exactly what you suggest, increasing the size of the search rectangle until it hits a path that moves in the right direction. Because fast segments broaden the search more quickly, if you're after least time, as A* uses time-so-far plus minimum-possible-time left, it explores the ends of fast paths first. It should do quite a decent job.

I suspect there's a class of nasty journeys from northern Denmark to Bergen, especially if you want to avoid tolls (and trolls) :twisted:

Whatever, I'm sufficiently sure it's worthwhile that I'll try to code it; if it works OK, we can try a properly-organised comparison. The next question is how little of route.c would need changing,,,


 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 09 Jul 2013, 06:15 
Offline
User avatar

Joined: 07 Jun 2013, 09:32
Posts: 200
Location: Rostock, North Germany
To compare both approaches, we might need a testing framework that makes sure, that the routes that work currently don't get wrong and that the ones that currently don't work fine, will get improvements.

There is currently this one, that takes the most current OSM planet into account:
http://qa.navit-project.org/status.php

@cp15 would it make a lot of work to clone this instance to use Goverp new approach?


 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 09 Jul 2013, 08:02 
Offline

Joined: 07 Jul 2013, 10:08
Posts: 8
cp15, A thought :idea: - we could combine A* with part of the current approach, to limit the search depth when far from the waypoints.

My proposed A* search loads a detailed graph about the destination. It could add less-detailed (and perhaps larger area) graphs when it meets a point outside that initial graph, (which effectively navit does now). It would need to preload detailed maps around the waypoints and start too.


 Profile  
 
 Post subject: Re: Routing algorithm - A*, Dijkstra and navit's
PostPosted: 09 Jul 2013, 18:24 
Offline

Joined: 09 Jul 2013, 17:41
Posts: 82
Using a config file workaround, I was able to get the needed route in a few seconds. I have modified default car vehicle profile in the following way:
Code:
<vehicleprofile name="car" route_depth="4:150%,8:40000,18:10000" flags="0x4000000" flags_forward_mask="0x4000002" flags_reverse_mask="0x4000001" maxspeed_handling="0" route_mode="0" static_speed="5" static_distance="25">


The changed part is 4:150% in route depth.


Last edited by usul on 09 Jul 2013, 19:18, edited 1 time in total.
formating


 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Silver Orange 2.0.6 for IPB Designed by Skins and Hosting
Converted for phpBB3, based on Royal Blue template by BigB © 2007 2008 AEON KINGS