Global Navigation Satellite System Engineering, Policy and Design

Can elliptical Galileo satellites be used for RTK?

Washington View: The Big Wheels Continue to Turn-Rolling to 5G on the River

Q: What is a factor graph?

The factor graph represents the global function of many variables as the product of local functions with a smaller subset of variables. This is not a method, but a framework that can use its local structure to model any system, that is, each variable depends on only a few other local variables and is independent of each other. This locality makes it useful for modeling various problems, including mapping, visual inertial odometry, motion planning, trajectory estimation, and deep learning. The use of GNSS factor graphs can achieve more seamless integration between GNSS and other sensor modes.

Junakdas, West Virginia University

Ryan Watson, Johns Hopkins University

Answer: Probabilistic modeling is a very important tool for any type of estimation problem. The graphical model uses the vertices in the graph to model the known and unknown variables of the system, and defines the edges between them to represent their relationship. Due to the inherent uncertainty of system modeling, these relationships are probabilistic. Factor graphs connect many types of these graphical models, such as Markov random fields, Bayesian networks, and Tanner graphs. A factor graph is defined as a bipartite graph with two types of vertices: one is the vertex of the variable to be estimated (ie, the state vector), and the other is the coding constraint (for example, a set of GNSS observations) applied to the variable vertex.

Edges can only exist between factor vertices and variable vertices. A factor vertex represents a local function that depends on the variable vertex of its shared edge. A common estimation problem in robotics uses a factor graph framework to estimate unknown robot poses and other parameters that depend on the problem. This is achieved by solving the maximum a posteriori (MAP) problem, which maximizes the product of the factors that are the probability constraints between the state and the measurement.

The factor graph has been regarded as an alternative framework for solving estimation problems and has proven to be very effective for specific applications, including simultaneous localization and mapping (SLAM). Due to the flexibility of the method and the ease of implementation granted by the availability of open source graphics optimization libraries such as GTSAM and g2o, the framework has attracted widespread use.

Although the factor graph framework has proven to be beneficial for many applications, the framework can be used in a way (ie, its generalization) equivalent to existing state estimation implementations (for example, Kalman filter and its many variants) . To start this comparison, we noticed that the factor graph finally encodes an objective function, which is solved by repeated re-linearization by non-linear optimization procedures (eg, Gauss-Newton, Levenberg-Marquardt). Previous work has shown that iterating the extended Kalman filter (EKF) measurement update and re-linearizing the system model between iterations is equivalent to Gauss-Newton optimization. This shows that, under a specific set of constraints, the factor graph running in batch mode is equivalent to the backward smooth EKF, which re-linearizes the system and the observation model and iterates.

Factor graph optimization has some advantages over standard non-iterative Kalman filters, which may be valuable for certain applications. First, like any optimization problem, it uses multiple iterations to minimize cost, instead of only one iteration for each state like a standard Kalman filter. Second, unlike the single linearization performed by the standard Kalman filter, it also linearizes the nonlinear measurement model for each iteration step of each state. The factor graph has also been shown to make better use of the temporal correlation between past and current periods, which is attributed to the batch nature of the estimation method.

In particular, when running in batch mode, the factor graph will be equivalent to a forward filter and will be smoothed backwards after each measurement update. For GNSS/INS applications, these advantages are supported by experimental results, in which factor graphs perform better than EKF in urban environments. It seems that as new measurements accumulate over a longer period of time, batch estimation may lose real-time performance. But this can be avoided by exploiting the sparsity of the graph. In addition, the sliding window method can also be used to reduce the computational cost. That is, instead of optimizing all states, only partial windows of states are used (for example, like a fixed-lag Kalman smoother).

It has been found that the window size is critical for good optimization results and may depend on environmental conditions. In addition to fixed lag smoothing, the incremental smoothing and mapping (isam2) formula achieves real-time performance by converting the factor graph into a Bayesian tree (a graphical representation of the square root information matrix (SRIF)) when adding new constraints. The vertices of the Bayesian tree represent the group of factor graph states. Therefore, only the states included in the same group as the state with the new constraints need to be re-linearized. The two authors used isam2 in the GNSS factor map to show higher positioning performance than the traditional EKF precise point positioning (PPP) method. Another researcher applied factor graph optimization to GNSS and GNSS-Real-time Kinematic (RTK) positioning problems and showed better performance than EKF.

