When designing systems that predict or plan paths through a space—whether an autonomous vehicle forecasting pedestrian movement, a navigation app calculating alternative highway routes, or a language model generating reasoning chains—we face a fundamental challenge: redundancy.
If you ask a standard optimization or generative algorithm to produce the top five best paths from point A to point B, it will naturally output five minor variations of the exact same optimal path. Mathematically, each variation scores highly on its own. Practically, however, a set of nearly identical paths is useless. It causes traffic congestion in routing networks, creates mode collapse in predictive models, and wastes computational resources in generative systems.
To solve this, a shared research direction has emerged across multiple domains: diversity-aware trajectory sampling. Instead of evaluating paths in isolation, these techniques score trajectories based on both their individual quality and their distinctness from already selected paths.
The Core Problem: The Redundancy of Independent Ranking
To understand why naive sampling fails, consider a vehicle approaching a fork in the road. A predictive model might generate 100 possible future trajectories. Because going straight is the most statistically likely action, the top 10 highest-scoring trajectories will all look like straight lines, differing only by millimeters.
As noted by the authors of Distributed Processing of k Shortest Path Queries over Dynamic Road Networks, mathematically optimal $k$-shortest path algorithms frequently return routes that share a massive percentage of their edges. This redundancy fails to provide the distinct alternatives required by human drivers or downstream robotic planners.
If the vehicle unexpectedly turns right, a model that only preserved the top variations of going straight will fail completely. To build resilient systems, we must trade a small amount of individual path optimality for a massive increase in global coverage. We need a way to filter out the redundant variations while preserving distinct behavioral modes (e.g., one path for going straight, one for turning left, and one for turning right).
Mechanism 1: Non-Maximum Suppression and Greedy Pruning
The most direct way to enforce diversity is to filter a large pool of candidate trajectories using Non-Maximum Suppression (NMS) or greedy elimination. The algorithm ranks all candidate paths by a quality score, selects the highest-scoring path, and then discards or penalizes any remaining candidates that are too similar to it. This process repeats iteratively.
[Dense Candidate Pool] ──> Sort by Score ──> Select Top Path ──> Remove Spatially Similar Paths ──> Repeat
The definition of "similarity" changes depending on the application:
- Spatial Proximity: Jianhua Sun et al. introduced a plug-and-play sampling module in Stimulus Verification is a Universal and Effective Sampler in Multi-modal Human Trajectory Prediction that ranks human paths by environmental and social compliance, then applies NMS to eliminate spatially redundant paths.
- Endpoint Distance: Rather than checking every point along a path, Julian Schmidt et al. show in RESET: Revisiting Trajectory Sets for Conditional Behavior Prediction that applying NMS based purely on the spatial distance between trajectory endpoints is an efficient way to filter out minor variations of the same maneuver.
- Intent Preservation: In diffusion-based trajectory forecasting, Younwoo Choi et al. develop a framework in DICE: Diverse Diffusion Model with Scoring for Trajectory Prediction that uses NMS to ensure low-probability but critical navigational intents (like a rare turn at an intersection) remain represented in the final prediction set.
This greedy filtering logic extends beyond physical motion. In Deep Learning-Based Alternative Route Computation, Alex Zhai et al. use a greedy selection process to generate high-quality alternative driving routes that avoid circuitous, overlapping detours. Similarly, Connor Lawless et al. apply a greedy subset selection algorithm in "I Want It That Way": Enabling Interactive Decision Support Using Large Language Models and Constraint Programming to present users with qualitatively distinct choices in decision-support systems rather than clusters of nearly identical results.
Mechanism 2: Clustering and Anchor-Based Selection
An alternative to filtering a ranked list is to group the entire trajectory space into distinct behavioral modes using clustering or predefined geometric anchors. Instead of discarding paths post-generation, these methods organize the generation space itself.
Trajectory Aggregation via Clustering
When combining predictions from multiple models or memory banks, trajectories can be aggregated by treating them as data points in a coordinate space. Ahmed Hefny et al. demonstrate this in MultiPath++: Efficient Information Fusion and Trajectory Aggregation for Behavior Prediction by using an Expectation-Maximization (EM) clustering approach to select a non-redundant set of trajectories.
This clustering step is crucial because it prevents the system from averaging distinct modes together. If a pedestrian might step left or step right, averaging those two paths results in a trajectory straight down the middle—potentially into an obstacle. Clustering preserves both distinct options.
This approach is mirrored by Xinshuo Weng et al. in MTP: Multi-Hypothesis Tracking and Prediction for Reduced Error Propagation, where clustering is used to manage a high volume of tracking hypotheses, and by Yonghao Dong et al. in Sparse Instance Conditioned Multimodal Trajectory Prediction, who cluster candidate paths retrieved from an external memory module.
Map-Based and Learned Anchors
Instead of clustering paths after they are generated, systems can use the underlying geometry of the environment to anchor diverse paths from the start.
The authors of Lanelet2 for nuScenes: Enabling Spatial Semantic Relationships and Diverse Map-based Anchor Paths construct a similarity matrix based on the Intersection over Union (IoU) of road centerlines. By iteratively pruning paths with high IoU, they establish a set of laterally diverse anchor paths that force the prediction model to consider structurally distinct maneuvers allowed by the map.
During training, these anchors can be explicitly decoupled. Longzhong Lin et al. show in EDA: Evolving and Distinct Anchors for Multimodal Motion Prediction that applying NMS to anchors before matching them with ground-truth data prevents similar anchors from receiving conflicting optimization signals, simplifying the model's learning process.
Mechanism 3: Iterative Path Exclusion and Network Constraints
In classical graph routing and spatial optimization, diversity is often maintained dynamically by altering the search graph or adding explicit penalties to shared segments.
In urban traffic management, routing every driver to the single fastest path causes the "Braess Paradox," where providing guidance actually worsens congestion. To counter this, Zhaosheng Yang et al. developed a method in Applicable Prevention Method of Braess Paradox in Urban Traffic Flow Guidance System that uses overlap and detour constraints to limit the number of shared segments between alternative routes. By forcing spatial dissimilarity, the system distributes traffic load more evenly across the network, a goal also shared by Zihan Luo 0002 et al. in Diversified Top-k Route Planning in Road Network.
This concept of iterative exclusion applies even to virtual camera work. Yu-Chuan Su et al. show in Making 360° Video Watchable in 2D: Learning Videography for Click Free Viewing that an automated cinematographer can generate multiple distinct viewing experiences from the same 360° footage by iteratively excluding previously selected visual trajectories, preventing the camera from getting stuck on a single dominant subject.
Extension to Abstract Trajectories: LLM Reasoning Chains
While diversity-aware sampling is most visible in physical space, its underlying mathematics applies to any sequential generation task—including text.
In Reinforcement Learning with Verifiable Rewards (RLVR) for Large Language Models, models are trained by generating multiple reasoning paths (rollouts) for a single prompt. Standard stochastic token sampling often suffers from a linguistic version of mode collapse: it generates a group of trajectories that are nearly identical, differing only by a few synonymous tokens.
To break this bottleneck, Shangyu Xing et al. applied trajectory pruning to token sequences in Lookahead Tree-Based Rollouts for Enhanced Trajectory-Level Exploration in Reinforcement Learning with Verifiable Rewards. By simulating a short sequence of tokens for each new reasoning branch and calculating its normalized edit distance against existing paths, the system prunes redundant branches early. This focuses the computational budget on exploring genuinely unique reasoning chains.
| Domain | Trajectory Type | Similarity Metric | Pruning/Selection Method |
|---|---|---|---|
| Autonomous Driving (Schmidt et al.) | Coordinate sequences | Endpoint distance | Non-Maximum Suppression |
| Map-Based Planning (nuScenes Map Paper) | Centerline polylines | Intersection over Union (IoU) | Iterative matrix pruning |
| Urban Navigation (Yang et al.) | Road network edges | Shared segment count | Overlap & detour constraints |
| LLM Reasoning (Xing et al.) | Token sequences | Normalized edit distance | Lookahead branch pruning |
Why It Works: The Intuition of Coverage
The universal success of diversity-aware trajectory sampling comes down to a simple geometric intuition: maximizing the volume of the explored solution space per unit of computational cost.
When a system evaluates a set of trajectories, it is trying to cover as many plausible future states as possible. If we model the future as a probability distribution with multiple peaks (modes), a naive top-$k$ sampler places all $k$ samples on the single highest peak. Diversity-aware sampling forces the samples to spread out, placing one sample on the highest peak, one on the second highest, and so on.
By treating similarity as a negative constraint, these algorithms prevent systems from wasting resources on redundant data. Whether managing urban traffic gridlock, predicting pedestrian safety, or guiding an LLM through a math problem, filtering for diversity ensures that the final set of trajectories offers meaningful, actionable variety.
Key Foundational Work
Applicable Prevention Method of Braess Paradox in Urban Traffic Flow Guidance System (2011) — contributed 1 concept elements to this direction.
Making 360° Video Watchable in 2D: Learning Videography for Click Free Viewing (2017) — contributed 1 concept elements to this direction.