GPS Dead Reckoning using G Sensor - Any takers?

[sama]

We've all seen it. We're stuck in traffic and the GPS signal starts going crazy! Or we're in a tunnel, or in an urban canyon.

It is possible to navigate using purely a g-sensor. The army does this.

The G Sensor information can be combined with the GPS signal, to clean the GPS signal, and make it more accurate.

Here's a thread about dead reckoning (http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=154870&pageID=1&sk=&date=). Now we just need a brave soul to attempt it!

[sama]

I can help with this. I'm a Java programmer and can help getting the maths required to do it.

[MrDerrickC]

I've noticed something strange with the Tomtom7 software.

I have never used TT7 before or any other TT product, have always used Route66 on my Nokia 6110.

When I was driving in an underground tunnel, there was no signal, but the car icon on TT kept on going? I think it's just taking last average speed and continuing on until it gets a signal lock again.

I thought it was cool.

[foo]

When I was driving in an underground tunnel, there was no signal, but the car icon on TT kept on going? I think it's just taking last average speed and continuing on until it gets a signal lock again.
Yes, that's right. This behavior helps in tunnels, but it's quite annoying, when stopping the car underneath a huge bridge because of a red traffic light.
The GPS signal is lost and the navigation just drives along the route assuming you are still going about the same speed and gives nice advices while you're waiting on the traffic light. Then, when you start driving again the GPS reception comes back and the navigation realizes: "Uhh, I have some mismatch - need to recalc!". This route recalculation can lead to missing navigation advices - so everything has it's pros and cons.

[sama]

this is where dead reckoning would be perfect. the g sensor would say "I'm not moving" and clean the gps signal to tomtom

the way it would be done by software is that an app would read the gps signal, and the g sensor signal, then provide a new serial port for tomtom to use. to that serial port, a cleaned gps signal would be given.

[krakout]

this is where dead reckoning would be perfect. the g sensor would say "I'm not moving" and clean the gps signal to tomtom

the way it would be done by software is that an app would read the gps signal, and the g sensor signal, then provide a new serial port for tomtom to use. to that serial port, a cleaned gps signal would be given.

Of course, the sensor wouldn't say "I'm moving/not moving", but "my situation is steady/changes so and so" :D (just nit-picking!)

Anyway, yes, this would be a great idea, but I really doubt we'll be able to see something useful if the gps software companies do not choose to build it in...

[sama]

We don't need to wait for GPS vendors to do this, it can be done with some s/w.

I would do this myself, but I'm a Java programmer and I'll have to learn .net thinking and syntax to do it, and I honestly have no time! :( The only tricky bit I see is configuring a kalman filter, but not for someone that's familiar with the maths.

http://www.gpsworld.com/gpsworld/data/articlestandard//gpsworld/152005/154870/i6.gif



If you look at the picture above (taken from here, (http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=154870&pageID=6#)which is a detailed discussion of dead reckoning), you can see that the GPS signal stops after Kalman Filter #1, the dead reckoning block shown in blue would be the software filter.


I'm happy to help with the design, and will try my best to get the maths done as psudeo code.

so... one more time :) ... any takers?

[JanDaMan]

ok maybe im missing something but this idea has issues with 2 things IMO

1) the G sensor will not be able to differentiate between travelling at a constant speed and not moving at all, because in both situations the G-force is zero [it can only detect acceleration/deceleration (hence accelerometer nomenclature) or phones orientation]

2) the phone may get all mixed up depending on how you mount the phone in the car (landscape, portrate, flat on dash), and if you move the phone in the car with your hand (eg you receive a call or just need to move it around in the car). lol

the way i can see to avoid problem 1 is if the G-sensor assumes that if you decelerate in a tunnel you are about to stop, if you accelerate you are moving, but the accuracy of this is affected by the hardware and problem 2, Overall i find it hard to see this working too well. *wonders how the army use it*

Defo worth a try tho is someone feels like putting the effort in :)

[sama]

agreed regarding point 2. If you pick up the phone, you're not going to be able to use it, but then, if you're on the phone you won't be able to use the navigation either. Once the phone is stationary again, the filter would work.

Also, it's possible to detect erratic movement and use primarily the gps signal when that happens.

regarding point 1, this is where the combining magic happens. The GPS signal in a constant vector is an indication that all is good with the gps. when it starts to get erratic, we consult to the g-sensor's vector. In essence, both gps and innertia signals would be producing a stream of navigation data, and the filter would make the best of the data.

