Here's something to stop and think about...

I have a TomTom One. It's a small, hand-held device with a set of road 
maps of the whole of the UK stored in flash RAM.

I have no idea what kind of CPU powers this device, but what I can tell 
you is this: When I ask it to plot a route, it can seemingly analyst 
tens of thousands of roads and quickly find a suitable route. (Typically 
takes less than 10 seconds.)

That doesn't *sound* very impressive... until you sit down and try to 
think of a way to program such a thing yourself. How would you do that??

Post a reply to this message

> That doesn't *sound* very impressive... until you sit down and try to 
> think of a way to program such a thing yourself. How would you do that??

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> That doesn't *sound* very impressive... until you sit down and try to 
> think of a way to program such a thing yourself. How would you do that??

  Not all roads have the same weight. Some of them are marked as being
more desirable than others. After that it's just a question of running
an algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> That doesn't *sound* very impressive... until you sit down and try to 
>> think of a way to program such a thing yourself. How would you do that??
> 
>   Not all roads have the same weight. Some of them are marked as being
> more desirable than others. After that it's just a question of running
> an algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm

As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
nodes of the graph. You can then read off the optimal path from the 
initial node to any desired node - but surely computing the distance 
function for every road in the country would be infeasible?

I guess if you know "approximately" what the optimal distance ought to 
be, you can just ignore any node that's further away then that or 
something... You're still computing quite a lot of data though.

Post a reply to this message

> As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
> nodes of the graph. You can then read off the optimal path from the 
> initial node to any desired node - but surely computing the distance 
> function for every road in the country would be infeasible?
>
> I guess if you know "approximately" what the optimal distance ought to be, 
> you can just ignore any node that's further away then that or something... 
> You're still computing quite a lot of data though.

You're beginning to invent the A* algorithm there ;-)

http://en.wikipedia.org/wiki/A*

I assume in real life applications there is some custom algorithm with many 
additions and hacks based on knowledge of the road system (as opposed to 
applying this to say a computer network).  Also I assume that roads are 
classified into speed ratings, so first it checks for any nearby motorways 
at either end and then checks a route based on that, before fiddling with 
the end sections etc, I imagine it can be quite complex!

Post a reply to this message

>> I guess if you know "approximately" what the optimal distance ought to 
>> be, you can just ignore any node that's further away then that or 
>> something... You're still computing quite a lot of data though.
> 
> You're beginning to invent the A* algorithm there ;-)
> 
> http://en.wikipedia.org/wiki/A*
> 
> I assume in real life applications there is some custom algorithm with 
> many additions and hacks based on knowledge of the road system (as 
> opposed to applying this to say a computer network).  Also I assume that 
> roads are classified into speed ratings, so first it checks for any 
> nearby motorways at either end and then checks a route based on that, 
> before fiddling with the end sections etc, I imagine it can be quite 
> complex!

I imagine it regards the road network as a "network of networks", 
similar to the way the high-level Internet routing protocols work.

As in, it probably attempts to construct a route on main roads only with 
endpoints "near" to the desired endpoints, and then attempts to augment 
that with the minor roads needed at each end. (Probably builds several 
possible motorway routes so it can find a reasonably optimal one.)

The selections like "prefer motorways" and "avoid motorways" probably 
adjust the internal cost function driving the algorithm. Of course, in 
terms of distance, Euclid straight-line distance is a pretty good 
estimate until you compute the actual road distances.

I wonder: Does it cost more to design a better routing algorithm, or fit 
a faster CPU? ;-)

Post a reply to this message

> I wonder: Does it cost more to design a better routing algorithm, or fit a 
> faster CPU? ;-)

More often than not the speed it limited by the read speed from the medium 
that the map data is stored on.  In my car for example it is on DVD, which 
means that is often takes up to 30 seconds to calculate the route - which is 
a bit pants.  Some cars have hard drive systems which are way faster, and of 
course the portable navigation systems have flash based memory.

