GPS Trajectory Completion Using End-to-End Bidirectional Convolutional Recurrent Encoder-Decoder Architecture with Attention Mechanism

Asif Nawaz, Zhiqiu Huang, Senzhang Wang, Muhammad Azeem Akbar, Hussain Alsalman, Abdu Gumaei

TL;DR

This paper tackles the challenge of incomplete GPS trajectories by proposing a novel deep learning architecture. Their end-to-end bidirectional ConvLSTM encoder-decoder with an attention mechanism effectively reconstructs missing GPS points, outperforming existing methods and offering a more robust solution for various real-world applications.

What Problem Does This Paper Address?

GPS data is invaluable for numerous applications, from navigation and tracking to understanding urban mobility. However, real-world GPS trajectories are often sparse and incomplete due to signal loss, device errors, or privacy concerns. This missing data poses a significant challenge for accurate analysis and inference. Existing methods often rely on complex heuristics or domain-specific knowledge, which can be cumbersome and may not generalize well. The authors aim to address this by developing a data-driven deep learning approach that can automatically learn patterns and fill in these gaps without requiring external information like road networks.

Methods

The core of the proposed solution is an end-to-end bidirectional Convolutional Long Short-Term Memory (ConvLSTM) encoder-decoder architecture. Here's a breakdown of the key components:

  • ConvLSTM: This is a powerful variation of LSTM that incorporates convolutional operations. This allows it to effectively capture both the spatial (grid-based representation) and temporal dependencies inherent in GPS trajectory data, overcoming the limitations of standard LSTMs that flatten spatial information.
  • Bidirectional Encoder: To capture movement patterns from both past and future timesteps, the encoder processes the input sequence in both forward and backward directions.
  • Encoder-Decoder Architecture: This standard sequence-to-sequence framework is employed. The encoder compresses the input trajectory into a context vector, and the decoder uses this vector to generate the completed trajectory.
  • Attention Mechanism: A crucial addition, the attention mechanism allows the decoder to dynamically focus on the most relevant parts of the encoded input sequence at each step. This significantly improves the model's ability to handle long-term dependencies and complex patterns.
  • Auxiliary and Global Features: The model also incorporates auxiliary features (like weekday and peak time) and global features (extracted via a parallel CNN) that are merged with the decoded output to further enhance prediction accuracy.

Datasets

The primary dataset used for training and evaluation is the Microsoft Geolife trajectory dataset. This is a widely used benchmark dataset containing GPS trajectories from 182 users across 30 cities in China, collected over five years. The authors specifically focus on data from Beijing due to its complex traffic patterns and dense GPS point representation.

Key Insights and Ideas

  • ConvLSTM is key for spatiotemporal data: The paper highlights that for GPS trajectories, which have both spatial and temporal aspects, ConvLSTM is superior to standard LSTMs because it preserves spatial information.
  • Bidirectionality matters for context: Understanding movement requires looking both backward and forward in time. The bidirectional encoder effectively captures this context.
  • Attention is a game-changer for long sequences: The attention mechanism is crucial for enabling the model to "remember" and utilize information from distant past or future points in the trajectory, leading to more accurate completions.
  • Auxiliary and global features provide valuable context: Incorporating information like time of day and day of the week, along with broader geographical patterns, significantly boosts performance.
  • Grid representation simplifies spatial modeling: Representing GPS points on an occupancy grid map allows for effective spatial feature extraction and integration with ConvLSTM.

Key Results

The proposed model achieved state-of-the-art performance in GPS trajectory completion, as measured by the Average Displacement Error (ADE).

  • For a 10-point missing segment at a 10m grid resolution, the model achieved an ADE of 2.53.
  • The model consistently outperformed various benchmark methods, including Linear Regression, Regression Trees, MLP, Simple RNN, CNN, GRU, Vanilla LSTM, and standard LSTM Encoder/Decoder.
  • The inclusion of the attention mechanism and auxiliary/global features led to significant improvements in ADE.
  • The performance generally degrades slightly as the length of the missing segment increases (from 10 to 30 points), but the model remains robust.
  • Higher grid resolutions (e.g., 2m) showed higher ADE, which the authors attribute to the increased likelihood of small prediction errors falling into different grid cells compared to lower resolutions where wider cells can absorb minor inaccuracies.

Limitations and Future Work

  • Dataset Size: The authors acknowledge that training on a larger dataset could further reduce the overall loss and optimize parameters, leading to even better performance.
  • Prediction Scope: Currently, the model predicts the spatial coordinates (latitude, longitude) of missing GPS points within an occupancy grid.
  • Future Work: The authors propose extending their work to predict not only the spatial coordinates but also the timestamp of missing GPS points. This would allow for georeferencing the completed trajectories onto actual geographical maps. They also aim to address more complex scenarios, such as trajectories in crowded environments where movement might be influenced by neighboring entities.

Summary updated

BibTeX
@inproceedings{nawaz2020gps,
  author = {Asif Nawaz and Zhiqiu Huang and Senzhang Wang and Muhammad Azeem Akbar and Hussain Alsalman and Abdu Gumaei},
  title = {{GPS Trajectory Completion Using End-to-End Bidirectional Convolutional Recurrent Encoder-Decoder Architecture with Attention Mechanism}},
  booktitle = {Sensors},
  year = {2020},
  url = {https://openreview.net/forum?id=6v5tMNKya1},
}
Figure