Estimating Urban Road GPS Environment Friendliness with Bus Trajectories: A City-Scale Approach

Liantao Ma, Chaohe Zhang, Yasha Wang, Guangju Peng, Chao Chen, Junfeng Zhao, Jiangtao Wang

TL;DR

This paper introduces a novel method to estimate the "GPS Environment Friendliness" (GEF) of urban road segments by analyzing massive historical bus GPS trajectory data. By leveraging fixed bus routes and a matrix completion approach that incorporates contextual information, they provide a city-scale map of GPS accuracy, crucial for improving location-based services and guiding the deployment of assisted positioning systems.

What Problem Does This Paper Address?

Global Positioning System (GPS) is ubiquitous for location-based services (LBS), but its accuracy is severely degraded in urban environments due to signal blockage and multipath effects caused by buildings and other structures. This leads to unreliable positioning, impacting LBS user experience and potentially causing errors in critical applications. While some methods exist to improve GPS accuracy, they often require additional infrastructure or are limited to small-scale, road-by-road studies. The challenge is to create a comprehensive, city-scale understanding of how the urban environment affects GPS accuracy, which can then inform LBS and strategic deployment of supplementary positioning technologies.

Methods

The authors propose a three-phase framework:

  1. Map Matching and Error Matrix Construction: They first use a Hidden Markov Model (HMM)-based map matching algorithm, enhanced by the known fixed routes of buses, to accurately map GPS trajectories to road segments. This process generates an initial sparse matrix where each entry represents the GPS positioning error (standard deviation of biases) of a specific bus on a specific road segment.
  2. Matrix Completion with Contextual Information: Recognizing the sparsity of the initial matrix (no single bus covers all roads, and not all buses traverse every road), they employ a matrix completion technique. This is where the novelty lies: they incorporate contextual information about road segments as regularization terms. This includes:
  3. POI Information: The density and types of Points of Interest (e.g., restaurants, shops) around a road segment.
  4. Tag Information: Road classifications from OpenStreetMap (e.g., "primary," "residential").
  5. Building Layout Information: The height distribution of nearby buildings.
  6. Bus Receiver Quality: An F-test is used to estimate the relative quality of GPS receivers across different buses, which is then used to weight their contributions.

    This enriched matrix completion aims to infer the GPS errors for road segments not directly covered by a bus's trajectory, by leveraging correlations between GPS errors and environmental factors.

  7. Weighted Estimation of GEF: Finally, the completed GPS error matrix is used to estimate the GPS Environment Friendliness (GEF) for each road segment. A weighted estimation strategy is applied, giving more importance to buses with higher-quality GPS receivers, to ensure a fair and robust GEF assessment. A lower GEF score indicates a more "friendly" GPS environment (lower error).

Datasets

  • GPS Trajectory Data: One month of GPS trajectory data from 4835 buses operating within the second ring road of Chengdu, China. This dataset contains approximately 62.7 million GPS points.
  • Urban Road Network Data: Obtained from OpenStreetMap for Chengdu.
  • POI and Tag Information: Derived from Gaode Map and OpenStreetMap, respectively.
  • Building Layout Information: Collected for buildings within 200m of road segments in Chengdu.
  • Field Test Data: Ground-truth GPS measurements collected on six specific road segments using Android smartphones.

Key Insights and Ideas

  • Leveraging Bus Routes for Map Matching: The fixed nature of bus routes is a powerful prior that significantly improves map matching accuracy and efficiency, reducing reliance on purely geometric matching.
  • Contextual Information as a Proxy for GPS Accuracy: The paper demonstrates that environmental factors like building density (layout), road type (tag), and surrounding amenities (POI) are strong indicators of GPS signal quality. This allows for the estimation of GEF even for roads with limited direct GPS data.
  • Matrix Completion for Sparse Data: The core challenge of sparse GPS data across a city is effectively addressed by matrix completion, but the innovation here is the integration of diverse contextual features as regularization terms, going beyond standard matrix completion techniques.
  • Weighted Estimation for Receiver Quality Variance: Acknowledging that GPS receiver quality varies significantly between buses is crucial. The proposed weighting scheme ensures that more reliable data sources have a greater influence on the final GEF estimation.
  • City-Scale GEF Mapping: The ability to generate a comprehensive GEF map for an entire city is a significant advancement over previous small-scale, road-specific studies.

Key Results

  • The proposed method successfully estimated the GEF for 8831 road segments in Chengdu.
  • The matrix completion approach, integrating layout, tag, and POI information, achieved the lowest matrix completion error (0.29220) compared to baseline methods like NMF (0.31883) and naive KNN.
  • Field tests on six road segments showed that the proposed method's GEF estimations were more accurate and aligned better with ground truth compared to a baseline method that relied solely on average GPS biases. For instance, the baseline method overrated the GEF of one segment, while the proposed method correctly identified it as poor.

Limitations and Future Work

  • Limited Road Coverage: While bus routes cover primary roads, many bypasses and smaller roads are not covered, meaning their GEF cannot be estimated by this method.
  • Future Work:
    • Applying the approach to other trajectory data sources like taxis to cover more roads.
  • Using GEF assessment results to extract environmental attributes from urban street view images, enabling GEF estimation without bus trajectory data.
  • Collecting more real-life GPS measurements for further case studies.
  • Applying the GEF evaluation to improve LBS by assessing the confidence level of real-time locations and predicted arrival times.

Summary updated

Abstract

GPS is taken as the most prevalent positioning system in practice. However, in urban areas, as the GPS satellite signal could be blocked by buildings, the GPS positioning is not accurate due to multi-path errors. Estimating the negative impact of urban environments on GPS accuracy, that is the GPS environment friendliness (GEF) in this paper, will help to predict the GPS errors in different road segments. It enhances user experiences of location-based services and helps to determine where to deploy auxiliary assistant positioning devices. In this paper, we propose a method of processing and analysing massive historical bus GPS trajectory data to estimate the urban road GEF integrated with the contextual information of roads. First, our approach takes full advantage of the particular feature that bus routes are fixed to improve the performance of map matching. In order to estimate the GEF of all roads fairly and reasonably, the method estimates the GPS positioning error of each bus on the roads that are not covered by its route, by taking POIinformation, tag information of roads, and building layout information into account. Finally, we utilize a weighted estimation strategy to calculate the GEF of each road based on the GPS positioning performance of all buses. Based on one month of GPS trajectory data of 4835 buses within the second ring road in Chengdu, China, we estimate the GEF of 8831 different road segments and verify the rationality of the results by satellite maps, street views, and field tests.
BibTeX
@inproceedings{ma2020estimating,
  author = {Liantao Ma and Chaohe Zhang and Yasha Wang and Guangju Peng and Chao Chen and Junfeng Zhao and Jiangtao Wang},
  title = {{Estimating Urban Road GPS Environment Friendliness with Bus Trajectories: A City-Scale Approach}},
  booktitle = {Sensors},
  year = {2020},
  url = {https://openreview.net/forum?id=j0VnGKZ8maN},
}
Figure