O.T. What kind of math?



#5

A car GPS navigator has coordinates for our location and our destination. It has spatial map of streets. How does it find an optimal path so quickly? If we blunder or choose not to follow the suggested direction it plans a new route before the next corner.
It was a gift, a MIO 300. It has been used for a year and once it sent us in a wrong direction, we knew better and went our way, It quickly corrected. It has a 400 Mhz processor. What is it doing? Sam


#6

GRAPH analysis, most certainly. It probably uses a modified Dijkstra´s algorithm, by suppressing unavailable path (congestion, void access, etc.) anytime it happens and giving the best route in no time.

Cheers.

Luiz (Brazil)

(In time: are you the same Sam who sent me some very interesting texts, about three years ago? If so, please, let´s get in contact again. I had been 'off line' for some reasons, health-related mostly, but it seems to me I'm back, now. e-mail: lc_vieira (at) quantica [.] com dot br )


Edited: 27 Dec 2009, 4:30 a.m.

#7

Sam,

a lot depends on the accuracy of the map data itself. I was in Australia last year, just couldn't find a restaurant in Melbourne that was supposed to be listed in the map. Turned out that the restaurant had closed ;-)

hpnut in Malaysia

#8

Hi,

Yes, the GPS has the latitude and longitude coordinates of your position acquired nearly every seconds and the latitude/longitude coordinates of your destination.

The road navigation GPS also have now on board map with the most detail of roads, intersections and a large bunch of points of interest. These maps are vectorial maps since they are draw using latitude/longitude coordinate, length and heading of road leg, as well as coordinate of intersection, town, point of interest, also contain street name, the road nomenclature, road categories and same other data concerning one-way roads and other circulation constrains.

This makes a lot of digital data, making that the full country maps are weighting several Go now. All this stuff is present in the map to allow precise drawing in the very probable case you decide to zoom in. But all these data are not used to compute a route.

One may be surprise that route computation is so quick at initial full trip computation as well as on road computation, as soon as the driver leave the planned route. Even with low speed processor (which generally share time with several internal functions concerning GPS signal processing, display and other user interface touch screen, etc… a GPS with 400 Mhz processor seems to be a power full one) and huge among of data in the vetorial map. These amazing little boxes still use a fraction of second to compute or re-compute the route !

The algorithm’s performance and the math involved there are of secondary importance. The high computation speed is mainly due to pre-compute link tables stored in the maps, which make that the GPS have not to carry the full process of a complete Drijska’s method, not to run all the heuristic, nor to evaluate a mountain of combinations. The GPS is mainly using a pre-computed look-up table that summarizes and regroups directions of the map at the appropriate scale.

This make that the computation of a trip following main roads or highways even on a long distance is much more fast than the computation of a short trip of a few tens of miles in a map’s region were no pre-computed table exist (or only incompletely).

The same, when the driver leave the planned route. The GPS rapidly compute a new partial route to the next node present in the already scanned pre-computed links table, never (or rarely) the GPS have to compute a full new route from crash. Sometime, depending of the region where you are travelling in, the GPS propose strange route on the fly with illogic or unnecessary detours.

Of course, the exact process vary from one model or brand of GPS. As well, the efficiency greatly relies of the data organization into the map and how well is all the system organizes altogether. For sure, the pre-compute links table are build up during map compilation using the Dijstra method or one dedicated method deduce from it.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Need help understanding math.... cyrille de Brébisson 9 1,302 12-13-2013, 02:23 AM
Last Post: Didier Lachieze
  OT: a math competition site Pier Aiello 0 353 09-16-2013, 06:03 AM
Last Post: Pier Aiello
  Simple Math Question Namir 2 504 08-09-2013, 06:13 PM
Last Post: Eddie W. Shore
  Elliptic integrals of 1st and 2nd kind calculated by complex agm Gjermund Skailand 3 558 06-29-2013, 03:39 PM
Last Post: Gjermund Skailand
  Cool math clock Bruce Bergman 28 2,552 04-10-2013, 03:13 AM
Last Post: Siegfried (Austria)
  Math Challenge I could not solve Meindert Kuipers 22 2,114 01-05-2013, 04:43 PM
Last Post: Thomas Klemm
  Math Question Namir 0 322 11-06-2012, 07:43 AM
Last Post: Namir
  Survey for Special Math Problem Namir 7 891 06-03-2012, 09:46 PM
Last Post: Namir
  HP41C: Factorial (kind of) in MCODE Frido Bohn 7 878 05-26-2012, 09:18 AM
Last Post: Frido Bohn
  math question Don Shepherd 22 1,902 04-25-2012, 11:38 PM
Last Post: Don Shepherd

Forum Jump: