Innovation: Filling in the Gaps

October 1, 2011 - By Richard B. Langley

Improving Navigation Continuity Using Parallel Cascade Identification

By Umar Iqbal, Jacques Georgy, Michael J. Korenberg, and Aboelmagd Noureldin

To reliably navigate with fewer than four satellites, GPS pseudoranges needs to be augmented with measurements from other sensors, such as a reduced inertial sensor system or RISS. What is the best way to combine the RISS measurements with the GPS measurements? The classic approach is to integrate the measurements in a conventional tightly coupled Kalman filter. But in this month’s column, we look at how a mathematical procedure called parallel case identification can improve the Kalman filter’s job, when navigating with three, two, one, or even no GPS satellites.

INNOVATION INSIGHTS by Richard Langley

THREE, TWO, ONE, ZERO! Can you still navigate with just a GPS receiver when the number of tracked GPS satellites drops from four to none? As we know, pseu- doranges from a minimum of four satellites, preferably well spaced out in the sky, are required for three-dimensional positioning. That’s because there are four unknowns to estimate: the three position coordinates (latitude, longitude, and height) and the offset of the receiver clock from GPS System Time. If we had a stable clock in the receiver, then we could hold the clock offset constant and have 3D navigation with just three satellites. But for every 3 nanoseconds of clock drift, we will have about 1 meter of pseudorange error, which will lead to several meters of position error depend- ing on the receiver-satellite geometry. On the other hand, we could hold the height coor- dinate constant (viable for navigation over slowly changing topography or at sea) and estimate the horizontal coordinates and the receiver clock offset. So far, so good.

What if the number of tracked satellites then drops to two? We can now only esti- mate two unknowns. They could be the two horizontal coordinates, if we hold both the receiver clock offset and the height fixed. Any errors in those fixed values will propagate into the estimated horizontal coordinates but the resulting position errors might still be acceptable. Instead of holding the clock offset
fixed, we could assume a constant heading and compute the position along the assumed trajectory. However, navigation will rapidly deteriorate as soon as we make the first turn. And one satellite? We would have to make assumptions about the vehicle trajectory, the height, and the clock offset, with likely very poor results. And with no satellites? We might be able to navigate over a short period of time by “dead reckoning,” assuming a constant trajectory and speed, but the resulting positions will be educated guesses at best.

Clearly, if we want to reliably navigate with fewer than four satellites we need to augment the GPS pseudoranges with measurements from some other sensors. A common approach is to use inertial measurement units or IMUs. A complete IMU consists of three accelerometers and three gyroscopes, and small, cost-effective microelectromechanical IMUs are readily available. For land navigation, however, it can be advantageous to use a reduced inertial sensor system or RISS, consisting of one single-axis gyroscope, two accelerometers, and the vehicle speedometer. We can also make use of GPS pseudorange rates along with the pseudoranges.

But what is the best way to combine the RISS measurements with the GPS measurements? The classic approach is to integrate the measurements in a conventional tightly coupled Kalman filter. But in this month’s column, we look at how a mathematical procedure called parallel cascade identification can improve the Kalman filter’s job, when navigating with three, two, or even one GPS satellite.

The Global Positioning System meets the requirements for numerous navigational applications when there is direct line-of-sight (LOS) to four or more GPS satellites. Vehicular navigation systems and personal positioning systems may suffer from satellite signal blockage as LOS to at least four satellites may not be readily available when operating in urban landscapes with high buildings, underpasses, and tunnels, or in the countryside with thick forested areas. In such environments, a typical GPS receiver will have difficulties attaining and maintaining signal tracking, which causes GPS outages resulting in degraded or non-existent positioning information. Due to these well-known limitations of GPS, multi-sensor system integration is often employed. By integrating GPS with complementary motion sensors, a solution can be obtained that is often more accurate than that of GPS alone.

