Smart ways to improve smartphone location accuracy

The Google Smartphone Decimeter Challenge (SDC) competition, co-sponsored by the Institute of Navigation (ION), took place this summer. For the competition, teams developed high-precision GNSS positioning using a pool of smartphone GNSS + inertial measurement unit (IMU) datasets accompanied by high-accuracy ground truth. Teams competed to achieve the best location accuracy with the datasets provided. Winners received cash prizes and sponsored attendance at the ION GNSS+ 2022 conference in Denver, Sept. 19-23, to present their results.

Origins

The SDC has its origins in the Android Operating System, which is an open-source platform. In 2016, Google made GNSS raw measurements available as a public application programming interface (API) on all Android phones. Since then, the available measurements have become more sophisticated and more accurate. For example, dual-frequency carrier-phase data is now available on many Android phones. This enables new areas of research.

Goals

The competition had two goals:
• Stimulate the research and development of high-accuracy algorithms that can produce submeter position accuracy on phones.

• Establish a publicly accessible repository of labeled data so that all future research on location algorithms can be judged in a consistent way against a standard set of data.

The first goal was met beyond our expectations. A total of 1,381 teams participated in the two competitions of 2021 and 2022. Discussion among competitors on the competition platform (kaggle.com) was wide-ranging, incredibly collegial, and beneficial to the entire community.

Competitors have written and shared detailed descriptions, and these have been reviewed and commented on by other competitors. Moreover, winners have written formally peer-reviewed papers and made presentations at the ION GNSS+ conferences, which are available from ion.org.

The second goal is a work-in-progress and is intended to be the legacy of the events.

Legacy

Disciplines such as machine learning have established benchmarks that make it possible to compare new approaches to previous ones in a proper quantitative way. In the GNSS community, this convention has been missing — a glance across papers at conferences will show that different algorithms tend to be presented with different test data and different metrics. Usually, the authors collect this data, and it is often fairly sparse (one or two drive tests, for example). Also, the reader never knows whether the data was cherry-picked (were bad results not mentioned?).

The SDC data provides:

• 206 different drive tests
•86 total hours of dual-frequency (L1, L5) data with code and carrier-phase measurements
•All labeled with ground-truth positions and velocities collected using NovAtel SPAN ISA-100C, with precise lever-arm compensation and validated with Google’s analysis tools.

The Kaggle site allowed users to submit their results, then automatically scored them against the ground-truth data. We advocate that all GNSS researchers use this resource to measure their location algorithm improvements in a standard way. This creates trust in published results, accelerating the recognition and adoption of truly great improvements for the benefit of the entire industry and GNSS users worldwide.

Read how to use the SDC data in Kaggle to test position algorithms here.

Winners Reveal Their Approaches

The top three winners of this year’s Smartphone Decimeter Challenge described their projects to Matteo Luccio, GPS World editor-in-chief.

Suzuki

Taro Suzuki, Chiba Institute of Technology

1st Place Winner: Two-Step Optimization of Velocity and Position using Smartphone’s Carrier Phase Observations

What is your research focus and how does it relate to the contest?

My current research focuses on the accurate positioning of vehicles and mobile robots in urban environments where GNSS multipath occurs. I usually use commercial GNSS receivers for my research. This competition is very relevant to my current research, except that the smartphone is replacing a receiver.

How long have you been developing the technology or approach you used to win the contest?

The competition was held for three months, but I concentrated my efforts on the past three weeks. However, I used technologies and resources developed in my previous research (for example, source code developed in last year’s competition).

Have you participated in previous editions of this contest?

Yes, I participated in the last competition and won. The approach used in this year’s competition is based on the method used to win last year’s competition, with additional innovations and improvements.

Where, in what GNSS signal conditions, and at what speeds were the test data collected?

The competition provides a training dataset, which contains raw GNSS observations from a smartphone installed on a vehicle as it travels on real roads. In addition to GNSS observations, the training dataset contains the ground truth of the smartphone’s position. The training dataset includes a wide range of GNSS signal conditions, such as driving on highways around San Francisco and Los Angeles, driving on tree-lined urban streets, and driving in tunnels and under overpasses. I have developed an algorithm that uses a training dataset containing ground truth to accurately estimate the location of smartphones in a variety of GNSS signal reception environments.