But still I find it amazing how I can be in the middle of nowhere in 
southern Germany, and then just type in my mum's address 1200 km away and in 
under a minute it tells me exactly which roads to go on to get there and 
exactly how many km it is.  Surely just knowing every single street name in 
Europe is quite a lot of data, let alone the routing information plus the 
road geometry information.

Post a reply to this message

scott wrote:

> But still I find it amazing how I can be in the middle of nowhere in 
> southern Germany, and then just type in my mum's address 1200 km away 
> and in under a minute it tells me exactly which roads to go on to get 
> there and exactly how many km it is.  Surely just knowing every single 
> street name in Europe is quite a lot of data, let alone the routing 
> information plus the road geometry information.

It *is* pretty mental, eh?

Mind you, I saw a guy with an illegal 186 laptop (you know, the ones 
with the blue and purple LCD screens?) that could compute routes around 
the UK given only a few seconds or so. And that was back in 1989. I 
guess the only difference is that now you don't need a £4,000 laptop, 
just a £40 hand-held device. ;-)

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> >   Not all roads have the same weight. Some of them are marked as being
> > more desirable than others. After that it's just a question of running
> > an algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm

> As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
> nodes of the graph.

  No, it doesn't. It starts advancing from the starting node towards all
possible directions, and then follows those paths which are most promising
(according to the sum of weights of those paths).

  In a way it's a kind of breadth-first search, where the weight of the
paths searched so far is kept as equal as possible. It stops immediately
when it reaches the end node (because it would, rather obviously, not make
any sense to continue because the optimal path has already been found). It
actually works even if all the arcs between nodes have the same weight, but
of course then there's no "most promising" path which would take priority.
However, even in this case it will not search through *all* nodes: It will
perform a pure breadth-first search and stop when it has found the shortest
path to the end node.

> I guess if you know "approximately" what the optimal distance ought to 
> be, you can just ignore any node that's further away then that or 
> something... You're still computing quite a lot of data though.

  Dijkstra's algorithm doesn't need any cutoff. It starts advancing in a
breadth-first order (according to the sum of weights of the paths) and
when it reaches the end node, it has found the optimal path.

-- 
                                                          - Warp

Post a reply to this message

>> As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
>> nodes of the graph.
> 
>   No, it doesn't. It starts advancing from the starting node towards all
> possible directions, and then follows those paths which are most promising
> (according to the sum of weights of those paths).
> 
>   In a way it's a kind of breadth-first search, where the weight of the
> paths searched so far is kept as equal as possible. It stops immediately
> when it reaches the end node (because it would, rather obviously, not make
> any sense to continue because the optimal path has already been found).

Ah. Wikipedia's article doesn't seem to mention a stopping condition 
other than "all nodes have been visited".

Also, I ran the algorithm by hand with pencil and paper and it appeared 
to give me a suboptimal route. I ran it for a bit longer and it became 
optimal. I don't know if I misunderstood the algorithm or just made a 
trivial mistake in running it.

>   Dijkstra's algorithm doesn't need any cutoff. It starts advancing in a
> breadth-first order (according to the sum of weights of the paths) and
> when it reaches the end node, it has found the optimal path.

Any idea how the A* algorithm is better than Dijkstra's algorithm?

I was working under the assumption that Dijkstra's algorithm visits all 
the nodes of the graph and A* doesn't need to - but if that isn't the 
case, I'm left wondering how A* is actually better...

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Any idea how the A* algorithm is better than Dijkstra's algorithm?

  Dijkstra's algorithm doesn't use any heuristic and thus probably may
expand more nodes than A*. As wikipedia puts it:

"Generally speaking, depth-first search and breadth-first search are
two special cases of A* algorithm. Dijkstra's algorithm, as another
example of a best-first search algorithm, is the special case of A*
where h(x) = 0 for all x." (h(x) is the heuristic function given to
the A* algorithm.)