Microelectromechanical systems (MEMS) inertial sensors have enabled production of lower-cost and smaller-size inertial measurement units (IMUs) with little power consumption. A complete IMU is composed of three accelerometers and three gyroscopes. These MEMS sensors have composite error characteristics that are stochastic in nature and difficult to model. In traditional low-cost MEMS-based IMU/GPS integration, a few minutes of degraded GPS signals can cause position errors, which can reach several hundred meters. For full 3D land vehicle navigation, we had earlier proposed a low-cost MEMS-based reduced inertial sensor system (RISS) based on only one single-axis gyroscope, two accelerometers, and the vehicle odometer, and we have integrated this system with GPS. RISS mitigates several error sources in the full-IMU solution; moreover, RISS reduces system cost further due to the use of fewer sensors. Another enhancement can be achieved by using tightly coupled integration, which can provide GPS aiding for a navigation solution when the number of visible satellites is three or lower, removing the foremost requirement of loosely coupled integration, which is visibility of at least four satellites. GPS aiding during limited GPS satellite availability can improve the operation of the navigation system for tightly coupled systems. Thus, in our reseach, a Kalman filter (KF) is used to integrate low-cost MEMS-based RISS with GPS in a tightly coupled scheme.

The KF employed in tightly coupled RISS/GPS integration utilizes pseudoranges and pseudorange rates measured by the GPS receiver. The accuracy of the position estimates is highly dependent on the accuracy of the range measurements. The tightly coupled solutions presented in the literature assume that the pseudorange measurement, after correcting for ionospheric and tropospheric delays, satellite clock errors, and ephemeris errors, only have errors due to the receiver clock and white noise. These latter two are the only errors modeled inside the measurement model in the tightly coupled solutions presented in the literature. Experimental investigation of the GPS pseudoranges for vehicle trajectories in different areas and for different scenarios showed that, in addition, there are residual correlated errors. Since it has been experimentally proven that there are residual correlated errors in addition to white noise and receiver clock errors, we have proposed using a nonlinear system identification technique called parallel cascade identification (PCI) to model such correlated errors in pseudorange measurements.

We propose that the PCI model for the residual pseudorange errors be cascaded with a KF since this nonlinear model cannot be included inside the KF measurement model. The normal operation of a KF is as follows: the difference between the measured pseudorange and pseudorange rate from the mth GPS satellite and the corresponding RISS-predicted estimates of pseudorange and pseudorange rate are used as a measurement update for the KF integration, which computes the estimated RISS errors and corrects the mechanization output. We propose the use of a PCI module, where the role of PCI is to model the pseudorange residual errors. When GPS is available, estimated full 3D position, velocity, and attitude are obtained by integrating the MEMS-based RISS with GPS. In parallel, as a background routine, a PCI model is built for each visible satellite to model its pseudorange error. The actual pseudorange of each visible satellite is used as the input to the model; the target output is the error between the corrected pseudorange (calculated based on corrected receiver position from the integrated solution) and the actual pseudorange. This target output provides the reference output to build the PCI model of the pseudorange residual error. Dynamic characteristics between system input and output help to identify a nonlinear PCI model and the algorithm can then achieve a residual pseudorange error model.

When fewer than four satellites are visible, the identified parallel cascades for the remaining visible satellites will be used to predict the pseudorange errors for these satellites and correct the pseudorange values to be provided to the KF. This improvement of pseudorange measurements will result in a more accurate aiding for RISS, and thus more accurate estimates of position and velocities.

We examined the performance of the proposed technique by conducting road tests with real-life trajectories using a low-cost MEMS-based RISS. The ultimate check for the proposed system’s accuracy is during GPS signal degradation and blockage. This work presents both downtown scenarios with natural GPS degradation and scenarios with simulated GPS outages where the number of visible satellites was varied from three to zero. The results are examined and compared with KF-only tightly coupled RISS/GPS integration without pseudorange correction using a PCI module. This comparison clearly demonstrates the advantage of using a PCI module for correcting pseudoranges for tightly coupled integration.

RISS/GPS Integration

