programming deadreckoning gps software?

djkriz · 09-15-2004, 01:55 PM

Hi,

I read an article about the new tomtom-go device, which uses some sort of software-based deadreckoning system, in case it looses its fix.
I think it wouldn't be too difficult to program something like that for the pc, but I don't have enough programming experience to do so...

Basically the software should do this:
- input the standard NMEA sentence of the GPS using a com-port
- check if the fix is lost (in case of a tunnel)
- in case the fix is lost : continue to send computed NMEA data, based on the last known position, in combination with speed and heading
- output the NMEA data to a (virtual) comport, feeding navigation software

Then you would be able to still have a (virtual) fix, even when you suddenly lose the fix, caused by bad skyview (tunnels etc)

I hope anyone can program such a little piece of software???

Dominik · 09-15-2004, 07:55 PM

I saw someone talking about this in another thread. I think it should go one step further. Use a Gyro/Compass to determine whether you are turning, speed sensor to detect change in speed, etc. It could almost be done in Hardware (more difficult, but easier to integrate with speed sensors etc). This is quite a cool idea i think!

Dominik · 09-15-2004, 09:26 PM

Further thinking, this could be done in code, as long as:
a) You could create a virtual Com port which you can point the GPS Software to
b) You have a way of getting Vehicle Speed/Direction INTO the computer

Now the following is just pseudocode dribble, but it might help someone who can work out how to achieve the 2 points above:

Code:

Variable Descriptions:
X=Coordinate (the further north you go = the lower the x coordinate; is this how GPS coordinates work? If not, then some of the calculations below might need changing)
Y=Coordinate
V=Velocity (MS)
D=Direction (0-359 degrees)
Timer=500Ms (User Settable)

Sample Pseudocode:
===============
Main.Initialize
    'Get starting coordinates. If no lock is present, read last known coordinates from file
    If Not ReadGPSNMEAString() Then
	ReadLastCoordinatesFromfile()
    EndIf
End Main.Initialize

Event Timer.Tick
    If ReadGPSNMEAString() Then  'GPS Lock exists
	'Bypass coordinate calculations
	TransmitNewGPSData()
    	WriteCoodinatesToFile() 'Always write last coordinates to file - incase user shuts down at this point
    Else  'No Lock exists
	'Process last known Speed/Direction values
	Select Case D '(Direction)
		Case 0:
			X=X-(V*(1000/Timer))
		Case 90:
			Y=Y+(V*(1000/Timer))
		Case 180:
			X=X+(V*(1000/Timer))
		Case 270:
			Y=Y-(V*(1000/Timer))
		Case Else:
			DeltaX=Sin(D) * (V*(1000/Timer))
			DeltaY=Cos(D) * (V*(1000/Timer))
			X=X-DeltaX
			Y=Y-DeltaY
	End Select

	'Send new coordinates to fake com port
	TransmitNewGPSData()
	WriteCoordinatesToFile() 'Always write last coordinates to file - incase user shuts down at this point

	'Get New Speed/Direction coordinates (this is assumed to be the vehicle's direction for until the next timer tick)
	V=GetVehicleSpeed()
	D=GetDirection
    End If
End Event

Procedure ReadGPSNMEAString()
	'Get X & Y Coordinates
	'Calculate velocity and Direction
End Procedure

Curiosity · 09-15-2004, 11:42 PM

The virtual COM port is easy enough.

This one... well, the one at the bottom, can take input from one port and send it to a few others. All you would need to do is read from the GPS, process it, and write it to this one.

Laidback · 09-16-2004, 05:13 AM

Quote: Originally Posted by Curiosity

The virtual COM port is easy enough.

This one... well, the one at the bottom, can take input from one port and send it to a few others. All you would need to do is read from the GPS, process it, and write it to this one.

Dude, when I click 'install service' I get 'unable to find xport.sys' message box. Tried xport.sys in same dir and in path! Could be my desktop pc of course, I'll try it on another....

Edit: S'ok, it's my desktop! I'll try it in the car.

wi77iam · 09-16-2004, 07:26 AM

