Navigation Logic
#21
Contributors
Join Date: Oct 2004
Location: Voorhees, NJ
Posts: 428
Likes: 0
Received 0 Likes
on
0 Posts
Originally Posted by Rudy' date='Aug 21 2005, 09:17 PM
Now if you're talking about dynamic re-routing due to current traffic conditions, that isn't currently available on our cars...
[snapback]161833[/snapback]
Acura was supposedly getting ready to release this. I remember seeing a disabled menu item on an earlier CIP release, but there is nothing like that now.
#22
Super Moderator
Join Date: Mar 2004
Location: Pittsburgh, PA USA
Posts: 17,310
Likes: 0
Received 2 Likes
on
2 Posts
My Ride: G30 M550i
Model Year: 2018
I think Acura is releasing it in conjunction with XM satellite radio's real-time data feed of traffic information.
I can only imagine that BMW will find a means to do something similar in the future for the US cars...
I can only imagine that BMW will find a means to do something similar in the future for the US cars...
#23
Originally Posted by wnrussell' date='Aug 21 2005, 10:06 PM
[quote name='joneill' date='Aug 21 2005, 09:01 PM']Re-routing feature works very well in my 530xi.
[snapback]161827[/snapback]
[snapback]161829[/snapback]
[/quote]This feature is not available for NA autos at this time.
#24
This info is several years old but some might find it interesting on how routes are calculated.
-------------------- snip --------------------
The basic principles have changed little since Dijkstra proposed his algorithm for this
problem.
A Google search on Dijkstra algorithm will turn up numerous references.
First the data. First we have a node corresponding to each junction and an
arc (between a pair of nodes) corresponding to each road. Later we will
extend this (hence the introduction of new names). Each node has a list of
the adjacent arcs --- that is the ways in which we can leave the node to
reach another node. Stored with each arc is its length and the time taken
to travel along it (this may be implicit --- store a type and infer the
time from the length and a table of speeds).
Now suppose we want the fastest route from node A to node B.
1. Initialise the time taken to reach every node to infinite, except for
node A which (obviously) is zero.
2. Add node A to a set we will call pending
3. Loop: Take the node X from pending with the minimum associated
time.
If the pending set was empty, node B is unreachable.
If the selected node is B, then we are done.
4. For each arc attached to X (the adjacency list), compare the time to
reach X + time traversing the arc with the existing time associated
with the other end of the arc. If the new value is better than the old,
replace the old value. If the old value was infinite then add the node to
the pending set.
5. continue with step 3.
At the end we have either determined that there is no possible route, or
we have the best possible time. To determine the route we can either
record some extra information during the algorithm every time we find a
better way to reach a node (just record the node it is reached from), or
we can work backwards from the end.
There are a variety of choices for the structure used to maintain the
pending set; it would be very slow if you checked every element each
time you wanted to select the one with the smallest time.
One way roads are represented by an arc which listed as adjacent only to
the node from which you can start (whereas a two way road is represented
by an arc which adjacent to both of its nodes). Alternatively you can use
arcs which are always only adjacent to one node (i.e. one way) and simply
use two of them for every two way road.
To represent banned turns, you need more than one node corresponding to
each junction that has such a restriction. (This is more easily explained
with a diagram than with text).
You may notice that the algorithm makes no use of the coordinates of the
junctions (nodes). In the case of finding a single A-B path it is possible
to make savings by using that information.
So much for the basics. It gets more exciting when you consider roads
where the speed depends on the time of day or with London lorry bans
(can't use certain roads at night, except ...).
The Navtech data for Great Britain (Northern Ireland is left out by almost
everyone), has about 1 million junctions and 2 million roads (where some
of those junctions are 'fake' as with motorway crossings).
-------------------- snip --------------------
-------------------- snip --------------------
The basic principles have changed little since Dijkstra proposed his algorithm for this
problem.
A Google search on Dijkstra algorithm will turn up numerous references.
First the data. First we have a node corresponding to each junction and an
arc (between a pair of nodes) corresponding to each road. Later we will
extend this (hence the introduction of new names). Each node has a list of
the adjacent arcs --- that is the ways in which we can leave the node to
reach another node. Stored with each arc is its length and the time taken
to travel along it (this may be implicit --- store a type and infer the
time from the length and a table of speeds).
Now suppose we want the fastest route from node A to node B.
1. Initialise the time taken to reach every node to infinite, except for
node A which (obviously) is zero.
2. Add node A to a set we will call pending
3. Loop: Take the node X from pending with the minimum associated
time.
If the pending set was empty, node B is unreachable.
If the selected node is B, then we are done.
4. For each arc attached to X (the adjacency list), compare the time to
reach X + time traversing the arc with the existing time associated
with the other end of the arc. If the new value is better than the old,
replace the old value. If the old value was infinite then add the node to
the pending set.
5. continue with step 3.
At the end we have either determined that there is no possible route, or
we have the best possible time. To determine the route we can either
record some extra information during the algorithm every time we find a
better way to reach a node (just record the node it is reached from), or
we can work backwards from the end.
There are a variety of choices for the structure used to maintain the
pending set; it would be very slow if you checked every element each
time you wanted to select the one with the smallest time.
One way roads are represented by an arc which listed as adjacent only to
the node from which you can start (whereas a two way road is represented
by an arc which adjacent to both of its nodes). Alternatively you can use
arcs which are always only adjacent to one node (i.e. one way) and simply
use two of them for every two way road.
To represent banned turns, you need more than one node corresponding to
each junction that has such a restriction. (This is more easily explained
with a diagram than with text).
You may notice that the algorithm makes no use of the coordinates of the
junctions (nodes). In the case of finding a single A-B path it is possible
to make savings by using that information.
So much for the basics. It gets more exciting when you consider roads
where the speed depends on the time of day or with London lorry bans
(can't use certain roads at night, except ...).
The Navtech data for Great Britain (Northern Ireland is left out by almost
everyone), has about 1 million junctions and 2 million roads (where some
of those junctions are 'fake' as with motorway crossings).
-------------------- snip --------------------
#25
Contributors
Join Date: Aug 2005
Location: L.A., California
Posts: 1,016
Likes: 0
Received 1 Like
on
1 Post
My Ride: 2013 535i (White with Oyster Interior. Premium Package, Navigation, Technology Pacakge, Park Distance Control, and Rear View Camera)
NAV can't be perfect. It's a computer, not a human. Re-routing on BMW is better than Acura.
Thread
Thread Starter
Forum
Replies
Last Post
bestofthebest
Complete Car Sales
5
01-05-2016 07:47 PM