> I was working under the assumption that Dijkstra's algorithm visits all 
> the nodes of the graph and A* doesn't need to - but if that isn't the 
> case, I'm left wondering how A* is actually better...

  I don't know if it's completely correct analogy, but I think you could
think that A* is a bit like Dijkstra's, but using a heuristic function to
discard nodes more efficiently. A* seems to also be more generic, in that
you can make it perform other types of searches besides pure breadth-first.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Not all roads have the same weight. Some of them are marked as being
> more desirable than others.

I guess things like one-way roads you'd just have two different distance 
metrics, too.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

scott wrote:
> I imagine it can be quite complex!

Me, I haven't been able to figure out how they store the road data in the 
first place. Just the storage format has to be pretty darn complicated, 
methinks.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

On Tue, 27 Jan 2009 09:43:49 +0000, Invisible wrote:

> That doesn't *sound* very impressive... until you sit down and try to
> think of a way to program such a thing yourself. How would you do that??

OSPF. ;-)

It's really no different than network routing and costing.

Jim

Post a reply to this message

scott wrote:
> But still I find it amazing how I can be in the middle of nowhere in
> southern Germany, and then just type in my mum's address 1200 km away and
> in under a minute it tells me exactly which roads to go on to get there
> and exactly how many km it is.

What would you do if the GPS showed "You're in: Middle of Nowhere"? :)

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> I have no idea what kind of CPU powers this device, but what I can tell
> you is this: When I ask it to plot a route, it can seemingly analyst
> tens of thousands of roads and quickly find a suitable route. (Typically
> takes less than 10 seconds.)
>
> That doesn't *sound* very impressive... until you sit down and try to
> think of a way to program such a thing yourself. How would you do that??

These days, the algorithms usually use an approach like a human would - using a
hierarchical network. Just like you wouldn't consider every byway in all of
Eurpoe when planning a route from, say, 12 Via di Avanti, Assisi, Italy to 42
Rue de Baguette, Beauvais, France, neither does your TomTom.

Theoretically, an exhaustive brute-force approach would be necessary to find the
best route. In practice, a common-sense approach can easily eliminate something
like 99.999% of all roads.

So a typical approach would look like this:

- Find out the best ways from 12 Via di Avanti to the nearest town centers,
using any roads available; this will get you to the town center of Assisi.

- Find out the best ways from Assisi to the nearest bigger cities, ignoring
byways; this will probably get you to Perugia or Terni.

- Find out the best ways from Perugia or Terni to the nearest metropoles, using
only major roads. This will almost inevitably get you to Rome. Make a mental
note to go via Terni, because it gets you faster to Rome than via Perugia.

- Find out the best ways to 42 Rue de Baguette from the nearest town centers,
using any roads available. This will give you the town center of Beauvais.

- Find out the best ways to Beauvais from the nearest bigger cities, ignoring
byways. This will probably give you Amiens, Rouen or St-Denis.

- Find out the best ways to Amiens, Rouen or St-Denis from the nearest
metropoles, using only major roads. This will almost inevitably give you Paris.
Make a mental note to go via St-Denis, because it gets you from Paris fastest.

- Find out the best way from Rome to Paris, using only highways.

- Try out a few alternatives near Rome to check if you can come up with a faster
way. You'll find out that you can eliminate Rome altogether.

- Try out a few alternatives near Terni to check if you can come up with a
faster way. You'll find out that you can eliminate Terni, too, and go via
Perugia.

- Try out a few alternatives near the town center of Assisi. You may find out
that 12 Via Avanti is close enough to the road to Assisi that you don't have to
go via the town center either.

- Similarly, try out a few alternatives near Paris, St-Deniz and Beauvais - only
to find out that you can't optimize much there because the french road systm is
too centered on Paris to come up with any reasonable alternatives ;)

(Actually, TomTom will most likely not operate on town centers, major cities and
metropoles, but rather more generic "traffic nodes" of different hierarchies;
however, the basic concept is the same.)