Earlier, we proposed the reduced inertial sensor system to reduce the overall cost of a positioning system for land vehicles without appreciable performance compromise depending on the fact that land vehicles mostly stay in the horizontal plane. It is the gyroscope technology that contributes the most both to the overall cost of an IMU and to the performance of the INS. In RISS mechanization, the heading (azimuth) angle is obtained by integrating the gyroscope measurement, ω_z. Since this measurement includes the component of the Earth’s rotation as well as rotation of the local level frame on the Earth’s curved surface, these quantities are removed from the measurement before integration. Assuming relatively small pitch and roll angles for land vehicle applications, we can write the rate of change of the azimuth angle directly in the local level frame as:
(1)
where ω^e is the Earth’s rotation rate, φ is the latitude, v_e is the east velocity of the vehicle, h is the altitude of the vehicle and R_N is the normal (prime vertical) radius of curvature of the vehicle’s position on the reference ellipsoid.

The two horizontal accelerometers can be employed for obtaining the pitch and roll angles of the vehicle. Thus, a 3D navigation solution can be achieved to boost the performance of the solution. When the vehicle is moving, the forward accelerometer measures the forward vehicle acceleration as well as the component due to gravity, g. To calculate the pitch angle, the vehicle acceleration derived from the odometer measurements, a_od, is removed from the forward accelerometer measurements, f_y. Consequently, the pitch angle is computed as:

(2)

Similarly, the transversal accelerometer measures the normal component of the vehicle acceleration as well as the component due to gravity. Thus, to calculate the roll angle, the transversal accelerometer measurement, f_x, must be compensated for the normal component of acceleration. The roll angle is then given by:

(3)

The computed azimuth and pitch angles allow the transformation of the vehicle’s speed along the forward direction, v_od (obtained from the odometer measurements) to east, north, and up velocities (v_e, v_n, and v_u respectively) as follows:
(4)
where is the rotation matrix that transforms velocities in the vehicle body frame to the navigation frame. The east and north velocities are transformed and integrated to obtain position in geodetic coordinates (latitude, φ, and longitude, λ). The vertical component of velocity is integrated to obtain altitude, h. The following equation shows these operations:
(5)

where, in addition to the terms already defined, RM is the meridional radius of curvature. We have used the KF as the estimation technique for tightly coupled RISS/GPS integration in our approach. KF is an optimal estimation tool that provides a sequential recursive algorithm for the optimal least mean variance (LMV) estimation of the system states. In addition to its benefits as an optimal estimator, the KF provides real-time statistical data related to the estimation accuracy of the system states, which is very useful for quantitative error analysis. The filter generates its own error analysis with the computation of the error covariance matrix, which gives an indication of the estimation accuracy.

In tightly coupled RISS/GPS system architecture, instead of using the position and velocity solution from the GPS receiver as input for the fusion algorithm, raw GPS observations such as pseudoranges and Doppler shifts are used. The range measurement is usually known as a pseudorange due to the contamination of errors, such as atmospheric errors, as well as synchronization errors between the satellite and receiver clocks.

After correcting for the satellite clock error and the ionospheric and tropospheric errors, we can obtain a corrected pseudorange. The receiver clock error and the residual errors remaining in the corrected pseudorange, assumed as white Gaussian noise, are the only errors modeled inside the measurement model in the tightly coupled solutions presented in the literature. Experimental investigation of the GPS pseudoranges in trajectories in different areas and under different scenarios showed that the residual errors are not just white noise as assumed in the literature, but, in fact, are correlated errors. As the GPS observables are used to update the KF, a technique must be developed to adequately model these errors to improve the overall performance of the KF. We propose using PCI to model these correlated errors. A PCI module models these errors, and then provides corrections prior to sending the GPS pseudoranges to aid the KF during periods of GPS partial outages (when the number of visible satellites drops below four).

Parallel Cascade Identification