ps. left/right g is also measurable.

[sama]

think of the g sensor data like a joystick top down view, recorded over time as a stream. that stream is the g-sensor's interpretation of the current path.

the gps signal, is also recorded as a stream.

overlay them, and if they agree, we're good. If one misbehaves, consult the other.

[-=Dennis=-]

You guys forgot another problem. When you're moving into a tunnel or something the device will detect the declining of the angle of the car you're driving. So it will detect that you're actually accelrating even if you don't.

[sama]

a raise/dip will have initial acceleration/deacceleration, but will become constant shortly after and would therefore be interpreted as vertical motion. vertical motion can be ignored here since we're only interested left/right and forward/back.

I've a friend that knows .net and we're going to work on this together. hopefully something will come out of it.

please keep any ideas/scepticism coming, they're all food for thought.

[JanDaMan]

think of the g sensor data like a joystick top down view, recorded over time as a stream. that stream is the g-sensor's interpretation of the current path.

the gps signal, is also recorded as a stream.

overlay them, and if they agree, we're good. If one misbehaves, consult the other.

ok i appreciate all the above points BUT surely the only reason one would want to implement the G-Sensor in the first place is so that it can provide data to the software during times when a GPS single is not available eg near high rise buildings and in tunnels...

when the software is depending on purely the data of the G-Sensor thats when it may have issues (like if u move the device) BUT i agree that it has to be better than no input at all... i am not trying to be negative here i am actually quite intrigued to see if someone would be able to get this working as the data provided by the sensor is probably just about accurate enough to work for short stints like in a tunnel etc

You guys forgot another problem. When you're moving into a tunnel or something the device will detect the declining of the angle of the car you're driving. So it will detect that you're actually accelrating even if you don't.

this is indeed another issue

a raise/dip will have initial acceleration/deacceleration, but will become constant shortly after and would therefore be interpreted as vertical motion. vertical motion can be ignored here since we're only interested left/right and forward/back.

I've a friend that knows .net and we're going to work on this together. hopefully something will come out of it.

please keep any ideas/scepticism coming, they're all food for thought.

well if you accelerate for a while that would be the same reading as going on an incline... the period of time for acceleration could be extended and hence be misunderstood as a gradient... hmmm but again this would only be an issue if it occurred when there was no GPS signal

[sama]

no negativity at all, it's all positive food for thought.

I guess when you're accelerating... you're going forward! some 0-60 measuring units use g-sensors (hey that's another application :p)

Perhaps there are a few scenario's that would need to be profiled and modelled. so possible scenarios could be:

1- stationary, accelerate hard
2- stationary, accelerate softly
3- moving, accelerate hard (sharp speed increase)
4- moving, accelerate softly (slow speed increase)
5- moving, decelerate hard (sharp speed decrease)
6- moving, decelerate softly (slow speed decrease)

I guess Dennis is correct that hills/dips would skew the results a little by showing an acceleration for a brief time, but not a huge amount.

That's all for Z axis.

Then there's the X axis:

1- a small-small change in x means a long bend
2- a small-large-small (bell) means a sharp bend

This output can be used in conjunction with the map data, to guess where it is/has gone. When the strength of the GPS signal falls below a certain amount, then it would use this 'guessed' data.

hmm.. this approach may be too simplistic... I guess some experimentation is needed. some data will need to be collected from the g sensor, and from the gps, and then to take a controlled route, and then look at all the data in a time line. Should be interesting!

[svenss]

ok maybe im missing something but this idea has issues with 2 things IMO

1) the G sensor will not be able to differentiate between travelling at a constant speed and not moving at all, because in both situations the G-force

(...)

but the accuracy of this is affected by the hardware and problem 2, Overall i find it hard to see this working too well. *wonders how the army use it*

Defo worth a try tho is someone feels like putting the effort in :)

i think that the army use a gyroscope instead of a g-force meter/sensor such as in a diamond. i don't know the exactly working of the army used gyroscope combined the gps but i can't find it out if you want to know ;)

Greetz

sven

http://web.rollins.edu/~jsiry/Gyroscope_operation.gif
(gyroscope):o

[swiftgs]

Guys,

I work on a military boat so I cant give to much information, but thrust me. Dead reckoning on a Gsensor only is completely impossible!!! :D

First of all as said before you need a gyro (able to meassure roll, pitch and yaw), wich is far more accurat than a gsensor because it lacks the yaw option wich is absolutely critical. Then to make a system like this functioning you will need a lot extras, most important a compass (most prefferable a gyrocompas)