The two authors described in detail the creation factors of using GNSS observations in the 2018 IEEE/ION/PLANS paper. The commonly estimated states in the GNSS factor graph are receiver position, tropospheric delay, carrier phase deviation, and receiver clock deviation. Figure 1 provides a visual representation of the GNSS factor graph, where ψ represents any probability constraints that may exist between the state and the measured value. In this specific implementation, ψp encodes the prior beliefs of each state, which depends on the specific data set and environmental characteristics. ψb is the motion constraint between two consecutive states along the trajectory, for example, it can be combined with motion data from an inertial measurement unit (IMU) or wheel odometer.

A common example of ψb used in GNSS/IMU navigation is the use of IMU pre-integration to calculate the factor of the displacement between two factor map positions, where multiple IMU measurements are integrated between them. Finally, ψm is the measurement constraint between the state and the measured value sensed from that state, such as GNSS pseudorange or carrier phase measurement. To find the MAP estimate of the GNSS factor graph, we can find the state set that maximizes the product of the factors. However, in practice, this optimization problem can be greatly simplified by using the Gaussian noise assumption, which converts the problem from the product of the maximization factor to a nonlinear least squares problem, where each component of the sum is a Mahalanobis cost, which represents the return The sum of squared residuals is shown in Equation 1, where f(*) is the mapping between states in different periods, and h(*) is the mapping from state space to observation space.

As mentioned earlier, the factor graph framework can also easily add existing and new robust estimation methods, which helps reduce location errors during spoofing attacks or large noise caused by multipath or atmospheric effects. The following discussion lists some robust methods applicable to GNSS.

Switch constraint (SC) is a lifting optimization method, which defines an observation weight function Ψ(), which is a function of the switch variable s, which is estimated in conjunction with the state parameters of interest. The SC method was originally developed for robust loop closure detection in SLAM, and then extended to GNSS for multipath mitigation. When using switch constraints, the pseudorange factor cost is expressed as a scaled version of the Markov cost between the predicted and actual measurements:

The function Ψ is the linear function of the switch variable. Add a priori factor to each of these switch variables to prevent optimization from zeroing all sk. If the same satellite is observed at the next time step, a conversion factor can also be added to simulate the change between sk-1 and sk. These switch functions help to automatically reduce the weight of erroneous measurements (for example, suspicious multipath measurements) and are considered to perform better than computationally expensive ray tracing methods.

In the SC extension called Dynamic Covariance Scaling (DCS), the switching variables are taken from the optimization method and calculated separately using residuals, current measurement uncertainty, and a priori switching uncertainty. After calculating sk, the information matrix related to the GNSS observation factor is scaled by Ψ(sk)2.

The Maximum Mixture (MM) was also developed to use Gaussian Mixture Model (GMM) to solve the wrong loop closure problem, but instead of the summation operator that is not suitable for maximum likelihood when using multimodal uncertainty models, the objective function Is converted to use the max operator, as shown in Equation 3.

The advantages of SC, DSC, and MM have been evaluated for GNSS factor graph applications with real-world data. Studies have shown that when optimizing degraded GNSS observations, substantial positioning improvements can be obtained by using robust estimation techniques.

In order to extend the maximum mixing work, the two authors and colleagues proposed to learn GMM based on clustering of observation residuals at runtime. Initially, this work was implemented in a batch processing framework; however, it was later extended to incremental work through an effective method for incrementally merging GMM.

M-estimators has also been tested in batch form within the GNSS framework recently and found that its performance is better than non-robust estimators. M-estimators assume that the loss function is different from the squared loss function. The squared loss function is highly sensitive to outliers because it will increase sharply for larger residual values. Therefore, a set of loss functions is introduced, and their growth is not as positive as the squared loss function. The Huber cost function provided in Equation 4 is such a function.