I've been considering doing something like this for awhile. I used to write the software for aircraft navigation systems for the Navy, so the dead-reckoning equations are not too difficult. The problems are getting an independent source of speed and heading, and feeding the resulting DR position in the form of NMEA statements back to the comm port, to be read by the regular mapping software.

I think this dual axis accelerometer phidget would be able to supply the speed and heading.

I have contacted the author of the GPSGate program, to see if he could add the capability to intercept and process the NMEA stream prior to sending it out the virtual port. He just recently added an SDK, but not sure yet if it can do this so I'm going to look into it.

One other thing that this software should have, is to be able to generate a fix position that could be used to compute position corrections, that could then be applied to the GPS position. Then you could mark on top a known lat/long and compare to the GPS position and compute lat and long corrections. These would be applied to all subsequent NMEA positions before sending on to the mapping program.

Ricky327 · 09-16-2004, 09:56 AM

I think this dual axis accelerometer phidget would be able to supply the speed and heading.

The TomTom Go doesnt use a standard gyro but instead it does use a dual-axis accelerometer to calculate speed, heading and acceleration...etc.

The accelerometer module only supply the forward-backward and lateral g's (I have the ADXL202 module used for measuring g's in the car). This work fine on flat roads for measuring g's but the problem is when the car is driven hard it will tilt naturally and therefore give a wrong g reading, you will get more g...unless the tilt g is substracted.

Applying this for GPS use, the software need to do some calculation such that it doesnt think that the car is accelerating when the GPS looses its signal on a hill...but how can it know as I dont think TomTom Go need any other connection to the car

If someone can work out how the accelerometer is used in the TomTom Go then a PIC MCU can be used to take over the calculation. The PIC get the NMEA data from the GPS, calculate the values read from the accelerometer and spit out the computed locations whenever the gps looses its signal. This way its going to be an add-on hardware module for the gps making it compatible with any gps software. No need for an extra serial port for the accelerometer or an additional software to compute the NMEA sentence and the accelerometer values and no need for a virtual comport to combine the 2 values into one port.

Maybe someone here can reverse engineer the TomTom to see whats going on.

GPS + Accelerometer + PIC = sounds like an interesting project

wi77iam · 09-16-2004, 12:35 PM

I think you would just need to put another accelerometer in the third axis to sense pitch (up-down), since the dual axis accelerometers would be sensing forward-back and left-right.

Either that or rig up something like a bubble level to know when the car is going up a hill. Maybe with the rotation sensor phidget and a weight?

Ricky327 · 09-16-2004, 12:47 PM

From TomTom Go review :

TomTom Go has a two plane acceleration sensor with no moving parts unlike conventional gyro systems. The sensor will be good enough for several hundred meters so TomTom Go can continue to work when GPS signals are not available (for example in tunnels with exits).

It does say no moving parts and only use a dual axis accelerometer, the rest must be softwares...the TomTom guys must have done it somehow.

jpelzer · 09-16-2004, 01:02 PM

It's not really that complicated... Most tunnels are straight, and hopefully not too many turns before gps lock is reestablished. I don't think you need to take into account tilt at all, but I think you WOULD need to calibrate the system based on incoming GPS date when it was first installed.

Depending on where the accelerometer was installed on the car (front to back), your G's would be different, and this would be more apparent for lower-speed (short radius), and negligable for large radius (highway speed) turns.

So you'd need to track a turn while the GPS was locked, and then correlate that to the measured G's.

I already ordered that Phidget accelerometer, for just this project. Damn you guys for beating me to post! I think it will be perfect for our application, as it has a VERY simple SDK for communicating with it. And it's only $50.

As soon as we have source for creating virtual com ports, we're there. NMEA shouldn't be a tough nut to crack.

Ricky327 · 09-16-2004, 02:05 PM

Most tunnels are straight

Not where I live where we have a zig-zag tunnel, curved and all sort

I don't think you need to take into account tilt at all, but I think you WOULD need to calibrate the system based on incoming GPS date when it was first installed.