What accuracies were you able to obtain?

The competition metric was “average of 50th and 95th percentile horizontal errors.” The metrics are computed for each of the 36 runs in the test dataset, which are divided into public and private groups, then the metrics are averaged in each group to compute the final score. My final score was 1.382 m for public and 1.229 m for private. The best score given after the competition was 1.372 m for public and 1.197 m for private. The final result achieved sub-meter accuracy in the median (50th percentile).

What are the key features of your approach?

The key point of my method is global optimization using graph optimization, unlike a conventional Kalman filter or least-squares-based positioning methods. In addition, highly accurate relative position estimation using the time difference of carrier wave phases of smartphones contributed to the accuracy. Because the competition dataset included environments such as tunnels and elevated structures in which GNSS cannot be received at all, I devised an algorithm with two optimization steps (first velocity optimization, then position optimization) and applied it to the competition. This method enables highly accurate position estimation for vehicle driving data in various GNSS signal reception environments using only smartphone GNSS observation data.

What end-user applications are you expecting your approach to enable?

Decimeter-accurate location estimation could lead to lane-level navigation for vehicles, pedestrian navigation, and advanced location-based smartphone games.

Dai

Shubin Dai, Kaggle Community

2nd Place Winner: Improving Smartphone GNSS positioning using Gradient Descent Method

What is your research focus and how does it relate to the contest?

I am a data scientist and one of the top competition grandmasters on Kaggle. My research interests include computer vision, natural language processing, autonomous driving, and reinforcement learning. I placed in the top three in 14 related competitions (13 of which were solo). So, despite my lack of background knowledge in the GNSS field, these methods, skills and experiences helped me find a solution.

How long have you been developing the technology or approach you used to win the contest?

I spent about 50 days on this competition, including learning principles of GNSS and understanding all kinds of algorithms by reading books, papers and source codes. The Kaggle platform is very helpful when we want to get started in a new field.

Have you participated in previous editions of this contest?

I did not participate in the competition held last year, but I learned a lot from solutions of recent years, particularly the third-place solution.

Where, in what GNSS signal conditions, and at what speeds were the test data collected?

The benchmark datasets include raw GNSS measurement and raw readings from inertial sensors, using smartphones (Xiaomi Mi 8, Google Pixel 4, etc.) enabled with dual-frequency and ADR (accumulated delta range) in driving scenarios, collected in the San Francisco Bay area.

In the GSDC2021 dataset, there are 29 drives with 73 phone GNSS logs in the training set and 19 drives with 48 phone logs in the test set. Compared to 2021’s competition, in the GSDC2022 dataset we can see more data overall and a wider variety of routes: 62 drives with 170 phone logs are provided in the training set and 36 drives with only one phone per drive are provided in the test set.

The drives in the training set took 15 to 60 minutes at an average speed of 18 m/s.

What accuracies were you able to obtain?

According to the metric of this competition, the score is calculated as the mean of the 50th and 95th percentile distance errors. The score on my local validation set is 1.929 m, the score on the public test set is 1.608 m, and the score on private test set is 1.499 m. When we calculate the mean error, the score is 1.401 m on a validated set, the mean error of 40% of the trips are under 1 m. I think the competition metric is more reliable as the 95th percentile distance error is also important.

By the way, my local validation set is more difficult to optimize than the test set, so the mean error on the test set is expected to be lower than 1.401 m.

What are the key features of your approach?

The competition data is noisy due to multipath effects, non-line-of-sight receptions, receiver noise and missing data, therefore it’s quite challenging. I found that the optimal estimation for each point locally is not stable and can be affected by noise at that point on the track. If we can find a solution to a whole track globally, the noise can be reduced as the model must follow all kinds of constraints, such as geometry constraints, speed constrains, and global acceleration constraints.

Although we could extend the WLS and Kalman filter solution to take more points on a track into consideration, it’s not so easy to model all kinds of constrains. On the other hand, if we use a global optimization method, such as factor graph optimization and neural networks, we can add the constrains easily, which makes it more efficient to conduct experiments.