The common sense behind this approach is that byways and even major roads won't
get you from Italiy to France in any acceptable time.


This approach often may *not* give you the optimal route. However, given that it
will only very rarely be significantly worse than the optimal one, it is
definitely good enough.

Post a reply to this message

> Me, I haven't been able to figure out how they store the road data in the 
> first place. Just the storage format has to be pretty darn complicated, 
> methinks.

Yes, and I suspect they can do quite a lot of pre-processing of the raw data 
to make the searches faster.

Post a reply to this message

Nicolas Alvarez wrote:

> What would you do if the GPS showed "You're in: Middle of Nowhere"? :)

I've seen that enough times now. My place of work isn't on any map, and 
nor is the Hell Hole where my mum likes to go for her holidays.

Post a reply to this message

Darren New wrote:
> scott wrote:
>> I imagine it can be quite complex!
> 
> Me, I haven't been able to figure out how they store the road data in 
> the first place. Just the storage format has to be pretty darn 
> complicated, methinks.

I have a 1 GB flash drive in my pocket. It cost me £2. How much space do 
you think they have to play with in a satnav device?

Post a reply to this message

> This approach often may *not* give you the optimal route. However, given that it
> will only very rarely be significantly worse than the optimal one, it is
> definitely good enough.

Depends on your definition of "optimal". (E.g., total distance, verses 
estimated travel time, any tolls that have to be paid for certain 
routes, traffic volume, etc.)

Did anybody see the one where Google Maps gave a route from something 
like Bristol to Norfolk via Ireland? :-D

Post a reply to this message

> I have a 1 GB flash drive in my pocket. It cost me £2. How much space do 
> you think they have to play with in a satnav device?

My SatNav comes on a DVD, so max 9GB (for all roads in western Europe). 
IIRC TomTom etc the map data comes on a memory card, perhaps 1-4GB depending 
on which map data set you get?

Post a reply to this message

> Depends on your definition of "optimal". (E.g., total distance, verses 
> estimated travel time, any tolls that have to be paid for certain routes, 
> traffic volume, etc.)

On most systems I think you get to choose whether you want the shortest or 
fastest route, the option to enable/disable motorways, tolls, ferries, 
tunnels etc.  Some systems even self-adjust the road weightings based on 
your driving style.  eg if you always drive at 220 km/hr on the autobahns it 
will take this into account when calculating the routing.

The other thing that is cool, is that when it tells you to turn right in 1 
km, it knows exactly which place names will be written on the roadsign, so 
you can easy double-check that you are taking the correct turning.

Post a reply to this message

scott wrote:
>> I have a 1 GB flash drive in my pocket. It cost me £2. How much space 
>> do you think they have to play with in a satnav device?
> 
> My SatNav comes on a DVD, so max 9GB (for all roads in western Europe). 
> IIRC TomTom etc the map data comes on a memory card, perhaps 1-4GB 
> depending on which map data set you get?

Indeed. So it can't be *that* hard to fit all the map into the space; 
it's pretty cavernous. ;-)

Post a reply to this message

Invisible wrote:
> I have a 1 GB flash drive in my pocket. It cost me £2. How much sp
ace do 
> you think they have to play with in a satnav device?

I wasn't talking about the size. I was talking about the format.  As in, 
how 
do you represent the paths of the road, the locations of services, etc et
c, 
in such a way that the machine can tell you "make the second left in X 
miles".  My machine even tells me if I'm on a 5-lane road and two lanes a
re 
exit-only, drawing the picture and telling me to keep to one side or the 
other.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

Darren New wrote:

> I wasn't talking about the size. I was talking about the format.  As in, 
> how do you represent the paths of the road, the locations of services, 
> etc etc, in such a way that the machine can tell you "make the second 
> left in X miles".  My machine even tells me if I'm on a 5-lane road and 
> two lanes are exit-only, drawing the picture and telling me to keep to 
> one side or the other.