How about if you are traveling at a constant speed then you loose the GPS signal? The accelerometer will then register zero reading since you are not changing speed...what would the software now present to the GPS program? would it be 0 mph or the last known speed from the GPS? ok lets say the last known speed is 30mph while going up the hill...the car will naturally slow down but the accelerometer think you are accelerating because the car tilted upward. In this case the 30mph last known speed is now wrong, the accelerometer is also wrong thinking the car is now moving at 100mph when infact you have stopped

Ricky327 · 09-16-2004, 02:08 PM

A good read here :

http://www.gpspassion.com/forumsen/t...TOPIC_ID=11302

I can see it working but the hill is still puzzeling me...or if you go on a straight road but banked to one side the accelerometer now think you are turning?

Ricky327 · 09-16-2004, 02:13 PM

Depending on where the accelerometer was installed on the car (front to back), your G's would be different

Im not sure if thats true because the angle of the whole car in respect to the horizontal plane of the earth is the same wherever you put the sensors.

siberia37 · 09-16-2004, 02:24 PM

Quote: Originally Posted by djkriz

Hi,

I read an article about the new tomtom-go device, which uses some sort of software-based deadreckoning system, in case it looses its fix.
I think it wouldn't be too difficult to program something like that for the pc, but I don't have enough programming experience to do so...

Basically the software should do this:
- input the standard NMEA sentence of the GPS using a com-port
- check if the fix is lost (in case of a tunnel)
- in case the fix is lost : continue to send computed NMEA data, based on the last known position, in combination with speed and heading
- output the NMEA data to a (virtual) comport, feeding navigation software

Then you would be able to still have a (virtual) fix, even when you suddenly lose the fix, caused by bad skyview (tunnels etc)

I hope anyone can program such a little piece of software???

To do it right is more complicated. Tomtom probably has navigation data like maps and so it if loses fix it has the information of what the last road you are on- possibly what your intended destination is AND speed and bearing. So then the problem becomes very simple, just display that the user is on the last road he is on going at the same speed and bearing. You can do this with just speed and bearing, but if the road curves through a tunnel then you are going to be off.

jpelzer · 09-16-2004, 03:37 PM

I think you guys are confusing yourselves:

Quote:

if you go on a straight road but banked to one side the accelerometer now think you are turning?

No. The accelerometer is not affected by gravity in this way. It would likely register a SMALL change when you transitioned from level to banked travel, but on a straight banked road (if they exist), the acceleration will read 0.

Quote:

Im not sure if thats true because the angle of the whole car in respect to the horizontal plane of the earth is the same wherever you put the sensors.

I'll give you a more concrete example of why calibration is important:

Consider if we put the sensor in a school bus. We'll choose 4 possible locations:

A) Over the front wheels
B) Somewhere between front and rear wheels
C) Over the rear wheels

OK, the bus driver is turning left onto a side street, so making a very sharp turn, going slow. Let's say it takes them 5 seconds to complete the turn, then they accelerate straight.

In A), the sensor senses acceleration to the left, relatively strongly because the front of the bus needs to move about 20 feet in 5 seconds.
In C), the sensor senses some acceleration, but it is (in the case of a bus) much less than the front, because the rear wheels actually trace a shorter path than the fronts, so they might only have to cover 10 feet in that same 5 seconds.
B) would be a value somewhere between A and C

Quote:

How about if you are traveling at a constant speed then you loose the GPS signal? The accelerometer will then register zero reading since you are not changing speed...what would the software now present to the GPS program? would it be 0 mph or the last known speed from the GPS? ok lets say the last known speed is 30mph while going up the hill...the car will naturally slow down but the accelerometer think you are accelerating because the car tilted upward.

If you are traveling 30 mph and lose signal, you are right, acceleration will be 0, so the program would continue displaying 30mph.

Tilt has nothing to do with an accelerometer. They can be USED as tilt sensors, but they are not affected by tilt in the way you are implying. A sensor at a 45deg angle that is moving at a constant speed will register the exact same value a sensor laying flat would: zero.

If you went up or down a hill and your speed changed, the acceleration would be applied to the last known speed, and the approximate speed would be calculated.