Source-linked AI summary
Non-Parametric Spatiotemporal Trajectory Prediction via State-Conditioned Transition Sampling
Michael Fore, Akshay Jain, Justin Downes, Rohan Pradhan, Duncan Botti
TL;DR
Trajectory prediction must represent multiple plausible routes, while learned models require GPU training and degrade with limited data. This paper introduces a training-free, non-parametric transition-sampling method that matches learned models with full data and remains competitive in data-scarce settings, using no GPU or learned parameters.
Problem
Trajectory prediction must represent multiple plausible routes, while recent learned models require GPU training, degrade with limited data, and require retraining across regions or entity types.
Method
The method retrieves historical state-to-next-position transitions using a product kernel over spatial proximity, bearing, speed, and temporal context, then samples diverse routes or performs beam search.
Results
Top-1 FDE is 9.00 km with beam search versus 9.84 km for TrAISformer argmax, while Best-of-16 FDE is 2.49 km versus 2.66 km with TrAISformer sampling.
Takeaways & Limitations
The method matches learned models with full data and offers dramatically better performance in data-scarce deployment scenarios, including new regions using 10% of training data.
Takeaways & Limitations
Without physics-based conditioning, the method cannot extrapolate behavior in states unrepresented in the transition table, and fixed speed limits accuracy for vessels that accelerate or decelerate.
Abstract
from arXiv · showhide
We present a training-free method for multi-modal trajectory prediction that achieves comparable accuracy to a 57M-parameter transformer while requiring no GPU and zero learned parameters. The method builds a transition table of historical state-to-next-position pairs and retrieves neighbors using a product kernel over spatial proximity, bearing, speed, and temporal context. Two inference modes operate over this shared representation: diversity-penalized sampling produces trajectories covering distinct plausible routes, while beam search finds the highest-likelihood path. On the TrAISformer benchmark (Danish Maritime AIS), our method achieves competitive accuracy at full data availability and dramatically outperforms the transformer in data-scarce regimes---remaining stable down to 10% of training data where TrAISformer degrades catastrophically. This enables deployment in new geographic regions from an order of magnitude less historical data, and with no GPU training.
1 Introduction
The paper introduces a training-free, nonparametric trajectory predictor that uses state-conditioned transition sampling to represent multiple plausible routes without learned parameters or GPU training. On the TrAISformer benchmark, it achieves competitive full-data accuracy and remains effective with only 10% of training data, where the transformer degrades catastrophically.
- Method: The method retrieves historical state-to-next-position pairs using product-kernel weights over spatial proximity, bearing, speed, and temporal context.This replaces the hard course gate used by earlier neighbor-search methods.
- Inference modes: Diverse sampling uses spatial repulsion to explore distinct plausible routes, while beam search retains multiple paths and prunes by cumulative likelihood.The two inference modes share the same transition representation.
- Results: 9.00 km Top-1 FDE is achieved by beam search versus 9.84 km for TrAISformer argmax, while 2.49 km Best-of-16 FDE is achieved by diverse sampling versus 2.66 km for TrAISformer sampling.These results use the DMA Danish maritime AIS benchmark with 1,481 test trajectories and a 3-hour prediction horizon.
- Deployment: The approach requires no GPU or learned parameters and needs only seconds of CPU setup.Its training-free design avoids the GPU training and retraining requirements associated with TrAISformer.
- Data efficiency: At full data, the method matches a 57M-parameter transformer and retains reasonable accuracy with 10% of training data, where the transformer degrades catastrophically.The paper frames this stability as enabling deployment in new geographic regions using substantially less historical data.
2 Method
The method builds a spatially indexed table of state-to-next-position transitions offline, then performs online inference with either diverse sampling or beam search. A five-term product kernel conditions retrieved transitions on spatial, bearing, speed, and temporal context, and both modes generate trajectories autoregressively from the shared procedure.
- Offline transition table: Offline setup constructs a BallTree-indexed transition table of 150,000 rows, each storing six state variables and a next position.Training observations sampled every 10 minutes are paired across a fixed prediction step Δt of 1 hour; the table occupies about 9.6 MB.
- State-conditioned retrieval: Each query retrieves transitions within spatial-kernel support and weights them with a product of five kernel terms.The terms model great-circle distance, bearing difference, speed difference, cyclic hour-of-day, and cyclic day-of-week.
- State-conditioned retrieval: The weighted next-position set forms a Nadaraya-Watson kernel regression over state-conditioned spatial transitions.The representation is a flat collection rather than a discretized grid, so kernel weights determine each record’s contribution.
- Shared inference procedure: Both inference modes generate branches autoregressively by weighting transitions, sampling candidates, smoothing predictions, and updating the query state.Smoothing uses a Gaussian with σ=15° on angular difference from the candidate’s bearing; speed remains fixed at its initial observed value.
- Inference modes: Diverse sampling sequentially applies continuous-space spatial repulsion to explore distinct routes, whereas beam search retains the top B of B×C candidates by cumulative log-density.Beam search omits the diversity penalty and prunes paths that accumulate lower scores, including routes wandering off high-traffic corridors.
3 Experiments
Experiments on the DMA AIS benchmark compare the proposed beam-search and diverse-sampling modes with classical and learned baselines under standard trajectory metrics. The method is competitive on the full test set, remains stable with limited data, and requires only CPU inference without training.
- Dataset: The DMA AIS evaluation uses 10,605 training trajectories and 1,481 temporally disjoint test trajectories, each with 3-hour observation and prediction windows.Trajectories are sampled at 10-minute intervals from vessel traffic in the Kattegat/Danish Straits region.
- Baselines: The comparison includes constant velocity, neighbor-based SPNS and NCDM, a spatial-only ablation, a 401,924-parameter LSTM, and the 57.4M-parameter TrAISformer.NCDM produces N=16 unranked trajectories, while the LSTM uses best-of-16 evaluation and TrAISformer uses top-1 argmax decoding.
- Full-data results: Our beam search achieves the best 3-hour top-1 FDE and top-1 ADE, while diverse sampling achieves the best 3-hour best-of-16 FDE.TrAISformer retains the best 1-hour top-1 and 3-hour best-of-16 ADE; both learned baselines outperform both proposed modes on CRPS.
- Data efficiency: 2.46–2.60 km: our method’s performance remains stable from 100% down to 10% of training data, whereas TrAISformer reaches 14.33 km at 1%.At 10% of data, our method is 2.2× more accurate than TrAISformer; TrAISformer’s error increases 5.5× from full data to 1%.
- Compute: 46 ms per trajectory: diverse sampling runs on CPU, beam search costs 14 ms, and transition-table construction takes 21 s at full data.The method requires no training, while TrAISformer training took 69 minutes on a T4 GPU.
4 Discussion and Conclusion
The nonparametric method is competitive with learned models at full data availability and substantially more robust in data-scarce deployment, while its inference modes expose a tradeoff between displacement accuracy and multimodal coverage. Its limitations include unrepresented behaviors and fixed-speed assumptions, but deployment requires no GPU or training loop.
- Discussion and Conclusion: The method matches learned models with full data and offers dramatically better performance in data-scarce deployments common when expanding to new regions.This supports using nonparametric transition-based prediction across a broad operating range.
- Discussion and Conclusion: 7.17 km beam best-of-16 is weaker than 2.49 km diverse sampling best-of-16 because beam branches cluster on the same high-likelihood route.Diverse sampling’s diversity penalty improves multimodal route coverage.
- Discussion and Conclusion: 9.00 km diverse-sampling CRPS exceeds 8.29 km beam CRPS because diversity deliberately places samples on routes the vessel did not take.Both methods trail learned baselines, so the paper claims displacement error and data efficiency rather than calibration.
- Discussion and Conclusion: 2.20 vs. 2.29 km at 1-hour top-1 favors TrAISformer, whose attention over the 3-hour observation window helps disambiguate routes at junctions.At the 3-hour horizon, independently sampled branches tend to cluster on the dominant route.
- Limitations: The method cannot extrapolate unrepresented rare maneuvers and is limited by its fixed-speed assumption for vessels accelerating or decelerating mid-trajectory.Beam search excels at top-1 while diverse sampling excels at best-of-N, and neither inference mode dominates all metrics simultaneously.
- Practical implications: 10% of training data matches TrAISformer’s result using 10 times as much, while deployment requires no GPU or training loop and the transition table can update incrementally.Kernel bandwidths and inference parameters were set from data characteristics, held fixed across experiments, and not systematically tuned.