🤖 machine learning

Non-Parametric Spatiotemporal Trajectory Prediction via State-Conditioned Transition Sampling

This paper introduces a training-free, non-parametric method for multi-modal trajectory prediction that leverages a state-conditioned transition table to achieve transformer-level accuracy without GPUs, while significantly outperforming deep learning models in data-scarce scenarios.

Original authors: Michael Fore, Akshay Jain, Justin Downes, Rohan Pradhan, Duncan Botti

Published 2026-08-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Michael Fore, Akshay Jain, Justin Downes, Rohan Pradhan, Duncan Botti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to guess where a friend will go next. If you only know they are walking down a street, you might guess they'll keep walking straight. But if you know they are at a busy train station, heading toward a specific platform at a specific time of day, your guess becomes much sharper. This is the heart of trajectory prediction: a branch of science that tries to forecast the future paths of moving things, like ships, cars, or people. It's tricky because the future isn't just one straight line; it's a web of possibilities. A ship might turn left, right, or keep going straight depending on the weather, the time of day, or where other ships are. To solve this, scientists usually build massive, complex computer brains (called deep learning models) that need huge amounts of data and powerful graphics cards to learn the rules of the road. But what if you could make a great guess without needing a supercomputer or years of training?

This paper introduces a clever, "training-free" method for predicting where ships will go next, specifically in the waters around Denmark. Instead of building a giant, complex AI brain that needs to be fed millions of examples to learn, the authors created a system that acts like a super-smart librarian. They built a massive "transition table"—a digital rolodex containing 150,000 snapshots of where ships have been and where they went next. When the system needs to predict a ship's future, it doesn't "think" in the way a neural network does; instead, it looks up the most similar past situations. It asks: "Has a ship ever been in this exact spot, moving at this speed, facing this direction, on this day of the week, at this hour?" It then weighs the answers based on how closely they match the current situation.

The magic happens in how they use this rolodex. The authors created two ways to play with the data. The first is like a "beam search," where the system follows the most likely path, similar to a GPS giving you the single best route. The second is "diverse sampling," which is like asking the librarian to suggest not just the most common route, but several different plausible routes a ship might take, ensuring they don't all look the same. They tested this on a dataset of ship movements and found something surprising: their simple, non-computer-heavy method was just as accurate as a massive, 57-million-parameter AI model (called TrAISformer) when they had plenty of data. But here is the real kicker: when they gave the AI only a tiny fraction of the data (just 10%), the AI crashed and gave terrible predictions, while the simple method stayed steady and accurate.

The authors suggest that this approach is a game-changer for places where we don't have years of historical data, like a new shipping route or a different part of the ocean. Because it doesn't need a graphics card to train and doesn't need to "learn" from scratch, it can be deployed almost instantly. They found that with just 10% of the data the AI needed, their method was actually twice as accurate. It's a reminder that sometimes, looking at the past with a clever, weighted lens is more powerful than trying to teach a computer to dream up the future from scratch. The paper concludes that while this method isn't perfect for every single scenario (it struggles with very rare, weird maneuvers that have never been seen before), it offers a robust, low-cost alternative that shines exactly where big AI models tend to fail: in data-scarce environments.

Technical Summary: Non-Parametric Spatiotemporal Trajectory Prediction via State-Conditioned Transition Sampling

Problem Statement

Predicting the future positions of moving entities (vessels, vehicles, pedestrians) is a fundamental spatial computing challenge with applications in maritime surveillance, traffic management, and search-and-rescue. The task is inherently multi-modal; at route junctions, an entity may proceed in multiple distinct directions, requiring predictors to represent this uncertainty rather than outputting a single deterministic path.

While recent deep learning approaches, such as the TrAISformer [7], achieve state-of-the-art results by modeling trajectory prediction as sequence modeling, they suffer from significant limitations:

High Resource Cost: They require GPU training and large parameter counts (e.g., 57M parameters).
Data Scarcity Sensitivity: Performance degrades catastrophically when training data is limited.
Lack of Portability: Models must be retrained for new geographic regions or entity types.

Conversely, classical non-parametric methods like Single Point Neighbor Search (SPNS) [5] require no training but fail to represent branching routes or provide multi-modal uncertainty, often collapsing predictions to a single median course.

Methodology

The authors propose a training-free, non-parametric method that bridges the gap between classical neighbor search and deep learning. The approach relies on a State-Conditioned Transition Sampling framework operating in two phases:

1. Offline Transition Table Construction

Instead of discretizing space into a grid, the method constructs a flat transition table from historical trajectories.

Data Extraction: Pairs of observations separated by a fixed time step $\Delta t$ (1 hour) are extracted.
State Representation: Each row stores a current state $s_i$ (latitude, longitude, speed, bearing, hour-of-day, day-of-week) and the subsequent position $p^+_i$ .
Indexing: A BallTree spatial index is built on current positions to facilitate efficient neighbor retrieval. The table contains approximately 150,000 records (9.6 MB), avoiding binning or discretization.

2. State-Conditioned Weighted Lookup

Given a query state $q$ , the system retrieves historical transitions and assigns weights based on a product kernel over five dimensions:
$w_i = K_{sp} \cdot K_{brg} \cdot K_{spd} \cdot K_{hr} \cdot K_{dow}$

Spatial ( $K_{sp}$ ): Quartic kernel on great-circle distance (adaptive bandwidth).
Bearing ( $K_{brg}$ ): von Mises density on bearing difference.
Speed ( $K_{spd}$ ): Gaussian on speed difference.
Temporal ( $K_{hr}, K_{dow}$ ): Cyclic Gaussians for hour-of-day and day-of-week.

This weighted set of next-positions represents a Nadaraya-Watson kernel regression applied to state-conditioned spatial transitions.

3. Autoregressive Inference Modes

The method supports two inference modes over the shared transition representation:

Diverse Sampling: To generate $N$ branches covering distinct plausible routes, the system samples sequentially. For subsequent branches ( $j > 1$ ), a spatial repulsion penalty is applied to the weights, suppressing observations near previously generated branches. This forces the exploration of different routes.
Beam Search: To find the highest-likelihood single path, the system maintains $B$ active branches in parallel. At each step, $C$ candidates are sampled per branch, and the top $B$ paths (by cumulative log-density) are retained. This prunes paths that deviate from high-traffic corridors.

Key Contributions

State-Conditioned Predictor: A transition predictor that replaces the hard course-gating of traditional neighbor search with soft, multi-dimensional product-kernel weighting (spatial, bearing, speed, and temporal).
Diversity-Promoting Sampling: The application of diverse sequential sampling to spatial transition lookups, enabling multi-modal trajectory predictions that cover distinct plausible routes without learned parameters.
Data Efficiency Demonstration: Systematic evaluation showing that this training-free approach matches a 57M-parameter transformer at full data availability but dramatically outperforms it in data-scarce regimes, retaining accuracy with as little as 10% of the training data.

Experimental Results

The method was evaluated on the DMA Danish Maritime AIS dataset (1,481 test trajectories, 3-hour prediction horizon) against baselines including Constant Velocity, SPNS, NCDM, an LSTM seq2seq model, and TrAISformer.

Accuracy (Full Data):
- Top-1 FDE (3h): The proposed beam search achieved 9.00 km, outperforming TrAISformer's argmax (9.84 km).
- Best-of-16 FDE (3h): The diverse sampling achieved 2.49 km, outperforming TrAISformer's sampling (2.66 km).
Data Efficiency:
- When training data was reduced to 10%, the proposed method maintained an FDE of 2.60 km, whereas TrAISformer degraded to 5.61 km (a 2.2x accuracy advantage).
- At 1% data, the proposed method (5.24 km) significantly outperformed TrAISformer (14.33 km), which suffered catastrophic degradation.
Computational Cost:
- The method requires no GPU and zero learned parameters.
- Inference takes 14–46 ms per trajectory on a CPU.
- Table construction takes 21 seconds on full data.

Significance and Claims

The paper claims that non-parametric transition-based prediction is competitive across a broad operating range. Its primary significance lies in deployment flexibility:

New Geographic Regions: The method enables deployment in new regions using an order of magnitude less historical data than deep learning models.
Resource Constraints: It eliminates the need for GPU training and complex hyperparameter tuning, relying instead on data characteristics to set kernel bandwidths.
Stability: The method remains stable and accurate even when data is scarce, a regime where deep learning models fail.

The authors acknowledge limitations, noting that the method cannot extrapolate behaviors unrepresented in the transition table (e.g., rare maneuvers) and relies on a fixed-speed assumption. Furthermore, while diverse sampling excels at multi-modal coverage (Best-of-N), beam search is superior for single-trajectory accuracy (Top-1), requiring practitioners to select the mode appropriate for their specific use case.