# 5th place solution (Saito)

Congrats to all the winners, and thanks so much for hosting such an interesting competition! Here, I want to share my part of our team's solution.
Improved satellite positioning
I spent the first month of the competition learning GNSS and developed my own positioning program. In my program, I tried the following ideas,
least squares weighting based on satellite elevation
satellite elevation mask
outlier removal based on least squares residuals
isrbM averaging and regularization
height smoothing and regularization
carrier smoothing using accumulated delta range
However, most ideas became ineffective after the subsequent optimization based smoothing. Perhaps the only essential improvement was carrier smoothing based on the accelerated delta range.
Use of sensor data
Based on acceleration, gyro, and geomagnetic sensors, I estimated vehicle orientation and acceleration, and added acceleration and lateral velocity terms to the cost function of subsequent optimizations. This idea may have had little effect after the introduction of velocity estimates.
Velocity estimation using doppler shift
The vehicle speed was estimated from the pseudo-range rate by the least squares method and used for subsequent optimization based smoothing. This improved the public LB by about 1 meter.
Optimization based smoothing
This part is the core of my solution.
First, the dynamics of the vehicle is expressed by the following state equation.
![state_equation](assets/6fade9e8e06d0abe1de1b591.png)
where \( \phi \) and \( \psi \) are latitude and longitude, respectively.
Then, by vertically arranging the states \( X \) and inputs, jerks,  \( U \)  at each time, the equality constraints on state transitions can be described as follows,
[
A X + B U = 0
]
In addition, by determining the observation matrix \( C \) according to the observation time based on Hermitian interpolation, the vector \( Y \), which is a vertical sequence of latitude and longitude at each observation time, can be written as follows,
[
Y = C X
]
The optimization evaluation function \( J \) is set as the sum of the squares of the jerk \( U \) and the position estimation error, as follows,
[
J = U^T R U + (\hat{Y} - C X)^T L (\hat{Y} - C X)
]
Finally, the position estimation is formulated as the following quadratic programming problem.
![optimization](assets/509ba5cdaad83ff6eae9f90f.png)
Based on this method, various information can be integrated by adding velocity error, acceleration error, cost related to lateral velocity, etc. to the cost function.
The important point is to perform the above optimization by using positions of all smartphones in one driving data at the same time. This method is clearly more accurate than the method of making estimates for each smartphone and calculating their average.
Map matching
This process is applied only SJC/downtown.
If the shortest distance between the GNSS position prediction result and the ground truth is more than a certain value, the prediction value is excluded in advance before smoothing.
Replace the smoothing result with the nearest neighbor point of ground truth and perform smoothing again.
Bias correction
Because the smartphones are placed in the vehicle, I thought that the effect of multipath would appear asymmetrically and the positioning result would be biased with respect to the direction of the vehicle. Based on this idea, our team added a process to correct the position according to the direction the vehicle is traveling. This method contributed to the improvement of CV and public LB, but did not improve the private LB score.
Do not use public LB for validation
In the last indoor location competition, my team wasn't able to implement drastic improvement ideas such that discrete optimization towards the end of the competition due to poor post-processing validation. In this competition, I tried to minimize the number of submits by completing all parameter tuning and validation locally. As a result, our team was able to stay in the gold medal range even if a shake up occurred.
notebooks
[GSDC - Optimization based smoothing (1st version)](https://www.kaggle.com/saitodevel01/gsdc-optimization-based-smoothing-1st-version)
[GSDC - Vehicle Speed Estimation by Doppler Shift](https://www.kaggle.com/saitodevel01/gsdc-vehicle-speed-estimation-by-doppler-shift)
[GSDC - Improved Raw GNSS Baseline](https://www.kaggle.com/saitodevel01/gsdc-improved-raw-gnss-baseline)
[DSDC - Unified post-processing](https://www.kaggle.com/saitodevel01/dsdc-unified-post-processing)
[GSDC - Bias EDA](https://www.kaggle.com/saitodevel01/gsdc-bias-eda)
[GSDC - Bias Correction](https://www.kaggle.com/saitodevel01/gsdc-bias-correction)