Comparison of Different Bounding Methods for Providing GPS Integrity Information
Hani Dbouk and Steffen Schön, Institut für Erdmessumg, Leibniz Universität Hannover, Germany
Nowadays, GPS is applied for a variety of highly demanding tasks like e.g. precision landing approaches. Thus, the quality and trust that we put into the GPS navigation solution must be extremely high: Integrity measures this performance, i.e. the ability of the navigation system to timely warn the user when error thresholds so-called alert limits are transgressed. One of the primary tasks in Receiver Autonomous Integrity Monitoring (RAIM) is to evaluate the integrity risk, or a protection level, which is an integrity bound on the positioning error. Integrity risk evaluation is needed when designing a navigation system to meet predefined integrity requirements, and it is needed operationally to inform the user whether to abort or to pursue a mission especially for safety critical application such as: landing approach in civil aviation. Integrity risk evaluation involves both assessing the fault detection capability and quantifying the impact of undetected faults on position estimation errors. Both the RAIM detector and the estimator have been investigated in literature. With regard to fault detection, two RAIM algorithms have been widely implemented over the past 25 years: chi-squared RAIM also called parity-based or residual based RAIM (M. Sturza 1988) and (R. Brown 1992) and Solution Separation RAIM (M. Brenner 2006). Differences between the two algorithms have been investigated in (M. Joerger, F. Chan, B. Pervan 2014). However, it is still unclear which one provide the lowest integrity risk. This depends on the system itself, for example: equipment noise. Moreover, researchers have explored the potential of replacing the conventional Least- Squares (LS) process with a Non-Least-Squares (NLS) estimator to lower the integrity risk in exchange for a slight increase in nominal positioning error (L. Young 2008), (J. Blanch, et.l. 2012), (M. Joerger et al., 2015) and (M. Joerger et al., 2016). The resulting methods show promising reductions in integrity risk, but are computationally expensive for real-time implementations.
However, a purely statistical determination will not be always adequate. In the past few years new RAIM approaches have been proposed based in interval mathematics, where a robust Set Inversion Via Interval Analysis (RSIVIA) used to compute the three-dimensional bounding zone in real time (V. Drevelle et al., 2009 and 2010) and (V. Drevelle et al., 2013). This new approach differs from the usual Gaussian error model, since the satellites positions and the pseudo-ranges measurements are represented by intervals which bounding the true values of the satellites position and the pseudo-range measurements with a particular confidence. Subsequently, the user position will be guaranteed to be in a bounded zone, which is a direct solution of the non-linear navigation equation.
In this work we propose different deterministic bounding methods to be applied on GPS positioning, namely: Least Squares Adjustments based on Interval Analysis (LSA-IA), extension of LSA-IA by means of Zonotopes, Linear Programing (LP) applied to linearized navigation equation by Taylor expansion, and finally solving the non-linear navigation equation by Set Inversion Via Interval Analysis (SIVIA). We compare the mathematical properties of the methods, and provide geometrical interpretation with respect to the navigation problem (e.g. form and orientation of the bounding area w.r.t. line-of-sight and number of satellites in view). In these approaches, an error bound is applied to the observed minus computed values to bound remaining observation uncertainty. This error bound should be taken with prior knowledge on the system performance, or depending on the desired range of acceptance biases. Thus, interval mathematics and set theory are adequate tools to describe this type of uncertainty.
The main characteristics of the analyzed methods are:
LSA-IA provides an estimated position identical with the classical least squares adjustment and an overestimated bounding box. The solution is guaranteed to be inside this box if there is no bias in the pseudo-range measurements, otherwise hypothesis tests based on parity vector are performed to detect and exclude the faulty measurements with certain probability of false alarm and probability of missed detection. The faces of box are always parallel to the coordinate system’s axes. Thus, information is lost about the true shape. To overcome this aspect a Zonotopes extension is applied. The bounding Zonotopes represent the factual range of the least squares problem under interval uncertainty. The faces of the Zonotopes depend on the satellites geometry and are not affected by the selection of coordinate system and its orientation.
LP problem is constructed in order to compute the minimum bounding zone by means of convex polytopes. In our implementation 16 objective (linear combination of the state vector) functions are applied to optimize the bounded region. LP is efficient tool to detect and exclude biases from the measurements, where the solution of LP is an empty set or non-convex when one or more measurements are biased. The polytope solution represents the Horizontal Protection Level (HPL) by projecting it onto the horizontal plan and a Vertical Protection Level (VPL) by taking the lowest and highest points in the polytopes.
SIVIA computes an approximation of the position confidence domain based on contraction and interval intersection. It is guaranteed to contain the true position if all the measurement intervals (error bound) are consistent with the true error. To get a high confidence level we have to enlarge the error bound. However, if the measurements are not consistence with the error bound, we get an empty solution. To detect the non-consistent measurement a q-relaxed solver is used. Moreover, different error bound with different confidence levels are used in order to assess the minimum position confidence domain with a certain confidence level.
A simulation of a trilateration (GPS positioning with receiver clock synchronized to the satellite clock) has been performed using the proposed methods. We considered different situation to have better understanding of the bounding solutions; error free measurements, measurements with white noise, as well as different number of satellites and satellite geometry. Finally, we introduced biases with different magnitude to one of the measurements. As a preliminary result, LSA-IA provides overestimated interval boxes and the size of the box depends only on the magnitude of the error bounds. It is the same for a different number of satellites. However, Zonotopes provide the factual range. The shape of the Zonotopes depends on the number of satellites and satellites geometry. With increasing number of satellites, Zonotopes have more edges and become more rounded. Their volume slightly decreases as the number of satellites increases. In contrast, the bounding zone from LP and SIVIA coincides (SIVIA solution is slightly bigger). It decreases as the number of satellites increases, due to fact that more constraints are applied. The edges of the polytope are always perpendicular to the line of sight (LOS) between receiver and satellites. When we introduce a bias to one measurement, the bounding zone from LP and SIVIA decreases in the LOS direction with respect to the biased measurement. Subsequently, it gets empty and thus errors are detectable at a certain bias value. Moreover, the minimum detectable bias depends on the deterministic bound and standard deviation of the random observation noise. In order to detect all biases greater than an error bound with certain confidence level, a multi-error bound algorithm is proposed and applied. We will show that this approaches efficiently detects any bias greater that the minimum error bound. We will compare this strategy to the classical statistic outlier detection and show the benefits of the methods.
Further simulations will be performed for the GPS case where the receiver clock bias will be considered. To this end a sensitivity analysis of the GPS correction methods is carried out to derive observation intervals. The size and shape of the parameter bounding regions obtained with the different approaches will be discussed. Finally, real GPS code data from a kinematic test drive will be analyzed.