When modifying the objective function to use the m estimator, the optimization problem takes the form described in Equation 5.

Where ri(x) is the residual of each measurement, and σ is the scale parameter.

Increasing the ∆ parameter makes the function closer to the square loss function. Equation 5 can be solved iteratively using the weighted least squares method. Choosing a suitable ∆ parameter is not simple, because it depends on the measurement noise statistics. Some M estimators have corresponding elliptical distributions to estimate Δ and the state in the Expectation Maximization (EM) framework. Another method jointly optimizes the state and parameters of computer vision applications.

The factor graph provides greater flexibility in the M-estimator application, because it can not only help reduce the weight of the current measurement, but also help change the weight of the past measurement. If it is later found to be an outlier, it can also help to completely delete some past measured values, and in the Kalman filter, the contribution of past measured values ​​cannot be changed in real-time. Most graphics optimization libraries also have built-in functions for using robust cost functions, which is also very helpful.

Finally, the robust estimation technique derived by Yang et al. Combining two famous ideas in computer vision, Black-Rangarajan duality and gradient non-convexity, it uses a robust cost function to iteratively solve the point cloud registration problem. According to the Black-Rangarajan duality, Equation 5 can be rewritten as Equation 6:

Where wi is the weight of the i-th measurement, and Φρ is a penalty term that depends on the weight and robustness cost ρ.

Hierarchical non-convex (GNC) is a method to minimize the non-convex function f without facing the local minimum problem. The idea is to replace the function f with a surrogate function fµ, whose convexity is controlled by the parameter µ. The optimization starts with the convex form of fµ, and µ is iteratively changed to increase the non-convexity. Combining these two methods, Yang et al. Two problems in Equation 5 are solved:

• Avoid local minima while optimizing a robust cost function

• Convert Equation 5 into a weighted least squares problem, which is always easier to solve.

The similarity between this issue and GNSS should be obvious to readers. Wen et al. It shows the importance of applying this robust estimation technique to the GNSS factor map in mitigating multipath effects in urban canyons. The batch nature of most of these robust estimation methods makes them suitable for factor graphs rather than EKF.

EKF has always been the first choice based on GNSS state estimation because of their simplicity and high computational efficiency, and the GNSS observation model can be well modeled by linear approximation, and it can usually represent Gaussian error well. Nevertheless, in some cases, the radio navigation community may benefit from factor graph optimization.

On the one hand, recent work has emphasized the potential uses and benefits of Signal of Opportunity (SOP) in radio navigation applications. SOP may include cell phone signals and low earth orbit satellites. The use of SOP usually needs to address unknown or very uncertain transmitter position and clock offset. Therefore, this type of problem has many similarities with SLAM, and similar benefits can be obtained from the use of factor graphs (as recognized by vision or LIDAR-based posture graph SLAM).

Next, as discussed in the context of GNSS, many robust estimation techniques for factor graphs have been developed. For the use of GNSS urban environments prone to multipath errors, these robust factor graphs may be beneficial. For example, the winning solution of Google's smart phone decimeter challenge, which includes collecting various data sets of different environment settings, is indeed a factor graph implementation.

Finally, the adoption of factor graphs may be beneficial because the factor graph framework has become the standard state estimation paradigm in robots and autonomous communities (ie, almost all sensor modes, except GNSS, are utilized and displayed-factor graph framework) . The use of GNSS factor graphs can achieve more seamless integration between GNSS and other sensor modes. The integration of multiple information sources is the recognized key to any critical navigation system.

(1) D. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.

(2) BJ Frey, FR Kschischang, H.-A. Loeliger and N. Wiberg, "Factor Graphs and Algorithms", "Communication Control and Computing Annual Allerton Conference Proceedings", Volume 1. 35. Citeseer, 1997, pp. 666-680.

(3) F. Dellaert, "Factor Graphs: Structures Using Robotics", Annual Review of Control, Robotics, and Autonomous Systems, Vol. 4. Pages 141-166, 2021.

(4) F. Dellaert, M. Kaess and others, "Factor Graph of Robot Perception", 2017.

