Kernel density estimation for target trajectory prediction

Vahab Akbarzadeh, Christian Gagné, Marc Parizeau

Abstract

Trajectory prediction is a critical component of autonomous navigation and collision avoidance. This paper presents a non-parametric approach based on Kernel Density Estimation (KDE) to measure similarity between a target's current path and historical trajectories. By integrating location and displacement into a 4D probabilistic framework, the proposed method achieves significant improvements over traditional techniques like Principal Component Analysis (PCA) and Longest Common Subsequence (LCSS), particularly for long-term predictions in complex, real-world environments.

Introduction

Predicting the future path of moving objects, such as pedestrians or vehicles, is essential for safe autonomous operation. While classical filters like the Kalman Filter are effective for short-term estimation, their uncertainty increases exponentially over longer horizons. Leveraging historical movement patterns provides a more robust basis for prediction. However, existing methods often struggle with the computational cost of re-training parametric models or the rigidity of binary similarity measures.

Methodology

The proposed approach utilizes a non-parametric similarity measure to compare current observations against a library of historical data.

4D State Space Representation

To capture local dynamics, the model represents each trajectory state as a 4D vector: $(x, y, \Delta x, \Delta y)$. Including displacement ($\Delta x, \Delta y$) allows the model to distinguish between targets at the same location moving in different directions, providing crucial context in crowded environments.

Probabilistic Similarity via KDE

Unlike methods that use hard thresholds (e.g., LCSS), this model employs KDE to calculate a continuous similarity score. The similarity is defined by the probability density of the test point relative to the historical path.

Trajectory similarity calculation using KDE.

Handling Uncertainty and Missing Data

Real-world sensor data often contains gaps. The authors address this by interpolating missing points and adjusting the kernel bandwidth linearly based on the distance from the nearest real observation. This variable bandwidth ensures that interpolated data is treated with appropriate uncertainty.

Weighted Prediction

Predictions are generated by calculating similarity weights for a sliding window of the 1,000 most recent historical trajectories. The final predicted path is a weighted average of the future states of these similar historical paths.

Datasets and Evaluation

The model was evaluated across three diverse environments:

  1. ULaval Campus: A simulated environment with 1,000 pedestrian trajectories navigating obstacles.
  2. MIT Trajectory Dataset: A real-world dataset containing over 36,000 trajectories from a parking lot.
  3. Train Station Dataset: A high-density real-world dataset with over 46,000 trajectories from New York’s Grand Central Station.
Visual representation of trajectories in the MIT parking lot dataset.

Key Results

The KDE-based method consistently outperformed PCA and LCSS across various time horizons and prediction steps.

  • Accuracy: In the MIT dataset, KDE achieved an average error of 26.0 pixels, significantly lower than LCSS (37.61 pixels) and PCA (44.41 pixels).
  • Robustness: KDE’s performance remained stable even as the prediction horizon increased, showing a much more graceful degradation compared to baseline methods.
  • Online Adaptability: As a non-parametric method, the model can incorporate new data instantly by updating its history buffer, eliminating the need for periodic re-training.

Conclusion

The integration of KDE into trajectory prediction offers a flexible and accurate framework for autonomous systems. By moving from binary matching to probabilistic similarity and incorporating velocity context, the model handles complex environmental dynamics more effectively than traditional baselines. Future work will focus on optimizing computational efficiency for high-speed applications and adapting to dynamic environmental changes.

Summary updated

Abstract

This paper proposes the use of a kernel density estimation to measure similarities between trajectories. The similarities are then used to predict the future locations of a target. For a given environment with a history of previous target trajectories, the goal is to establish a probabilistic framework to predict the future trajectory of currently observed targets based on their recent moves. Instead of clustering trajectories into groups, we calculate the similarity between a given test trajectory and the set of all past trajectories in a dataset. Next, we use a weighted mechanism for prediction, that can be used in target tracking and collision avoidance applications. The proposed method is compared with two other commonly used similarity models (PCA and LCSS) over a dataset of simulated trajectories, and two datasets of real observations. Results show that the proposed method significantly outperforms the existing models for those datasets and experimental settings.
BibTeX
@inproceedings{akbarzadeh2015kernel,
  author = {Vahab Akbarzadeh and Christian Gagné and Marc Parizeau},
  title = {{Kernel density estimation for target trajectory prediction}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2015},
  doi = {10.1109/iros.2015.7353858},
}
Figure