1 of 30

Learning GNSS Positioning Corrections for Smartphones using Graph Convolution Neural Networks

Adyasha Mohanty and Grace Gao

ION GNSS+ 2022, Session E2a, Sept 21, 2022

2 of 30

Android Positioning: The New Era

1

Our smartphones comprise about ~1.5 billion GNSS receivers^[1]manufactured in the world

Mapping

Lane-level Positioning

Augmented/Mixed Reality

[1] https://insidegnss.com/smartphone-based-gnss-positioning-today-and-tomorrow/

3 of 30

Challenges and Opportunities

Higher noise and lower signal levels
~5 m^[2] of positioning accuracy
Degraded accuracy in dense urban canyon

2

Access to carrier phase measurements
Multi-constellation and multi-frequency capabilities
Access to raw GNSS measurements via open-source tools

[2] Fu and van Diggelen, ION GNSS+ 2020

Challenges

Opportunities

4 of 30

Prior Decimeter Challenge Approaches

3

Factor graph approach for joint position-velocity optimization (winning approach: 2020, 2021)^[3]
EKF approach with GNSS-IMU-Magnetometer^[4]
PPP-based approach^[5]

Model-based

Linear regression^[6]
Bayesian ridge regression^[6]
Attention-based neural network approach for learning corrections^[7]

Learning-based

Kalman filter approach for GNSS-IMU with Reinforcement Learning for adaptive noise covariance^[8]

Hybrid

[3] Suzuki, ION GNSS+ 2021

[4] Campos-Vega and Bevly, ION GNSS+ 2021

[5] Liu and El-Sheimy, ION GNSS+ 2021

[6] Siemuri and Elmusrati, ION GNSS+ 2021

[7] Kanhere, Gupta and Gao, NAVIGATION, 2022

[8] Han and Won, ION GNSS+ 2021

5 of 30

Pros and Cons of Prior Approaches

4

Approach	Model-based	Learning-based
Pros	High positioning accuracy Faster runtime	Makes less assumptions about data structure Fault tolerant to uncertain noise models
Cons	Needs covariance tuning Needs accurate noise models	Sensitive to initialization and feature design Cannot outperform model-based approaches

6 of 30

Our Approach: Hybrid Framework

5

Model-based approach

(temporal)

Learning-based approach

(snapshot)

Initialization

Conditioning of inputs

Position Correction

7 of 30

Contributions

We propose a hybrid framework using model-based and learning-based methods to learn position corrections

For learning-based approach, we design a Graph Convolutional Neural Network (GCNN) that can represent different graph structures

We use a Kalman filter for better initialization of the GCNN and to condition the input features

We evaluate our proposed approach on real-world datasets collected in urban environments

6

8 of 30

Outline

Proposed Algorithm

Choice of Model-Based Approach: Kalman Filter
Choice of Learning-Based Approach: Graph Convolutional Neural Networks (GCNN)
Background on GCNN
Feature Preprocessing
GCNN Architecture

Evaluation on Urban Datasets

Real-world Datasets
Baselines, Metrics and Key Parameters
Evaluating Positioning Errors

Conclusion

7

9 of 30

Choice of Model-Based Approach: Kalman Filter

Kalman filter viable choice

Uses temporal history of GNSS measurements
Converges quickly
Computationally efficient

State: 3D position and 3D velocity
Tracking velocity jointly improves positioning performance

Use position estimate to condition inputs for learning-based approach

8

10 of 30

Choice of Learning-Based Approach: �Graph Convolutional Neural Networks (GCNN)

Factor Graph Optimization^[3]: Winning approach of the 2020, 2021 Google Decimeter challenge^[2]

GCNN can learn such a graph with satellite positions as nodes and preconditioned inputs from Kalman filter

GCNN can also

Handle varying satellite visibility in urban environment
Model measurements from multiple constellations and multiple signal frequencies

9

[2] Fu and van Diggelen, ION GNSS+ 2020

11 of 30

GCNN: Background^[9]

10

[9] Kipf and Welling, ICLR 2017

^[9]

12 of 30

GCNN: Background Cont’d

GCNN is able to learn and distinguish between different graph structures
Different graph structures are dictated by graph isomorphism

Isomorphic graphs have identical node adjacencies
Classical method to check: Weisfeiler-Lehman (WL) test^[10]

Only some convolution layers satisfy WL test and can model different graph structures
Our design choice of the graph convolutional operator: GINConv^[11], since it satisfies the WL test

11

Isomorphic Graphs

[10] Weisfeiler and Lehman, Nauchno-Tekhnicheskaya, Informatsiya, 1968

[11] Xu and Jegelka, ICLR 2019

13 of 30

Feature Preprocessing

12

Range residuals

LOS vector

Group by constellation/signal type

Eliminate inter-system and inter-frequency biases, clock biases, tropospheric and ionospheric errors

Apply ADR smoothing or Doppler if cycle slip

Feature Vector

14 of 30

GCNN: Feature Matrix

Feature matrix contains feature vector for every satellite in graph

Feature vector: concatenated LOS vectors and range residuals

Compute feature vector using position estimate from Kalman filter

13

GPS L1/L2

GAL E1/E5

GLO L1/L2

Sample feature vector for a node

0.2

0.5

0.6

15

Sample feature matrix for GPS cluster

0.2

0.5

0.6

15

0.5

0.9

0.3

20

0.7