(5) F. Dellaert, "Factor graphs and gtsam: a hands-on introduction", Georgia Institute of Technology, Technology. Representative, 2012.

(6) G. Grisetti, R. Ku¨mmerle, H. Strasdat and K. Konolige, "g2o: a general framework for (hyper)graph optimization", IEEE International Conference on Robotics and Automation (ICRA) Proceedings, Shanghai, China, 2011 Years, pages 9-13.

(7) BM Bell and FW Cathey, "As an Iterative Kalman Filter Update of the Gauss-Newton Method", IEEE Automatic Control Transactions, Vol. 38, no. 2. Pages 294-297, 1993.

(8) ML Psiaki, "Smooth Backward Extended Kalman Filter", Journal of Guidance, Control and Dynamics, Vol. 28, no. 5. Pages 885-894, 2005.

(9) W. Wen, T. Pfeifer, X. Bai, and L.-T. Hsu, "Factor graph optimization of gnss/ins integration: comparison with extended Kalman filter", NAVIGATION, Journal of the Nautical Society, No. 1 roll. 68, no. 2. Pages 315-331, 2021.

(10) D. Wilbers, C. Merfels and C. Stachniss, "Sliding window factor graph localization on third-party maps for autonomous driving", 2019 International Conference on Robotics and Automation (ICRA). IEEE, 2019, pages 5951-5957.

(11) M. Kaess, H. Johannsson, R. Roberts, V. Ila, JJ Leonard, and F. Dellaert, "isam2: Using Bayesian Trees for Incremental Smoothing and Mapping", International Journal of Robotics Research, Vol. . 31, no. 2. Pages 216-235, 2012.

(12) M. Kaess, V. Ila, R. Roberts and F. Dellaert, "Bayesian Tree: Algorithmic Basis for Probabilistic Robot Mapping", Robot Algorithm Basis IX. Springer, 2010, pp. 157-173.

(13) RM Watson and JN Gross, "Using the Incremental Graph Optimizer to Evaluate the Convergence of Kinematics Precise Point Positioning", 2018 IEEE/ION Position, Position, and Navigation Symposium (PLANS), 2018, pages 589-596 .

(14) W. Wen and L.-T. Hsu, "Using factor graph optimization to achieve robust gnss positioning and real-time kinematics", arXiv preprint arXiv: 2106.01594, 2021.

(15) C. Forster, L. Carlone, F. Dellaert, and D. Scaramuzza, "Imu pre-integration on manifolds for effective maximum posterior estimation of visual inertia." Georgia Institute of Technology, 2015.

(16) N. Sunderhauf and P. Protzel, "Switchable Constraints for Robust Attitude Graph Slam", 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2012, pages 1879-1884.

(17) C. Zach and G. Bourmaud, "Iterative Improvement of Robust Cost Optimization", BMVC, 2017.

(18) N. Sunderhauf, M. Obst, G. Wanielik, and P. Protzel, "Multipath mitigation in gnss-based positioning using robust optimization", 2012 IEEE Smart Vehicle Symposium. IEEE, 2012, pages 784-789.

(19) P. Agarwal, GD Tipaldi, L. Spinello, C. Stachniss, and W. Burgard, "Robust map optimization using dynamic covariance scaling", 2013 IEEE International Conference on Robotics and Automation. IEEE, 2013, pp. 62-69.

(20) E. Olson and P. Agarwal, "Hybrid Network Reasoning for Robust Robot Mapping", International Journal of Robot Research, Vol. 32, no. 7, pp. 826-840, 2013.

(21) T. Pfeifer, P. Weissig, S. Lange and P. Protzel, "Robust Factor Graph Optimization-Comparison of Sensor Fusion Applications", 2016 IEEE 21st International Conference on Emerging Technologies and Factory Automation (ETFA). IEEE, 2016, pages 1-4.

(22) RM Watson and JN Gross, "Using graph optimization for robust navigation in degraded gnss environment", in Proceedings of the 30th International Conference on Satellite Division of the Institute of Navigation (ION GNSS 2017), 2017, p. 2906 2918.