What is PCI? System identification is a procedure for inferring the dynamic characteristics between system input and output from an analysis of time-varying input-output data. Most of the techniques assume linearity due to the simplicity of analysis since nonlinear techniques make analysis much more complicated and difficult to implement than for the linear case. However, for more realistic dynamic characterization nonlinear techniques are suggested. PCI is a nonlinear system identification technique proposed by one of us [MJK]. This technique models the input/output behavior of a nonlinear system by a sum of parallel cascades of alternating dynamic linear (L) and static nonlinear (N) elements. The parallel array shown in Figure 1 can be built up one cascade at a time.

Figure 1. Block diagram of parallel cascade identification.

It has been proven that any discrete-time Volterra series with finite memory and anticipation can be uniformly approximated by a finite sum of parallel LNL cascades, where the static nonlinearities, N, are exponentials and logarithmic functions. [A Volterra series, named after the Italian mathematician and physicist Vito Volterra, is similar to the more familiar infinite Taylor series expansion of a function used, for example, in systems analysis, but the Volterra series can include system “memory” effects.] It has been shown that any discrete-time doubly finite (finite memory and order) Volterra series can be exactly represented by a finite sum of LN cascades where the N are polynomials. A key advantage of this technique is that it is not dependent on a white or Gaussian input, but the identified individual L and N elements may vary depending on the statistical properties of the input chosen. The cascades can be found one at a time and nonlinearities in the models are localized in static functions. This reduces the computation as higher order nonlinearities are approximated using higher degree polynomials in the cascades rather than higher order kernels in a Volterra series approximation.

The method begins by approximating the nonlinear system by a first such cascade. The residual (that is, the difference between the system and the cascade outputs) is treated as the output of a new nonlinear system, and a second cascade is found to approximate the latter system, and thus the parallel array can be built up one cascade at a time. Let y_k(n) be the residual after fitting the kth cascade, with y_o(n) = y(n). Let z_k(n) be the output of the kth cascade, so
(6)
where k = 1, 2, …

The dynamic linear elements in the cascades can be determined in a number of ways. The method we have employed uses cross correlations of the input with the current residual. Best fitting of the current residuals was used to find the polynomial coefficients of the static nonlinearities. These resulting cascades are such that they drive the cross-correlations of the input with the residuals to zero. However, a few basic parameters have to be specified in order to identify a parallel cascade model, including the memory length of the dynamic linear element that begins each cascade, the degree of the polynomial static nonlinearity that follows the linear element (this polynomial is best fit to minimize the mean-square error (MSE) of the approximation of the residual), the maximum number of cascades allowable in the model, and a threshold based on a standard correlation test for determining whether a cascade’s reduction of the MSE justifies its addition to the model.

Augmented Kalman Filter

In the previous section, the parallel cascade model was briefly presented, together with a simple method for building up the model to approximate the behavior of a dynamic nonlinear system, given only its input and output. In order to apply PCI to 3D RISS/GPS integration, we propose the use of a KF-PCI module, where the role of PCI is to model the residual errors of GPS pseudoranges.

In full GPS coverage when four or more satellites are available to the GPS receiver, the KF integrated solution provides an adequate position benefiting from both GPS and RISS readings, and the PCI builds the model for the pseudorange errors for each visible satellite. The input of each PCI module is the pseudorange of the visible mth GPS satellite, and the reference output is the difference between the observed pseudorange and the estimated pseudorange from the corrected navigation solution.

The reference output has no corrections during full GPS coverage. It is only used to build the PCI model. Dynamic characteristics between system input and output help to achieve a residual pseudorange error model as shown in the Figure 2.

Figure 2. Block diagram of augmented KF-PCI module for pseudoranges during GPS availability.

During partial GPS coverage, when there are fewer than four satellites available, the PCI modules for all satellites cease training, and the available PCI model for each visible satellite is used to predict the corresponding residual pseudorange errors, as shown in Figure 3. The KF operates as usual, but in this instance the GPS observed pseudorange is corrected by the output of the corresponding PCI. The pre-built PCI models, only for the visible satellites during the partial outage, predict the corresponding residual pseudorange errors to obtain a correction. Thus, the corrected pseudorange can then be obtained.

