An Approach to Vehicle Trajectory Prediction Using Automatically Generated Traffic Maps

Jannik Quehl, Haohao Hu, Sascha Wirges, Martin LauerarXiv 2018 · arXiv

TL;DR

This paper introduces a method for predicting vehicle trajectories by leveraging automatically generated, lane-accurate traffic maps built from historical data. By matching a vehicle's current state to "prototype" trajectories and transition probabilities stored in a topological graph, the system achieves significantly higher accuracy for mid-term predictions (up to 20 meters ahead) compared to standard physics-based motion models.

What Problem Does This Paper Address?

Predicting where a vehicle will be in the next few seconds is a cornerstone of autonomous driving safety. However, most existing approaches fall into two camps, both with flaws:

  1. Physics-based models: Models like Constant Yaw Rate and Acceleration (CYRA) work well for the next few milliseconds but fail miserably at intersections because they don't know the road curves or where the lanes go.
  2. Maneuver-based models: These try to guess if a car is "turning left" or "changing lanes," but they often require the vehicle to actually start the maneuver before they can recognize it—making the prediction "too little, too late."

The authors address this gap by providing the prediction engine with context. If we know how thousands of other cars have navigated a specific intersection, we can make a much better guess about what a new vehicle will do before it even begins to turn.

Methods

The authors propose a two-stage framework: Map Generation and Trajectory Prediction.

1. Automatic Map Generation

Instead of relying on potentially inaccurate GPS maps, the authors build their own using raw trajectory data:

  • Topology Extraction: They convert historical trajectories into a top-view heatmap. Using image processing techniques—specifically binarization and the Zhan-Suen-Thinning algorithm—they boil these paths down to a skeleton of one-pixel-thick lines representing lanes.
  • Graph Construction: This skeleton is converted into a directed graph $G = (V, E)$. Nodes are classified as Start, End, Crossover, or Decision points.
  • Prototype Extraction: For every edge in the graph, they cluster historical trajectories by velocity and extract a "prototype" path that represents typical driving behavior for that speed and lane.
The multi-step process of turning raw trajectory heatmaps into a clean topological graph.

2. The Prediction Process

When a new vehicle is observed:

  • Matching: The system finds the graph edge that best matches the vehicle's current position and heading.
  • Probability Weighting: At decision nodes (like a fork in the road), the system doesn't just guess. It uses the vehicle's current velocity to calculate transition probabilities. For example, a car slowing down is statistically more likely to turn than one maintaining high speed.
  • Prototype Transformation: To ensure the prediction is smooth, the system takes the stored prototype trajectory and applies a spatial transformation so it connects perfectly with the vehicle's current observed path.
Fig. 1: Comparison of different prediction approaches at two points in time. CYRA in orange, MRM-based prediction in red (solid and dashed) and our proposed method in green.

Datasets

The researchers evaluated their approach using a custom dataset recorded at a busy intersection in Karlsruhe, Germany.

  • Sensor Setup: A Velodyne HDL64E-S2 LiDAR mounted on an experimental vehicle.
  • Scale: Over 14,500 vehicle trajectories were extracted, with 5,766 of those being at least 20 meters long.
  • Processing: Data was cleaned using RANSAC for ground plane removal and manual labeling to ensure only cars and trucks were included.

Key Insights and Ideas

  • Velocity as an Intention Signal: One of the most clever aspects is using velocity to resolve ambiguity at decision nodes. By clustering historical data, the authors found a clear relationship between a vehicle's speed approaching a fork and its eventual choice of path.
  • Image Processing for Robotics: Treating trajectory data as an image allowed the authors to use well-established thinning and morphological operations to solve the complex problem of lane-accurate map generation.
  • Linear vs. Exponential Error: While standard motion models see their error grow exponentially as the prediction horizon increases, this map-based approach sees only linear error growth because the "path" is constrained by the known road geometry.

Key Results

The evaluation compared the proposed method against a standard CYRA baseline. The results, measured in average distance from the ground truth (in cm) over a prediction horizon (in cm), were striking:

  • Short-term: For the first 4-6 meters, both methods perform similarly.
  • Mid-term (20m): At a 20-meter horizon, the CYRA model's error balloons to nearly 300 cm (3 meters). In contrast, the proposed graph-based method maintains an average error of roughly 50-75 cm.
  • Reliability: In over 75% of cases, the predicted path was highly accurate, with error accumulating only linearly with distance.
Quantitative results showing the proposed method (blue/red) significantly outperforming the Kinematic CYRA model (green) as the distance increases.

Limitations and Future Work

  • Site Specificity: The current method requires a significant amount of historical data for a specific area to generate the map. It cannot predict behavior in a completely new, unmapped environment.
  • Rule-Following Assumption: The model assumes vehicles behave according to typical traffic patterns and rules. It might struggle with highly erratic drivers or emergency maneuvers that deviate from "prototype" behaviors.
  • Dynamic Environments: The paper focuses on static road geometry. Future work could incorporate how the presence of other moving participants (like a car blocking a lane) changes the transition probabilities in the graph.

Summary updated

Abstract

Trajectory and intention prediction of traffic participants is an important task in automated driving and crucial for safe interaction with the environment. In this paper, we present a new approach to vehicle trajectory prediction based on automatically generated maps containing statistical information about the behavior of traffic participants in a given area. These maps are generated based on trajectory observations using image processing and map matching techniques and contain all typical vehicle movements and probabilities in the considered area. Our prediction approach matches an observed trajectory to a behavior contained in the map and uses this information to generate a prediction. We evaluated our approach on a dataset containing over 14000 trajectories and found that it produces significantly more precise mid-term predictions compared to motion model-based prediction approaches.
BibTeX
@misc{quehl2018approach,
  author = {Jannik Quehl and Haohao Hu and Sascha Wirges and Martin Lauer},
  title = {{An Approach to Vehicle Trajectory Prediction Using Automatically Generated Traffic Maps}},
  year = {2018},
  eprint = {1802.08632},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.08632},
}

Loading related content...

Figure