(23) RM Watson, JN Gross, CN Taylor, and RC Leishman, "Achieving Robust State Estimation Through Covariance Adaptation of Measurement Errors", IEEE Transactions on Aerospace and Electronic Systems, Vol. 2. 56, no. 3. Pages 2026-2040, 2019.

(24) ——, "Robust incremental state estimation through covariance adaptation", IEEE Robotics and Automation Letters, Vol. 5. No. 2. Pages 3737-3744, 2020.

(25) M. Bosse, G. Agamennoni, I. Gilitschenski, etc. Robust estimation and application in robotics.

(26) OG Crespillo, A. Andreetti, and A. Grosch, "Design and Evaluation of Robust M Estimator for Gnss Positioning in Urban Environment", Proceedings of the 2020 International Technical Conference of the School of Navigation, San Diego, California, USA, 2020 Years, pages 21-24.

(27) PJ Huber, "Robust Estimation of Position Parameters", in a statistical breakthrough. Springer, 1992, pages 492-518.

(28) G. Agamennoni, P. Furgale, and R. Siegwart, "Self-tuning m-estimators", at the 2015 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2015, pages 4628-4635.

(29) JT Barron, "Universal and Adaptive Robust Loss Function", in Proceedings of the IEEE/CVF Computer Vision and Pattern Recognition Conference, 2019, pages 4331-4339.

(30) H. Yang, P. Antonante, V. Tzoumas, and L. Carlone, "The Asymptotic Nonconvexity of Robust Spatial Perception: From Non-Minimum Solver to Global Outlier Rejection", IEEE Robotics and Automation Letters, Vol. 2 . 5. No. 2. Pages 1127-1134, 2020.

(31) MJ Black and A. Rangarajan, "On the unification of production line processes, rejection of outliers, and robust statistics in early vision applications", International Journal of Computer Vision, Volume 2. 19. No. 1, pp. 57-91, 1996.

(32) A. Blake and A. Zisserman, visual reconstruction. MIT Press, 1987.

(33) W. Wen, G. Zhang and L.-T. Hsu, "Gnss outlier mitigation is optimized by progressive non-convexity factor graph", arXiv preprint arXiv: 2109.00667, 2021.

(34) K. Shamaei and ZM Kassas, "Receiver Design and Time of Arrival Estimation for Opportunistic Positioning Using 5g Signals", IEEE Wireless Communication Transactions, 2021.

(35) ——, "LTE Receiver Design and Multipath Analysis for Navigation in Urban Environment", NAVIGATION, Journal of Navigation Academy, vol. 65, no. 4. Pages 655-675, 2018.

(36) JJ Morales, J. Khalife, US Cruz, and ZM Kassas, "Orbital modeling for simultaneous tracking and navigation using leo satellite signals", in the 32nd International Technical Conference of the Satellite Division of the United States Institute of Navigation (ION) GNSS 2019), 2019, pages 2090-2099.

(37) T. Suzuki, "First Prize Winner of the Smart Phone Decimeter Challenge: Global Optimization of Position and Speed ​​Through Factor Graph Optimization", in the ION GNSS 2021 Proceedings, 2021, pages 2974-2985.

Shounak Das is a PhD. West Virginia University student. He has a Master of Technology in Aerospace Engineering (M.Tech) from the Indian Institute of Technology.

Ryan Watson completed his PhD. At West Virginia University, he now works in the Autonomous Systems Group at the Johns Hopkins Applied Physics Laboratory.

Jason Gross is an associate professor and research associate director in the Department of Mechanical and Aerospace Engineering at West Virginia University, where he received his Ph.D.

Can elliptical Galileo satellites be used for RTK?

Washington View: The Big Wheels Continue to Turn-Rolling to 5G on the River

Copyright © Inside GNSS Media & Research LLC. all rights reserved. | Privacy Policy

157 Broad Street, Suite 307 | Red Bank, New Jersey 07701, USA, phone (732) 741-1964

Can elliptical Galileo satellites be used for RTK?

Washington View: The Big Wheels Continue to Turn-Rolling to 5G on the River