Following the solution of the third-place winner in last year’s competition, I used the global optimization method by taking into account gradient descent, pseudorange, pseudorange rate, accumulated carrier phase (ADR), phone speed and acceleration constraints of every time epoch on a track. When optimizing the track using gradient descent, the losses are designed to filter out abnormal data and reduce the noise by a series of physical and geometrical rules. I spent much time searching for the constraints, proving them and turning them into losses that can be used to update the coordinates iteratively during the competition.

What end-user applications are you expecting your approach to enable?

According to the setting of this competition, we can post-process data collected using Android phones, which is easily obtained. The track obtained can then be optimized using the solutions from this competition. The solutions from the first and the second place can both be considered as a framework that can be extended by adding more constrains to it to improve accuracy.

Everett

Tim Everett, RTK Consultants LLC

3rd Place Winner: An RTKLIB Open-Source-Based Solution

What is your research focus and how does it relate to the contest?

I develop and maintain the demo5 fork of the popular RTKLIB open-source GPS/GNSS software tool. I have optimized this software for low-cost precision GNSS solutions, so it is very closely related to the goals of this competition. My background is in control system theory and I worked in product and technology development for servo systems in the disk drive industry for 25 years before switching to the GNSS field. The mathematics turns out to be quite similar between the two as both are problems in precision positioning, just different in scale. In disk drives, it is nanometers over centimeters and in precision GNSS, it is centimeters over kilometers.

How long have you been developing the technology or approach you used to win the contest?

I have been developing and maintaining low-cost precision GNSS solutions in the RTKLIB software for about six years but have only worked with smartphone solutions in the last year or two.

Have you participated in previous editions of this contest?

I did not participate in last year’s competition but I did work with the data after the contest was over and shared a solution using RTKLIB that would have placed fifth in the competition.

What accuracies were you able to obtain?

I achieved a score of 1.648 m on the private leaderboard. This represents the average of the 50th percentile and the 95th percentile of the errors as scored by Kaggle. Kaggle does not provide any further breakdown of this number but, based on the training data for which ground truths were provided, this corresponded to a 50th percentile error of roughly 0.9 m and a 95th percentile error of roughly 2.3 m. With a small tweak to my solution after the competition was over, I was able to improve my private leaderboard score to 1.593 m, which would have been within 1 cm of the third-place solution.

What are the key features of your approach?

My approach was to use the existing post-processing kinematic (PPK) solution algorithm in RTKLIB but to reoptimize it for the unique characteristics of the smartphone observation data. A PPK solution is the post-processing equivalent of a real-time kinematic (RTK) solution and is a differential solution that relies on differencing the receiver observations with observations from a nearby base station to cancel out most of the largest error sources — including atmospheric, orbital and clock errors — since these errors are common between the two sets of proximate observations.

Because smartphones have very poor GNSS antennas and they were mounted inside vehicles, the signal quality is much lower and the multipath much greater than those for which the RTKLIB algorithm was optimized. In addition, the smartphones were using the L5 frequency band, whereas RTKLIB was optimized for the more commonly used L2 frequency band. One of the main goals of my optimization process was to include many low-quality observations in the solution that would normally be discarded, but to de-weight them appropriately.

What end-user applications are you expecting your approach to enable?

RTKLIB software is currently used to provide precision solutions for many end-user applications such as surveying, drone photogrammetry, sports tracking, precision agriculture, utility location, marine navigation and ground subsistence monitoring. Although smartphones won’t replace dedicated low-cost GNSS receivers, the challenging nature of the smartphone data severely stresses the RTKLIB algorithms and exposes numerous opportunities for improvement that are much less obvious with more typical, higher quality data. I have pulled these improvements into the main branch of the demo5 version of RTKLIB, and hence this work should immediately improve the quality of all these applications and extend their use into more challenging environments.

Photo: Google

Acknowledgements: Thanks to the Institute of Navigation (ION) for co-sponsoring the 2022 Smartphone Decimeter Challenge. Thanks to Luke Walcher and Tolu Ojelade for their contributions to the photos used in this article.