Hello Everyone,
I just got back home from a 600 mile trip and on the way I kept looking at my GPS and got a bit annoyed. When you enter your destination the GPS gives you a time remaining for your trip. I would assume that because the GPS can measure the speed at which you a traveling that the arrival time would be very accurate. However just to see I went about 30 miles at the posted speed limit of 65 miles an hour. Then I increased my speed to about 85 mph for about another 30 minutes. It didn’t seem that the GPS ever adjusted the arrival time to coincide with the increase in speed.
Yes, I do know that a short increase in speed isn’t going to affect the time, but I would figure that if you increase your speed by 20 mph for a 1/2 hour that it would recalculate the time remaining based on your current speed. Maybe I am thinking that the proccessing power of your average Tom Tom is greater that it is, but it doesn’t seem like to would be that difficult. I do know that the gadget will eventually re-adjust the arrival time as you near your destination.
Anyways, I guess my real question is, does the GPS approximate your arrival time based on a pre-programed speed for each kind of road and just guesses the arrival time based on that or does it actually base the est time on your current speed?
I apologize if my question is a bit confusing, I am tired after the long trip.
WAG:
It starts off by using rough approximation based on your distance from your destination, and perhaps, at first (and like Google Map’s directions) establishes an ETA based off the mph data for your particular course.
Then, once you get close enough where your varying velocity doesn’t make much difference, and the extra computing necessary will be short lived, it then switches over to calculating your speed by checking your location over time, at close enough intervals to narrow in on your arrival to the minute.
I’ve thought about this as well. What’s the point in constantly computing your ETA over sufficiently long trips, when the variable of driving at +/- 20 mph of the speed limit, over the course of several hours, would be giving you ever shifting and inaccurate estimates?
I don’t think it ever considers how fast you’re actually driving, strictly the distance remaining on the planned route (and the fixed nominal speeds for each segment of that). Consider, you can stop, and the ETA doesn’t rapidly climb toward infinity; it just pushes out one more minute for each minute you’re parked. If you drive faster for an extended period, the ETA will indeed creep in sooner, but it’s not because you’re going faster, it’s because it’s constantly being recalculated against a shrinking distance.
It wouldn’t make any sense to base the calculation on your current speed. If you’re driving 1500 miles across the country, but need to go a while on residential city streets to reach the freeway on-ramp, you wouldn’t want your navigation system assuming that you’ll be making the whole trip at 25 MPH.
what kind of gps are you using? I mean are you using your cell phone or an actual gps unit? if acutal gps partly it depends on how many satellites your unit can “see”. a true gps unit figures your location, movement and speed based on the time it takes the signal to travel between your unit and the satellites. The more satellites your unit can see above the horizon, the more accurate your reading will be up to the limits set by the DoD.
spark240 has it. The good quality systems have data bases including speed limits for all the roads, and often some empirical speed estimates of what is possible. Your ETA is back calculated out from this.
The accuracy or your position isn’t going to be much of an an issue. You need four satellites for a basic fix, with additional satellites providing increments in accuracy in the face of sub-optimal geometries of satellites. (For instance if they are all in a line in the sky, accuracy in the direction of the line is very high, and awful at right angles. This is more an issue when the terrain blots out parts of the sky than limitations of the receivers. Most can find the satellites they need so long as they are visible.) All GPS units work in the same manner, those in cell phones are one chip wonders that are not as able (fewer channels, poorer noise specs, slower processing) as the chipsets found in higher spec dedicated units, but they all work the same way. This usually manifests itself as longer times to get a fix, especially when cold starting.
Instantaneous speed for GPS units is typically based upon doppler shift of the received signal, whilst more accurate long term speed averages are calculated from location fixes.
Most phones use the same system. It’s possible to do an approximation using knowledge of cell phone tower locations, and some phones will do that…but in general, your phone will use the same satellites, in the same way, that a dedicated GPS unit will.
-D/a
I’m a programmer. Basically, a simple way to model a road map is with a weighted graph. Intersections are treated as points, and the line segment between the points is “weighted” with an estimate of the real-life amount of time it would take to drive between the points.
To determine the best way to get from arbitrary point A to arbitrary point B, you search the graph. You find the shortest path between A and B and the “weight” is your time (generally, it is the “cost”, which here, is measured in terms of time). If there isn’t enough time (based on clock cycles and memory available) then you can search only parts of a graph and come up with a best-available estimate.
This is a classic CS problem.
This model can be used for other navigational modeling activities as well - you can model sea navigation, with the points being harbors and the segments being the shipping lanes, or model air travel, with the points being airports and the segments representing existing flights, so e.g. you can model a map of the world’s airports and flights and determine the cheapest way from Brasilia to Vladivostok (e.g. should you pick Brasilia->San Juan->New York->Berlin->Moscow->Vladivostok or Brasilia->Mexico City->Los Angeles->Honolulu->Tokyo->Vladivostok?). I did something similar in school myself.
You can also weight by raw distance, or by estimated fuel consumption if those are more important, e.g. if you are mapping a mountainous area and want to avoid driving up to the top of a mountain if you can, not because it takes a lot of time, but because it wastes fuel. You can weight by monetary cost, e.g. saying that a flight from NY to Chicago costs x dollars, and a flight from NY to Toronto costs y dollars.
My satnav (a Garmin Nuvi) certainly recalculates the ETA “on the fly”. In my experience it usually starts off with a rather conservative estimate, such that on clear roads you can usually shave off 7 or 8 minutes per hour. It’s quite satisfying.
If I plug in the traffic data receiver, however, the ETA tends to be rather unreliable as it will suddenly add on 90 minutes to the journey time because of a traffic jam on the route, that usually turns out not to exist…
My TomTom recalculates the time on the fly, as well. I like to look at the time estimate and guess what time I will actually reach my destination.
My Garmin seems a bit problematic on the ETA issue. When I’m stuck in traffic, it will often neglect to update the arrival time, even after the point where it would take an actual violation of the laws of physics to get there by the indicated time. So I don’t really understand what algorithm they could be using.
In CS, what do you call this type of problem? Do you know if there are any open toolkits/code snippets/etc that specifically address it?
It uses posted speed limits on the roads that you will be traveling on. Easy peasy. It expects that you will go those limits. Simple math. That’s how it does it.
Really, please, people, I’ve been in GIS before it was called GIS (it was AM\FM [Automated Mapping and Facilities Management]). The data in the system is pretty damn good. It stuns me but it can’t always account for the guy with a flat tire that blocks traffic for a bit.
Me too. I spend a couple of hours shaving 15 minutes off of my arrival time and then the wife or daughter needs to stop to use the restroom. Even though I don’t need to be there at any particular time, I still get upset because her piss break caused my two hard hours of driving to be for naught. 
That’s not really the point. The point is that stopping for an extended period, for whatever reason, does not seem to update the ETA in a reasonable fashion.
So maybe the question is, how long does your speed need to be zero, or very near it, for the ETA to take that into account? Even if it pays no attention to instantaneous speed. surely it should know that if the trip still has a hundred mile left, it’s not going to be done in an hour – or whatever. If it doesn’t make a reasonable ETA based on remaining distance and a reasonable speed estimate, it is failing.
Bad time to raise the issue. The recent solar flare may be causing problems with GPS.
I have had four GPS units over the last 10 years. The three Garmins all estimate your arrival time based on the speed limits of the roads you will be on. The frustrating part is that it does not make any allowance for time at red lights or stop signs so it is overly optimistic about travel times on local roads. This is worst downtown when you have a red light every couple of blocks or so. Therefore it occasionally routes me onto secondary roads when a slightly longer highway route is much faster.
It does not assume you will travel the speed limit; it seems to assume you will be somewhat over it. For trips that are mostly highway (not in rush hour), its estimates are a dead-on match for my driving style and I find that the arrival time doesn’t vary by more than +/- 1 minute over the course of a trip that might last over an hour.
If you are slowed by heavy traffic at 40 in a 55 for miles at a time, it doesn’t notice or care. It assumes you are just about to resume driving at (or above) the speed limit.
The GPS built into my 2009 Toyota seems to estimate the same way but is somewhat more conservative, and I consistently beat the estimate by 5-10%. I don’t know who manufactures it.
Just doing a little quick math, you only increased your speed 30% (from 65 to 85MPH) and for only about 5% of the whole journey (half an hour from a total of say maybe nine hours?) Which only makes for an overall increase of 1.5%. Which, out of nine hours, would be about eight minutes.
Besides the fact that I’m sure I’ve made all kinds of errors in that preceding paragraph, the reason I think that your GPS still didn’t show any increase is because I think that GPS units tend to smooth out small perturbations in their ETAs. As others have said they rely primarily on set values (road speed limits) to compute an ETA and it will only start to vary with a *major *anomaly (like a very large & unrelenting speed change).
In fact I’ve seen this. On a 5½ hour trip as I drove consistently above the speed limit on an interstate (about 78-80MPH in a 65) I did see my ETA start to get a little closer. But only after steadily traveling at the increased speed for more than an hour and even then it only got a minute or two earlier.
Ma’ puzzler hurts…
I can’t address the Garmins, but I can provide some info on the VDO systems (as found in some previous-generation BMWs, for example).
The map data disc in the navigation system has information about the speed limits on roads, as well as things like the average speed, turn restrictions / one way, etc. That data may be out of date (as, for example, when Indiana went to a 70MPH limit, or when the PA Turnpike added variable speed limits west of Sideling Hill). By the way, this is why the VDO system displays some minor roads as gray instead of black, and shows “Correct guidance not possible” on the screen and says “You are not on a digitized road” if it is currently giving directions. You look at the map and say “Stupid box! You have a picture of the road on the screen! What is your problem?!?!” The problem is that all it has is a picture of a road, just like it has pictures of railroad tracks, rivers, etc. It doesn’t have data that ties that road into its navigation database.
The navigation software (which isn’t on the disc, but is in flash memory in the navigation system) also takes into account things such as penalizing local streets due to low speed limits, stop signs, traffic lights, and so on.
All of this comes together to compute a (hopefully) somewhat accurate estimated time of arrival (ETA). But the data the navigation system works with was out-of-date when it was first issued (for example, the BMW “2009.1” disc uses map information dated January 2008; the disc wasn’t mastered until August 2008; and the final product wasn’t available at dealers until October 2008), and got further out-of-date in the subsequent year. Things like Google Maps and TomTom have access to frequent updates, from their map data providers and/or from users reporting errors.
For really screwball routing, combine either a very old map with new software, or vice versa. It will come up with things like sending you from Newark, NJ to Hartford, CT by zigzagging across every block in Manhattan.
Anyway, whenever any changes were made to the way the VDO system worked to make some set of vocal users happy, another set would start complaining about what changed. As an example, people complained that the “official” name of the road wasn’t being displayed, instead the common name was displayed. Well, in Passaic County, NJ it seems like a quarter of the roads are County Road 511. A map that displays this isn’t particularly useful, so the change was reverted.
There are a bunch of things that could have been improved. Off the top of my head, taking time zones into account for long drives; storing info when a user always deviated from a route in the same manner and using that for planning future routes; etc. But because of the huge outcry whenever anything was changed, the software stagnated and hasn’t seen an update in years. New maps are available, but they can only provide whatever data the software is willing to use.