Design Article
Comment
Carlos1966
Duane Benson
It's not clear if the "constant calibration" is just positional calibration so ...
Dead reckoning fills-in GPS navigation gap
Etienne Favey, Alexander Somieski, Christine Hollenstein, Michael Ammann, and Carl Fenger, u-blox
8/18/2011 3:00 AM EDT
Dead reckoning solution (and drawbacks)
To address this growing problem, u-blox, for example has integrated dead reckoning functionality into GPS receiver chip technology. Dead reckoning is actually a centuries old concept originally used by sailors and later aviators to extrapolate their position based on how far and in what direction they have travelled from a last known location, typically the last harbor.
Based on proprietary Sensor Fusion Dead Reckoning technology, the u-blox GPS receiver chip accomplishes the same task when travelling through regions of poor GPS reception. Based on the last known position, vehicle sensors feed information to the receiver indicating how far and in what direction the vehicle has travelled. The chip processes the sensor data and blends it with GPS positional readings. In this way, a better approximation of where the vehicle actually is can be extrapolated, regardless of GPS satellite visibility.
Dead reckoning has one drawback: The displacement and heading errors accumulate over time. The errors depend on the accuracy of the sensors, data quantization errors, and time granularity. It is the job of dead reckoning hardware and software to minimize the errors for as long as possible to provide accurate location information during short signal interruptions as well as long drives through tunnels.
The figure below illustrates accumulated dead-reckoning error.
The following list shows typical sensor and information sources used by dead reckoning technology to calculate a position:
Distance Sensing:
Sensing distance traveled
There are a variety of sensor techniques for detecting distance travelled. Typically a direct connection to the vehicle’s odometer is enough. If this is not available, for example for after-market installations, wheel sensors can provide the raw information for distance travelled. The variable reluctance sensor and Hall Effect position sensor are two common types of electromagnetic sensors for this purpose.
Direction Sensing:
Sensing direction
Besides distance, direction or turn-rate information (measured, for example, in degrees per second) is also needed to extrapolate the travelled route. The easiest approach is to use a small turn-rate sensor, also called a gyroscope. Several types of gyroscopes exist: mechanical (a rotating mass suspended in gimbals), optical, and micro-electromechanical system (MEMS) vibrating structures.
The first two types of gyros provide excellent accuracy but are large and expensive. MEMS gyroscopes excel in their small size, good performance, and user-friendliness and are relatively inexpensive. They are also available as surface-mount devices easily installed on a printed circuit board.
Map matching
In addition, a technique known as map matching can be used. Based on an actual map, application software knows to always report a position located on an actual road, even if the extrapolation calculated by the GPS receiver is slightly off due to accumulated position and heading error.
Ultimately, an approach of using the dead reckoning solution based on both GPS and sensor measurements simultaneously together with map matching delivers the best result in city environments where a wide range of signal conditions can be expected: Partial, reflected, and blocked GPS signals.
Next: Specific examples
To address this growing problem, u-blox, for example has integrated dead reckoning functionality into GPS receiver chip technology. Dead reckoning is actually a centuries old concept originally used by sailors and later aviators to extrapolate their position based on how far and in what direction they have travelled from a last known location, typically the last harbor.
Based on proprietary Sensor Fusion Dead Reckoning technology, the u-blox GPS receiver chip accomplishes the same task when travelling through regions of poor GPS reception. Based on the last known position, vehicle sensors feed information to the receiver indicating how far and in what direction the vehicle has travelled. The chip processes the sensor data and blends it with GPS positional readings. In this way, a better approximation of where the vehicle actually is can be extrapolated, regardless of GPS satellite visibility.
Dead reckoning has one drawback: The displacement and heading errors accumulate over time. The errors depend on the accuracy of the sensors, data quantization errors, and time granularity. It is the job of dead reckoning hardware and software to minimize the errors for as long as possible to provide accurate location information during short signal interruptions as well as long drives through tunnels.
The figure below illustrates accumulated dead-reckoning error.
The following list shows typical sensor and information sources used by dead reckoning technology to calculate a position:
Distance Sensing:
- Odometer pulses (absolute distance traveled, this is most typical)
- Distance information from wheel ticks
- Digital speed information (distance is reconstructed from a single integration),
- Linear accelerometers (distance reconstructed from double-integrating acceleration)
- Radar, optical, and acoustic sensors.
Sensing distance traveled
There are a variety of sensor techniques for detecting distance travelled. Typically a direct connection to the vehicle’s odometer is enough. If this is not available, for example for after-market installations, wheel sensors can provide the raw information for distance travelled. The variable reluctance sensor and Hall Effect position sensor are two common types of electromagnetic sensors for this purpose.
Direction Sensing:
- Turn rate sensor (gyroscopes, most typical)
- Linear accelerometers
- Steering linkage angular sensor
- Differential wheel speed information (between left and right wheels)
- Magnetic compass
Sensing direction
Besides distance, direction or turn-rate information (measured, for example, in degrees per second) is also needed to extrapolate the travelled route. The easiest approach is to use a small turn-rate sensor, also called a gyroscope. Several types of gyroscopes exist: mechanical (a rotating mass suspended in gimbals), optical, and micro-electromechanical system (MEMS) vibrating structures.
The first two types of gyros provide excellent accuracy but are large and expensive. MEMS gyroscopes excel in their small size, good performance, and user-friendliness and are relatively inexpensive. They are also available as surface-mount devices easily installed on a printed circuit board.
Map matching
In addition, a technique known as map matching can be used. Based on an actual map, application software knows to always report a position located on an actual road, even if the extrapolation calculated by the GPS receiver is slightly off due to accumulated position and heading error.
Ultimately, an approach of using the dead reckoning solution based on both GPS and sensor measurements simultaneously together with map matching delivers the best result in city environments where a wide range of signal conditions can be expected: Partial, reflected, and blocked GPS signals.
Next: Specific examples
|
|
|
|
|
Navigate to related information
EREBUS
8/21/2011 5:45 PM EDT
Dead reckoning has been used for millenia for navigation the world wide. It is amazing to me how quickly people forget that we found places just fine with maps and street signs long before GPS became readily available.
Vehicles with installed inertial navigation systems and digital maps should be more than sufficient to augment the GPS driven navigation needed today.
That said, I cannot overstress the need for driver participation in the process. If you put all of your reliance on the computers, it will not end well.
Thanks,
Sign in to Reply
David Ashton
8/21/2011 6:53 PM EDT
"...typical signal strength....of 120 dBm (1 x 10–15W)."
Shouldn't this be -120 dBm? 120dBm would be 1 x 10+9 watts - a gigawatt....
Nevertheless a great article. My GPS gets totally confused in Sydney's urban canyons (and so do I if I am going somewhere I am not familiar with). I'd thought about accelerometers myself to help the GPS.
As Erebus says, the old fasioned Map is also a good solution. I keep a Sydney CBD map in my glove box for these occasions.
Sign in to Reply
tomkawal1
8/24/2011 11:01 AM EDT
It's been for a while - all the gyros and odometer. If thinking seriously about autonomous driving, for increased safety, one need to provide network of transponders along motorways and process the signal similar way satellites are used. There are some technical issues, like precise timing of the network == huge cost, but balanced by better efficiency.
Sign in to Reply
selinz
8/24/2011 2:52 PM EDT
Seems like it's a bad marketing idea to use the term dead...
Sign in to Reply
c.scott
8/24/2011 3:09 PM EDT
Which is why I'm glad marketing people aren't in charge of (re)naming things all the time... Taking 30 seconds to look up the name meaning came up with this: dead reckoning - a homophone of ded (for deduced) reckoning.
Sign in to Reply
docdivakar
8/24/2011 7:47 PM EDT
Agree! If it were up to marketing types, we would have ridiculous words & phrases that may not have anything to do with the product.
In my dictionary, an alternate for 'ded'uced reckoning would be 'common sense!' It surprising how fast people let go of it these days, getting addicted to GPS's & mobile phones. Unlike most places in Asia, cities in USA are laid out in grid iron pattern and are quite easy to navigate without 'artificial' aides! Try doing that in a rural town in China or India, you will need the 'positioning' advice of a number of locals before you get your distination!
MP Divakar
Sign in to Reply
kmilnes
8/25/2011 2:30 PM EDT
Technology gets reinvented many times. In 1985 a Silicon Valley company, Etak, pioneered the consumer vehicle navigation technology. They invented and marketed a system that used differential wheel sensors, magnetic compass, and map matching for navigation.
Maps were stored on a cassette tape, heading was measured with a flux gate compass, and distance traveled was measured by a variable reluctance sensor mounted next to magnetic tape stuck to the inside of the wheel rim. The two non-driven wheels were instrumented so that relative turns could be measured. Maps were displayed on a CRT using vector graphics.
Several key patents were issued to them including map matching, absolute and relative heaing sensor fusion, heading up map display, and methods to label the streets. The popular vehicle navigation systems of today have their roots in the Etak Navigator.
The system suffered from the lack of an absolute position sensor (i.e. GPS). It would be another 15 years until GPS became economical.
It did work remarkably well for the limited sensors available. It would typically navigate without "getting lost" for about 200 miles in both urban and rural environments.
Etak went through several mergers and acquisition (News Corp, Sony, TeleAtlas and now TomTom).
Sign in to Reply
Duane Benson
8/26/2011 1:29 PM EDT
It's not clear if the "constant calibration" is just positional calibration so that the nav system will know the last known good location, or if it is also calibrating for vehicle variables, such as tire size.
If the vehicle ends up with different size tires or after enough wear, the odometer / wheel sensors will not be giving accurate distance measurements. If the nav system is constantly reading those sensors and calculating the actual verses sensed speed and distance, the accuracy would be greater under a variety of real-world conditions.
Sign in to Reply
Carlos1966
9/7/2011 11:31 AM EDT
Duane,
Typically the Kalman Filter as used in an inertial navigation system is estimating the drift and bias of the gyros and accelerometers along with other modeled errors in the system. These values are what is being calibrated. The calibrated values are then used to correct the estimates made by integrating the accelerations.
Sign in to Reply