I would imagine it's some kind of space partitioning method, similar to 
how a game engine figures out with world polygons are "near to" where 
you're currently standing. ;-)

Actually the video data for displaying the map and the topological data 
for route planning are probably seperate. I would guess.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> > This approach often may *not* give you the optimal route. However, given that it
> > will only very rarely be significantly worse than the optimal one, it is
> > definitely good enough.
>
> Depends on your definition of "optimal". (E.g., total distance, verses
> estimated travel time, any tolls that have to be paid for certain
> routes, traffic volume, etc.)

Well, it actually depends on *your* definition of "optimal": You as the user
assign a certain abstract "cost" to any of these parameters (typically by
choosing from a limited set of predefined factors), e.g.: A km of distance = 7
points, a minute estimated travel time = 10 points, a dollar of toll = 30
points, 40 miles of bad road = 80 points, ...

These abstract "cost" factors are then used to assign a cost to each road
section. The algorithm will then try to come up with a "cheap" route according
to these factors.

So from this perspective, the "optimum" is always well-defined: Lowest abstract
"cost". But even to these standards, the algorithm will only very seldom pick
the optimal route - because it would by any means not be efficient to do so.
After all, it doesn't make much sense to have your navigator spend 3 days
finding the optimal route, if within 30 seconds it can come up with one that is
at most 5 minutes longer :P

Post a reply to this message

> > I wasn't talking about the size. I was talking about the format.  As in,
> > how do you represent the paths of the road, the locations of services,
> > etc etc, in such a way that the machine can tell you "make the second
> > left in X miles".  My machine even tells me if I'm on a 5-lane road and
> > two lanes are exit-only, drawing the picture and telling me to keep to
> > one side or the other.
>
> I would imagine it's some kind of space partitioning method, similar to
> how a game engine figures out with world polygons are "near to" where
> you're currently standing. ;-)

Just a wild guess:

- For route finding, a (multiply) weighted, directed graph representing the
roads and junctions (pick your favorite data structure serving this purpose;
make sure it's space efficient, so probably no 2d array adjacency matrix), with
the weights representing the associated time, distance and other "costs"

- For navigation and display, some type of spline curve attached to each edge of
the graph, representing the road in real world

- For precise directions at junctions, additional data attached to each node
detailing the precise junction geometry, lane designation etc.

- For address finding, additional data attached to each edge indicating the
first and last house number, as well as lookup tables linking city names to
streets, and streets to street sections (= graph edges)

- For places of interest, a list of places with their respective co-ordinates
and reference to the graph edge they are adjacent to, with a spatial
sub-division tree for efficient look-up of nearby POIs.

That should get you started for typical applications.

Post a reply to this message

clipka wrote:
> Invisible <voi### [at] devnull> wrote:
>>> This approach often may *not* give you the optimal route. However, given that it
>>> will only very rarely be significantly worse than the optimal one, it is
>>> definitely good enough.
>> Depends on your definition of "optimal". (E.g., total distance, verses
>> estimated travel time, any tolls that have to be paid for certain
>> routes, traffic volume, etc.)
> 
> Well, it actually depends on *your* definition of "optimal": You as the user
> assign a certain abstract "cost" to any of these parameters.

That's kind of my point, yes. :-)

> So from this perspective, the "optimum" is always well-defined: Lowest abstract
> "cost". But even to these standards, the algorithm will only very seldom pick
> the optimal route - because it would by any means not be efficient to do so.
> After all, it doesn't make much sense to have your navigator spend 3 days
> finding the optimal route, if within 30 seconds it can come up with one that is
> at most 5 minutes longer :P

Indeed. And if I make a wrong turn somewhere, it would be far more 
"optimal" for the device to quickly find a new route before I become 
*hopelessly* lost in a one-way system or something.

I'm looking at you, NAVMAN! >:-[

Post a reply to this message