Idea for solving GPS jittering and outages (also: tunnel extrapolation)

Issue migrated from trac ticket # 1232

component: core | priority: major

2014-08-10 10:17:45: thomas.maus@gmx.de created the issue

Perhaps we could make good use of the demo vehicle: With proper visual cues it could be used as a fall-back when the GPS signal is lost, as well as a guidance to prevent jittering of the vehicle to nearby streets when the GPS signal is imprecise.

Given a demo vehicle capable of adapting its speed to the projected speed of the route segment, the following solution is proposed:

A (virtual/invisible) demo vehicle continuously follows the route. Essentially it is identical to the real vehicle until the real vehicle looses the route or GPS position. From that moment the demo vehicle takes over, and continues to run the designated route with the last measured speed¹ of the real vehicle, accelerating/decelerating as the the designated travel and max speeds of new route segments suggest.²

This demo vehicle serves as a useful temporary substitute for GPS degradation and imprecisions in tunnels, under bridges, within mountain or city chasms, dense road grids, ... and should help us solve various problems:

Whenever the real vehicle leaves the designated route, or needs to be snapped, or looses GPS position altogether, it is snapped to the simulated vehicle's position and bearing, if within a certain radius around the simulated vehicle.³

A few details:

To indicate the simulation and the accumulating error margin, the simulated vehicle leaves a colored "snail trail" and is represented by center mark and a growing circle (The circle represents the imprecision because of possible speed changes up to some extent, i.e. the current snap radius.)

After a few seconds (first threshold: e.g. 10 seconds) the simulation state is audibly signaled to the user (e.g. "GPS signal degradation" or a simple jingle).

Routing guidance is continued. After the first threshold together with some acoustic indication of the simulation (especially distances should probably not be given anymore).

Of course this simulation can not run forever. There is a second threshold (time and/or radius), when we either:

have to stop the simulation (and announce this).

need some simple interaction with the user along the lines of "Tap on the screen when you have taken the announced turn". The simulated vehicle will wait just before the next turn, to enable the user to repeatedly look at the navigation maneuver and its surroundings.

IMHO this proposal solves elegantly the following problems and tickets with a single mechanism:

GPS outages [http://trac.navit-project.org/ticket/932]

tunnel extrapolation [http://trac.navit-project.org/ticket/901]

GPS jitter and preferential snapping to current route to avoid annoying false maneuvers:

[http://trac.navit-project.org/ticket/931]

[http://trac.navit-project.org/ticket/1093]

[¹] To avoid erratic behavior I suggest an exponential moving average with a half-value time of a few seconds (eventually, weighted with the quality of the reading (HDOP, distance moved since last reading), this smoothing could be applied to the heading too) [²] If there is no route to follow, the demo vehicle does the natural thing: sit without moving or turning where the real vehicle left it of ... [³] The radius is calculated from the GPS HDOP and the time since the last valid GPS reading.

2014-08-10 11:12:26: bart.cockheyt@gmail.com commented

You have my vote...

2014-08-10 12:35:16: openid@bokomoko.de commented

I think this is a great idea.

Since most smartphones and tablets do have an accelerometer and a gyroscope, i.e. an Inertial Measurement Unit (IMU), you may want to use this information to detect turns etc. or even implement a Kalman filter (maybe in a second step).

See also https://en.wikipedia.org/wiki/GPS/INS

2014-08-11 01:44:14: spielraum@web.de commented

the idea of Ticket 932 was to be informed if gps signal is lost. I like the general solution proposed in this ticket but would still want to have some announcement if the signal is lost and I am now relying on some virtual vehicle. So I would keep ticket 932 open for now.

2014-08-11 01:47:38: spielraum@web.de commented

ticket 931 is only for the first fix (see comment 10), whereas this solution is great once you have had a proper fix and then start to deviate from a route.

2014-08-11 08:35:12: thomas.maus@gmx.de commented

Replying to [comment:2 rainer dorsch]:

I think this is a great idea.

Thanks.

Since most smartphones and tablets do have an accelerometer and a gyroscope, i.e. an Inertial Measurement Unit (IMU), you may want to use this information to detect turns etc. or even implement a Kalman filter (maybe in a second step).

An excellent suggestion! (Alas I neither development experience nor environment for these devices, so somebody would need to help with this!)

2014-08-11 10:52:02: thomas.maus@gmx.de commented

The approach may contribute to the solution of other tickets too (or provide a more consistent implementation and user experience)¹:

The "route guard" (see [http://wiki.navit-project.org/index.php/OSD#route_guard] and [http://trac.navit-project.org/ticket/905]) is an useful feature. It could be easily extended to calculated routes (navit has calculated IMO useful routes for hiking in the Alps): If the real vehicle leaves² the "snap radius" of the simulated vehicle, give an alarm (and stop after the first threshold is crossed). The snap radius and thresholds take into account speed and direction of recent movement as well as GPS quality and thus should avoid false alarms because of GPS jitter ... Slightly of topic this could be extended along the following lines -- for discussion:

a loaded track actually could be handled like a proper route or a route skeleton (even with automatic recalculations, see below)

a calculated route could be automatically saved as track to improve crash recovery: on restart not only the recent destination but also the calculated route could be retrieved

of course a pure track is not sufficient for real routing: we might have moved of the track, etc. But we can concentrate computation of destination distances to a corridor around the given or recovered track -- this should speed up routing calculations significantly ...

Several people complained about re-routing behavior. Because of the Dijkstra algorithm this actually should not be a computational problem, as the area should already be flooded with distance metrics. So I assume they main complaint is actually when the route is redrawn. The "old route" actually constitutes a valuable orientation aid, as long as you do not really intend a deviation. As long as devices lack a mind-reading interface or telepathic networking we have to resort to guesstimates (or user interaction, not very practical for routing devices). If the real vehicle leaves the dynamic snap radius of the simulated device you get a "route guard" warning, giving you an opportunity to return to the still displayed "old" route. After crossing the first threshold we assume you actually want to deviate from the route, and display a new alternative route.

This leads to the following consistent behavior:

GPS position is lost -> simulation mode starts (including adjusting real vehicle position from INS (gyros + acceleration sensors) readings)

as long as the positional uncertainty (snap radius) stays below threshold 1, i.e. for a few seconds or meters, only visual cues are given to avoid flooding the user with GPS outage announcements

after threshold 1 is exceeded audible and visual cues are given

after threshold 2 is exceeded audible and visual alarms (and eventually haptic alarms) are given, and simulation either stops or goes to some interactive emergency mode (e.g. in tunnels several km long)

GPS position leaves route

within snap radius -> vehicle is snapped to position of simulated vehicle

crossing snap radius ->

real vehicle is drawn at GPS position (visible cue)

simulated vehicle follows old route, both are still displayed

you get an audible warning, that you are leaving the route

alternative routing calculations start

after threshold 1 is exceeded ->

audible alarm that alternative route will be choosen

simulated vehicle is snapped to real vehicle position

alternatives:

old route is substituted as soon as we have a new route (finding a new route might prove impossible: consider traveling on a new street not yet in the map, or the only hiking track washed away and the user climbs around ... IMHO then the old route should still be displayed as it still gives valuable guidance)

old route and new route are displayed in parallel -- here some questions remain to discussed:

unconditional or until some threshold (time/distance) is exceeded?

how to handle a deviation form the "new route" -- drop the "original old route" or the "new old route" or display more than two routes?

use different markup for old and new route?

Any logical gaps? Any use cases not yet covered? Any further suggestions?

[¹] I'm walking thru open tickets to get an impression of the state of navit, and especially the open construction sites. IMHO it is beneficial from the aspects of user experience, configuration complexity, and SW maintenance to solve multiple problems with a minimal set of central mechanisms -- that is the motivation of my suggestions ... [²] "Leave" means has a valid GPS position, "Lost" means no usable GPS reading. A vehicle "lost" would instead trigger simulation ...

2014-08-12 08:09:48: @mvglasow commented

Bad news first: it wouldn't help with #931, as #931 is about obtaining the first fix (see comments 9 and 10).

Now for the good news: this would be great for GPS outages (#932) and tunnel extrapolation (#901).

As for the visual cue: Tomtom had a good UX for this – upon losing the GPS signal, the screen would turn black and white, and color would get restored when GPS was back.

We could even (to am extent) use this feature without a route, as long as there is only one road on which the vehicle can continue. This is the case when there are no intersections, or with intersections that fulfill certain criteria: Each intersection on the route has an "entry" (the edge of the graph over which the vehicle approaches the intersection) and potentially multiple "exits" (on which the vehicle continues its intersection). We can use restrictions (oneway, turn, vehicle) to rule out some of the connecting ways as exits, and assume that the entry is never an exit. If this leaves us with just one potential exit, we can calculate a pseudo-route up to the next intersection with more than one possible exit.

With #1093 it might somewhat improve things. I have seen similar behavior in commercial sat-nav systems – here it appeared to be some sort of "snap to route".

However, there may be cases in which the vehicle actually does leave the route – thus we need to avoid overcompensating and sticking to a route that the vehicle has left long since. Here I'd go for the modified snap logic I had proposed in #1093: when the vehicle is somewhere between two roads, give the route a greater weight than other nearby roads. (Maybe even make that weight dynamic: high at the beginning and decreasing if the position continues to be far away from the route).

As for inertial navigation, I have experimented with that myself. I didn't get very far because my approach was about calculating a GPS trace by means of inertial navigation, but the Navit use case might be easier: Instead of calculating a position, we can just watch for events such as "90° left turn detected" and find the nearest spot on the map where there is the corresponding kind of turn in the road. The main challenge is detecting device orientation within the vehicle (including changes). Another is that errors accumulate, but that could be mitigated through map data.

2014-08-12 11:55:41: thomas.maus@gmx.de commented

Replying to [comment:8 http://wiki.navit-project.org/index.php/user:mvglasow (2)]:

Bad news first: it wouldn't help with #931, as #931 is about obtaining the first fix (see comments 9 and 10).

I only referred to this part of #931:

The problem:

If you are eg. on a landline right next to a highway and the gps signal jumps in position navit is constantly recalculating the route. If you have a low powered cpu as in the neo freerunner your system crashes and (android-froyo) freezes...

which I obviously perceived wrong (because actually I would not see any reason for continously restarting route calculation as it calculation starts from the constant destination and is flooding the area anyhow ...)

Now for the good news: this would be great for GPS outages (#932) and tunnel extrapolation (#901).

:-)

As for the visual cue: Tomtom had a good UX for this – upon losing the GPS signal, the screen would turn black and white, and color would get restored when GPS was back.

Personally I would hate to loose the valuable color-coded map information, just when things get complicated and I need it most to substitute lack of GPS positioning by good, old-fashioned map reading.

Perhaps some kind of overlay could be used, either

a alpha-blended overlay indicating the snap area (i.e. the area of positional uncertainty), or

a alpha-blended overlay outside the snap area (i.e. the snap area proper has a completely undisturbed display), e.g. a dark ring ending in a red circle indicating the threshold 1

We could even (to am extent) use this feature without a route, as long as there is only one road on which the vehicle can continue. This is the case when there are no intersections, or with intersections that fulfill certain criteria: Each intersection on the route has an "entry" (the edge of the graph over which the vehicle approaches the intersection) and potentially multiple "exits" (on which the vehicle continues its intersection). We can use restrictions (oneway, turn, vehicle) to rule out some of the connecting ways as exits, and assume that the entry is never an exit. If this leaves us with just one potential exit, we can calculate a pseudo-route up to the next intersection with more than one possible exit.

That is an interesting idea and definitely better than the simulated device just stopping dead in its tracks. My only fear is that we need some kind of physics model to simulate proper acceleration and, more difficult, deceleration before turns. Then, together with INS, this could substitute GPS perhaps for some while ...

Such a physics model is difficult, but actually would allow very interesting things, e.g.

while driving with valid GPS signals advice to

slow down, whenever the real vehicle is driving faster than the simulation (by some absolute and/or relative threshold)

more difficult: giving reasons (the simulation typically should have some possible speed range chosen for some reason), the advice is given if the speed range is exceeded e.g.

before sharp turns: "slow down, sharp turn in X m", X depending on current speed (reaction time), the necessary deceleration and some safety margin

prudence warnings "slow down, school/kindergarden ahead"

speed limits "slow down, speed limit X km/h"

accident hotspots "slow down, accident hotspot ahead"

shift gears before climbs or descents (depends on both height data and a detailed vehicle model), which could be especially nice for bike or truck navigation

when routing calculate more precise route metrics

actual travel speeds, imagine

a route winding through villages with many tight turns

twisty coastal roads, having speed limits not imposed by human but physic laws ...

red-lights

implement metrics for economic routing (needing detailed vehicle model + height data)

fuel or electric power consumption

exhaustion for bike, hikers, equestrians

(But probably not in version 0.6.0 ;-)

With #1093 it might somewhat improve things. I have seen similar behavior in commercial sat-nav systems – here it appeared to be some sort of "snap to route".

However, there may be cases in which the vehicle actually does leave the route – thus we need to avoid overcompensating and sticking to a route that the vehicle has left long since. Here I'd go for the modified snap logic I had proposed in #1093: when the vehicle is somewhere between two roads, give the route a greater weight than other nearby roads. (Maybe even make that weight dynamic: high at the beginning and decreasing if the position continues to be far away from the route).

I recently drove with navit through an Austrian village (Vils), which had an incredibly tight road network. It was situated between high mountains, so the GPS HDOP was bad (15-20). navit was happily jumping the "vehicle" all over the place, even positioning it several streets away. This experience is the background of my suggestion (and I'm convinced your approach would have failed in that environment).

Let me lay out the approach in more detail:

The snap radius is computed¹ as HDOP × DevicePrecision DevicePrecision is a configurable parameter, 6m would be a good consumer device ... One should add a small safety margin to the DevicePrecision to avoid flapping, let's say we set DevicePrecision=7m

In the Austrian village the snap radius would approximately have been 20 × 7m = 140m (with 120m actually expected error of GPS readings!)

This would have prevented navit from jumping around, but intended route deviations would only be effective (i.e. navit considers alternative routes and displays the new GPS position separately from the simulated vehicle) if the distance is at least 140m. Given the GPS signal quality I would have considered that reasonable behavior ...

Now take a similar situation with an acceptable GPS quality, say HDOP of 5. The snap radius then would be 35m -- in this village the next, occassionally even the second next parallel street. If I deviate by purpose I must have some plan or some knowledge from the map or follow an explicit deviation sign. These should carry me for at least 100m and thus give navit time to accept the fact and derive an alternative route, IMHO. Barring some mind-reading interface of navit this seems still very reasonable for me.

Now assume really good GPS quality, say HDOP of 2. The snap radius then is 14m. Actually I know a village, where this might still place you on the wrong street (but I don't know, if a HDOP of 2 actually is achievable there).

But exceeding the snap radius just means displaying the alternative position and considering alternative routes. The original route is only in danger of being substituted when we exceed threshold 1.

I would define Threshold1 = Minimum(Factor × SnapRadius, Threshold1Limit) Reasonable configuration of parameters could be Threshold1 = Minimum(2 × SnapRadius, 200m)

With this configuration the new route would be displayed (and the original route erased if not displayed in parallel until some further threshold) after route deviations of:

200m in that Austrian village (HDOP 20)

70m for HDOP 5

28m for HDOP 2

I see no risk of overcompensation, and personally would even rise DevicePrecision to 8m or 9m for a better safety margin.

What do you think? [[BR]]

As for inertial navigation, I have experimented with that myself. I didn't get very far because my approach was about calculating a GPS trace by means of inertial navigation, but the Navit use case might be easier: Instead of calculating a position, we can just watch for events such as "90° left turn detected" and find the nearest spot on the map where there is the corresponding kind of turn in the road. The main challenge is detecting device orientation within the vehicle (including changes). Another is that errors accumulate, but that could be mitigated through map data.

You are the expert here -- perhaps the Kalman filter mentioned by Rainer Dorsch can calibrate the INS readings via the GPS readings, and thus solve the problem of the unknown device orientation. Of course this calibration is moot, if the device is moved within the vehicle, because it is hold manually or the suction cup drops from the screen ...

[¹] Well, to be more precise: HDOP_of_last_valid_GPS_reading × DevicePrecision + Simulated_Movement_since_last_valid_GPS_reading

If the GPS position leaves the route, we have a current reading and simulated movement is Zero (so the simplification above was OK).

Now have a short look what happens, if GPS position is lost:

Assume we enter a tunnel with 80 km/h, the HDOP of the last GPS reading was 5:

An audible warning will be given when exceeding Threshold1

This happens after 7.5 seconds ((200m - 5×7m)/80 km/h)

simulation will quit or switch to interactive mode when exceeding Threshold2

assuming Threshold2=1km and no INS support, this will happen after 43,5 seconds (actually to early for many tunnels I know, perhaps a configurable time threshold would be better? E.g. without INS support this would cover 4km: Simulation critical if it runs >3 minutes and position uncertainty exceeds Threshhold2?)

Now assume a situation like in the Austrian village: degraded GPS (HDOP 20), low speed (30-50km/h):

Threshold1 is exceeded and warning sounded after 5.4 seconds ((200m - 20×7)/40 km/h)

simulation is considered uncritical for around 77 seconds (or with 3 min time threshold after 1860m)

You are hiking within a dense forest, GPS degrades because of foliage to HDOP 20 before dropping out, your speed is 6 km/h

warning would be sounded after 36 seconds (perhaps somewhat late and suggesting the parameters should be vehicle specific ...)

simulation is considered uncritical for around 8.5 minutes (actually when hiking, user interaction is acceptable and should happen much earlier ... -> parameters should be vehicle specific)

Handling extended simulation will need some consideration and practical experiments ...

aerostitch / testnavit

Idea for solving GPS jittering and outages (also: tunnel extrapolation) #243

2014-08-10 10:17:45: thomas.maus@gmx.de created the issue

2014-08-10 11:12:26: bart.cockheyt@gmail.com commented

2014-08-10 12:35:16: openid@bokomoko.de commented

2014-08-11 01:44:14: spielraum@web.de commented

2014-08-11 01:47:38: spielraum@web.de commented

2014-08-11 08:35:12: thomas.maus@gmx.de commented

2014-08-11 10:52:02: thomas.maus@gmx.de commented

2014-08-12 08:09:48: @mvglasow commented

2014-08-12 11:55:41: thomas.maus@gmx.de commented

2014-08-12 11:55:41: thomas.maus@gmx.de