View the Equations for this article
Various designs of inertial/GNSS integrated navigation systems exist, with different architectures depending on the quality of sensors, the mission, the dynamics of the vehicle, and the non-linearity of the dynamics model, measurement model, or both.
View the Equations for this article
Various designs of inertial/GNSS integrated navigation systems exist, with different architectures depending on the quality of sensors, the mission, the dynamics of the vehicle, and the non-linearity of the dynamics model, measurement model, or both.
The techniques and solutions used for integration are generally “loosely coupled,” “tightly coupled,” “ultra tightly,” and “deeply coupled” navigation systems. Figure 1 illustrates a loosely coupled INS/GNSS architecture under non-Gaussian measurement noise.
However, before selecting the best system architecture for an integrated navigation system (INS), we should first calculate the lower bound of state estimation exactly, if possible, or approximately if it requires heavy and/or complex mathematical operations.
In general, let us consider a system for which a lower bound is sought (in our case, an inertial/GNSS system):
Equation (1)
where x is the state vector being estimated, f(x) represents the system model, w is the process noise with covariance matrix Q, z is the measurement vector, h(x) is the measurement model, and η is the measurement noise with covariance matrix R.
For linear systems with uncorrelated white Gaussian process and measurement noises, the lower bound is called the Cramer Rao Lower Bound (CRLB). The definition of CRLB is based on the Fisher Information Matrix, which in turn is defined as:
Equation (2)
where p(x,z) is the likelihood function.
The main advantage to calculating the CRLB is to determine the value of the best estimation of the state variables amongst all estimators. This provides advance information about whether the goals of a system are achievable or not.
Specifically, CRLB is calculated offline around the true state values. When these values are not available, online approximation techniques must be developed using the estimated values instead of the true ones. (For details, see the article by L. Zuo, R. Niu, and P. K. Varshney listed in the Additional Resources section at the end of this article.)
This article focuses on filtering algorithms applied to inertial/GNSS integrated navigation systems based on non-linear dynamic inertial kinematic models and the calculation of their corresponding approximated lower bounds.
Inertial measurement units (IMUs) typically contain three orthogonal rate-gyroscopes and three orthogonal accelerometers, measuring angular velocity and linear acceleration, respectively. Ideally, the output of the rate-gyroscopes is written as
Equation (3)
In practice, however, the outputs contain errors and are written as
Equation (4)
Integrating these angular rates over time yields the updated attitude information for the system:
Equation (5)
Equation (6)
Similarly, accelerometers outputs can be written as
Equation (7)
Two integrations subsequently yield velocity and position updates as follows:
Equation (8)
Equation (9)
where g is the estimated gravity vector and Δt is the data period. Collectively, equations (3) to (9) describe the system model.
For the purpose of our discussion here, the measurement model is assumed to consist of GNSS-observed position (PGNSS), velocity (VGNSS), and attitude (AGNSS) — the latter derived using a multiple antenna system. Correspondingly, we can write the observation matrix as
Equation (10)
Having defined the relevant models, let’s look at two ways to approximate the lower bound. The first assumes Gaussian errors and uses the non-linear approximation of the Kalman filter called the extended Kalman filter (EKF). The second approach considers the full non-linear model and non-Gaussian errors.
Approximating the CRLB Using an Extended Kalman Filter
Although for brevity we omit certain details here (see the Additional Reading section at the end of this article for more information), the derivation of the lower bounds based on the EKF are given by
Equation (11)
Equation (12)
Equation (13)
Where Fk=∇xkƒTxk(xk) is the Jacobian matrix of ƒTxk(xk) and Hk=∇xkhTxk(xk) is the Jacobian matrix of hTxk(xk) and P0 is the covariance matrix of the initial estimate. Comparing these equations with the update step in an EKF, it is clear that the approximated CRLB for non-linear state estimation is exactly analogous to the EKF covariance matrix, replacing the state estimate with its real value.
Based on this, experienced users of extended Kalman filters — and other variants of non-linear filters — can approximate the CRLB directly using well-known EKF equations. For example, Figure 2 shows the approximated CRLB for the east velocity and yaw attitude along with the corresponding mean square error (MSE) computed using an EKF, an unscented Kalman filter (UKF), a central difference Kalman filter (CDKF) and the cubature Kalman filter (CKF). (See the articles by I. Arasaratnam and S. Haykin, and also O. Straka, J. Dun´ık, and M. Simandl listed in Additional Resources.)
Approximating CRLB for Non-Linear Systems in the Presence of Non-Gaussian Errors
Typical inertial/GNSS integration approaches usually adopt the Gaussian error assumption. However, in practice, especially during urban navigation and when several sources of GNSS interference are present, this assumption does not hold.
To this end, the best non-Gaussian noise model that has been presented in specialized literature is the Huber estimator (in the article by C. Karlgaard and H. Schaubt, Additional Resources) using a robust estimator algorithm, which is able to handle multipath GNSS signals as well as intentional and unintentional interferences.
Before explaining the approximation of the lower bound, let us describe the method used to estimate state variables when non-Gaussian errors are present. In this case, non-linear filtering variants given in previous sections do not perform well and need to be transformed into robust forms resilient to non-Gaussian measurement errors.
Amongst the different Bayesian estimation algorithms, the particle filter is the most generic since it can handle non-Gaussian errors as well as non-linear systems. However, developing an accuracy bound for this case is very difficult. Instead, a technique called Gaussian mixture filter is applied to EKF, Sigma Point KF (SPKF) and CKF (as discussed in the article by I. Arasaratnam et alia, 2007).
Gaussian mixture models are based on the representation of any non-Gaussian distribution as the sum of multiple Gaussian densities with different “weights.” For the inertial/GNSS algorithm discussed here, the noise is assumed to be composed of two Gaussian components. With this in mind, two approximations to the CRLB are possible, as described in the following sections.
Use of Kullback–Leibler Approach to Gaussian Mixture Reduction
A Kullback-Leibler approach can be applied to inertial/GNSS integrated navigation systems and consists of successively merging pairs of components (“twin density”) and replacing them with a single Gaussian component with equivalent mean and variance values calculated based on the sum of two Gaussian random variables.
The Kullback-Leibler (KL) discrimination of probability density functions f2 from f1 is defined by
Equation (14)
Suppose we are given the following mixture of two Gaussian components:
Equation (15)
Equation (16)
with which we need to approximate this mixture by a single Gaussian density. The best and easiest candidate for this approximation is given by the Gaussian density with mean μ and variance P.
Based on the minimal Kullback-Leibler discrimination principle, a strong and direct candidate to this approximation is given by
Equation (17)
Equation (18)
We can then approximate the CRLB using equations 11–13, thus yielding the posterior CRLB (PCRLB) of non-linear Gaussian systems. Effectively, this approach is based on transforming the non-Gaussian non-linear estimation of an inertial/GNSS integrated navigation system into the classic well-known non-linear estimation problem under Gaussian assumptions (see Figure 3).
Use of Gaussian Mixture Approach to Approximate CRLB under Non-Gaussian Noises Assumption
Similar to the discussion in the previous section, this approach approximates the non-Gaussian errors as Gaussian and then approximates the CRLB from this simplified model. However, in this case, a bank of Kalman filters are used, each assumed to process one of the Gaussian mixture components. The outputs of the filters are then combined to form the final estimate. This concept is illustrated in Figure 4.
The idea here is to obtain an optimal approximation based on parallel optimal estimations. In this way, inertial/GNSS integrated navigation systems could be implemented using the approximated optimal lower bound when the Gaussian assumption is not followed. Sample results of this are shown in Figure 5.
As can be seen, the differences between Gaussian mixture EKF (GMEKF) and the approximated CRLB (ACRLB) are nearly the same, as expected. However, if we use a standard EKF, the results are considerably worse because the filter is not designed to handle non-Gaussian errors. This demonstrates the effectiveness of properly selecting the estimation algorithm based on the input noise characteristics.
Summary
The design of optimal inertial/GNSS integrated navigation systems begins with the calculation or the estimation of the lower bound of the system before its development. This article has looked at various ways of obtaining an approximation to the CRLB. It is hoped that online approximation of these lower bounds may soon be applied to modern non-linear filtering approaches.
Additional Resources
[1] Arasaratnam, I., and S. Haykin, “Cubature Kalman Filtering,” IEEE Transactions on Automatic Control, vol. 54, no. 6, pp. 1254–1269, June 2009
[2] Arasaratnam, I., and S. Haykin and J. Elliot (2007), “Discrete Time Nonlinear Filtering Algorithms Using Gauss-Hermite Quadrature,” Proceedings of the IEEE, Vol. 95, No. 5, May 2007
[3] Benzerrouk. H, and A. V. Nebylov, “Robust Nonlinear Filtering Applied to Integrated Navigation System under Non Gaussian Measurement Noise Effect,” in Proceedings of IEEE Aerospace Conference 2012, pp. 1–8
[4] Karlgaard, C. D., and H. Schaubt, “Huber-Based Divided Difference Filtering,” AIAA Journal of Guidance, Control and Dynamics, vol. 30, no. 3, pp. 885-891, 2007
[5] Runnalls, A. R., “Kullback-Leibler Approach to Gaussian Mixture Reduction,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 43, No. 3, pp. 989–999, July 2006
[6] Straka, O., and J. Dun´ık and M. Simandl, “Gaussian Sum Unscented Kalman Filter with Adaptive Scaling Parameters,” 14th International Conference on Information Fusion, Chicago, Illinois, USA, 2011
[7] Tichavsky, P., and C. H. Muravchik and A. Nehorai, “Posterior Cramer Rao Bounds for Discrete Time Nonlinear Filtering,” IEEE Transactions on Signal Processing, Vol. 46, No. 5, pp. 1386–1396, May 1998
[8] Zuo, L., R. Niu, and P. K. Varshney, “Conditional Posterior Cramér–Rao Lower Bounds for Nonlinear Sequential Bayesian Estimation,” IEEE Transactions on Signal Processing, Vol 59. No.1, 2011