During a full GPS outage, when no satellites are available, the KF operates in prediction mode and the PCI modules neither provide corrections nor operate in training mode.

FIGURE 3 Block diagram of augmented KF-PCI module for pseudoranges during limited availability of GPS.

Experimental Setup

The performance of the developed navigation solution was examined with road test experiments in a land vehicle. The experimental data collection was carried out using a full-size passenger van carrying a suite of measurement equipment that included inertial sensors, GPS receivers, antennae, and computers to control the instruments and acquire the data as shown in the Figure 4. The inertial sensors used in our tests are packaged in a MEMS-grade IMU. The specifications of the IMU are listed in Table 1.

Table 1. IMU specifications.

The vehicle’s forward speed readings were obtained from vehicle built-in sensors through the On-Board Diagnostics version II (OBD II) interface. The sample rate for the collection of speed readings was 1 Hz. The GPS receiver used in our integrated system was a high-end dual-frequency unit. Our results were evaluated with respect to a reference solution determined by a system consisting of another receiver of the same type, integrated with a tactical grade IMU.

This system provided the reference solution to validate the proposed method and to examine the overall performance during simulated GPS outages.
Several road test trajectories were carried out using the setup described above. The road test trajectory considered for this article was performed in the city of Kingston, Ontario, Canada, and is shown in Figure 5. This road test was performed for nearly 48 minutes of continuous vehicle navigation and a distance of around 22 kilometers. Ten simulated GPS outages of 60 seconds each were introduced in post-processing (they are shown as blue circles overlaid on the map in Figure 5) during good GPS availability. The trajectory was run four times with the simulated partial outages having three, two, one, and zero visible satellites, respectively. The case with no satellites seen is like a scenario that would occur in loosely coupled integration. The errors estimated by KF-PCI and KF-only solutions were evaluated with respect to the reference solution.

Experimental Results

The results in Figure 6 and Figure 7 demonstrate the benefits of the proposed PCI module. The main benefit of using PCI for pseudorange correction is the modeling capability, which enables correction of the raw GPS measurements. The benefit of more satellite availability can also be seen from these results. Figures 6 and 7 clearly show that both the average maximum position error and the average root-mean-square (RMS) position error are lower with the KF-PCI approach compared to the conventional KF, even when data from only one satellite is available.

Figure 6. Bar graph showing average maximum positional errors for all outages.

Figure 7. Bar graph for RMS positional errors for all outages.

To gain more insight about the performance of the proposed technique to enhance the aiding of the KF by correcting the pseudoranges, we can look at the results of KF-PCI and KF approaches with different numbers of satellites visible to the receiver for one of the artificial outages. Figure 8 shows a map featuring the different compared solutions during outage number 8. Eight solutions are presented for the cases of three, two, one, and zero satellites observed for the standard KF and KF with PCI. To get some idea of the vehicle dynamics during this outage, we can examine Figure 9, which depicts the forward speed of the vehicle as well as its azimuth angle as obtained from the reference solution. There is a significant variation in speed, with only a small variation in azimuth.

Figure 8. Performance of tightly coupled 3D-RISS during outage #8.

Figure 9. Vehicle dynamics (speed and azimuth) during GPS outage #8.

Figure 10 illustrates the performance differences between the KF-PCI and KF-only solutions for different numbers of satellites for this outage. Similar to Figure 7, Figure 10 shows the average RMS position differences between the KF-PCI and KF-only solutions and the reference solution (without the artificial outages). While the differences increase as the number of available satellites decreases, the accuracies may still be acceptable for many navigation purposes.

And while the differences between the KF-PCI and KF-only approaches for this particular outage are small, the KF-PCI approach consistently provides better accuracy.

Figure 10. Performance of PCI-KF (shades of blue for different number of satellites) and KF (shades of green for different number of satellites) of tightly coupled 3D-RISS during outage #8.

Conclusion