Also you need a lot of extra equipment, wind meters, acceleration meters, tilt meters, sideway movement meters etc. etc. etc.

Offcourse you can make a program wich use it a little bit, but I bet you will not be able to navigate more than 2 seconds with it and keep reliable information....

more info... inertial navigation system (http://en.wikipedia.org/wiki/Inertial_navigation_system)

anyway, I follow this just for fun :D

[svenss]

hehe i started good with my story :p

only the gyro part then ^^

[joaormf]

My BMW iDrive GPS actually does this.

When in an underground park the "car" moves in the map, and it gets the position solid right when I exit the park.

[Wizard-of-Oz]

These systems are not science-fiction - they're installed in every fighter jet, some commercial jets, and in fact the technology roots back to WWII.

See (also given a couple of posts up by swiftgs):

http://en.wikipedia.org/wiki/Inertial_navigation_system

Basically, if you have accurate angular and linear accelerometers, you can know exactly your position at any time, provided you knew your starting point.
The commercial/military systems have an accuracy of about 1NM/hour - i.e. after 1 hour of navigating it's about 1NM off. Of course with the aid of other navigational systems that can be recalibrated periodically.
swiftgs - you don't need any of the "extras" you mentioned - if your initial position, heading and velocity are known, you only need three gyros and three accelerometers. No compass, etc - those are there to supplement the system, minimize errors, etc.

I see two basic physical problems with implementing it in the Diamond:

1. Only 3 linear accelerometers present, angular movement information is missing (that's the "gyro" part)
2. Probably the accuracy is so low, that even internal thermal noise would give crazy readings quite fast.

[goRt]

My BMW iDrive GPS actually does this.

When in an underground park the "car" moves in the map, and it gets the position solid right when I exit the park.

The BMW nav reads all sorts of telemetry data - wheel speed, steering turn, etc. not available to the diamond

[schnitzelbrain]

This software here
http://forum.xda-developers.com/showthread.php?t=422662

does all what we want and plots it on the screen. It takes the gps data and puts it together with the g-sensor data.

so anyone who can bring this together for use with a navi system

[Lakva]

I think it IS possible to made usable system based on G-sensor - because there are comercial BT GPS modules using only GPS and G-sensor.

The true is, that G-sensors in phones are simple, above all for orientation detection. But still they are G-sensors and we can use it with some limitations.

We don't need gyroscope - it's necessary only if we don't have initial movement info - but we have one! We have GPS.
GPS running for 10-30 seconds should be enough to CALIBRATE the G-detection. Then, in the tunnel, if we lost GPS signal, the G-detection should be enough to help decide, if we are runing at the same speed/decelerate/accelerate.

Precission is not big, that's true! But we are not trying to build extremely precise system for military aircraft! We want just simple system to help us in tunnels or "city canyons"!

Possible problems:
1) Moving the phone in the car or changing it's orientation.
Yes, this MAY be a problem. But if you use phone as navigation, you hardly hold it in your hand... Phone is in the holder and even if you take the call, you can do it using headset or handsfree set.
It is possible that someone holds a phone for you... but if you mean the phone navigation seriously, you have a holder and you dont move the phone in the car during driving.

2) Orientation of the phone in the car.
This is the problem, too. Even if we have a holder in the car, phone orientation may be slightly different for each ride.
But we have the GPS. We can compare data from both systems at the beginnig of ride. I think few hundred meters should be enough to "calibrate" the "G-system", to decide exact orientation of the phone towards the car.

And... I think this is all. I can't see another big problem. Everithing else is just an "implementation trouble" ;-)

As I can see it, we will need an application with those functions:
1) Recieving the GPS data from the system - on some COM port.
2) Recieving the G-data from system. It's not so easy, but still possible.
3) Correlate those data togather.
a) while GPS data are available, application should simply calibrate data from G-sensor and "learn", how the G-sensor reacts on movements during ride.
b) as soon as the GPS position is unavailable, application should switch to "G-mode" and continue to provide position based on G-sensor data and all informations, which it have learned from previous mode - as in 3)a)
4) Provide the position data (in NMEA form) to another - virtual - COM port, from where the navigation app will read it.

I'm afraid we can't use the map data to improve precision. For this, the application would need acces to map data - and it does not.
We would have to crack the navigation app and write the necessary code directly into it, to use map data...

[m@riner]