0.8

0.6

5

0.1

0.6

0.4

10

0.3

0.7

0.5

2

15 of 30

GCNN: Adjacency Matrix

Design adjacency matrix that connects

Satellites in same constellation
Satellites from different constellations with similar measurement residuals

Adjacency matrix helps leverage multi-constellation measurements

Otherwise, GCNN loses discriminative power

14

GPS L1/L2

GAL E1/E5

GLO L1/L2

0.2

0.5

0.6

15

0.1

0.3

0.9

18

Connect both nodes since residuals difference < 5 m

16 of 30

GCNN: Convolution Layers

15

Design GINConv^[11] layers that

Update node features iteratively by aggregating feature vectors of neighbors
Can effectively distinguish between different graph structures

[11] Xu and Jegelka, ICLR 2019

^[10]

If feature vectors of a node’s neighbors form a multiset, �aggregation in GINConv equals aggregation over the multiset

17 of 30

GCNN: Pooling & Prediction

16

Pooling instantiates message passing among different nodes
Mean pooling

Averages node predictions
Reduces spatial resolution of graph for subsequent layers

Post-message passing, linear layers increase graph expressivity before final prediction

Pooling

Position Correction (3 X 1)

Post-message

passing layers

Sample GCNN

18 of 30

Algorithm

17

Feature

Processing

Predicted

Position

Model-based Approach

(Kalman Filter)

Feature

Matrix

GNSS Measurements

(Code Phase, Carrier Phase, Doppler)

Satellite positions, velocities

+

ReLU

GINConv

Linear

Layers

Global Mean-Pool

Position

Correction

Learning-based Approach (GCNN)

Adjacency

Matrix

17

Input

Conditioning

Initialization

19 of 30

Outline

Proposed Algorithm

Choice of Model-Based Approach: Kalman Filter
Choice of Learning-Based Approach: Graph Convolutional Neural Networks (GCNN)
Background on GCNN
Feature Preprocessing
GCNN Architecture

Evaluation on Urban Datasets

Real-world Datasets
Baselines, Metrics and Key Parameters
Evaluating Positioning Errors

Conclusion

18

20 of 30

Real-world Datasets for Evaluation

Google Smartphone Decimeter Challenge 2021 datasets collected in multiple cities^[2]

GNSS measurements from Android smartphones

Ground Truth from Novatel SPAN system

19

[2] Fu and van Diggelen, ION GNSS+ 2020

Sample trajectory from SJC (used as training dataset)

21 of 30

Baselines and Metrics

Metrics

Quantitative

Mean, median, maximum and minimum horizontal positioning error
Distribution of positioning error

Qualitative

Trajectory tracking w.r.t. ground truth

20

Baselines

Robust WLS solution (snapshot)
Kalman filter solution (temporal)

Baselines were tuned using Bayesian hyperparameter optimization for maximal performance

22 of 30

GCNN Experimental Parameters

21

Training/test split

81 training datasets
17 test datasets
Some test datasets include new cities (absent from training dataset) such as LAX

Loss function: MSE
Optimizer: Adam^[12]
Hardware platform: Kaggle, AWS
Accelerator: GPU, TPU
Libraries: Pytorch Geometric^[13]

GCNN Parameters

Module	Layer	Parameter
GINConv (1)	Linear	4 x 32
	ReLU
	Linear	32 x 32
GINConv (2)	Linear	32 x 32
	ReLU
	Linear	32 x 32
	LayerNorm	32
Post-Message Passing	Linear	32 x 32
	Dropout	p =0.25
	Linear	32 x 3

[12] Kingma and Ba, ICLR 2015

[13] Fey and Lenssen, ICLR 2019

23 of 30

Error on Test Datasets: Summary

22

Metric (meter)	WLS	Kalman Filter	Our Approach
Mean Error	5.7	4.6	3.4
Median Error	4.4	3.9	3.3
Min. Error	1.7	2.4	1.4
Max. Error	25.5	7.8	5.6

Our algorithm outperforms WLS and Kalman filter across all 17 unseen test datasets

24 of 30

Horizontal Positioning Error Distribution: Test Datasets

Validation Dataset: 2021-12-15-US-MTV1

23

Kalman Filter baseline

Our Algorithm

Our approach has fewer outliers (> 5 m error) and provides more accurate positioning

25 of 30

Horizontal Positioning Error Distribution: Selected Test Datasets

24

Validation Dataset: 2021-12-09-US-LAX-2

Kalman Filter baseline

Our Algorithm

Our approach has fewer outliers and provides more accurate positioning even in unseen cities

26 of 30

Positioning Accuracy Example

Validation Dataset: 2021-12-15-US-MTV1

25

Ground Truth

Our Algorithm

Kalman Filter

Our approach follows ground truth more closely compared to Kalman filter position

27 of 30

Conclusion

We designed a hybrid framework using model-based and learning-based methods to learn position corrections

For learning-based approach, we designed a GCNN to aggregate measurements across multiple constellations and multiple frequencies

For better initialization of the GCNN, we constructed features using position estimate from Kalman filter

We evaluated our approach on real-world datasets collected in urban environments and outperformed model-based approaches

26

28 of 30

Acknowledgement

Google for publicly available

datasets

27

Zach, Nikhil, Shubh, Ramya, and the rest of NAVLab members for insightful discussions and feedback!

29 of 30

Thank You!

28

30 of 30

29