In this article, we have described a novel design for a navigation system that augments a tightly coupled KF system with PCI modules using low-cost MEMS-based 3D RISS and GPS observations to produce an integrated positioning solution. A PCI module is built for each satellite during good signal availability where the integrated solution presents a good position estimate. The output of each PCI module provides corrections to the GPS pseudoranges of the corresponding visible satellite during GPS partial outages, thereby decreasing residual errors in the GPS observations. This KF-PCI module was tested with real road-test trajectories and compared to a KF-only approach and was shown to improve the overall maximum position error during GPS partial outages.

Future work with PCI for modeling the residual pseudorange errors will consider replacing the KF with a particle filter to provide more robust integration and a consistent level of accuracy.

Acknowledgments

The research discussed in this article was supported, in part, by grants from the Natural Sciences and Engineering Research Council of Canada, the Geomatics for Informed Decisions (GEOIDE) Network of Centres of Excellence, and Defence Research and Development Canada. The equipment was acquired by research funds from the Directorate of Technical Airworthiness and Engineering Support, the Canada Foundation for Innovation, the Ontario Innovation Trust, and the Royal Military College of Canada. The article is based on the paper “Modeling Residual Errors of GPS Pseudoranges by Augmenting Kalman Filter with PCI for Tightly Coupled RISS/GPS Integration” presented at ION GNSS 2010, the 23rd International Technical Meeting of the Satellite Division of The Institute of Navigation held in Portland, Oregon, September 21–24, 2010.

Manufacturers

The test discussed in this article used a NovAtel Inc. OEM4 dual-frequency GPS receiver and a Crossbow Technology Inc., now Moog Crossbow IMU300CC-100 MEMS-grade IMU. The On-Board Diagnostics data was accessed with a Davis Instruments CarChip Pro data logger. The reference solutions were provided by a NovAtel G2 Pro-Pack SPAN unit, interfacing a NovAtel OEM4 receiver with a Honeywell HG1700 tactical grade IMU.

Umar Iqbal is a doctoral candidate at Queen’s University, Kingston, Ontario, Canada. He received a master’s of electrical engineering degree in integrated positioning and navigation systems from Royal Military College (RMC) of Canada, Kingston, in 2008. He also holds an M.Sc. in electronics engineering from the Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi, Pakistan, and a B.Sc. in electrical engineering from the University of Engineering and Technology, Lahore, Pakistan. His research focuses on the development of enhanced performance navigation and guidance systems that can be used in several applications including car navigation.

Jacques Georgy received his Ph.D. degree in electrical and computer engineering from Queen’s University in 2010. He received B.Sc. and M.Sc. degrees in computer and systems engineering from Ain Shams University, Cairo, Egypt, in 2001 and 2007, respectively. He is working in positioning and navigation systems for vehicular, machinery, and portable applications with Trusted Positioning Inc., Calgary, Alberta, Canada. He is also a member of the Navigation and Instrumentation Research Group at RMC. His research interests include linear and nonlinear state estimation, positioning and navigation by inertial navigation system/global positioning system integration, autonomous mobile robot navigation, and underwater target tracking.

Michael J. Korenberg is a professor in the Department of Electrical and Computer Engineering at Queen’s University. He holds an M.Sc. (mathematics) and a Ph.D. (electrical engineering) from McGill University, Montreal, Quebec, Canada, and has published extensively in the areas of nonlinear system identification and time-series analysis.

Aboelmagd Noureldin is a cross-appointment associate professor with the Department of Electrical and Computer Engineering at Queen’s University and the Department of Electrical and Computer Engineering at RMC. He is also the founder and leader of the Navigation and Instrumentation Research Group at RMC. He received the B.Sc. degree in electrical engineering and the M.Sc. degree in engineering physics from Cairo University, Giza, Egypt, in 1993 and 1997, respectively, and the Ph.D. degree in electrical and computer engineering from The University of Calgary, Calgary, Alberta, Canada, in 2002. His research is related to artificial intelligence, digital signal processing, spectral estimation and de-noising, wavelet multiresolution analysis, and adaptive filtering, with emphasis on their applications in mobile multisensor system integration for navigation and positioning technologies.