Allow me to agree with the idea of DR using G-sensor and GPS combined. I'm a ship captain and I've been using all sorts of navigation equipment for quite a long time...In the next rows, I will try to put things in a very simplified way which might be quite hepful...

1) A gyro is able to maintain it's spinning axis stable in space irrespective of movement (earth moves-gyro appears to tilt but in fact it's stable-The Sperry Experiment-) ; gyro container bears cardinal markings and it's actually itself moving around gyro thus indicating direction.
2) A gyro aligns with meridians after completing oscillation while gaining RPM till normal operation value. This way it's capable of providing N-S direction.

Basis above, a hard-wired G-sensor-WHICH IS NOT A GYRO-cannot yield N-S directional information by default, it can however "sense" deviations from it's initial state.

Coding of an inertial compass applet incorporating G-sensor in my opinion is possible, by implementing following operation principle:

In order to properly initiate directional monitoring (with an accuracy depending on sensor's sensitivity), an initial course (orientation) with the device lying flat must be fed to the application. Any motion towards Left(Port) or Right (Starboard) will cause measurable deviation also to be fed to application-this amount translated in degrees of deviation for the display-.

Initial course can be derived either by use of -most preferrably- GPS COG (course over ground) or by built-in digital compass corrected for Magnetic Variation or even manually provided that user has a compass (Gyro or Magnetic) available or any other means of accurately knowing his heading.

Potentiall accuracy flaws:

1)Inherent qualities of G-sensor.

2)GPS COG input: When GPS cold started or poorly receiving, COG may fluctuate as much as 10-15 deg Port or Starboard; A possible remedy to this is an averaging filter able to detect the amplitude of Port-Starboard fluctuation and use a stable average.

3)Built-in digital compass: Must be corrected for Variation depending on the area being used;In this particular case a deviation database used in combination with GPS position, constantly feeding data would give the digital compass a very acceptable accuracy thus rendering our planned G-sensor app practically useless.

4)Manual fed initial course: Will very much depend on the proper orientation-placing-mounting of the device but in my opinion is an additional MUST option.

And now, some of my professional likes if only this kind of software is ever coded:
1) True heading indication through principles mentioned above
2) ROT (Rate Of Turn) indication in degrees per minute towards Port or Stbd.
3) Manual compensation-correction of true heading both initially and during program execution (the latter case using stylus and setting digits or rose pointer real time)
4) NMEA 183 format output through virtual port in various Baud rates to feed data to NMEA compatible applications, such as an electronic chart system.

That Would Rock!!!:cool:

Looking forward to hearing from developers!!! :rolleyes:

[laggflor]

Hi, I haven't tested it - but here is something promising:
http://forum.xda-developers.com/showthread.php?t=571266

I also have other strange ideas ;-)
If we loose GPS we could not only use the G-Sensor - we also have:
* Front and Back Camera (if one is heading outside of the window it could measure speed?)
* known Wifi-Networks

Anyhow - a big estimating job. Good luck for everyone jumping into it.

[Lakva]

* Front and Back Camera (if one is heading outside of the window it could measure speed?)

This is possible, in theory. But practicaly I'm affraid, that processing of images in real time is too much for today's PPCs. Especially if there is runnig navi application. The cocpit view animation will became rather slideshow, probably :-(


* known Wifi-Networks

There would be necessarry very large database. And another problem is, that in situations when GPS signal is lost - tunels etc. - wifi is often unavailable, too :-(

[laggflor]

But practicaly I'm affraid, that processing of images in real time is too much for today's PPCs.

WiFi: There would be necessarry very large database.

Sure. I just insert some ideas for discussion.

Wifi could be interesting in car parks. often in cities, wifi-networks are around. Well - I don't know - maybe we do not need large databases: What if we record the position of wifi-ap of the current cruise - if we drive into a car park the gps is lost but we could probably find the correct exit.
Again: Just ideas...

For Camera analysis: yes, you might be right - it will take some (maybe too much) resources. But in combination to the G-Sensor it gives me some hope:
We mostly need it in tunnels and car parks. both are relatively dark areas with lights and reflectors. We probably do not need a good resolution, and working with contrast we have view parts of the video we have to look at. We probably will need an accurate framerate to follow these items.
Maybe these should be a definition for a college project ;-)

But I think both is out-of-scope for a small project.
I still hope someone is coming up with a good idea.

I'll try the "GPS Mod driver" of my last post - but I read the description again and think it not doing what we want it to.
--- edit ---
The above mentioned driver caused problems on my device.